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

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

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

• user3094403: 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.
• Vectorized: 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
• PurkkaKoodari: Use only one space to indent. Saves 9 chars here.
• PurkkaKoodari: Another idea: while c not in s[:-1]: could be while(c in s[:-1])-1:.
• PurkkaKoodari: 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.

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)=l0ドル: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.

• proud haskeller: You could squish the where to the previous ]. Also, did you try using cycle l!!i instead of l!!mod n(length l)?
• proud haskeller: Also, you can inline b, and use a pattern guard |n<-l a to eliminate the where.

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.

• KSFT: I think you can save some characters by defining j with a lambda.

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.

• KSFT: This looks very similar to mine. Mine was off by one (before dividing by two) at first. I'm still not sure why, but I just subtracted one before dividing.
• KSFT: I don't know Mathematica, so I can't really help more.
• kukac67: @Zgarb Oh! Well that explains everything. I didn't even think of that. Thanks!
• Martin Ender: For with 3 arguments is usually shorter than While (since you can save on a semicolon in front of the For).

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").