Leaping Lizards!

Question

Suppose we define a simple program that takes an array L of natural numbers with some length N and does the following:

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

Every such program will either run forever or will eventually terminate, producing a list of positive integers. Your job is to, given a list P of positive integers, produce a shortest list, L, of natural numbers that terminates and produces P when plugged into the previous program.

Such a list always exists, since one can just add P[i]-1 zeros after each P[i] in the list, then one final 0, and it will produce the original list. For example, given [5,5], one solution is [5,0,0,0,0,5,0,0,0,0,0]. However, [5,0,5] is much shorter, so the automatic solution is not a valid one for your program.

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

Input is a list of positive integers(in some format you can specify) and output should be in the same format. List and integer size can be up to 2^16. This is code golf, so shortest program in bytes wins!

Answer 1

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

A recursive solution. Call it like f([1,2,3,4]). Watch it pass all test cases.

We start with k=1 (length of output) and i=0 (position in output), and make a list P with k zeros. Then we iterate along the elements x of L, updating P[i] to P[i]or x (so P[i] keeps its value if it's nonzero) and i to (i+P[i])%k. After that, we check that the final value of P[i] is zero, incrementing k if it's not, and return P.

If at any point of the algorithm P[i] is already nonzero, it enters a loop going around some of the nonzero values of P, and ends up at a nonzero value; then we recurse.