We do tower hopping

Question

Task

Given an array of non-negative integers a, determine the minimum number of rightward jumps required to jump "outside" the array, starting at position 0, or return zero/null if it is not possible to do so.

A jump from index i is defined to be an increase in array index by at most a[i].

A jump outside is a jump where the index resulting from the jump i is out-of-bounds for the array, so for 1-based indexing i>length(a), and for 0-based indexing, i>=length(a).

Example 1

Consider 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

The shortest path by "jumping" to go out-of-bounds has length 2:

We could jump from 0->2->4->outside which has length 3 but 0->4->outside has length 2 so we return 2.

Example 2

Suppose 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 this case, it is impossible to jump outside the array, so we should return a zero/null or any non deterministic value like ∞.

Example 3

Suppose Array=[4]:

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

We can directly jump from index 0 outside of the array, with just one jump, so we return 1.

Edit:

Due to multiple questions about the return value: Returning ∞ is totally valid, if there is no chance to escape. Because, if there is a chance, we can define that number.

This is code-golf, so the shortest code in bytes wins!

Answer 1

Haskell, 70 58 bytes

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

Try it online!

EDIT: -12 bytes thanks to @Esolanging Fruit and the OP for deciding to allow infinity!

Returns Infinity when there is no solution which makes the solution a lot simpler. Since we can only move forwards f just looks at the head of the list and drops 1<=k<=x items from the list and recurs. Then we just add 1 to each solution the recursive calls found and take the minimum. If the head is 0 the result will be infinity (since we cannot move there is no solution). Since 1+Infinity==Infinity this result will be carried back to the callers. If the list is empty that means we have left the array so we return a cost of 0.

Answer 2

Husk, 9 bytes

Γö→▼Mo₀↓ŀ

Returns Inf when no solution exists. Try it online!

Explanation

Husk's default return values come in handy here.

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

If the input list is empty, then Γ cannot deconstruct it, so it returns the default integer value, 0. If the first element is 0, then the result of Mo₀↓ŀ is an empty list, on which ▼ returns infinity.

Answer 3

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

Try it online!

-11 bytes thanks to Mr. Xcoder
-12 bytes thanks to Mr. Xcoder and Rod

Answer 4

APL (Dyalog Classic) ngn/apl, 18 bytes

EDIT: switched to my own implementation of APL because Dyalog doesn't support infinities and the challenge author doesn't allow finite numbers to act as "null"

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

Try it online! try it at ngn/apl's demo page

returns ⌊/⍬ ∞ for no solution

Answer 5

Haskell, 45 bytes

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

Try it online!

Outputs Infinity when impossible. The auxiliary left argument to % tracks how many more spaces we can move in our current hop.

Answer 6

Perl 5, 56 53 bytes

Includes +1 for a

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

Just the code:

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

Try it online!

Answer 7

Perl 5, 80 bytes

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

Try it online!

Answer 8

Jelly, 32 bytes

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

Try it online!

This is just too long...

Answer 9

Jelly, 19 18 bytes

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

Try it online!

Explanation

<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

Answer 10

JavaScript ES6, 118 bytes

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

Try it online!

Performs a breadth first search of the array to find the shortest path.

Answer 11

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

Try it online!

Answer 12

Julia 0.6, 79 bytes

Returns the number of jumps or Inf if you can't escape. Recursively look at the first element and either return Inf or 1 depending on if you can escape, otherwise add 1 to the shortest solution for truncated arrays representing each valid jump. The control flow is done with two ternary statements like 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)

Try it online!

Answer 13

C# (.NET Core), 97 bytes

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

Try it online!

Returns 0 if no path was found.

Explanation

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

Answer 14

Python 2, 83 73 72 bytes

^{-10 thanks to @user202729
-1 thanks to @JonathanFrech}

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

Try it online! Returns infinity for a null value.