13
\$\begingroup\$

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ 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]? \$\endgroup\$ – tsh Aug 28 '17 at 7:40
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Sriotchilism O'Zaic Aug 28 '17 at 7:45
  • \$\begingroup\$ Is it ok if I output numbers, each separated by a newline? \$\endgroup\$ – scottinet Aug 28 '17 at 19:28
  • \$\begingroup\$ @scottinet That is a reasonable way to output a list. Go ahead. \$\endgroup\$ – Sriotchilism O'Zaic Aug 28 '17 at 19:30
  • \$\begingroup\$ 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] \$\endgroup\$ – scottinet Aug 29 '17 at 12:48
2
\$\begingroup\$

JavaScript (Node.js), 237 221 213 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) + ...]
\$\endgroup\$
1
\$\begingroup\$

Jelly, 42 bytes

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

Try it online!

Full program. Extremely inefficient, but works.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 230 228 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)]+[[]]
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.