Aufgabe

aBestimmen Sie bei einem Array nicht negativer Ganzzahlen die Mindestanzahl von Rechtssprüngen, die erforderlich sind, um "außerhalb" des Arrays zu springen, beginnend an Position 0, oder geben Sie null / null zurück, wenn dies nicht möglich ist.

Ein Sprung vom Index iist definiert als eine Erhöhung des Array-Index um höchstens a[i].

Ein Sprung nach draußen ist ein Sprung, bei dem der aus dem Sprung resultierende Index ifür das Array außerhalb der Grenzen liegt, also für die 1-basierte Indizierung i>length(a)und für die 0-basierte Indizierung i>=length(a).

Beispiel 1

Betrachten Sie Array = [4,0,2,0,2,0]:

Array[0] = 4 -> You can jump 4 field
Array[1] = 0 -> You can jump 0 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 0 -> You can jump 0 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 0 -> You can jump 0 field

Der kürzeste Weg durch "Springen" zum Überschreiten der Grenzen hat Länge 2:

Wir könnten springen, von 0->2->4->outsidedem Länge hat, 3aber 0->4->outsideLänge hat, 2also kehren wir zurück 2.

Beispiel 2

Nehmen wir an Array=[0,1,2,3,2,1]:

Array[0] = 0 -> You can jump 0 fields
Array[1] = 1 -> You can jump 1 field
Array[2] = 2 -> You can jump 2 field
Array[3] = 3 -> You can jump 3 field
Array[4] = 2 -> You can jump 2 field
Array[5] = 1 -> You can jump 1 field

In diesem Fall ist es nicht möglich, aus dem Array herauszuspringen. Wir sollten daher eine Null / Null oder einen beliebigen nicht deterministischen Wert wie zurückgeben ∞.

Beispiel 3

Nehmen wir an Array=[4]:

Array[0] = 4 -> You can jump 4 field

Wir können mit nur einem Sprung direkt von Index 0 außerhalb des Arrays springen, also kehren wir zurück 1.

Bearbeiten:

Aufgrund mehrfacher Fragen zum Rückgabewert: Die Rückgabe ∞ist vollständig gültig, wenn keine Fluchtmöglichkeit besteht. Denn wenn es eine Chance gibt, können wir diese Zahl definieren.

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes!

Schale , 9 Bytes

Γö→▼Mo₀↓ŀ

Gibt zurück, Infwenn keine Lösung vorhanden ist. Probieren Sie es online!

Erläuterung

Hier bieten sich die Standard-Rückgabewerte von Husk an.

Γö→▼Mo₀↓ŀ  Implicit input: a list, say [2,3,1,1]
Γ          Deconstruct into head H = 2 and tail T = [3,1,1]
 ö         and feed them into this function:
        ŀ   Range from 0 to H-1: [0,1]
    Mo      For each element in range,
       ↓    drop that many element from T: [[3,1,1],[1,1]]
      ₀     and call this function recursively on the result: [1,2]
   ▼        Take minimum of the results: 2
  →         and increment: 3

Wenn die Eingabeliste leer ist, Γkann sie nicht dekonstruiert werden, sodass der standardmäßige ganzzahlige Wert 0 zurückgegeben wird. Wenn das erste Element 0 ist, ist das Ergebnis vonMo₀↓ŀ eine leere Liste, für die ▼unendlich zurückgegeben wird.

Haskell , 70 58 Bytes

f[]=0
f(0:_)=1/0
f(x:s)=minimum[1+f(drop k$x:s)|k<-[1..x]]

Probieren Sie es online!

EDIT: -12 Bytes dank @Esolanging Fruit und dem OP für die Entscheidung, Unendlich zuzulassen!

Gibt zurück, Infinitywenn es keine Lösung gibt, was die Lösung viel einfacher macht. Da wir uns nur vorwärts bewegen können, fschaut einfach auf den Kopf der Liste und löscht 1<=k<=xElemente aus der Liste und wiederholt sich. Dann addieren wir zu jeder gefundenen Lösung einfach 1 und nehmen das Minimum. Wenn der Kopf 0 ist, ist das Ergebnis unendlich (da wir uns nicht bewegen können, gibt es keine Lösung). Da 1+Infinity==Infinitydieses Ergebnis an die Anrufer zurückübertragen wird. Wenn die Liste leer ist, bedeutet dies, dass wir das Array verlassen haben und einen Wert von 0 zurückgeben.

Python 2 , 124 Bytes

def f(a):
 i={0};l=len(a)
 for j in range(l):
	for q in{0}|i:
	 if q<l:i|=set(range(q-a[q],q-~a[q]))
	 if max(i)/l:return-~j

Probieren Sie es online!

-11 Bytes dank Mr. Xcoder
-12 Bytes dank Mr. Xcoder und Rod

APL (Dyalog Classic) ngn / apl , 18 Bytes

BEARBEITEN: wurde auf meine eigene Implementierung von APL umgestellt, da Dyalog keine Unendlichkeiten unterstützt und der Herausforderungsautor nicht zulässt, dass endliche Zahlen als "null" fungieren.

⊃⊃{⍵,⍨1+⌊/⍺↑⍵}/⎕,0

