9
\$\begingroup\$

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!

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Are you sure that handling arbitrary lists of up to 65536 elements in 10 minutes is feasible? Do you have a reference implementation which achieves it? \$\endgroup\$ Mar 1, 2016 at 22:21
  • 2
    \$\begingroup\$ Just an FYI, the sandbox is more effective when used for longer than 3 hours :P I understand it can be tempting to post right away, but I think Peter's comment shows how this question could have benefited from a longer run there. \$\endgroup\$ Mar 1, 2016 at 22:35

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.