Array Escape - verschwinde

32

Eines Tages erwachst du nur, um dich gefangen in einer Reihe zu finden. Du versuchst einfach rauszugehen und nimmst jeweils einen Index, aber es scheint andere Regeln zu geben:

Das Array ist vollständig mit natürlichen Zahlen gefüllt.

  • Wenn Sie sich in einem Index befinden n, wechseln Sie zum Index array[n], mit Ausnahme von:
  • Wenn Sie sich in einem Index befinden, nder eine Primzahl ist, treten Sie einen array[n]Schritt zurück

Beispiel: Sie beginnen mit Index 4in diesem Array (Startindex ist 0):

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

Da der Wert des Feldes, in dem Sie sich befinden, ist 8, gehen Sie 8als erster Schritt zum Index . Das Feld, auf dem Sie landen, enthält den Wert 2. Anschließend gehen Sie 2als zweiten Schritt zum Index . Als 2Primzahl machst du 5 Schritte zurück, was dein dritter Schritt ist. Da es keinen Index gibt -3, haben Sie das Array in insgesamt 3 Schritten erfolgreich maskiert.

Ihre Aufgabe ist:

So schreiben Sie ein Programm oder eine Funktion, die ein Array und einen Startindex als Parameter akzeptiert und die Anzahl der Schritte ausgibt, die zum Verlassen des Arrays erforderlich sind. Wenn Sie das Array nicht verlassen können (z. B. [2,0,2]mit start-index 2=> Sie wechseln ständig von index 2zu 0), geben Sie einen falschen Wert aus. Sie können eine einbasierte oder eine nullbasierte Indizierung verwenden, geben Sie jedoch an, welche Sie verwenden.

Testfälle

Eingang: [2,5,6,8,1,2,3], 3

Ausgabe: 1

Eingang: [2, 0, 2], 2

Ausgabe: false

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

Ausgabe: 6

Die kürzeste Antwort gewinnt.

Michael Kunst
quelle
7
Willkommen bei PPCG! Dies ist eine anständige erste Herausforderung. :) Können wir auch 1-basierte Indizierung verwenden? Es könnte auch gut sein, noch ein paar Testfälle zu haben. Für zukünftige Herausforderungen können Sie auch die Sandbox verwenden, in der Sie Feedback von der Community erhalten, bevor eine Herausforderung live geht.
Martin Ender
1
Sehr eng verwandt
Peter Taylor
1
@Martin Ender es hat nichts mit der frage zu tun ... aber ich als mobiler benutzer finde es unmöglich die sandbox zu benutzen. Was kann ich tun, um ein Feedback zu meinen Fragen zu erhalten, bevor ich sie tatsächlich poste?
user6245072
1
@JerryJeremiah warum kannst du nicht 3 Schritte zurück gehen? Sie landen auf Index 2, wenn Sie mit 5 anfangen und 3 Schritte zurück gehen
Michael Kunst
5
@ user902383 Gehe zu Index 2, der Primzahl ist. Wir machen also zwei Schritte zurück und gehen zu Index 0, der keine Primzahl ist. Der Wert bei Index 0 ist 2, also gehen wir zu Index 2, der prim ... repeat
edc65 ist

Antworten:

4

Pyth, 31 Bytes

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

Die Testfälle

Es wird Null verwendet, um einen falschen Wert anzugeben, andernfalls die Anzahl der Sprünge.

Cameron McCluskie
quelle
9

Python, 161 138 Bytes

Credits für Fakultät.

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 es!

Wie es funktioniert

Der Satz von Wilson wird für die Primärprüfung verwendet.

Schleifenerkennung durch Speichern der angezeigten Indizes in einem Array ( l) und Überprüfen, ob sich der aktuelle Index in befindet l.

Undichte Nonne
quelle
6

Python, 107 Bytes

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

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

Rückgabe 0für Schleifen (erkannt wenn n > len(a))

RootTwo
quelle
5

Matlab, 138 Bytes

Dies ist ein geradliniger Ansatz, bei dem 1-basierte Indizes verwendet werden, da Matlab standardmäßig 1-basierte Indizes verwendet. Um die Anzahl der Schritte zu zählen, verwenden wir eine forSchleife, die von 1 bis unendlich (!) Zählt. Für den Fall, dass wir dem Array nicht entkommen können, verwenden wir einen Vektor v, um zu verfolgen, welche Einträge wir bereits besucht haben. Wenn wir einen Eintrag zweimal besuchen, wissen wir, dass wir in einem unausweichlichen Zyklus stecken. Um zu überprüfen, ob wir uns außerhalb eines Arrays befinden, verwenden wir die try/catchStruktur, die auch Ausnahmen außerhalb des zulässigen Bereichs enthält.

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
Fehler
quelle
5

05AB1E, 32 Bytes

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

Erläuterung

ï                                 # 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

Probieren Sie es online aus

