19
\$\begingroup\$

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

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.

\$\endgroup\$
8
\$\begingroup\$

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

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]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You could squish the where to the previous ]. Also, did you try using cycle l!!i instead of l!!mod n(length l)? \$\endgroup\$ – proud haskeller Jan 3 '15 at 8:44
  • \$\begingroup\$ Also, you can inline b, and use a pattern guard |n<-l a to eliminate the where. \$\endgroup\$ – proud haskeller Jan 3 '15 at 9:50
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think you can save some characters by defining j with a lambda. \$\endgroup\$ – KSFT Jan 2 '15 at 20:11
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – KSFT Jan 2 '15 at 20:00
  • \$\begingroup\$ I don't know Mathematica, so I can't really help more. \$\endgroup\$ – KSFT Jan 2 '15 at 20:36
  • \$\begingroup\$ @Zgarb Oh! Well that explains everything. I didn't even think of that. Thanks! \$\endgroup\$ – kukac67 Jan 2 '15 at 20:55
  • \$\begingroup\$ For with 3 arguments is usually shorter than While (since you can save on a semicolon in front of the For). \$\endgroup\$ – Martin Ender Jan 3 '15 at 14:31
1
\$\begingroup\$

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}

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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