353. Design Snake Game

Problem Description

The LeetCode problem presents us with a classic game of Snake, where the objective is to control a snake that moves around a grid, eats food, and grows in length with each piece of food it consumes. The game stops if the snake either runs into the wall or itself. We're asked to design the game logic for a snake initially of length 1 unit, starting from the top-left corner of the grid with dimensions height x width.

The grid functions like a 2D array where the food items are coordinates listed in the food array. The snake moves in one of four directions each turn: up (U), down (D), left (L), or right (R). The game scores a point when the snake eats a piece of food, which involves moving to the same coordinate location as the next item in the food array. Food items appear sequentially, with the next item making its appearance only after the current one has been eaten. The game is over if the snake tries to move beyond the boundary of the grid or into a space occupied by its body.

The objective is to implement the SnakeGame class with:

• A constructor SnakeGame(int width, int height, int[][] food) which initializes the game with the screen size and the food positions.
• A method int move(String direction) to move the snake in the requested direction and return the game's score or -1 if the game is over.

Intuition

A smart approach to this problem involves simulating the snake's movement and food consumption on a virtual grid. We need to track the snake's segments and manage our game's state in response to each move call representing the snake's new direction. Given that the snake moves one unit per turn, we can represent its body as a queue, specifically a deque (double-ended queue), where we add the head to one end and remove the tail from the other end each time the snake moves.

To implement this, we require a system to check whether the new position after a move is valid (not hitting walls or its own body), and a way to check whether the snake has reached food.

The solution consists of the following steps:

• Initialize the game state with a deque to represent the snake's body, starting with just the head at the cell (0,0). We'll also use a set for O(1) lookups to ensure the snake does not collide with itself.
• Upon each move action, calculate the snake's new head position.
• If this position is off-grid, the game is over.
• If the new position has food, update the score, and increase the food index to the next food item without removing the current tail segment. This simulates the growth of the snake.
• If there is no food, remove the tail segment (pop from the deque), as we're moving without growing.
• Check if the new position would cause a self-collision. If so, the game is over.
• If the snake survives, update the deque and the set to include the new head position and return the current score.

The usage of a deque allows us to efficiently handle the snake's body segments without the need to shift elements - operations are O(1) for adding/removing from both ends. The set facilitates O(1) lookups to detect self-collisions.

Learn more about Queue patterns.

Solution Approach

The solution to this Snake game problem uses a combination of a queue, specifically a deque (double-ended queue), and a set for efficient operations and checks. Here's a step-by-step approach to the implementation:

• Initialization (__init__): Set up the initial state in the constructor. The snake's body is represented by a deque called q with one element, (0, 0), the initial head position. A set called vis (short for visited) stores the same position to keep track of the cells occupied by the snake (this helps with collision checks). The game's score, the index of the current food item to be eaten (idx), the list of food coordinates food, and the dimensions of the grid are also initialized here.

• Move Method (move):

  1. Extract the current head position of the snake (i, j) from the front of the deque.
  2. Based on the direction provided, calculate the new head position (x, y). Utilizing Python's match-case allows a clear syntax to adjust the coordinates for each possible direction.
  3. Check if the new position is outside the bounds of the grid (x < 0 or x >= self.m or y < 0 or y >= self.n). If so, return -1 to signify the game is over.
  4. Determine if the new position contains food by comparing it to the current food item at index idx. If it does, increase score by 1 and increment idx to point to the next food item but do not pop the tail from the deque because we want the snake's length to increase.
  5. If the new position doesn't have food, remove the tail end of the snake (pop from the deque) and remove the corresponding position from the vis set because the snake moves forward without growing.
  6. If the new position is in the vis set (meaning the new head position is a cell already occupied by its body), return -1 to indicate a self-collision.
  7. Otherwise, add the new position to the front of the deque and add it to the vis set, representing the snake moving forward.
  8. Return the current score.

Algorithmic Complexity:

