MediumArrayHash TableDesignQueueMatrixSimulation

Design Snake Game

1 approach, code in every language

Design the classic snake game played on a grid with the given width and height. The snake starts one cell long at the top-left corner, position row 0 and column 0, and food appears one piece at a time at the coordinates listed in the food array, in that order.

Implement the class SnakeGame with the constructor SnakeGame(width, height, food) and the method move(direction), where direction is one of the strings U, D, L, or R for up, down, left, and right. Each call advances the snake one cell in the requested direction. If the snake moves onto the current food cell, it grows by one and the next piece of food becomes active; otherwise its tail advances so its length stays the same.

The game ends, and move returns -1, if the snake runs into a wall or bites its own body. The subtle rule is that the snake may move into the cell its tail currently occupies, because the tail vacates that cell on the same step. Otherwise move returns the current score, which equals the snake length minus one.

Example 1

Input: operations = ["SnakeGame", "move", "move", "move", "move", "move", "move"] args = [[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]

Output: [null, 0, 0, 1, 1, 2, -1]

On a 3 by 2 board the snake moves right then down with no score. Moving right onto [1, 2] eats the first food for score 1. Moving up then left onto [0, 1] eats the second food for score 2. The final up move leaves the board, ending the game with -1.

Example 2

Input: operations = ["SnakeGame", "move", "move"] args = [[2, 2, [[0, 1]]], ["R"], ["R"]]

Output: [null, 1, -1]

On a 2 by 2 board the snake starts at the top-left, moves right onto the food at [0, 1] to score 1, then moving right again runs off the board for game over.

Constraints

1 <= width, height <= 10^4
0 <= food.length <= 50 and food[i].length == 2, with 0 <= food[i][0] < height and 0 <= food[i][1] < width
direction is one of U, D, L, or R, and at most 10^4 calls will be made to move.

Body Deque with an Occupancy Set

Track the snake body in a double-ended queue and mirror its cells in a hash set for constant-time self-collision checks, advancing a pointer through the food list.

Loading animation…

Intuition

The snake behaves exactly like a queue: it gains a new head at the front and, when it does not eat, drops its tail from the back. To detect biting itself quickly we keep a set of every cell the body occupies, so membership tests are constant time instead of scanning the whole body. The one tricky rule is that the tail moves away on the same step, so before testing the new head we temporarily remove the tail cell from the set; if the snake eats, we put it back because the tail does not move. A single index into the food list tells us which piece is currently active, and we advance it each time the head lands on food.

Algorithm walkthrough

1Store the body as a deque of cells with the head at the front, and keep a set holding the encoded coordinates of every body cell, starting with the corner cell.
2On move, compute the new head by shifting the current head one step in the given direction, and return -1 immediately if it leaves the grid.
3Remove the current tail from the occupancy set, since it will vacate its cell unless the snake grows this step.
4If the new head cell is still in the set, the snake bit itself, so return -1.
5If the new head matches the active food cell, advance the food pointer and keep the tail; otherwise pop the tail off the deque so the length stays fixed.
6Push the new head onto the front of the deque, add it to the set, and return the score, which is the body length minus one.

Implementation

from collections import deque
from typing import List

class SnakeGame:
    def __init__(self, width: int, height: int, food: List[List[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.foodIndex = 0
        self.snake = deque([(0, 0)])
        self.occupied = {(0, 0)}

    def move(self, direction: str) -> int:
        row, col = self.snake[0]
        if direction == "U":
            row -= 1
        elif direction == "D":
            row += 1
        elif direction == "L":
            col -= 1
        elif direction == "R":
            col += 1

        if row < 0 or row >= self.height or col < 0 or col >= self.width:
            return -1

        tail = self.snake[-1]
        self.occupied.discard(tail)
        if (row, col) in self.occupied:
            return -1

        eat = (self.foodIndex < len(self.food)
               and self.food[self.foodIndex][0] == row
               and self.food[self.foodIndex][1] == col)

        if eat:
            self.foodIndex += 1
            self.occupied.add(tail)
        else:
            self.snake.pop()

        self.snake.appendleft((row, col))
        self.occupied.add((row, col))
        return len(self.snake) - 1

Time

O(1) per move using the occupancy set; the food pointer and deque updates are all constant time.

Space

O(L) where L is the current snake length, stored once in the deque and once in the set.

Encoding each cell as row times width plus column lets a single integer set stand in for a two-dimensional lookup.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free