Design Snake Game Python Solution with Tests

Tested Python solution for LeetCode 353 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 353, Medium. Topics: Design, Queue, Array, Hash Table, Simulation. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

lcpy gen -n 353   # by problem number
lcpy gen -s design_snake_game   # by problem name

​

Problem

Design a Snake game that is played on a device with screen size height x width.

The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.

You are given an array food where food[i] = (r_i, c_i) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game’s score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

• SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
• int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, return -1.

​

Examples

Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]

Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

​

Constraints

• 1 <= width, height <= 10^4
• 1 <= food.length <= 50
• food[i].length == 2
• 0 <= r_i < height
• 0 <= c_i < width
• direction.length == 1
• direction is 'U', 'D', 'L', or 'R'.
• At most 10^4 calls will be made to move.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class SnakeGame:
    # Time: O(1) per move
    # Space: O(w * h + f) for the snake body and food list
    def __init__(self, width: int, height: int, food: list[list[int]]) -> None:
        self.height = height
        self.width = width
        self.food = food
        self.score = 0
        self.food_idx = 0
        self.snake = deque([(0, 0)])
        self.occupied = {(0, 0)}

    def move(self, direction: str) -> int:
        head_i, head_j = self.snake[0]
        new_i, new_j = head_i, head_j
        if direction == "U":
            new_i -= 1
        elif direction == "D":
            new_i += 1
        elif direction == "L":
            new_j -= 1
        elif direction == "R":
            new_j += 1
        if not (0 <= new_i < self.height and 0 <= new_j < self.width):
            return -1
        if (
            self.food_idx < len(self.food)
            and new_i == self.food[self.food_idx][0]
            and new_j == self.food[self.food_idx][1]
        ):
            self.score += 1
            self.food_idx += 1
        else:
            self.occupied.remove(self.snake.pop())
        if (new_i, new_j) in self.occupied:
            return -1
        self.snake.appendleft((new_i, new_j))
        self.occupied.add((new_i, new_j))
        return self.score

​

Complexity

Time	Space
O(1) per move	O(w * h + f) for the snake body and food list

​

Tags

NeetCode All.