NUHMAN.com

🎮 Problem Statement

Design a Snake game that supports:

1. Moving the snake in 4 directions: 'U' (Up), 'D' (Down), 'L' (Left), 'R' (Right)
2. Eating food and growing longer
3. Ending the game when the snake runs into the wall or itself

🧾 Class Definition

python

class SnakeGame:
    def __init__(self, width: int, height: int, food: List[List[int]]):
        pass

    def move(self, direction: str) -> int:
        pass

• __init__ Parameters:
• width and height – dimensions of the game grid
• food – list of food positions
• move(direction):
• Moves the snake and returns the game score (number of food items eaten).
• Returns -1 if the game is over (wall hit or snake bites itself)

🧠 Key Concepts

• Use a deque to represent the snake’s body, with the head at the end.
• A set is used to quickly check if the snake collides with itself.
• A food pointer tracks the current food to consume.

🐍 Python Implementation

python

from collections import deque

class SnakeGame:
    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0

        self.snake = deque([(0, 0)])         # starting position
        self.snake_set = set([(0, 0)])       # for O(1) collision checks

        self.directions = {
            'U': (-1, 0),
            'D': (1, 0),
            'L': (0, -1),
            'R': (0, 1)
        }

    def move(self, direction: str) -> int:
        dx, dy = self.directions[direction]
        head_x, head_y = self.snake[-1]
        new_x, new_y = head_x + dx, head_y + dy
        new_head = (new_x, new_y)

        # Check wall collision
        if not (0 <= new_x < self.height and 0 <= new_y < self.width):
            return -1

        # Remove tail temporarily
        tail = self.snake.popleft()
        self.snake_set.remove(tail)

        # Check self collision
        if new_head in self.snake_set:
            return -1

        # Add new head
        self.snake.append(new_head)
        self.snake_set.add(new_head)

        # Check if food is eaten
        if self.food_index < len(self.food) and self.food[self.food_index] == [new_x, new_y]:
            self.snake.appendleft(tail)           # grow back the tail
            self.snake_set.add(tail)
            self.food_index += 1

        return self.food_index

✅ Example

python

game = SnakeGame(3, 2, [[1,2],[0,1]])

print(game.move("R")) # 0
print(game.move("D")) # 0
print(game.move("R")) # 1 (eats food at [1,2])
print(game.move("U")) # 1
print(game.move("L")) # 2 (eats food at [0,1])
print(game.move("U")) # -1 (hits wall)

🔍 Step-by-Step Logic

1. Track snake's head and body using deque and set.
2. For each move:

• Compute the new head position.
• Check wall or self-collision.
• Remove tail (unless eating).
• Add new head.
• If eating food, grow the tail back and increment score.

⏱️ Time & Space Complexity

OperationComplexitymove()O(1)InitializationO(N) where N is the food listSpaceO(L) for snake length

💭 Final Thoughts

This simulation teaches:

• Classic queue-based modeling
• Real-time collision detection
• Clean separation of game state and actions

Great for practicing real-time grid games and object-oriented design!