Pewnego dnia budzisz się tylko, aby znaleźć się w tablicy. Próbujesz po prostu wyjść, biorąc jednocześnie jeden indeks, ale wydaje się, że istnieją inne zasady:

Tablica jest całkowicie wypełniona liczbami naturalnymi.

• Jeśli znajdziesz się w indeksie n, przejdź do indeksuarray[n] , z wyjątkiem:
• Jeśli znajdziesz się w indeksie, nktóry jest liczbą pierwszą, array[n]cofnij się

Przykład: Zaczynasz od indeksu 4w tej tablicy (indeks początkowy to 0):

array = [1,4,5,6,8,10,14,15,2,2,4,5,7];
-----------------^ you are here

Ponieważ wartość pola, w którym się znajdujesz 8, to przejdziesz do indeksu 8jako pierwszy krok. Pole, na którym wylądujesz, zawiera wartość 2. Następnie przejdź do indeksu 2jako drugi krok. Podobnie 2jak liczba pierwsza, cofasz się o 5 kroków, co jest twoim trzecim krokiem. Ponieważ nie ma indeksu -3, udało ci się uciec z tablicy w 3 krokach.

Twoim zadaniem jest:

Aby napisać program lub funkcję, która akceptuje tablicę i indeks początkowy jako parametr, i wyświetla liczbę kroków do ucieczki z tablicy. Jeśli nie możesz uciec przed tablicą (np. [2,0,2]Przy pomocy start-index 2=> ciągle przechodzisz od indeksu 2do 0), wypisz wartość fałszowania. Możesz użyć indeksowania opartego na jednym lub zerowania, ale określ, którego używasz.

Przypadki testowe

Wkład: [2,5,6,8,1,2,3], 3

Wydajność: 1

Wkład: [2, 0, 2], 2

Wydajność: false

Wkład: [14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11], 5 ;

Wydajność: 6

Najkrótsza odpowiedź wygrywa.

Pyth, 31 bajtów

KlQ%tl-.u?}NUK?P_N-N@QN@QNKQEKK

Przypadki testowe

Wykorzystuje zero, aby wskazać fałszywą wartość, w przeciwnym razie liczbę przeskoków.

Python, 161 138 bajtów

Kredyty dla silni.

g=lambda x:0**x or x*g(x-1)
f=lambda a,i,n=0,l=[]:(i<0)+(i>=len(a))and n or(0 if i in l else f(a,[a[i],i-a[i]][i and-g(i-1)%i],n+1,l+[i]))

Ideone to!

Jak to działa

Twierdzenie Wilsona służy do sprawdzania liczby pierwszej.

Wykrywanie pętli poprzez przechowywanie widocznych indeksów w tablicy ( l) i sprawdzanie, czy obecny jest bieżący indeks l.

Python, 107 bajtów

import sympy
f=lambda a,i,n=0:0if n>len(a)else f(a,[a[i],i-a[i]][sympy.isprime(i)],n+1)if 0<=i<len(a)else n

Zastosowanie: f(list, start)ex:f([2,5,6,8,1,2,3], 3)

Zwraca 0pętle (wykryte, gdy n > len(a))

Matlab, 138 bajtów

To proste podejście, oparte na indeksach 1, ponieważ Matlab domyślnie używa indeksów 1. Aby policzyć liczbę kroków, używamy forpętli zliczającej od 1 do nieskończoności (!). W przypadku, gdy nie możemy uciec z tablicy, używamy wektora, vaby śledzić, które wpisy już odwiedziliśmy. Jeśli odwiedzimy wpis dwa razy, wiemy, że utknęliśmy w cyklu, którego nie można zmienić. Aby sprawdzić, czy jesteśmy poza tablicą, używamy try/catchstruktury, która również wychwytuje wyjątki poza granicami.

function r=f(a,i);v=a*0;v(i)=1;for k=1:Inf;if isprime(i);i=i-a(i);else;i=a(i);end;try;if v(i);r=0;break;end;v(i)=1;catch;r=k;break;end;end

05AB1E, 32 bajty

ï[U¯Xåi0,q}²gL<Xå_#X²XèXDˆpi-]¯g

Wyjaśnienie

ï                                 # explicitly convert input to int
 [                            ]   # infinite loop
  U                               # store current index in X
   ¯Xåi0,q}                       # if we've already been at this index, print 0 and exit
           ²gL<Xå_#               # if we've escaped, break out of infinite loop
                   X²XèXDˆpi-     # else calculate new index
                               ¯g # print nr of indices traversed