• The operations deque.appendleft(), deque.pop(), set.add(), and set.remove() are all O(1), meaning they have a constant time complexity per move.
• Checking if the new head position collides with the body ((x, y) in self.vis) is also O(1) thanks to the set data structure.

Data Structures:

• Deque: Chosen for representing the snake's body because it allows for appending and popping at both ends efficiently.
• Set: Chosen for O(1) collision checks with the snake's body.

By judiciously combining these data structures and careful handling of edge cases, the reference solution simulates the game of Snake correctly and efficiently.

Example Walkthrough

In this walkthrough, we'll follow a simple example to demonstrate how the solution approach is implemented when a SnakeGame instance is created and several moves are made. Assume we have a 3x3 grid (width = 3, height = 3) and two food items at positions [[1, 2], [2, 2]].

1. Initialization: We instantiate the SnakeGame with a width of 3, a height of 3, and a food list. The snake starts at (0, 0) (top-left corner).

2. First Move (Right - 'R'): The snake's head is currently (0, 0). With this move to the right, the new head position will be (0, 1). Since this is neither off the grid nor does it have food, the tail stays therefore, we remove the tail from the deque (0,0), and vis set. We add the new head (0, 1) to the q and vis. The game’s score remains 0.

3. Second Move (Right - 'R'): Now, the head moves further right to (0, 2). At this position, there is food ([1, 2] is our first food item). The snake grows and scores a point. We add (0, 2) to the q and vis. We do not remove the tail because the snake has grown. The score is now 1, and the food index (idx) increments to point to the next food at [2, 2].

4. Third Move (Down - 'D'): The snake moves down to (1, 2). This space doesn't have food because we've already consumed the food here. We remove the tail from the q and the vis set. The tail was (0, 1); therefore, the snake's body now consists of the cells at (0, 2) and (1, 2). The score remains 1.

5. Fourth Move (Down - 'D'): The snake moves further down to (2, 2). This is where the second food item is located, so the snake grows again, scoring another point. We add (2, 2) to the q and vis. Again, we do not pop the tail. The game's score is now 2.

6. Fifth Move (Left - 'L'): If the snake attempts to move left, its new head position would be (2, 1) which doesn't result in a boundary collision or self-collision, and it does not contain food. Thus, we pop (0, 2) from the q and remove it from vis. The body now occupies cells (1, 2) and (2, 2). Head is added at (2, 1) and the game score is still 2.

7. Subsequent Movements: Any subsequent moves will follow the same logic about the grid boundaries, food presence, and self-collision checks, modifying the score, deque, and set accordingly. If a move results in a collision with a wall or the snake itself, the game would end, and -1 would be returned.

Following this logic properly simulates the snake's movement around the grid, ensuring efficient and correct behavior for the game.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity for the move operation of the SnakeGame class is generally O(1) for every call. The primary operations consist of updating the head position, checking for collisions, eating food, and updating the snake body.

• Updating Position & Checking Collisions: All these operations involve constant time arithmetic operations and checks, as they only depend on the current direction and the new potential head position.
• Eating Food: This also involves a constant-time comparison to check if the new head position corresponds to the next item in the food list.
• Updating Snake Body: In the case where the snake doesn't eat food, removing the tail (self.q.pop()) and checking for body collisions ((x, y) in self.vis) are both O(1) operations due to the double-ended queue deque and hash set self.vis.

Space Complexity

The space complexity of the SnakeGame is O(N + M) where N is the length of the snake and M is the total number of food items. This is because:

• Snake Representation (self.q and self.vis): The snake is represented by a dequeue (self.q) and a set (self.vis). In the worst case, the snake can grow to fill the entire board, leading to a space complexity of O(N) where N is the number of cells on the board (maximum length of the snake).
• Food List (self.food): The food list is stored in the self.food attribute and takes O(M) space, where M is the number of food items.

Therefore, the overall space complexity is determined by the space needed to store the snake and the food.

Learn more about how to find time and space complexity quickly using problem constraints.