Lassen Sie uns ein Ein-Spieler-Spiel namens Jump the Array spielen . Zum Spielen benötigen Sie beispielsweise nur eine Reihe von ganzen Zahlen a. Sie beginnen an einer bestimmten Position iund springen in jeder Runde zu einer neuen Position. Am Turn n,

• wenn ngerade, springt man zur absoluten Position a[i] mod length(a),
• Wenn nungerade ist, springen Sie zur relativen Position (i + a[i]) mod length(a).

Die Array-Indizierung beginnt bei Null. Sie können den ersten Sprung als Zug 0oder Zug zählen 1, was ein anderes Spiel ergibt. Da der Zustandsraum des Spiels endlich ist (Ihr Zug wird durch Ihre Position und die Parität der Zugnummer bestimmt), werden Sie natürlich irgendwann eine Schleife von gerader Länge eingeben. Geben Sie loop(a, i, b)die Länge dieser Schleife an, wenn der erste Sprung als Drehung gezählt wird b.

Eingang

Ein nicht leeres Array avon Ganzzahlen, mit denen das Spiel gespielt werden soll.

Ausgabe

Die maximale Anzahl p, sodass Sie, wenn Sie an einer bestimmten Position beginnen iund die erste Abbiegung als entweder 0oder zählen 1, schließlich eine Längenschleife eingeben 2 * p. Mit anderen Worten, Ihre Ausgabe ist die Zahl

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

Regeln

Sie können eine Funktion oder ein vollständiges Programm angeben. Die kleinste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

[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

Python : 28 Zeichen (Python 2: 116 Zeichen)

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

Verwendung:

Probieren Sie es hier aus: Pyth Compiler / Executor

Es erwartet eine Liste von Ganzzahlen als Eingabe [0,2,5,4,-9,0,-1,1,-1,1,-6]

Erläuterung:

Mir ist eine wichtige Eigenschaft der Funktion aufgefallen loop: Für jede igibt es ein j, also das loop(a,i,0) == loop(a,j,1)und umgekehrt. Daher müssen wir nur die Werte loop(a,i,b)für berechnen b=0.

Beweis: Wenn das ein Zyklus i -> j -> k -> ... -> z -> imit ist b = 0, dann existiert der Zyklus j -> k -> ... -> z -> i -> jmit b = 1.

Daher kann ein einfaches Skript folgendermaßen funktionieren. Iteriere über alles iund versuche es idurch iteratives Rechnen zu erreichen i = a[(i + a[i]) mod len(a)] mod len(a). Da diese Berechnung ohne einen Zyklus ablaufen kann i, brechen wir die Berechnung nach len(a)Schritten ab. Dann drucken wir den maximalen Zyklus.

Eine Python 2- Implementierung sieht folgendermaßen aus ( 125 Zeichen ):

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)

Für die Pyth-Implementierung habe ich einen etwas anderen Ansatz gewählt. Für jeden iberechne ich die Liste der Positionen und suche iin dieser Liste.

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)  

Bearbeiten: Python 2: 116 Zeichen

Die Lösung von @proud haskeller war einige Zeichen kürzer als meine Python-Lösung, daher musste ich sie ein wenig kürzen.

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

Der Unterschied ist, dass ich die Zahl rekursiv statt iterativ berechne.

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

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

dies erzeugt eine unendliche Liste für jeden Startpunkt (aus Golfgründen iterieren wir über alle Werte anstelle aller Indizes, die äquivalent sind). dann berechnet es den Zyklus jeder Liste (die Zykluslänge von xsist xs % []).

es verwendet @ jakubes Beobachtungen über Zyklen. weil es 2 Schritte auf einmal macht, müssen wir am Ende nicht durch 2 teilen.

Bearbeiten : Verwenden Sie jetzt den @ MthViewMark-Trick zum Löschen der ersten nElemente, um sicherzustellen, dass Sie einen Zyklus mit dem ersten Element haben. Übrigens habe ich es geschafft, seinen Algorithmus auf 112Charaktere zu beschränken:

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]

Haskell - 139 Zeichen

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

Beispiele:

λ: 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

Dies nutzt die Beobachtung von @ jakube, dass Sie nur die Hälfte der Startwerte prüfen müssen, während Sie 2 Schritte pro Iteration ausführen.

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

Funktion zur Beantwortung ist j.
Die rekursive Funktion lgibt die Schleifenlänge für ein bestimmtes Array, Start und erste Runde zurück, und die Funktion ermittelt jdie max.

Mathematica, 189 162 161 Bytes

Wenn anonyme Funktionen erlaubt sind - 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]&

Ansonsten - 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]&

Laufen dies auf allen Testfällen:

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}
}

Ergebnisse 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

Dies ist fast eine Portierung meiner Mathematica-Antwort.

Mathematica, 113 112 Zeichen

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

Beispiel:

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}

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'

Das erste Argument zählt nicht zur Länge (Array-Initialisierung in $1und bInitialisierung in $2- wählen Sie das "Spiel").