Probieren Sie es online! Probieren Sie es auf der Demoseite von ngn / apl aus

kehrt für keine Lösung zurück⌊/⍬ ∞

Haskell , 45 Bytes

(1%)
0%_=1/0
a%(h:t)=min(1+h%t)$(a-1)%t
_%_=0

Probieren Sie es online!

Ausgänge Infinitywenn unmöglich. Das Hilfsargument left gibt an %, um wie viel Leerzeichen wir uns in unserem aktuellen Hop bewegen können.

Perl 5 , 56 53 Bytes

Beinhaltet +1füra

perl -aE '1until-@F~~%v?say$n:$n++>map\@v{$_-$F[-$_]..$_},%v,0'  <<< "4 0 2 0 2 0"; echo

Nur der Code:

#!/usr/bin/perl -a
1until-@F~~%v?say$n:$n++>map\@v{$_-$F[-$_]..$_},%v,0

Probieren Sie es online!

Perl 5 , 80 Bytes

sub f{$_[0]>=@_||1+((sort{$a?$b?$a-$b:-1:1}map f(@_[$_..$#_]),1..$_[0])[0]||-1)}

Probieren Sie es online!

Jelly , 32 Bytes

ṛ/ṆȧJ’Ṛ
Rḟ"ÇƤZ$$Tị$Œp+\€Ṁ<Li0ȧ@Ḣ

Probieren Sie es online!

Das ist einfach zu lang ...

Jelly , 19 18 Bytes

<LḢ
ḊßÐƤṁḢḟ0‘Ṃµ1Ç?

Probieren Sie es online!

Erläuterung

<LḢ  Helper link. Input: array
<    Less than
 L   Length
  Ḣ  Head - Returns 0 if its possible to jump out, else 1

ḊßÐƤṁḢḟ0‘Ṃµ1Ç?  Main link. Input: array
            Ç   Call helper link
             ?  If 0
           1      Return 1
                Else
          µ       Monadic chain
Ḋ                   Dequeue
 ßÐƤ                Recurse on each suffix
     Ḣ              Head of input
    ṁ               Mold, take only that many values
      ḟ0            Filter 0
        ‘           Increment
         Ṃ          Minimum

JavaScript ES6 , 118 Byte

(x,g=[[0,0]])=>{while(g.length){if((s=(t=g.shift())[0])>=x.length)return t[1];for(i=0;i++<x[s];)g.push([s+i,t[1]+1])}}

Probieren Sie es online!

Führt eine Breitensuche im Array durch, um den kürzesten Pfad zu finden.

C (gcc) , 80 Bytes

f(A,l,M,j,r)int*A;{M=~0;for(j=0;l>0&&j++<*A;)if(M<1|M>(r=f(A+j,l-j)))M=r;A=-~M;}

Probieren Sie es online!

Julia 0.6 , 79 Bytes

Gibt die Anzahl der Sprünge zurück oder Infwenn Sie nicht entkommen können. Schauen Sie sich das erste Element rekursiv an und geben Sie entweder zurück Infoder 1fügen Sie, je nachdem, ob Sie es verlassen können, 1die kürzeste Lösung für abgeschnittene Arrays hinzu, die jeden gültigen Sprung darstellen. Der Kontrollfluss erfolgt mit zwei ternären Anweisungen wie test1 ? ontrue1 : test2 ? ontrue2 : onfalse2.

f(a,n=endof(a))=a[1]<1?Inf:a[1]>=n?1:1+minimum(f(a[z:min(z+a[1],n)]) for z=2:n)

Probieren Sie es online!

C # (.NET Core) , 97 Byte

f=l=>{for(int c=l.Count,s=0,j=l[0];j>0;s=f(l.GetRange(j,c-j--)))if(s>0|j>=c)return s+1;return 0;}

Probieren Sie es online!

Gibt 0 zurück, wenn kein Pfad gefunden wurde.

Erläuterung

f = 
    l =>                                      //The list of integers
    {
        for (
            int c = l.Count,                  //The length of the list
                s = 0,                        //Helper to keep track of the steps of the recursion
                j = l[0];                     //The length of the jump, initialize with the first element of the list
                j > 0;                        //Loop while the jump length is not 0
                s = f(l.GetRange(j, c - j--)) //Recursive call of the function with a sub-list stating at the current jump length. 
                                              //Then decrement the jumplength. 
                                              //Returns the number of steps needed to jump out of the sup-list or 0 if no path was found. 
                                              //This is only executed after the first run of the loop body.
            )
        {
            if (j >= c |                      //Check if the current jump lengt gets you out of the list. 
                                              //If true return 1 (s is currently 0). OR
                s > 0 )                       //If the recursive call found a solution (s not 0) 
                                              //return the number of steps from the recursive call + 1
                return s + 1;
        }
        return 0;                             //If the jump length was 0 return 0 
                                              //to indicate that no path was found from the current sub-list.
    }

Python 2 , 83 73 72 Bytes

^{-10 danke an @ user202729
-1 danke an @ JonathanFrech}

lambda a:a and(a[0]and-~min(f(a[k+1:])for k in range(a[0]))or 1e999)or 0

Probieren Sie es online! Gibt unendlich für einen Nullwert zurück.