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!