Anteriormente definí el proceso de aplastar una matriz

En un flechazo leemos la matriz de izquierda a derecha. Si en un momento nos encontramos con dos del mismo elemento en una fila, eliminamos el primero y duplicamos el segundo.

Por ejemplo, aquí está el proceso de aplastar la siguiente matriz

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

Tenga en cuenta que el mismo elemento se puede contraer varias veces. En el ejemplo 2,2,4se colapsó 8en una sola pasada.

Ahora aplastar matrices es fácil, lo difícil es deshacerlas. Su tarea es tomar una matriz de enteros positivos como entrada y salida de la matriz más grande que puede formar la entrada cuando se aplasta repetidamente. Por ejemplo, la matriz [4]se forma por trituración, [2,2]que a su vez se forma por trituración [1,1,1,1]. Dado que no podemos tener valores no enteros, [1,1,1,1]no podemos destrabarnos más y por eso es nuestra respuesta.

Nunca recibirá un 0en su matriz de entrada porque tales matrices se pueden expandir indefinidamente. Nunca recibirá un caso con dos del mismo número impar uno al lado del otro, tales casos no pueden ser el resultado de un aplastamiento.

Este es el código de golf, por lo que las respuestas se puntuarán con el tamaño de su fuente medido en bytes, siendo mejores menos bytes.

Antes de comenzar a responder, solo quiero decir que este desafío es significativamente más difícil de lo que parece. Verifique su intuición a medida que avanza y asegúrese de que su respuesta pase todos los casos de prueba.

Casos de prueba

[] -> []
[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]

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)},[])

Pruébalo en línea!

Este algoritmo calcula arreglos estirados óptimos, estirando cada número al máximo, y luego, si es necesario, aplasta un par de números en el lugar correcto, creando efectivamente un "bloqueador de aplastamiento", interrumpiendo la secuencia de aplastamiento del número anterior.

Por ejemplo:

[1, 1, 1, 1, 1, 1]da [4,2]una vez aplastado, pero [1, 1, 1, 1, 2]da como resultado[2, 4]

El desafío es determinar dónde se debe colocar exactamente un bloqueador de aplastamiento para que aplastar la matriz resultante dé el resultado correcto:

• Un bloqueador de aplastamiento debe colocarse solo si el número extendido anterior es igual al número actual y si la secuencia extendida actual es mayor que la anterior. Por ejemplo, [2, 4]requiere un bloqueador de aplastamiento (el número extendido es 1, repetido y[1, 1] es más corta que [1,1,1,1]), pero [4, 2]y [2, 6]no requieren una
• si llamamos a nla secuencia extendida anterior, y si se verifica la condición anterior, entonces la secuencia actual es una repetición de la nsecuencia. Para interrumpir la secuencia de aplastamiento del número anterior, necesitamos colocar el bloqueador de aplastamiento al final de la segunda nsecuencia del número actual para estirar. Ejemplo: [2, 8] => [(1, 1)=n, (1, 1) + (2) + (1, 1) + ...]o[4, 8] => [(1, 1, 1, 1)=n, (1, 1, 1, 1) + (1, 1, 2) + ...]

Jalea , 42 bytes

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

Pruébalo en línea!

Programa completo Extremadamente ineficiente, pero funciona.

Python 2 , 230 228 226 bytes

Funciona iterando todas las listas posibles con la misma suma que la entrada. Eliminando aquellos que no son iguales a la matriz de entrada en algún estado aplastado, seleccionando el más largo.

Editar: -2 bytes eliminando el ifen la función principal

Editar: -2 bytes eliminando dos corchetes innecesarios

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)]+[[]]

Pruébalo en línea!

Explicación

Función principal, responsable de encontrar todas las soluciones posibles y seleccionar la más larga.

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

Función de aplastamiento, que comprueba si y es igual a uno de los aplastamientos.

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)

Genera todas las permutaciones posibles con la suma dada

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ć·®·Íǝ}»,

Pruébalo en línea!

Puerto de mi solución Javascript.

Explicaciones:

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