Minimum Jumps to Reach Home

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

---

This problem is similar to the Jump Game problems.

What makes this problem difficult is the addition of a left jump that can be performed from any spot that hasn't already been left jumped to.  

Similar to some other Jump Game problems, we can solve this by utilizing a Breadth-First Search.  A BFS is key because this algorithm is superb at finding the shortest distances, or the minimum jumps.

What we can do is continuously pop a landing spot node from a queue we'll create.  Each time we visit a node, we will calculate its left and right landing spot.  If these landing spots are within the boundary we set, they are not on the forbidden list, and they have not been landed on yet from the given direction, we will visit them next.

This will allow us to concurrently make each valid left and right jump from each spot to find the minimum path to the target.

---

Let's start by pushing each forbidden landing spot into the queue so that we can look these up within constant time during each iteration.

We will also create a seen HashMap which we will use to track the landing spots we have seen, and whether they were seen during a left jump or not.  This part will be explained momentarily.

        forbidden_set = set(forbidden)
        seen = {}

 

We'll also want to set a boundary for when our left jump has gone too far.

If we don't set this, then we will be infinitely jumping to the right since there is no rule about how many right jumps we can perform in a row.

This upper boundary is fickle, but the idea is if we have gone past the maximum between the target and the last forbidden jump spot, past the left jump and two right jumps, then we have gone too far.

At that point, we have made a left jump and two right jumps past this limit and aren't allowed to jump left two times, so there wouldn't be any way for us to jump left twice in order to reach it.

        boundary = max(x, max(forbidden)) + a + 2*b

---

Next, let's make a helper function that will let us know if the current landing spot we are about to visit is valid.

This function will take a spot we're wanting to jump to and whether we are wanting to left jump there.

        def in_bounds(jump:int, left_jumped:bool) -> bool:

 

If a jump is a negative number,  or the jump is greater than the boundary we just set, then we will return false.

If the jump is forbidden, we or if the jump has been seen before, not just the spot but if we jumped there from the same direction, then we will return false.

The reason for this is we can arrive at a spot from either the left or the right.  If we have jumped to this spot before through a right jump, we can still jump back to it through a left jump.  We won't have any cycles until we jump to a spot from the same side multiple times.

            if (jump, left_jumped) in seen or jump in forbidden_set:
                return False

 

If neither of these cases is true, then we have a valid spot that we can jump to.

            return True

---

Lastly, we will make our BFS function.

        def bfs() -> int:

 

We'll need a queue and a counter for the number of jumps that were taken.

            jumps = 0

 

Let's push the first spot into the queue with the left jumped flag set to false, and also mark it as seen.

            seen[(0, False)] = True
            queue.append((0, False))

 

While we still have spot nodes in our queue, we will continue jumping.

            while queue:

 

Each iteration will begin by us taking the length of the queue.

This will let us know how many jumps are in the current layer because each additional layer will be an extra jump taken.

                width = len(queue)

 

Then, for each jump within the current layer, we will pop a jump node from the queue and check if it is the target.  If it is, we will return how many jumps were taken.

                for _ in range(width):
                    spot, left_jumped = queue.popleft()
                    if spot == x:
                        return jumps

 

If it is not, then we will calculate the left jump and right jump from the current spot.

                    left_jump, right_jump = spot - b, spot + a

 

If the right jump is in bounds then we will push it in the queue and mark it as seen.

                    if in_bounds(right_jump, False):
                        queue.append((right_jump, False))
                        seen[(right_jump, False)] = True

 

If we just left jumped to the current post then we can't make another left jump so we will continue to the next node.

                    if left_jumped:
                        continue

 

If we hadn't, then we will check if the left jump is in bounds then push it into the queue and mark it as seen as well.

                    if in_bounds(left_jump, True):
                        queue.append((left_jump, True))
                        seen[(left_jump, True)] = True

 

Once the current layer has been traversed, we will increment our jumps counter.

                jumps += 1

 

If we never reached the target and ran out of jumping spots, we will return false because a path didn't exist to it.

            return -1

---

Now that our helper functions are created, we just need to make the initial call to run and return the BFS output.

        return bfs()

---