Design Snake Game
Problem
Design a snake game on a grid of given width and height with a list of food positions; implement a move function that moves the snake in the given direction, returns the game's score after the move, or -1 if the game is over due to collision or boundary crossing.
- 1 ≤ width, height ≤ 10⁴
- 0 ≤ food.length ≤ 10⁴
- food[i].length == 2
- 0 ≤ food[i][0] < height
- 0 ≤ food[i][1] < width
- direction is one of 'U', 'D', 'L', 'R'
Example
width = 3, height = 2, food = [[1,2],[0,1]]; moves = ['R', 'D', 'R', 'U', 'L', 'U'][0, 0, 1, 1, 2, -1]Initially, the snake is at (0,0). Move 'R' moves it to (0,1), no food eaten, score 0. Move 'D' to (1,1), no food, score 0. Move 'R' to (1,2), eats first food, snake grows, score 1. Move 'U' to (0,2), no food, score 1. Move 'L' to (0,1), eats second food, snake grows, score 2. Move 'U' to (-1,1), out of bounds, game over, returns -1.
Approach
Straightforward Solution
A naive approach might store the snake's body as a list and check for collisions by scanning the list, resulting in O(n) collision checks per move, which is inefficient for long snakes.
Core Observation
The snake's position and body must be tracked precisely to detect collisions with itself and boundaries. The snake moves by adding a new head and removing the tail unless it eats food, in which case it grows by not removing the tail. Efficient membership checks for the snake's body are essential to detect self-collisions in O(1) time.
Path to Optimal
The key insight is to use a deque to represent the snake's body for O(1) head and tail operations, and a hash set to track body positions for O(1) collision detection. When moving, the tail is removed before checking collisions to allow the snake to move into the tail's previous position without false collision. Food consumption is handled by checking if the new head matches the next food position, in which case the tail is restored to grow the snake.
Optimal Approach
Use a deque to store the snake's body coordinates with the head at the front and a set for constant-time membership checks. On each move, compute the new head position, remove the tail from the set and deque, check for collisions, then add the new head. If the new head matches the current food, increment score and restore the tail to grow the snake. Return the score or -1 if the game ends.
Time
O(1) per move
Each move involves constant-time operations: deque pop and append, set add and remove, and simple arithmetic for position updates. Collision checks are O(1) due to the set.
Space
O(n)
The snake's body can grow up to the size of the grid or the number of food items, so the deque and set store up to O(n) positions, where n is the number of moves or food items.
Pattern Spotlight
Simulation (Stateful Grid Movement with Collision Detection)
When simulating a moving object with a dynamic body on a grid, maintain both an ordered structure for the body and a hash set for quick collision checks, carefully updating these in the correct order to avoid false positives when the tail moves forward.
Solution
| 1 | class SnakeGame: |
| 2 | def __init__(self, width: int, height: int, food: List[List[int]]): |
| 3 | self.width = width |
| 4 | self.height = height |
| 5 | self.food = food |
| 6 | self.food_index = 0 |
| 7 | self.snake = deque([(0, 0)]) |
| 8 | self.body = {(0, 0)} |
| 9 | self.score = 0 |
| 10 | self.dirs = { |
| 11 | "U": (-1, 0), |
| 12 | "D": (1, 0), |
| 13 | "L": (0, -1), |
| 14 | "R": (0, 1) |
| 15 | } |
| 16 | |
| 17 | def move(self, direction: str) -> int: |
| 18 | dr, dc = self.dirs[direction] |
| 19 | head_r, head_c = self.snake[0] |
| 20 | new_r, new_c = head_r + dr, head_c + dc |
| 21 | new_head = (new_r, new_c) |
| 22 | |
| 23 | if not (0 <= new_r < self.height and 0 <= new_c < self.width): |
| 24 | return -1 |
| 25 | |
| 26 | tail = self.snake.pop() |
| 27 | self.body.remove(tail) |
| 28 | |
| 29 | if new_head in self.body: |
| 30 | return -1 |
| 31 | |
| 32 | self.snake.appendleft(new_head) |
| 33 | self.body.add(new_head) |
| 34 | |
| 35 | if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]): |
| 36 | self.food_index += 1 |
| 37 | self.score += 1 |
| 38 | self.snake.append(tail) |
| 39 | self.body.add(tail) |
| 40 | |
| 41 | return self.score |
Step-by-Step Solution
Initialize Snake State and Movement Directions
| 3 | self.width = width |
| 4 | self.height = height |
| 5 | self.food = food |
| 6 | self.food_index = 0 |
| 7 | self.snake = deque([(0, 0)]) |
| 8 | self.body = {(0, 0)} |
| 9 | self.score = 0 |
| 10 | self.dirs = { |
| 11 | "U": (-1, 0), |
| 12 | "D": (1, 0), |
| 13 | "L": (0, -1), |
| 14 | "R": (0, 1) |
| 15 | } |
Objective
To set up the initial game state including grid dimensions, food list, snake body tracking, and movement direction mappings.
Key Insight
Representing the snake's body as both a deque and a set allows efficient updates and collision detection. The deque maintains the order of the snake's segments for head and tail operations, while the set enables O(1) membership checks. Predefining direction vectors simplifies move calculations and reduces errors.
Interview Quick-Check
Core Logic
Using a deque for the snake's body preserves order for head/tail operations, while a set tracks occupied positions for constant-time collision detection.
Common Pitfalls & Bugs
Failing to keep the set and deque in sync can cause incorrect collision detection or state corruption.
State & Boundaries
Initialize the snake at position (0, 0) with score zero and food index zero to track progress through the food list.
Compute New Head Position and Check Boundary Collision
| 17 | def move(self, direction: str) -> int: |
| 18 | dr, dc = self.dirs[direction] |
| 19 | head_r, head_c = self.snake[0] |
| 20 | new_r, new_c = head_r + dr, head_c + dc |
| 21 | new_head = (new_r, new_c) |
| 23 | if not (0 <= new_r < self.height and 0 <= new_c < self.width): |
| 24 | return -1 |
Objective
To calculate the snake's next head position based on the input direction and verify it remains within grid boundaries.
Key Insight
Mapping directions to row and column deltas allows concise and error-free position updates. Boundary checks are essential to detect game-over conditions immediately when the snake moves outside the grid.
Interview Quick-Check
Core Logic
Translate the direction into coordinate offsets and apply them to the current head to get the new head position.
State & Boundaries
Check if the new head position is within the grid bounds; if not, return -1 to indicate game over.
Common Pitfalls & Bugs
Off-by-one errors in boundary checks can cause incorrect game termination or allow invalid moves.
Update Snake Body by Moving Tail and Detect Self-Collision
| 26 | tail = self.snake.pop() |
| 27 | self.body.remove(tail) |
| 29 | if new_head in self.body: |
| 30 | return -1 |
Objective
To simulate the snake moving forward by removing the tail, then check if the new head collides with the body.
Key Insight
Removing the tail before collision detection allows the snake to move into the tail's previous position without falsely triggering a collision. Checking the new head against the body set ensures immediate detection of self-collision, which ends the game.
Interview Quick-Check
Core Logic
Pop the tail from the deque and remove it from the set before checking if the new head collides with the remaining body.
State & Boundaries
If the new head is found in the body set after tail removal, return -1 to indicate the snake bit itself.
Common Pitfalls & Bugs
Checking collision before removing the tail leads to false positives when the snake moves into its tail's position.
Add New Head and Handle Food Consumption to Grow Snake
| 32 | self.snake.appendleft(new_head) |
| 33 | self.body.add(new_head) |
| 35 | if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]): |
| 36 | self.food_index += 1 |
| 37 | self.score += 1 |
| 38 | self.snake.append(tail) |
| 39 | self.body.add(tail) |
Objective
To add the new head position to the snake's body and grow the snake if food is eaten at the new head location.
Key Insight
Appending the new head to the front of the deque and adding it to the set updates the snake's position. If the new head matches the current food position, increment the score and restore the tail to grow the snake by not removing it. This approach elegantly handles growth without complex state management.
Interview Quick-Check
Core Logic
Add the new head to both the deque and set to update the snake's body state.
State & Boundaries
Check if the new head matches the next food position; if so, increment score, advance food index, and restore the tail to grow the snake.
Common Pitfalls & Bugs
Failing to restore the tail after eating food causes the snake to shrink incorrectly.
Return Current Score or Game Over Indicator
| 41 | return self.score |
Objective
To return the current score after a successful move or -1 if the game ended due to collision or boundary crossing.
Key Insight
Returning the score reflects the number of food items eaten, which is the game's progress metric. Returning -1 signals the game is over, allowing the caller to handle termination.
Interview Quick-Check
Core Logic
Return the current score if the move is valid, or -1 if the game ended.
Line Analysis
This solution has 10 Critical lines interviewers watch for.
return -1Return -1 to indicate game over due to boundary collision.
Returning -1 signals to the caller that the game has ended because the snake moved out of bounds.
if new_head in self.body:Check if the new head position collides with the snake's body.
Detecting self-collision is critical to end the game when the snake bites itself.
return -1Return -1 to indicate game over due to self-collision.
Returning -1 signals the game has ended because the snake collided with itself.
self.snake.append(tail)Restore the tail position to the snake's deque to grow the snake.
Appending the tail back prevents its removal, effectively growing the snake by one segment.
self.body = {(0, 0)}Initialize a set to track the snake's body positions for O(1) collision checks.
The set enables constant-time membership tests to detect self-collisions quickly, which is critical for performance.
if not (0 <= new_r < self.height and 0 <= new_c < self.width):Check if the new head position is outside the grid boundaries.
Boundary checks prevent invalid moves and detect game-over conditions immediately.
self.body.remove(tail)Remove the tail position from the body set to update occupied positions.
Updating the set prevents false collision detection when the snake moves into the tail's previous position.
self.body.add(new_head)Add the new head position to the body set for collision tracking.
Updating the set maintains accurate membership for collision detection.
if self.food_index < len(self.food) and new_head == tuple(self.food[self.food_index]):Check if the new head position matches the current food position.
Detecting food consumption triggers snake growth and score increment.
self.body.add(tail)Add the tail position back to the body set to maintain accurate collision tracking.
Restoring the tail in the set ensures the snake's body is correctly represented after growth.
self.snake = deque([(0, 0)])Initialize the snake's body as a deque starting at position (0, 0).
A deque efficiently supports adding/removing from both ends, which models the snake's head and tail movements.
new_r, new_c = head_r + dr, head_c + dcCalculate the new head's row and column by applying the direction deltas.
Computing the new head position is the fundamental step in simulating the snake's movement.
tail = self.snake.pop()Remove the tail position from the snake's deque to simulate forward movement.
Removing the tail models the snake moving forward by vacating the last position unless it grows.
self.snake.appendleft(new_head)Add the new head position to the front of the snake's deque.
Appending the new head updates the snake's position to reflect the move.
self.dirs = {Define a dictionary mapping directions to coordinate offsets.
Mapping directions to row and column deltas simplifies move calculations and reduces errors.
dr, dc = self.dirs[direction]Retrieve the row and column deltas for the move direction.
Using the direction dictionary ensures consistent and error-free movement calculations.
head_r, head_c = self.snake[0]Get the current head position of the snake.
The head position is the reference point for calculating the new position after the move.
self.score += 1Increment the score to reflect food eaten.
The score represents the number of food items consumed, which is the game's progress metric.
return self.scoreReturn the current score after a successful move.
Returning the score communicates the game's progress after each valid move.
def move(self, direction: str) -> int:Start processing a move in the given direction.
This method encapsulates the logic for updating the snake's position and game state after a move.
new_head = (new_r, new_c)Create a tuple representing the new head position.
Using a tuple allows consistent storage and lookup in the deque and set.
self.food_index += 1Increment the food index to point to the next food item.
Advancing the food index tracks progress through the food list.
self.food_index = 0Initialize the index to track the next food item.
Tracking the current food index allows efficient sequential checking of food consumption without scanning the entire list.
self.food = foodStore the list of food positions.
The food list defines where the snake can grow and is used to check if the snake eats food on a move.
self.width = widthStore the grid width.
The width is essential for boundary checks to ensure the snake does not move outside the grid horizontally.
self.height = heightStore the grid height.
The height is essential for boundary checks to ensure the snake does not move outside the grid vertically.
self.score = 0Initialize the game score to zero.
The score tracks how many food items the snake has eaten, which is the game's progress metric.
"U": (-1, 0),Map 'U' to move up by decreasing row index.
Defines the vertical movement for the 'up' direction.
"D": (1, 0),Map 'D' to move down by increasing row index.
Defines the vertical movement for the 'down' direction.
"L": (0, -1),Map 'L' to move left by decreasing column index.
Defines the horizontal movement for the 'left' direction.
"R": (0, 1)Map 'R' to move right by increasing column index.
Defines the horizontal movement for the 'right' direction.
}End of direction mapping dictionary.
Completes the direction-to-offset mapping for all valid moves.
Test Your Understanding
Why is the tail removed from the body set before checking for collisions with the new head position?
Because the snake moves forward by removing its tail and adding a new head, the tail's previous position is vacated and thus should not count as a collision. Removing the tail first prevents falsely detecting a collision when the snake moves into the space just vacated by its tail.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Design Snake Game from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Design Snake Game drill