# 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

[0] -> 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. – Zgarb Jan 2 '15 at 18:25
• I assume that mod is defined as always positive (-1 mod 5 == 4) unlike in C. Is that the case? – nutki Jan 2 '15 at 20:53
• @nutki Yes, I use a Haskell-style mod, which always gives nonnegative results. – Zgarb Jan 2 '15 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 '15 at 22:46
• @MartinBüttner No, I was asking about indexing the turns, not the arrays. – KSFT Jan 2 '15 at 23:21

# 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.

# 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. – ProgramFOX Jan 2 '15 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 – Vectorized Jan 2 '15 at 19:15
• Use only one space to indent. Saves 9 chars here. – PurkkaKoodari Jan 2 '15 at 20:39
• Another idea: while c not in s[:-1]: could be while(c in s[:-1])-1:. – PurkkaKoodari Jan 2 '15 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. – PurkkaKoodari Jan 2 '15 at 20:52

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