The Jump Algorithm

Meetup

Went to a Coding Whiteboard Meetup tonight.  It was pretty great.  One of the leaders was even a CS master's student.  At first, honestly, I felt a little bit frustrated, especially because everyone around me seemed to be using pretty high level concepts / approaches that I wasn't familiar with.  But I found someone and relentlessly talked him through his approach until we both kind of realized there were issues in the problem we hadn't worked out yet.  I guess it just reinforces my feeling that when something seems too difficult, if you can, you need to find someone and force him to explain it to you in terms you can understand.  If the people around you really understand what they're about, they will have no problem and you'll learn a lot (assuming they're patient, I guess).  If they don't, you'll realize you aren't as alone as you thought you were.  Bit of the old Socrates.

Problem

So imagine you have an array with a bunch of numbers, I guess all greater than or equal to zero.  Maybe they could be less than zero in a slightly more challenging version of the problem, if it makes much of a difference at all -- but for now say they're greater than or equal to zero.  So it might look like this:

[ 5 , 10 , 3 , 0 , 4 ]

You start at the beginning of the array.  At any given entry, you have the option of traveling up to so many squares as the value of that entry forward.  First entry (index zero) I can go up to five forward.  So certainly I can reach the end of the array from there.  Similarly for the second entry and the third.  But if I were unlucky enough to start on the fourth entry, I would have nowhere to go from there.  It's a sticking point.

So you might have an array of arbitrary size and arbitrary entries, and you want to know whether it's possible to get from the start of the array to the end.

The Trivial Solution / An Intuition

I did not think of this, I have to admit.  But if every entry in the array is greater than zero, of course you can get to the end.  The problem is when the array has a bunch of zeroes in it.  So that's where my first intuition came from.  I thought, "Well these zeroes are just so many holes.  If I have a row of n zeroes, provided that the entry before that row is n+1 or more, I can get across it."  A little bit of discussion with a dubious colleague led me to add that the entry before the entry before the hole could also be n+2, and in general the i-th entry before the hole has to be, I guess, n+i.  But my dubious colleague felt this would be a lot of stuff to check, and it would be inefficient.  You'd have to loop through the array.  If you got to a hole, then you'd count the length of the whole.  Then you'd check the entries before the hole to see if any of them would get you across it.  

Kudos to anyone who can figure out how to keep track of that.

Recursion

After that my colleague started talking about recursion and back-tracking, which wasn't clear to me at all.  That's when I started feeling stressed and inadequate, so I fended off those feelings with questions.  It was only gradually that his idea became clear to me -- and it was a good idea.

What you want to know, in short, is the farthest point you can get to from a given block.  By "block" I mean a series of entries in the array beginning from index zero and going to index n.  So let's consider another array and think about where you can get from different blocks.

[ 2 , 3 , 1 , 3 , 0 , 1 ]

The smallest block is just index zero.  The furthest we can get from index zero is 

0 + 2 = (the index) + (the value of the index) = i + v(i)

-- if you follow the shorthand.  But what about the block that includes index zero and index one?  The situation is a bit different in that case.  Because when we were just considering index zero, the furthest you could go was of course the furthest you could go.  You could go the whole way or something less than the whole way -- but something less than the whole way would fall short of the furthest.  If I'm confusing you, it's just because this is more obvious than you think.  Something less than two, in this example, is less than two.

But here's the riddle.  If you we look at larger blocks, I might have to go less than the furthest in order to get furthest.  It's not too difficult to see in our example: if I start at index zero and go the full value of at that index, I'll get to index two.  But for all the itineraries in the block consisting of index zero and one, that isn't the itinerary that gets me furthest.  I should actually only go one step away from index zero to land on index one, then take advantage of the three at index one to go ahead to index four -- much further than index two.  So the furthest I can get considering the block from index zero to one is the greater of these two:

A. 0 + v(0)

B. 1 + v(1) = (2 - 1) + v(2 - 1) = (v(0) - 1)  + v(v(0) - 1)

I think the generalization I'm gesturing at is right -- or at least on the right track.  And if it's on the right track, it looks like things are going to get messy if we want to figure out the farthest you can go for a block of arbitrary size.

But we thought we would try to do this recursively, with the first block as the base case.  The farthest we could go from the first block was the value of the first block.  Simple.

So what if we assumed that we knew how far you could go for a block ending at index n?  What was the furthest you could go for a block ending at index n + 1?  It gradually dawned on us.  It was the maximum of these two values:

A. The furthest you can get for the block up to n (given)

B. (n + 1) + v ( n + 1 ) -- the full distance you can travel if you get to block (n+1) and ride it as far as it will take you.

And that's when I sort of thought that whether or not you can get to the end of the array is determined by the value of that starting index.  Because it defines a telescoping series of blocks that either end at / past the end -- or don't.

But how to put that insight -- if it really is an insight -- into a nice algorithm?

The Nice Solution

It came from someone else -- but I think all the reasoning we did helps make sense of it.  The trick is finding a nice way to incorporate that recursive step into the final algorithm -- that is, assuming that I can make it from n -- can I make it from n + 1?  So...

Work backwards.  Look to the end.  You know you can make it to the end if you're at the end, assuming everything up until that point went well.  Now go back.  If at each i - 1 we can make it back (that is, forward) to i, then we have a path to the end.

But what if we can't make it back to i from i - 1?  That's OK -- you just keep going and check if you can make it back to i from i - 2.  The demands on v(i - 2) will be greater than they were on v(i - 1), of course.  But if somewhere down the line you meet something that meets those demands, you know you can get back to i.  And then you start looking at whether you can get to that thing from the entries that come before it.  Until you get to the start of the array.

It isn't my first intuitive idea, but there is a thread leading from that idea to the solution.  It's an efficient way of carrying out the intuition -- the idea is to start with the holes and then look to see whether you can leap across them.

So all in all -- when you do an algorithm you think about a lot of things.  Some of those things are just structural speculations (our "recursion"), some of them are naive intuitions -- but you learn about the structure of the problem.  And if you can't solve it, you still know more about it than when you began.  Or -- don't despair if you lose a chess game.  You learned something about the possibility space of chess.  The nice thing about failing to solve an algorithm like this one, though, is that the possibility space isn't so huge.  You'll get your break through eventually -- or at least get someone else's.

And the other moral: question people relentlessly until you drag them down to your level.