Minimum Jumps to Reach Home
Problem
A bug starts at position 0 on a number line and wants to reach its home at position x. Each jump moves it exactly a positions forward or b positions backward, but it may never jump backward twice in a row, never land on a negative position, and never land on any position listed in forbidden. Return the minimum number of jumps needed to land exactly on x, or −1 if home is unreachable.
forbidden = [14,4,18,1,15], a = 3, b = 15, x = 93from collections import deque
def minimum_jumps(forbidden, a, b, x):
limit = max([x] + forbidden) + a + b
bad = set(forbidden)
q = deque([(0, 0, 0)]) # position, back-flag, jumps
seen = {(0, 0)}
while q:
pos, back, jumps = q.popleft()
if pos == x:
return jumps
f = pos + a
if f <= limit and f not in bad and (f, 0) not in seen:
seen.add((f, 0))
q.append((f, 0, jumps + 1))
g = pos - b
if not back and g >= 0 and g not in bad and (g, 1) not in seen:
seen.add((g, 1))
q.append((g, 1, jumps + 1))
return -1function minimumJumps(forbidden, a, b, x) {
const limit = Math.max(x, ...forbidden, 0) + a + b;
const bad = new Set(forbidden);
const q = [[0, 0, 0]]; // position, back-flag, jumps
const seen = new Set(["0,0"]);
let head = 0;
while (head < q.length) {
const [pos, back, jumps] = q[head++];
if (pos === x) return jumps;
const f = pos + a;
if (f <= limit && !bad.has(f) && !seen.has(f + ",0")) {
seen.add(f + ",0");
q.push([f, 0, jumps + 1]);
}
const g = pos - b;
if (!back && g >= 0 && !bad.has(g) && !seen.has(g + ",1")) {
seen.add(g + ",1");
q.push([g, 1, jumps + 1]);
}
}
return -1;
}int minimumJumps(int[] forbidden, int a, int b, int x) {
int limit = x;
for (int f : forbidden) limit = Math.max(limit, f);
limit += a + b;
boolean[][] seen = new boolean[limit + 1][2];
for (int f : forbidden) { seen[f][0] = true; seen[f][1] = true; }
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{0, 0, 0}); // position, back-flag, jumps
seen[0][0] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int pos = cur[0], back = cur[1], jumps = cur[2];
if (pos == x) return jumps;
int f = pos + a;
if (f <= limit && !seen[f][0]) {
seen[f][0] = true;
q.add(new int[]{f, 0, jumps + 1});
}
int g = pos - b;
if (back == 0 && g >= 0 && !seen[g][1]) {
seen[g][1] = true;
q.add(new int[]{g, 1, jumps + 1});
}
}
return -1;
}int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
int limit = x;
for (int f : forbidden) limit = max(limit, f);
limit += a + b;
vector<array<bool, 2>> seen(limit + 1, {false, false});
for (int f : forbidden) seen[f] = {true, true};
queue<array<int, 3>> q;
q.push({0, 0, 0}); // position, back-flag, jumps
seen[0][0] = true;
while (!q.empty()) {
auto [pos, back, jumps] = q.front(); q.pop();
if (pos == x) return jumps;
int f = pos + a;
if (f <= limit && !seen[f][0]) {
seen[f][0] = true;
q.push({f, 0, jumps + 1});
}
int g = pos - b;
if (back == 0 && g >= 0 && !seen[g][1]) {
seen[g][1] = true;
q.push({g, 1, jumps + 1});
}
}
return -1;
}Explanation
The bug's journey is a shortest-path problem on an implicit graph: every jump has the same cost, so plain BFS works — the first time we dequeue the home position we have the minimum number of jumps.
The catch is that position alone is not enough state. Whether a backward jump is allowed depends on the previous jump, so each BFS node is the pair (position, justJumpedBack). The same cell can legitimately be visited twice — once arriving forward, once arriving backward — and only the backward arrival forbids jumping back again.
BFS also needs a finite graph, but the number line is infinite. The fix is a safe upper bound: limit = max(x, max(forbidden)) + a + b. Once the bug is more than a + b past everything that matters (home and every forbidden cell), going even further forward can never be part of a shortest route — any return trip could have been started earlier with the same move pattern. Clipping the line at limit makes the state space finite without losing any optimal path.
Walk through the default example: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9 gives limit = 18 + 3 + 15 = 36. From 0 the backward jump would land at −15, so only forward moves are possible: 0 → 3 → 6 → 9. None of those cells is forbidden, and 9 is dequeued at depth 3, so the answer is 3.
Each of the limit + 1 positions appears in at most two states (back-flag 0 or 1), every state is enqueued at most once thanks to the seen set, and each dequeue does O(1) work checking two neighbors. Both time and space are therefore linear in the bound max(x, max(forbidden)) + a + b.