Snake Game: Minimum Moves to Reach the Apple
Company: Jane Street
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Snake Game: Minimum Moves to Reach the Apple
You are simulating the classic Snake game on a grid with `R` rows and `C` columns. Cells are identified as `(r, c)` with `0 <= r < R` and `0 <= c < C`.
The snake is a sequence of `L` distinct cells `body[0], body[1], ..., body[L-1]`, where `body[0]` is the head and every pair of consecutive cells is adjacent (shares an edge). A single apple is located at cell `apple = (ar, ac)`, which is guaranteed not to lie on the snake.
## Movement rules
On each move you choose one of the four directions — up, down, left, or right — and the game advances one tick:
1. The new head cell `h'` is the current head shifted one cell in the chosen direction.
2. If `h'` is the apple cell, the snake **eats and grows**: `h'` is prepended to the body and the tail stays in place (length becomes `L + 1`).
3. Otherwise, `h'` is prepended and the tail cell `body[L-1]` is vacated on the same tick (length is unchanged).
4. The move is **legal** only if `h'` is inside the grid and `h'` does not collide with the snake's body as it exists **after** the tail update. Concretely, `h'` must not equal any of `body[0..L-2]`; moving into the current tail cell `body[L-1]` **is** legal on a non-eating move, because the tail vacates that cell during the same tick.
The snake cannot pass through walls or through itself, and only ever moves one cell per tick.
## Task
Return the minimum number of moves needed for the snake's head to reach the apple cell (the move on which the head enters the apple cell counts), or `-1` if the apple can never be reached by any sequence of legal moves.
## Examples
**Example 1**
```
Input: R = 2, C = 3, body = [[0, 0]], apple = [1, 2]
Output: 3
```
A length-1 snake needs 3 moves, e.g. right, right, down.
**Example 2**
```
Input: R = 3, C = 3, body = [[0, 2], [0, 1], [0, 0]], apple = [2, 0]
Output: 4
```
One optimal route for the head: down to `(1, 2)`, down to `(2, 2)`, left to `(2, 1)`, left to `(2, 0)`. The body follows the head, vacating one tail cell per tick.
**Example 3**
```
Input: R = 2, C = 2, body = [[0, 0], [0, 1], [1, 1]], apple = [1, 0]
Output: 1
```
Moving down puts the head on the apple immediately; the tail does not move on the eating tick.
## Constraints
- `2 <= R, C <= 10`
- `1 <= L <= min(8, R * C - 1)`
- The initial body cells are distinct, consecutive cells are adjacent, and the apple is not on the body.
Quick Answer: This question evaluates proficiency in state-space modeling, constrained grid pathfinding, and dynamic collision handling, testing skills in shortest-path reasoning and movement legality within the Coding & Algorithms domain; the level of abstraction is practical application of algorithmic techniques to simulate evolving game states rather than purely theoretical analysis. It is commonly asked in technical interviews because it requires reasoning about evolving constraints and reachable states, demonstrating an applicant's ability to model complex movement rules and perform effective search under limited grid and body-size constraints.
You are simulating the classic Snake game on a grid with `R` rows and `C` columns. Cells are identified as `(r, c)` with `0 <= r < R` and `0 <= c < C`.
The snake is a sequence of `L` distinct cells `body[0], body[1], ..., body[L-1]`, where `body[0]` is the head and every pair of consecutive cells is adjacent (shares an edge). A single apple is located at cell `apple = (ar, ac)`, guaranteed not to lie on the snake.
**Movement rules.** On each move you choose one of four directions (up, down, left, right) and the game advances one tick:
1. The new head cell `h'` is the current head shifted one cell in the chosen direction.
2. If `h'` is the apple cell, the snake eats and grows: `h'` is prepended and the tail stays in place (length becomes `L + 1`).
3. Otherwise, `h'` is prepended and the tail cell `body[L-1]` is vacated on the same tick (length unchanged).
4. A move is legal only if `h'` is inside the grid and does not collide with the body as it exists after the tail update: `h'` must not equal any of `body[0..L-2]`. Moving into the current tail cell `body[L-1]` is legal on a non-eating move, because the tail vacates that cell during the same tick.
The snake cannot pass through walls or through itself, and moves exactly one cell per tick.
**Task.** Return the minimum number of moves for the snake's head to reach the apple cell (the move on which the head enters the apple counts), or `-1` if the apple can never be reached.
The function receives `R`, `C`, `body` (a list of `[r, c]` cells, head first), and `apple` (`[ar, ac]`).
Constraints
- 2 <= R, C <= 10
- 1 <= L <= min(8, R * C - 1)
- The initial body cells are distinct, consecutive cells are adjacent (share an edge), and the apple is not on the body.
- The head only ever moves one cell per tick, in one of the four cardinal directions.
Examples
Input: (2, 3, [[0, 0]], [1, 2])
Expected Output: 3
Explanation: A length-1 snake starting at (0,0) reaches apple (1,2) in 3 moves, e.g. right, right, down.
Input: (3, 3, [[0, 2], [0, 1], [0, 0]], [2, 0])
Expected Output: 4
Explanation: Head goes down to (1,2), down to (2,2), left to (2,1), left to (2,0)=apple; the body follows, vacating one tail cell per tick.
Hints
- The board layout alone is not a sufficient BFS state: because the snake occupies a path of cells and its tail follows the head, the set of blocked cells depends on the full ordered body. Use the entire body (an ordered tuple of cells) as the BFS state.
- The eating move is what ends the search: as soon as the new head equals the apple, return the current move count + 1. Because the apple is never part of the body during the search, that move is always legal, so growth and the tail-freezing rule never affect the answer.
- For a non-eating move, the new head may not land on any of body[0..L-2], but it MAY land on the current tail body[L-1] since the tail vacates on the same tick. The next state is (newHead, body[0], ..., body[L-2]).
- Standard BFS with a visited set of configurations gives the minimum moves; if the queue empties without the head reaching the apple, return -1.