Design Snake Game

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

1. 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.
2. 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.
3. 3Remove the current tail from the occupancy set, since it will vacate its cell unless the snake grows this step.
4. 4If the new head cell is still in the set, the snake bit itself, so return -1.
5. 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.
6. 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