Wypróbuj online

JavaScript (ES6), 100

Baza indeksu 0. Uwaga: ta funkcja modyfikuje tablicę wejściową

(a,p)=>eval("for(s=0;1/(q=a[p]);++s,p=p>1&&p%i||p==2?p-q:q)for(a[p]=NaN,i=1;p%++i&&i*i<p;);q==q&&s")

Mniej golfa

(a,p)=>
{
  for(s = 0; 
      1/ (q = a[p]); 
      ++s)
  {
    a[p] = NaN; // mark visited position with NaN to detect loops
    for(i = 1; p % ++i && i*i < p;); // prime check
    p = p > 1 && p % i || p == 2 ? p-q : q;
  }
  return q==q && s // return false if landed on NaN as NaN != NaN
}

Test

F=
(a,p)=>eval("for(s=0;1/(q=a[p]);++s,p=p>1&&p%i||p==2?p-q:q)for(a[p]=NaN,i=1;p%++i&&i*i<p;);q==q&&s")

;[
 [[2,5,6,8,1,2,3], 3, 1]
,[[2, 0, 2], 2, false]
,[[14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11], 5, 6]
].forEach(t=>{
  var [a,b,k]=t, i=a+' '+b,r=F(a,b)
  console.log(r==k?'OK':'KO',i+' -> '+r)
  
})  

JAVA, 229 218 bajtów

Object e(int[]a,int b){Stack i=new Stack();int s=0;for(;!(a.length<b|b<0);s++){if(i.contains(b))return 1>2;i.add(b);b=p(b)>0?b-a[b]:a[b];}return s;}int p(int i){for(int j=2;j<i/2;j++)if(i%j<1)return 0;return i<2?0:1;}

Dzięki Kevinowi 11 bajtów gryzie kurz.

CJam, 44 bajty

Oczekuje index arrayna stos.

