Tâche

Étant donné un tableau d'entiers non négatifs a, déterminez le nombre minimum de sauts vers la droite requis pour sauter "en dehors" du tableau, en commençant à la position 0, ou renvoyez zéro / nul s'il n'est pas possible de le faire.

Un saut d'index iest défini comme une augmentation de l'index du tableau d'au plusa[i] .

Un saut à l'extérieur est un saut où l'index résultant du saut iest hors limites pour le tableau, donc pour l'indexation basée sur 1 i>length(a)et pour l'indexation basée sur 0,i>=length(a) .

Exemple 1

Considérez 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

Le chemin le plus court en "sautant" pour sortir des limites a une longueur 2:

Nous pourrions sauter de 0->2->4->outsidequi a de la longueur 3mais de la 0->4->outsidelongueur, 2alors nous revenons 2.

Exemple 2

Supposons 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

Dans ce cas, il est impossible de sauter en dehors du tableau, nous devons donc retourner un zéro / null ou toute valeur non déterministe comme ∞.

Exemple 3

Supposons Array=[4]:

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

Nous pouvons directement sauter de l'index 0 en dehors du tableau, avec un seul saut, donc nous revenons 1.

Éditer:

En raison de plusieurs questions sur la valeur de retour: Le retour ∞est totalement valide s'il n'y a aucune chance de s'échapper. Parce que, s'il y a une chance, nous pouvons définir ce nombre.

C'est du code-golf , donc le code le plus court en octets gagne!

Coque , 9 octets

Γö→▼Mo₀↓ŀ

Renvoie Inflorsqu'aucune solution n'existe. Essayez-le en ligne!

Explication

Les valeurs de retour par défaut de Husk sont utiles ici.

Γö→▼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

Si la liste d'entrée est vide, elle Γne peut pas être déconstruite, elle renvoie donc la valeur entière par défaut, 0. Si le premier élément est 0, le résultat de Mo₀↓ŀest une liste vide, sur laquelle ▼renvoie l'infini.

Haskell , 70 58 octets

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

Essayez-le en ligne!

EDIT: -12 octets grâce à @Esolanging Fruit et à l'OP pour avoir décidé d'autoriser l'infini!

Renvoie Infinitylorsqu'il n'y a pas de solution, ce qui la rend beaucoup plus simple. Puisque nous pouvons seulement avancer, il fsuffit de regarder le début de la liste et de supprimer les 1<=k<=xéléments de la liste et de les répéter. Ensuite, nous ajoutons simplement 1 à chaque solution les appels récursifs trouvés et prenons le minimum. Si la tête vaut 0 le résultat sera infini (puisque nous ne pouvons pas bouger il n'y a pas de solution). Étant donné que 1+Infinity==Infinityce résultat sera renvoyé aux appelants. Si la liste est vide, cela signifie que nous avons quitté le tableau, nous retournons donc un coût de 0.

Python 2 , 124 octets

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

Essayez-le en ligne!

-11 octets grâce à M. Xcoder
-12 octets grâce à M. Xcoder et Rod

APL (Dyalog Classic) ngn / apl , 18 octets

EDIT: je suis passé à ma propre implémentation d'APL car Dyalog ne prend pas en charge les infinis et l'auteur du défi ne permet pas aux nombres finis d'agir comme "null"

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

Essayez-le en ligne! essayez-le sur la page de démonstration de ngn / apl

revient sans solution⌊/⍬ ∞

Haskell , 45 octets

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

Essayez-le en ligne!

Sorties Infinityquand impossible. L'argument auxiliaire gauche pour %suivre le nombre d'espaces supplémentaires que nous pouvons déplacer dans notre saut actuel.

Perl 5 , 56 53 octets

Comprend +1poura

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

Juste le code:

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

Essayez-le en ligne!

Perl 5 , 80 octets

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

Essayez-le en ligne!

Gelée , 32 octets

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

Essayez-le en ligne!

C'est trop long ...

Gelée , 19 18 octets

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

Essayez-le en ligne!

Explication

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

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

Essayez-le en ligne!

Effectue une première recherche étendue du tableau pour trouver le chemin le plus court.

C (gcc) , 80 octets

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

Essayez-le en ligne!

Julia 0,6 , 79 octets

Renvoie le nombre de sauts ou Infsi vous ne pouvez pas vous échapper. Examinez récursivement le premier élément et retournez Infou 1selon si vous pouvez vous échapper, sinon ajoutez 1à la solution la plus courte pour les tableaux tronqués représentant chaque saut valide. Le flux de contrôle se fait avec deux instructions ternaires comme 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)

Essayez-le en ligne!

C # (.NET Core) , 97 octets

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

Essayez-le en ligne!

Renvoie 0 si aucun chemin n'a été trouvé.

Explication

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 octets

^{-10 grâce à @ user202729
-1 grâce à @JonathanFrech}

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

Essayez-le en ligne! Renvoie l'infini pour une valeur nulle.