Saltando lagartos!

Supongamos que definimos un programa simple que toma una matriz L de números naturales con cierta longitud N y hace lo siguiente:

i=0                 #start at the first element in the source array
P=[]                #make an empty array
while L[i]!=0:      #and while the value at the current position is not 0
    P.append(L[i])  #add the value at the current position to the end of the output array
    i=(i+L[i])%N    #move that many spaces forward in the source array, wrapping if needed
return P            #return the output array

Cada uno de estos programas se ejecutará para siempre o terminará eventualmente, produciendo una lista de enteros positivos. Su trabajo es, dada una lista P de enteros positivos, producir una lista más corta, L, de números naturales que termina y produce P cuando se conecta al programa anterior.

Tal lista siempre existe, ya que uno puede agregar P[i]-1ceros después de cada uno P[i]en la lista, luego un 0 final, y producirá la lista original. Por ejemplo, dada [5,5], una solución es [5,0,0,0,0,5,0,0,0,0,0]. Sin embargo, [5,0,5]es mucho más corto, por lo que la solución automática no es válida para su programa.

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

La entrada es una lista de enteros positivos (en algún formato que puede especificar) y la salida debe estar en el mismo formato. El tamaño de lista y entero puede ser de hasta 2 ^ 16. Este es el código de golf, por lo que gana el programa más corto en bytes.

Python 3, 109102100 95 93 bytes

def f(L,k=1,i=0):
 P=[0]*k
 for x in L:x=P[i]=P[i]or x;i=(i+x)%k
 return P[i]and f(L,k+1)or P

Una solución recursiva. Llámalo como f([1,2,3,4]). Míralo pasar todos los casos de prueba.

Comenzamos con k=1(longitud de salida) y i=0(posición en salida), y hacemos una lista Pcon kceros. Luego iteramos a lo largo de los elementos xde L, actualizando P[i]a P[i]or x(por lo que P[i]mantiene su valor si no es cero) y ia (i+P[i])%k. Después de eso, verificamos que el valor final de P[i]es cero, incrementando ksi no lo es, y regresamos P.

Si en algún punto del algoritmo P[i]ya no es cero, entra en un bucle que rodea algunos de los valores distintos de cero Py termina en un valor distinto de cero; entonces recurrimos.