Pulando lagartos!

Suponha que definamos um programa simples que use uma matriz L de números naturais com algum comprimento N e faça o seguinte:

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

Todo programa desse tipo será executado para sempre ou será encerrado, produzindo uma lista de números inteiros positivos. Seu trabalho é, dada uma lista P de números inteiros positivos, produzir uma lista mais curta, L, de números naturais que termina e produz P quando conectado ao programa anterior.

Essa lista sempre existe, pois é possível adicionar P[i]-1zeros após cada um P[i]na lista, depois um 0 final e ela produzirá a lista original. Por exemplo, dado [5,5], uma solução é [5,0,0,0,0,5,0,0,0,0,0]. No entanto, como [5,0,5]é muito mais curto, a solução automática não é válida para o seu 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]

Entrada é uma lista de números inteiros positivos (em algum formato que você pode especificar) e a saída deve estar no mesmo formato. O tamanho da lista e do número inteiro pode ter até 2 ^ 16. Isso é código de golfe, e o programa mais curto em bytes vence!

Python 3, 109 102 100 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

Uma solução recursiva. Chame assim f([1,2,3,4]). Assista a ele passar em todos os casos de teste.

Começamos com k=1(comprimento da saída) e i=0(posição na saída) e fazemos uma lista Pcom kzeros. Em seguida, iteramos ao longo dos elementos xde L, atualizando P[i]para P[i]or x(portanto, P[i]mantém seu valor se for diferente de zero) e ipara (i+P[i])%k. Depois disso, verificamos que o valor final de P[i]é zero, incrementando kse não for, e retornamos P.

Se em algum momento do algoritmo P[i]já for diferente de zero, ele entra em um loop contornando alguns valores diferentes de zero Pe termina com um valor diferente de zero; então nós recorremos.