# We do tower hopping

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 , so the shortest code in bytes wins!

• Also, please consider using the sandbox for your challenges! Many of these concerns might have been addressed earlier if you had posted there. – Giuseppe Feb 22 '18 at 18:48
• – Mr. Xcoder Feb 22 '18 at 18:51
• @0x45 What assumption? The fact that I linked you to some related challenges? I never said duplicate. I am not sure what you mean. – Mr. Xcoder Feb 22 '18 at 18:53
• @0x45 please assume good intentions. We are asking these questions not because we're trying to make fun of your challenge. Actually, it's quite the opposite: we're interested in your challenge. Just think about it, why would we ask clarifying questions if we disliked your challenge? We have the downvotes/close votes for that purpose. (And as I see, nobody has downvoted your post!) – JungHwan Min Feb 22 '18 at 19:06
• It would be good to have a test case where greedily jumping the maximum distance at every step is not optimal. For example [2, 3, 1, 1]. – Martin Ender Feb 22 '18 at 19:21

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

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. • 58 bytes, but only if you allow Infinity as the null value (which the OP hasn't clarified yet). – Esolanging Fruit Feb 23 '18 at 5:31 • Actually, OP has now allowed this, so that should be valid. – Esolanging Fruit Feb 23 '18 at 14:54 # 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 • You failed print(f([4,1,0,4,1,1,1])) You return 3, but should be 2 Like [0] -> [3] -> outside – 0x45 Feb 22 '18 at 19:20 • @0x45 how so... wait, when you jump, do you have to jump as far as possible or anywhere in between? – HyperNeutrino Feb 22 '18 at 19:21 • @Mr.Xcoder oh yeah, duh. also thanks for the -~ trick, forgot about that one. – HyperNeutrino Feb 22 '18 at 19:22 • @HyperNeutrino "A jump from index i is defined to be an increase in array index by at most a[i]." – Martin Ender Feb 22 '18 at 19:22 • @0x45 ok, thanks for clarifying. I think I fixed it – HyperNeutrino Feb 22 '18 at 19:25 # 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  returns ⌊/⍬ ∞ for no solution • What is the "right argument" of ?? – Erik the Outgolfer Feb 22 '18 at 21:52 • This challenge is in desperate need of better test-cases. But your solution is invalid for example 2 3 1 1 should be mapped to 2 – H.PWiz Feb 22 '18 at 21:55 • @EriktheOutgolfer 0N which is k's integer null; if you're interested, I can explain further in the apl room – ngn Feb 22 '18 at 22:14 • @H.PWiz now it can deal with that – ngn Feb 23 '18 at 11:38 # 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.

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

# Perl 5, 80 bytes

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


Try it online!

# Jelly, 32 bytes

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


Try it online!

This is just too long...

# 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

?  If 0
1      Return 1
Else
Ḋ                   Dequeue
ßÐƤ                Recurse on each suffix
ṁ               Mold, take only that many values
ḟ0            Filter 0
‘           Increment
Ṃ          Minimum


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

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

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

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


# Python 2, 8373 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.

• and min(...)+1for can be and-~min(...)for. – Jonathan Frech Feb 26 '18 at 11:38
• @JonathanFrech Edited. – Esolanging Fruit Feb 26 '18 at 19:49