17
\$\begingroup\$

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

\$\endgroup\$
  • 9
    \$\begingroup\$ Also, please consider using the sandbox for your challenges! Many of these concerns might have been addressed earlier if you had posted there. \$\endgroup\$ – Giuseppe Feb 22 '18 at 18:48
  • 3
    \$\begingroup\$ Related, Related. \$\endgroup\$ – Mr. Xcoder Feb 22 '18 at 18:51
  • 3
    \$\begingroup\$ @0x45 What assumption? The fact that I linked you to some related challenges? I never said duplicate. I am not sure what you mean. \$\endgroup\$ – Mr. Xcoder Feb 22 '18 at 18:53
  • 10
    \$\begingroup\$ @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!) \$\endgroup\$ – JungHwan Min Feb 22 '18 at 19:06
  • 13
    \$\begingroup\$ 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]. \$\endgroup\$ – Martin Ender Feb 22 '18 at 19:21

14 Answers 14

4
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 58 bytes, but only if you allow Infinity as the null value (which the OP hasn't clarified yet). \$\endgroup\$ – Esolanging Fruit Feb 23 '18 at 5:31
  • \$\begingroup\$ Actually, OP has now allowed this, so that should be valid. \$\endgroup\$ – Esolanging Fruit Feb 23 '18 at 14:54
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You failed print(f([4,1,0,4,1,1,1])) You return 3, but should be 2 Like [0] -> [3] -> outside \$\endgroup\$ – 0x45 Feb 22 '18 at 19:20
  • \$\begingroup\$ @0x45 how so... wait, when you jump, do you have to jump as far as possible or anywhere in between? \$\endgroup\$ – HyperNeutrino Feb 22 '18 at 19:21
  • \$\begingroup\$ @Mr.Xcoder oh yeah, duh. also thanks for the -~ trick, forgot about that one. \$\endgroup\$ – HyperNeutrino Feb 22 '18 at 19:22
  • \$\begingroup\$ @HyperNeutrino "A jump from index i is defined to be an increase in array index by at most a[i]." \$\endgroup\$ – Martin Ender Feb 22 '18 at 19:22
  • 1
    \$\begingroup\$ @0x45 ok, thanks for clarifying. I think I fixed it \$\endgroup\$ – HyperNeutrino Feb 22 '18 at 19:25
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ What is the "right argument" of ?? \$\endgroup\$ – Erik the Outgolfer Feb 22 '18 at 21:52
  • \$\begingroup\$ 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 \$\endgroup\$ – H.PWiz Feb 22 '18 at 21:55
  • \$\begingroup\$ @EriktheOutgolfer 0N which is k's integer null; if you're interested, I can explain further in the apl room \$\endgroup\$ – ngn Feb 22 '18 at 22:14
  • \$\begingroup\$ @H.PWiz now it can deal with that \$\endgroup\$ – ngn Feb 23 '18 at 11:38
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 80 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 32 bytes

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

Try it online!

This is just too long...

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.
    }
\$\endgroup\$
0
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.