Jump the Array!

Question

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

Answer 1

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

Answer 2

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)
   h                              add 1
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.

Answer 3

Haskell, 120 105

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]

Answer 4

Haskell - 139 characters

l=length
o(x:y)=1+l(takeWhile(/=x)y)
j a=maximum$map(o.drop n.iterate(b!!))[0..n-1]
 where b=zipWith(\x y->mod(a!!mod(x+y)n)n)a[0..];n=l a

Examples:

λ: j [0]
1

λ: j [-213]
1

λ: j [1,3,12,-1,7]
1

λ: j [2,3,5,7,9,11,13,17,19]
2

λ: j [-2,3,-5,7,-9,11,-13,17,-19,23,-27]
3

λ: j [0,2,5,4,-9,0,-1,1,-1,1,-6]
4

This makes use of @jakube's observation that you need only check half the starting values, while performing 2 step per iteration.

Answer 5

Python, 160

l=lambda a,b,c,d:(b,c)in d and len(d)-d.index((b,c))or l(a,(a[b]+[0,b][c])%len(a),~c,d+[(b,c)])
j=lambda a:max(l(a,b,c,[])for b in range(len(a))for c in(0,1))/2

Function for answer is j.
The recursive function l returns the loop length for a given array, start, and first turn, and the function j finds the max.

Answer 6

Mathematica, 189 162 161 bytes

If anonymous functions are allowed - 161 bytes:

Max[l=Length;Table[b={};n=p;i=s-1;e:={i,n~Mod~2};While[b~Count~e<2,b~AppendTo~e;h=#[[i+1]];i=If[EvenQ@n++,h,i+h]~Mod~l@#];l@b-b~Position~e+1,{s,l@#},{p,0,1}]/4]&

Otherwise - 163 bytes:

f=Max[l=Length;Table[b={};n=p;i=s-1;e:={i,n~Mod~2};While[b~Count~e<2,b~AppendTo~e;h=#[[i+1]];i=If[EvenQ@n++,h,i+h]~Mod~l@#];l@b-b~Position~e+1,{s,l@#},{p,0,1}]/4]&

Running this on all the test-cases:

f /@ {
  {0},
  {-213},
  {1, 3, 12, -1, 7},
  {2, 3, 5, 7, 9, 11, 13, 17, 19},
  {-2, 3, -5, 7, -9, 11, -13, 17, -19, 23, -27},
  {0, 2, 5, 4, -9, 0, -1, 1, -1, 1, -6}
}

Results in:

{1, 1, 1, 2, 3, 4}

Python 2, 202 bytes

def l(a,n,i):
 b=[]
 while not[i,n]in b:b.append([i,n]);i=(a[i]if n<1 else i+a[i])%len(a);n+=1;n%=2
 return len(b)-b.index([i,n])
def f(a):print max([l(a,n,i) for n in[0,1]for i in range(len(a))])/2

DEMO

This is nearly a port of my Mathematica answer.

Answer 7

Mathematica, 113 112 chars

l=Length;m=MapIndexed;f=Max[l/@ConnectedComponents@Graph@m[Tr@#2->#&,Part@@Thread@Mod[#+{Tr@#2,1}&~m~#,l@#,1]]]&

Example:

f /@ {
  {0},
  {-213},
  {1, 3, 12, -1, 7},
  {2, 3, 5, 7, 9, 11, 13, 17, 19},
  {-2, 3, -5, 7, -9, 11, -13, 17, -19, 23, -27},
  {0, 2, 5, 4, -9, 0, -1, 1, -1, 1, -6}
}

{1, 1, 1, 2, 3, 4}

Answer 8

ised 82

ised '@1{0,2,5,4,-9,0,-1,1,-1,1,-6};@2{1};' '@{4 5}{(@3{:$1_x++x*@2{1-$2}:}2*#$1)::[#$1]};{1+?{:@5{$3::$5}=$4:}@::[2*#$1]_0}/2'

The first argument doesn't count into length (array initialization into $1 and b initialization into $2 - select the "game").