Zagrajmy w grę dla jednego gracza o nazwie przeskocz tablicę . Powiedzmy, że do gry wystarczy tablica liczb całkowitych a. Zaczynasz od pewnej pozycji ii za każdym razem skaczesz do nowej pozycji. Na kolei n,

• jeśli njest parzysty, przeskakujesz do pozycji absolutnej a[i] mod length(a),
• jeśli njest nieparzysty, przeskakujesz do względnej pozycji (i + a[i]) mod length(a).

Indeksowanie tablicy rozpoczyna się od zera. Pierwszy skok możesz zaliczyć jako turę 0lub turę 1, które dają inną grę. Ponieważ przestrzeń stanu gry jest skończona (ruch zależy od twojej pozycji i parzystości liczby tur), oczywiście w końcu wejdziesz w pętlę o równej długości. Oznacz loop(a, i, b)długość tej pętli, gdy pierwszy skok jest liczony jako zwrot b.

Wejście

Niepuste tablice aliczb całkowitych do gry.

Wynik

Maksymalna liczba ptaka, że ​​rozpoczynając od jakiejś pozycji ii licząc pierwszy zakręt jako jeden 0lub 1, ostatecznie wprowadzasz pętlę długości 2 * p. Innymi słowy, twój wynik to liczba

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

Zasady

Możesz podać funkcję lub pełny program. Wygrywa najmniejsza liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

[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

Pyth : 28 znaków (Python 2: 116 znaków)

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

Stosowanie:

Wypróbuj tutaj: Pyth Compiler / Executor

Oczekuje listy liczb całkowitych jako danych wejściowych [0,2,5,4,-9,0,-1,1,-1,1,-6]

Wyjaśnienie:

Zauważyłem jedną ważną właściwość funkcji loop: dla każdej ijest taka j, więc loop(a,i,0) == loop(a,j,1)i na odwrót. Dlatego musimy tylko obliczyć wartości loop(a,i,b)dla b=0.

Dowód: jeśli jest to cykl i -> j -> k -> ... -> z -> iz b = 0, to istnieje cykl j -> k -> ... -> z -> i -> jz b = 1.

Dlatego prosty skrypt może działać w następujący sposób. Powtórz wszystko ii spróbuj dotrzeć iiteracyjnie i = a[(i + a[i]) mod len(a)] mod len(a). Ponieważ obliczenia te mogą przebiegać bez cyklu i, anulujemy je po len(a)krokach. Następnie drukujemy maksymalny cykl.

Python 2 wygląda realizacja tak ( 125 znaków }:

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)

Do implementacji pytha zastosowałem trochę inne podejście. Dla każdego iobliczam listę pozycji i szukam na itej liście.

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)  

edycja: Python 2: 116 znaków

Rozwiązanie @proud haskeller było o kilka znaków krótsze niż moje rozwiązanie Python, dlatego musiałem je nieco skrócić.

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

Różnica polega na tym, że obliczam liczbę rekurencyjnie zamiast iteracyjnie.

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

generuje to nieskończoną listę dla każdego punktu początkowego (z powodów golfowych iterujemy wszystkie wartości zamiast wszystkich indeksów, które są równoważne). następnie oblicza cykl każdej listy (długość cyklu xswynosi xs % []).

wykorzystuje obserwacje @ jakubes na temat cykli. ponieważ wykonuje 2 kroki na raz, nie musimy dzielić przez 2 na końcu.

Edycja : teraz przy użyciu sztuczki @ MthViewMark polegającej na upuszczeniu pierwszych nelementów, aby zagwarantować cykl z pierwszym elementem. nawiasem mówiąc, udało mi się prześledzić jego algorytm do 112postaci:

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 znaków

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

Przykłady:

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

Wykorzystuje to obserwację @ jakube, że wystarczy sprawdzić tylko połowę wartości początkowych, wykonując 2 kroki na iterację.

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

Funkcja odpowiedzi to j.
Funkcja rekurencyjna lzwraca długość pętli dla danej tablicy, startu i pierwszego obrotu, a funkcja jznajduje maks.

Matematyka, 189 162 161 bajtów

Jeśli dozwolone są funkcje anonimowe - 161 bajtów:

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

W przeciwnym razie - 163 bajty:

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

Uruchamianie tego na wszystkich testowych przypadkach:

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

Prowadzi do:

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

Python 2, 202 bajty

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

PRÓBNY

To prawie port mojej odpowiedzi Mathematica.

Mathematica, 113 112 znaków

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

Przykład:

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'

Pierwszy argument nie liczy się do długości (inicjalizacja tablicy do $1i binicjalizacja do $2- wybierz „grę”).