:G\{_G,,&{G=_L#)0{_L+:L;_mp3T?-F}?}L,?}:F~o@

Wypróbuj online!

Moja pierwsza odpowiedź CJam, dlatego jest tak straszna i bezwzględnie konieczna ...

:G\{_G,,&{G=_L#)0{_L+:L;_mp3T?-F}?}L,?}:F~o@
:G                                              Store the array as G
  \                                             Put the index first
   {                                  }:F~      The recursive F function
     G,,                                        Generate a 0..length(G) sequence
    _   &                            ?          Check that the index is contained
         {                        }             If so, then...
          G=                                    Get the value at the index
            _L#)                 ?              If the value is in L (`-1)` gives `0` which is falsy)
                0                               Return 0 (infinite loop)
                 {              }               Otherwise...
                  _L+:L;                        Store the value we're accessing in L (infinite loop check)
                        _mp3T?-                 Remove 3 if the number is prime
                               F                Then recursively call F
                                   L,           We escaped! Return the size of "L" (number of steps)
                                          o     Print the top value of the stack
                                           @    Tries to swap 3 elements, which will error out

(uważa się, że można zawiesić się po wydrukowaniu prawidłowego wyjścia, co właśnie robi ten program)

C, 121 bajtów

Funkcja fakceptuje tablicę, indeks początkowy (oparty na 0) i liczbę elementów w tablicy, ponieważ nie ma sposobu na przetestowanie końca tablicy w C (przynajmniej nie znam żadnego).

p(n,i,z){return--i?p(n,i,z*i*i%n):z%n;}c;f(a,i,n)int*a;{return i<0||i/n?c:c++>n?0:i&&p(i,i,1)?f(a,i-a[i],n):f(a,a[i],n);}

Wypróbuj na ideone!

Uwaga: function p(n) sprawdza, czy njest pierwsza, czy nie. Podziękowania za to @Lynn i jego odpowiedź na Czy liczba ta jest liczbą pierwszą?

JavaScript, 121 132 bajtów

p=n=>t=i=>n%i&&n>i?t(i+1):(0<n&&n<=i?1:0),c=-1,a=>r=s=>(++c,0<=s&&s<a.length?(p(s)(2)?r(s-a[s]):0||([a[s],s]=[0,a[s]])[1]?r(s):0):c)

f=(p=n=>t=i=>n%i&&n>i?t(i+1):(0<n&&n<=i?1:0),c=-1,a=>r=s=>(++c,0<=s&&s<a.length?(p(s)(2)?r(s-a[s]):0||([a[s],s]=[0,a[s]])[1]?r(s):0):c));

let test_data = [[[1,4,5,6,8,10,14,15,2,2,4,5,7],4],
                 [[2,5,6,8,1,2,3],3],
                 [[2,0,2],2],
                 [[14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11],5]];
for (test of test_data) {
    c = -1;
    console.log(f(test[0])(test[1]));
}

edycja 1: Ups, brakowało mi trochę o zwróceniu liczby kroków. naprawić już wkrótce.

edycja 2: naprawiono

Rakieta, 183 156 bajtów

Prawdopodobnie więcej bajtów do zapisania przy dalszym golfie, ale to wszystko dla mnie. :)

(require math)(define(e l i[v'()][g length])(cond[(memq i v)#f][(not(< -1 i(g l)))(g v)][else(e l((λ(a)(if(prime? i)(- i a)a))(list-ref l i))(cons i v))]))

Kompletny moduł z pakietem testowym z funkcją czyszczenia:

#lang racket

(require math)

(define (e l i [v'()] [g length])
  (cond
    [(memq i v) #f]
    [(not (< -1 i (g l))) (g v)]
    [else (e l
             ((λ (a) (if (prime? i)
                         (- i a)
                         a))
              (list-ref l i))
             (cons i v))]))

(module+ test
  (require rackunit)
  (define escape-tests
    '((((2 5 6 8 1 2 3) 3) . 1)
      (((2 0 2) 2) . #f)
      (((14 1 2 5 1 3 51 5 12 3 4 41 15 4 12 243 51 2 14 51 12 11) 5) . 6)))
  (for ([t escape-tests])
    (check-equal? (apply e (car t)) (cdr t) (~a t))))

Uruchom to jak raco test e.rkt

Najważniejsze podziękowania dla @cat za odkrycie nieudokumentowanej prime?funkcji .

Java, 163 160 bajtów

boolean p(int n){for(int i=2;i<n;)if(n%i++==0)return 0>1;return 1>0;}
int f(int[]a,int n){return n<0||n>=a.length?1:p(n)?n<a[n]?1:1+f(a,a[n-a[n]]):1+f(a,a[n]);}

p(n)służy do testowania wstępnego, f(a,n)służy do funkcji ucieczki. Stosowanie:

public static void main(String[] args) {
    int[] array = {14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11};
    System.out.println(f(array, 5));
}

Wersja bez golfa:

static boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

static int escape(int[] array, int n) {
    if (n < 0 || n >= array.length) {
        return 1;
    } else if (isPrime(n)) {
        if (n < array[n]) {
            return 1;
        } else {
            return 1 + escape(array, array[n - array[n]]);
        }
    } else {
        return 1 + escape(array, array[n]);
    }
}

Perl 6 , 85 bajtów

->\n,\a{{.[+a].defined??0!!+$_}(lazy n,{.is-prime??$_- a[$_]!!a[$_]}...^!(0 <=* <a))}

Wyjaśnienie:

lazy n, { .is-prime ?? $_ - a[$_] !! a[$_] } ...^ !(0 <= * < a)

Jest to leniwa sekwencja indeksów przemierzanych zgodnie z regułą. Jeśli indeks ostatecznie przekroczy granice tablicy wejściowej (!(0 <= * < a) warunek), sekwencja jest skończona; w przeciwnym razie indeksy będą się zmieniać bez końca.

Ta sekwencja jest przekazywana do wewnętrznej funkcji anonimowej:

{ .[+a].defined ?? 0 !! +$_ }

Jeśli sekwencja jest zdefiniowana na podstawie indeksu podanego przez rozmiar tablicy wejściowej, musi ona wejść w nieskończony cykl, więc 0jest zwracana. W przeciwnym razie +$_zwracany jest rozmiar sekwencji .

Perl 5 , 107 + 1 ( -a) = 108 bajtów

for($i=<>;!$k{$i}++&&$i>=0&&$i<@F;$s++){$f=0|sqrt$i||2;1while$i%$f--;$i=$f?$F[$i]:$i-$F[$i]}say$k{$i}<2&&$s

Wypróbuj online!

Lista oparta na 0. Zwraca false (puste), jeśli listy nie można przeszukiwać.