Nous sautons des tours

17

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 , donc le code le plus court en octets gagne!

0x45
la source
9
Pensez également à utiliser le bac à sable pour vos défis! Beaucoup de ces préoccupations auraient pu être traitées plus tôt si vous y aviez posté.
Giuseppe
3
Lié , Lié .
M. Xcoder
3
@ 0x45 Quelle hypothèse? Le fait que je vous ai lié à des défis connexes? Je n'ai jamais dit doublon . Je ne suis pas sûr de ce que tu veux dire.
M. Xcoder
10
@ 0x45 veuillez supposer de bonnes intentions . Nous ne posons pas ces questions parce que nous essayons de nous moquer de votre défi. En fait, c'est tout le contraire: nous sommes intéressés par votre défi. Pensez-y, pourquoi poserions-nous des questions de clarification si nous n'aimions pas votre défi? Nous avons les votes négatifs / rapprochés à cet effet. (Et comme je vois, personne n'a voté contre votre message!)
JungHwan Min
13
Il serait bon d'avoir un cas de test où sauter goulûment la distance maximale à chaque étape n'est pas optimal. Par exemple [2, 3, 1, 1].
Martin Ender

Réponses:

4

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.

Zgarb
la source
6

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.

user1472751
la source
1
58 octets , mais uniquement si vous autorisez Infinityla valeur nulle (ce que l'OP n'a pas encore clarifié).
Esolanging Fruit
En fait, OP a maintenant permis cela, donc cela devrait être valide.
Esolanging Fruit
3

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

HyperNeutrino
la source
Vous avez échoué print(f([4,1,0,4,1,1,1]))Vous revenez 3, mais devrait être 2comme[0] -> [3] -> outside
0x45
@ 0x45 comment faire ... attendez, quand vous sautez, devez-vous sauter le plus loin possible ou n'importe où entre les deux?
HyperNeutrino
@ Mr.Xcoder oh ouais, duh. merci aussi pour l' -~astuce, oublié celui-là.
HyperNeutrino
@HyperNeutrino "Un saut à partir de l'index i est défini comme une augmentation de l'index du tableau d' au plus a [i]."
Martin Ender
1
@ 0x45 ok, merci pour la clarification. Je pense que je l'ai corrigé
HyperNeutrino
3

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⌊/⍬

ngn
la source
Quel est le "bon argument" de ??
Erik the Outgolfer le
Ce défi a désespérément besoin de meilleurs cas de test. Mais votre solution n'est pas valide, par exemple, 2 3 1 1doit être mappée sur2
H.PWiz
@EriktheOutgolfer 0Nqui est le nombre entier nul de k; si vous êtes intéressé, je peux vous expliquer plus en détail dans la salle
apl
@ H.PWiz maintenant, il peut gérer cela
ngn
3

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.

xnor
la source
2

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!

Ton Hospel
la source
1

Gelée , 32 octets

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

Essayez-le en ligne!

C'est trop long ...

Erik le Outgolfer
la source
1

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
miles
la source
1

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.

fəˈnɛtɪk
la source
0

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!

gggg
la source
0

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.
    }
raznagul
la source
0

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.

Esolanging Fruit
la source
and min(...)+1forpeut être and-~min(...)for.
Jonathan Frech
@JonathanFrech Edited.
Esolanging Fruit