# Jump the Array!

Let's play a one-player game called jump the array. To play, you only need an array of integers, say a. You start at some position i, and on each turn, you jump to a new position. On turn n,

• if n is even, you jump to the absolute position a[i] mod length(a),
• if n is odd, you jump to the relative position (i + a[i]) mod length(a).

The array indexing starts at zero. You can count the first jump as turn 0 or turn 1, which give a different game. Since the state space of the game is finite (your move is determined by your position and the parity of the turn number), you will of course eventually enter a loop of even length. Denote by loop(a, i, b) the length of this loop, when the first jump is counted as turn b.

# Input

A nonempty array a of integers to play the game with.

# Output

The maximum number p such that, when starting on some position i and counting the first turn as either 0 or 1, you eventually enter a loop of length 2 * p. In other words, your output is the number

max { loop(a, i, b)/2 : i in [0 .. length(a)-1], b in [0,1] }


# Rules

You can give a function or a full program. The smallest byte count wins, and standard loopholes are disallowed.

# Test cases

 -> 1
[-213] -> 1
[1,3,12,-1,7] -> 1
[2,3,5,7,9,11,13,17,19] -> 2
[-2,3,-5,7,-9,11,-13,17,-19,23,-27] -> 3
[0,2,5,4,-9,0,-1,1,-1,1,-6] -> 4

• @kukac67 Yeah, it's the latter option, as Martin said. Jan 2, 2015 at 18:25
• I assume that mod is defined as always positive (-1 mod 5 == 4) unlike in C. Is that the case? Jan 2, 2015 at 20:53
• @nutki Yes, I use a Haskell-style mod, which always gives nonnegative results. Jan 2, 2015 at 20:55
• If zero-indexing turns gives a different result from one-indexing, should we output either result, or whichever one is less?
– KSFT
Jan 2, 2015 at 22:46
• @MartinBüttner No, I was asking about indexing the turns, not the arrays.
– KSFT
Jan 2, 2015 at 23:21

# Python - 157

a=input()
z=len(a)
b=[]
for i in range(z):
s,c,t=[],"",0
while(c in s[:-1])-1:j=(i*t+a[i])%z;c=t+i;s+=[c];t^=1
b+=[len(s)-s.index(c)-1]
print max(b)/2

• If you put len(a) in a variable and replace all len(a)s with the name of that variable, you can save some characters. Jan 2, 2015 at 18:19
• Some ideas: t+=1;t%=2 -> t^=1 and if t: j=(j+a[j])%z else: j=a[j]%z -> j=(t*j+a[j])%z Jan 2, 2015 at 19:15
• Use only one space to indent. Saves 9 chars here. Jan 2, 2015 at 20:39
• Another idea: while c not in s[:-1]: could be while(c in s[:-1])-1:. Jan 2, 2015 at 20:46
• And one more. You don't have to use j, as this loop assigns the contents of range(z) to i instead of incrementing it. Just replace j with i to save 4 chars. Jan 2, 2015 at 20:52

# Pyth: 28 character (Python 2: 116 character)

eSmhxtu+G%@Q+eG@QeGlQUQ]ddUQ


## Usage:

Try it here: Pyth Compiler/Executor

It expects a list of integers as input [0,2,5,4,-9,0,-1,1,-1,1,-6]

## Explanation:

I noticed one important property of the function loop: For each i there is a j, so that loop(a,i,0) == loop(a,j,1) and vice versa. Therefore we only need to compute the values loop(a,i,b) for b=0.

Proof: If the is a cycle i -> j -> k -> ... -> z -> i with b = 0, then there exists the cycle j -> k -> ... -> z -> i -> j with b = 1.

Therefore a simple script can work the following way. Iterate over all i and try to reach i by iteratively computing i = a[(i + a[i]) mod len(a)] mod len(a). Since this computation may ran into a cycle without i, we cancel the computation after len(a) steps. Then we print the maximum cycle.

A Python 2 implementation looks like this (125 character}:

a=input();A=len(a);m=[]
for i in range(A):
j=i
for c in range(A):
j=a[(j+a[j])%A]%A
if i==j:m+=[c+1];break
print max(m)


For the pyth implementation I used a little different approach. For each i I compute the list of positions, and look for i in this list.

eSmhxtu+G%@Q+eG@QeGlQUQ]ddUQ
m                       UQ    for each d in [0, ..., len(input)-1] compute a
u                ]d         list G (using reduce),
which is first initialized with G = [d]
UQ           for each H in [0, ..., len(input)-1]:
+G                            append to G the value
%@Q+eG@QeGlQ                   input[G[-1] +input[G[-1]] % len(input)
(notice that list lookups in pyth work with modular wrapping)
t                            remove the first value (which is d)
x                    d        and find the index of d in this shortend list
(it's -1, if d is not in the list)
eS                              print the maximum (end of sorted list)


## edit: Python 2: 116 characters

@proud haskeller's solution was i few characters shorter than my Python solution, therefore I 'had' to shorten it a bit.

a=input();A=len(a);l=lambda j,i,c:c<=A and(c*(i==j)or l(a[(j+a[j])%A]%A,i,c+1));print max(l(i,i,0)for i in range(A))


The difference is, that I calculate the number recursively instead of iteratively.

f s|t<-l s=maximum[g$drop t$iterate(\i->s!!mod(i+s!!mod i t)t)i|i<-s]
g(x:s)=l$0:fst(span(/=x)o) l=length  this generates an infinite list for each starting point (for golfing reasons we iterate over all values instead of all indexes, which are equivalent). then it calculates the cycle of each list (the cycle length of xs is xs % []). it uses @jakubes's observations about cycles. because it steps 2 steps at a time, we don't need to divide by 2 at the end. Edit: now using @MthViewMark's trick of dropping the first n elements to guarantee having a cycle with the first element. by the way, I managed to golf his algorithm to 112 characters: l=length o(x:y)=1+l(takeWhile(/=x)y) j a|n<-l a=maximum$map(o.drop n.iterate(\i->mod(a!!mod(i+a!!i)n)n))[0..n-1]

l=length