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,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!