Katkat
Back

Snake Game: Minimum Moves to Reach the Apple

Jane StreetSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.