# Stretch an array

Earlier I defined the process of crushing an array

In a crush we read the array left to right. If at a point we encounter two of the same element in a row we remove the first one and double the second one.

For example here is the process of crushing the following array

[5,2,2,4]
^
[5,2,2,4]
^
[5,2,2,4]
^
[5,4,4]
^
[5,4,4]
^
[5,8]
^


Note that the same element can be collapsed multiple times. In the example 2,2,4 was collapsed into 8 in a single pass.

Now crushing arrays is easy, whats hard is uncrushing them. Your task is to take an array of positive integers as input and output the largest array that can form the input when crushed repeatedly. For example the array [4] is formed by crushing [2,2] which is in turn formed by crushing [1,1,1,1]. Since we can't have non integer values [1,1,1,1] cannot be uncrushed any further and thus is our answer.

You will never receive a 0 in your input array because such arrays can be expanded indefinitely. You will also never receive a case with two of the same odd number next to each other, such cases cannot be the result of a crushing.

This is so answers will be scored with the size of their source measured in bytes with less bytes being better.

Before you start making your answer I just want to say that this challenge is significantly more difficult than it seems. Check your intuition as you go along and make sure your answer passes all the test cases.

## Test Cases

[] -> []
[5] -> [5]
[6] -> [3,3]
[8] -> [1,1,1,1,1,1,1,1]
[4,8] -> [1,1,1,1,1,1,1,1,1,1,2]
[2,8] -> [1, 1, 1, 1, 2, 1, 1, 1, 1]
[4,4] -> [1,1,1,1,1,1,1,1]

• Sorry but i still cannot understand the rule. why [1,1,1,1,1,1,1,1,1,1,2] produce [4, 8] instead of [8, 4]? should this be [1,>1,1,1,1,1,1,1,1,1,2], [2,1,>1,1,1,1,1,1,1,2], [2,>2,1,1,1,1,1,1,2], [4,1,>1,1,1,1,1,2], [4,2,1,>1,1,1,2], [4,2,>2,1,1,2], [4,>4,1,1,2], [8,1,>1,2], [8,2,>2],[8,4]? – tsh Aug 28 '17 at 7:40
• @tsh I think you have a misconception in the way that crushing works. Here is the path it takes first pass: [1,>1,1,1,1,1,1,1,1,1,2], [2,>1,1,1,1,1,1,1,1,2], [2,1,>1,1,1,1,1,1,1,2], [2,2,>1,1,1,1,1,1,2],[2,2,1,>1,1,1,1,1,2], [2,2,2,>1,1,1,1,2],[2,2,2,1,>1,1,1,2], [2,2,2,2,>1,1,2], [2,2,2,2,1,>1,2], [2,2,2,2,2,>2], [2,2,2,2,4>], second pass: [2,>2,2,2,4], [4,>2,2,4], [4,2,>2,4], [4,4,>4], [4,8>]. Hopefully that clears it up. If you would like some code to look at the previous question has answers that implement a crushing function. – Wheat Wizard Aug 28 '17 at 7:45
• Is it ok if I output numbers, each separated by a newline? – scottinet Aug 28 '17 at 19:28
• @scottinet That is a reasonable way to output a list. Go ahead. – Wheat Wizard Aug 28 '17 at 19:30
• The test case [4, 4] should be removed, as we can never get that array after a stretch=>crush sequence, since this will end up with [8] – scottinet Aug 29 '17 at 12:48

# JavaScript (Node.js), 237221213 186 bytes

f=a=>a.map(b=>{for(i=1;~b%2;b/=2)i*=2;return Array(i).fill(b)}).reduce((t,c,i,s)=>{b=c.slice();if(i)r=2*s[--i].length,b.length>=r&&b[0]==s[i][0]?b[r-2]+=b.pop():b;return t.concat(b)},[])


Try it online!

This algorithm computes optimal stretched arrays, by stretching each number to the max, and then, if necessary, it crushes back a pair of number at the right place, effectively creating a "crush blocker", interrupting the crush sequence of the preceding number.

For instance:

[1, 1, 1, 1, 1, 1] gives [4,2] once crushed, but [1, 1, 1, 1, 2] results in [2, 4]

The challenge is to determine where exactly a crush blocker should be placed so that crushing the resulting array gives the right result:

• A crush blocker needs to be placed only if the previous stretched number is equal to the current one, and if the current stretched sequence is greather than the previous one. For instance, [2, 4] requires a crush blocker (the stretched number is 1, repeated, and [1, 1] is shorter than [1,1,1,1]), but [4, 2] and [2, 6] do not require one
• if we call n the previous stretched sequence, and if the condition above is verified, then the current sequence is a repetition of the n sequence. To interrupt the crush sequence of the previous number, we need to place the crush blocker at the end of the second n sequence of the current number to stretch. Example: [2, 8] => [(1, 1)=n, (1, 1) + (2) + (1, 1) + ...], or [4, 8] => [(1, 1, 1, 1)=n, (1, 1, 1, 1) + (1, 1, 2) + ...]

# Jelly, 42 bytes

ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿċ³
ṗÐ€⁸ẎS⁼¥Ðfµ€ŒpẎ€ÇÐfṪ


Try it online!

Full program. Extremely inefficient, but works.

# Python 2, 230228 226 bytes

Works by iterating all possible lists with the same sum as the input one. Removing those that do not equal to the input array in some crushed state, selecting the longest one.

Edit: -2 bytes by removing the if in the main function

Edit: -2 bytes by removing two unnecessary square brackets

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]
def c(x,y):
i=e=1
while x[i:]:
if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
i+=1
return x==y or~-e and c(x,y)
b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]


Try it online!

# Explanation

Main function, responsible for finding all possible solutions and selecting the longest one

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]


Crush function, that checks if y is equal to one of the crushes.

def c(x,y):
i=e=1
while x[i:]:
if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
i+=1
return x==y or~-e and c(x,y)

Generate all possible permutations with the given sum

b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]


# 05AB1E, 41 37 bytes

vy[DÉ#2÷]DYQX©NoDU‹&sDV¸X∍sić·®·Íǝ}»,


Try it online!

Port of my Javascript solution.

Explanations:

vy                   for each member of the list
[DÉ#2÷]              divide by 2 until odd: stack = stretched value, N = iterations
DYQ                  stetched value equal to the previous one?
X©NoDU‹              previous size < current one? (+store the new size in X)
&                    AND on the 2 previous tests
sDV¸X∍s              build a list of the new stretched value repeated X times
(+store the new stetched value in Y)
ić·®·Íǝ}             if the previous tests are true:
reduce the result list size by 1
multiply by 2 the number at the crush block position
»,                   join by newline + print the list