Emigna
quelle
4

JavaScript (ES6), 100

Index base 0. Hinweis: Diese Funktion ändert das Eingabearray

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

Weniger golfen

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

Prüfung

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

edc65
quelle
4

JAVA, 229 218 Bytes

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

Dank Kevin beissen 11 Bytes den Staub.

user902383
quelle
Noch ein paar Dinge zum Golfspielen: Stack<Integer>i=new Stack<>();Kann geändert werden in Stack i=new Stack();und return 1==2;kann geändert werden in return 0>1;. Vielleicht möchten Sie auch Java 7 anstelle von Java im Allgemeinen erwähnen .
Kevin Cruijssen
@ KevinCruijssen Ich bin nicht sicher, ob es sinnvoll ist zu erwähnen, dass es sich um Java 7 handelt, da diese Lösung gerade jetzt mit den meisten Java-Versionen kompatibel ist.
User902383
Nun, in Java 8 können Sie eine Lambda - Ausdrücke verwenden , die kürzer ist: a,b->{...}statt Object e(int[]a,int b){...}, weshalb ich persönlich Java erwähne 7 Leute wissen zu lassen, ich habe absichtlich nicht Java 8 lambdas verwendet, aber es ist bis zu Ihnen.
Kevin Cruijssen
@KevinCruijssen Wenn ich lamda verwende, spezifiziere ich Java-Version, aber wenn die Lösung mit Java 7 funktioniert, funktioniert sie normalerweise auch mit Java 8, so dass es sinnlos war, Version hinzuzufügen. Aber Sie könnten Recht haben, ich sollte Mindestversion angeben.
User902383
4

CJam, 44 Bytes

Erwartet index arrayauf dem Stapel.

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

Probieren Sie es online!

Meine erste CJam-Antwort, warum es so schrecklich und unerlässlich ist ...

: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

(Es wird als in Ordnung angesehen, nach der korrekten Ausgabe, wie sie gedruckt wurde, einen Absturz zu verursachen. Das macht das Programm hier.)

Ven
quelle
3

C 121 Bytes

Funktion fakzeptiert Array, Startindex (0-basiert) und Anzahl der Elemente im Array, da es keine Möglichkeit gibt, das Ende eines Arrays in C zu testen (zumindest kenne ich keine).

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

Probiere es auf ideone aus!

Hinweis: function p(n) Prüft, ob nPrime ist oder nicht. Gutschrift dafür geht an @Lynn und seine Antwort für Ist diese Zahl eine Primzahl?

Jasmes
quelle
1
@raznagul Unsinn, Sie können die Länge eines Eingabeparameter-Arrays nicht bestimmen. Siehe Antwort 2 zur gleichen Frage
edc65
@ edc65: Sorry, ich hätte über die erste Antwort hinaus lesen sollen.
Raznagul
@Jasmes - Im Codegolf sollte eine Funktion mehrere Male aufgerufen werden können, um die gleiche Ausgabe zu erhalten. Ihr Code muss zurückgesetzt werden c, um die Funktion erneut aufzurufen.
Owacoder
3

JavaScript, 121 132 Bytes

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]));
}

edit 1: hoppla, habe das bisschen über die Anzahl der zurückgegebenen Schritte verpasst. behebe es bald.

edit 2: behoben

Yay295
quelle
3

Schläger, 183 156 Bytes

Wahrscheinlich mehr Bytes, die beim weiteren Golfen gespart werden können, aber das war's für mich. :)

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

Komplettes Modul mit Testsuite mit Cleaner-Funktion:

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

Führen Sie es wie raco test e.rkt

Ein großes Lob für @cat bei der Entdeckung der undokumentierten prime?Funktion .

Winny
quelle
2

Java, 163-160 Bytes

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)ist für die Hauptprüfung, f(a,n)ist für die Fluchtfunktion. Verwendung:

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

Ungolfed-Version:

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]);
    }
}
Justin
quelle
1

Perl 6 , 85 Bytes

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

Erläuterung:

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

Dies ist eine träge Folge der Indizes, die gemäß der Regel durchlaufen werden. Wenn der Index die Grenzen des Eingabearrays (die !(0 <= * < a)Bedingung) überschreitet , ist die Sequenz endlich. ansonsten zyklieren die Indizes unendlich.

Diese Sequenz wird der internen anonymen Funktion zugeführt:

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

Wenn die Sequenz an dem durch die Größe des Eingabearrays angegebenen Index definiert ist, muss sie in einen unendlichen Zyklus eingetreten sein und 0wird zurückgegeben. Andernfalls wird die Größe der Sequenz +$_zurückgegeben.

Sean
quelle
1

Perl 5 , 107 + 1 ( -a) = 108 Bytes

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

Probieren Sie es online!

0-basierte Liste. Gibt false (leer) zurück, wenn die Liste nicht ausweichbar ist.

Xcali
quelle