17
3
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!
What do you mean by "if you can jump outside of the Collection with a minimum of jumps!"? – HyperNeutrino – 2018-02-22T18:43:05.230
@HyperNeutrino is this troll or you really don't get it? Check Example #2. It has
2 Solutions
, with2 or 3 Jumps
, option with2 Jumps
would be the right. – 0x45 – 2018-02-22T18:43:57.320I really don't get what a minimum of jumps is... it suggests to me that there's meant to be a number of jumps such that if you can't escape the collection in fewer jumps than that it should return false, but the examples mention nothing about that. – HyperNeutrino – 2018-02-22T18:44:48.350
Also, please add more test cases. – HyperNeutrino – 2018-02-22T18:44:54.077
I edited your challenge such that the formatting is less confusing and the task can now be more easily understood. Feel free to edit / rollback if you disagree with the changes I've made. – Mr. Xcoder – 2018-02-22T18:45:19.223
1Also, in general, when people ask for clarification or raise suggestions, they're generally not "trolling". I'd suggest you not assume that. – HyperNeutrino – 2018-02-22T18:45:24.303
@0x45 whether 2 or 3 jumps, we can escape the array so we return
TRUE
so I don't quite understand what that is supposed to mean. – Giuseppe – 2018-02-22T18:45:50.170@HyperNeutrino We want the most optimal path. Which (according to Example 2) would be Index 0 to Index 4 from index 4 we can jump outside. This check of best path should be the crux to this task. – 0x45 – 2018-02-22T18:46:55.457
But since we're returning true/false, it doesn't matter whether or not we find the best path, just whether or not there is a path... – HyperNeutrino – 2018-02-22T18:47:22.260
@Mr.Xcoder Challenge spec says truthy/falsy... – HyperNeutrino – 2018-02-22T18:47:36.437
If we cannot escape, you return false, if you took the return list approach, you should return a empty list. – 0x45 – 2018-02-22T18:47:59.457
9
Also, please consider using the sandbox for your challenges! Many of these concerns might have been addressed earlier if you had posted there.
– Giuseppe – 2018-02-22T18:48:21.233@0x45 wait so if it is escapable return # steps? – HyperNeutrino – 2018-02-22T18:48:24.233
@HyperNeutrino well, thats a great idea. I will consider to update it to your suggestion. Stand by- – 0x45 – 2018-02-22T18:49:03.203
3Related, Related. – Mr. Xcoder – 2018-02-22T18:51:31.427
@Mr.Xcoder, I totally disagree with your assumption – 0x45 – 2018-02-22T18:52:46.013
3@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 – 2018-02-22T18:53:57.277
10
@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 – 2018-02-22T19:06:23.1331I have edited the post to clarify what I think it's now asking; please feel free to roll it back if there's anything you disagree with. – Giuseppe – 2018-02-22T19:10:54.143
@Giuseppe thanks, i'm not native speaking english. Your assumptions are correct – 0x45 – 2018-02-22T19:13:01.620
@0x45 yep, we totally understand here! we have lots of people posting from all over the world, which is why we have places like the Sandbox to help you edit your challenge in a friendly manner without anyone getting frustrated by something as reasonable as a simple language barrier! :) I really like this challenge and hope it gets lots of good answers!
– Giuseppe – 2018-02-22T19:16:14.33313It 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 – 2018-02-22T19:21:38.060@0x45 can we use maxint as a null value? – ngn – 2018-02-23T01:55:26.743
@0x45 Can we use ∞ as a null value? – Esolanging Fruit – 2018-02-23T05:08:37.833
@EsolangingFruit ∞ is valid. – 0x45 – 2018-02-23T12:46:57.880
@ngn No. So you would say, you could escape the Array with
MaxInt
Value, eventhough you can't. However,∞
is valid. See updated question – 0x45 – 2018-02-23T12:47:57.227When you say
You can jump 4 fields
, do you meanYou MUST jump 4 fields
, orYou can jump UP TO 4 fields
? – Flater – 2018-02-23T16:20:34.487@Flater up to 4 fields, you gotta make the best decision to escape the array with a minimum of jump. So always the highest isn't necessary the best. – 0x45 – 2018-02-24T16:10:38.953