Design Snake Game

Medium

Atlassian

11 views

Topics:

Arrays

Design a Snake game that is played on a grid of width width and height height. Play the game online if you are not familiar with the game.

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

You are given a list of food's positions in the format of (row, col). The food is guaranteed to be placed on empty cells.

Each time the snake eats the food, its length and score increase by 1.

When the snake moves, the first cell the snake occupies is emptied, and the snake moves to the new cell. The snake dies if it moves out of bounds (not within width x height) or moves into a cell that is part of its body.

Implement the SnakeGame class:

SnakeGame(int width, int height, int[][] food) Initializes the object with the width and height of the game board and the food's positions.
int move(String direction) Moves the snake. If the snake moves successfully, return the score after the move. Otherwise, return -1.

Example 1:

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 (snake moves right, no food).
snakeGame.move("D"); // return 0 (snake moves down, no food).
snakeGame.move("R"); // return 1 (snake moves right, eats the first food. The length of snake is now 2).
snakeGame.move("U"); // return 1 (snake moves up, no food)
snakeGame.move("L"); // return 2 (snake moves left, eats the second food. The length of snake is now 3).
snakeGame.move("U"); // return -1 (game over because snake collides with border).

Constraints:

1 <= width, height <= 10⁴
0 <= food.length <= 2000
food[i].length == 2
0 <= food[i][0] < height
0 <= food[i][1] < width
direction.length == 1
direction is 'U', 'D', 'L', or 'R'.
At most 10⁴ calls will be made to move.

Design Snake Game

Medium

Atlassian

11 views

Topics:

Arrays

Design a Snake game that is played on a grid of width width and height height. Play the game online if you are not familiar with the game.

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

You are given a list of food's positions in the format of (row, col). The food is guaranteed to be placed on empty cells.

Each time the snake eats the food, its length and score increase by 1.

When the snake moves, the first cell the snake occupies is emptied, and the snake moves to the new cell. The snake dies if it moves out of bounds (not within width x height) or moves into a cell that is part of its body.

Implement the SnakeGame class:

SnakeGame(int width, int height, int[][] food) Initializes the object with the width and height of the game board and the food's positions.
int move(String direction) Moves the snake. If the snake moves successfully, return the score after the move. Otherwise, return -1.

Example 1:

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 (snake moves right, no food).
snakeGame.move("D"); // return 0 (snake moves down, no food).
snakeGame.move("R"); // return 1 (snake moves right, eats the first food. The length of snake is now 2).
snakeGame.move("U"); // return 1 (snake moves up, no food)
snakeGame.move("L"); // return 2 (snake moves left, eats the second food. The length of snake is now 3).
snakeGame.move("U"); // return -1 (game over because snake collides with border).

Constraints:

1 <= width, height <= 10⁴
0 <= food.length <= 2000
food[i].length == 2
0 <= food[i][0] < height
0 <= food[i][1] < width
direction.length == 1
direction is 'U', 'D', 'L', or 'R'.
At most 10⁴ calls will be made to move.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the game board (rows x columns), and what are the coordinate ranges?
Where does the snake initially start on the board, and what is its initial length?
How is the food represented, and how is its placement determined (e.g., randomly, provided as input)?
How does the game end (e.g., snake hits a wall, snake hits itself)? What should the `move()` function return in such cases?
How often will the `move()` function be called, and how should I handle the case where the snake doesn't eat food during a move?

Brute Force Solution

Approach

The brute force strategy for the Snake game involves simulating every possible move the snake can make at each step. We essentially explore every path the snake could take until it either finds food or runs into itself or a wall. This method ensures we find a solution, if one exists, but is not very efficient.

Here's how the algorithm would work step-by-step:

Start with the snake's initial position.
From that position, consider all possible moves the snake can make: up, down, left, and right.
For each possible move, check if the new position is valid. A position is invalid if the snake runs into a wall or itself.
If the move is valid, check if the snake found food.
If the snake found food, the game is won!
If the snake didn't find food, repeat this process from the new position, considering all possible moves from there.
If we reach a point where no valid moves are possible, we backtrack to the previous position and try a different move.
Continue exploring all possible move combinations until the food is found, or all possibilities are exhausted.

Code Implementation

def design_snake_game_brute_force(grid_height, grid_width, food_positions):
    snake_initial_position = [0, 0]
    snake_body = [snake_initial_position[:]]
    food_index = 0

    def is_valid_move(new_head_position, current_snake_body):
        row, col = new_head_position
        if row < 0 or row >= grid_height or col < 0 or col >= grid_width:
            return False
        
        # Check if the snake hits itself
        for segment in current_snake_body[:-1]:
            if segment == new_head_position:
                return False
        return True

    def find_path(current_snake_body, current_food_index):
        if current_food_index == len(food_positions):
            return True

        food_position = food_positions[current_food_index]
        head_row, head_col = current_snake_body[-1]

        possible_moves = [
            [head_row - 1, head_col],  # Up
            [head_row + 1, head_col],  # Down
            [head_row, head_col - 1],  # Left
            [head_row, head_col + 1]   # Right
        ]

        for new_head_position in possible_moves:
            if is_valid_move(new_head_position, current_snake_body):
                new_snake_body = current_snake_body + [new_head_position[:]]
                
                #Check if the snake eats food
                if new_head_position == food_position:
                    
                    #Snake ate food, increment food
                    if find_path(new_snake_body, current_food_index + 1):
                        return True
                else:
                    #If not eating food, remove the tail
                    if find_path(new_snake_body[1:], current_food_index):
                        return True

        return False

    #Start recursive call from the snake's initial position
    return find_path(snake_body, food_index)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^m) – The described brute force solution explores all possible move sequences for the snake. Let m be the number of moves required to reach the food. At each step, the snake has up to 4 possible moves (up, down, left, right). In the worst case, the algorithm explores every possible path of length m before finding the food or determining it's unreachable. This results in a branching factor of 4 for each move, leading to roughly 4^m possible move sequences to explore. Therefore, the time complexity is O(4^m), where m is the number of moves.

Space Complexity

O(b^d) – The described brute force approach uses recursion to explore possible snake movements. The depth of the recursion (d) represents the number of moves the snake makes before finding food or reaching a dead end. At each level of recursion, a constant amount of space is used for variables like the current snake position. However, the branching factor (b) represents the number of possible moves (up, down, left, right) from each position. Therefore, the maximum size of the call stack can grow exponentially with the depth and branching factor, approximating O(b^d), where b is the branching factor and d is the maximum recursion depth. We also need to keep track of visited locations for backtracking, and this can grow up to the number of cells visited by snake leading to the overall auxiliary space complexity of O(b^d).

Optimal Solution

Approach

The Snake game design involves carefully managing the snake's body and movement on a game board. The optimal approach utilizes a data structure to efficiently track the snake's location and food placement, enabling quick updates and collision detection. By employing these strategies, we prevent unnecessary checks and calculations, leading to a faster and more responsive game.

Here's how the algorithm would work step-by-step:

Create a game board, representing the playing area as a grid.
Represent the snake's body as a list of positions on the grid. The head is at the beginning of the list.
Start the snake at a specific location on the game board with a default length.
Place the food at a random, unoccupied location on the game board.
When the snake moves, calculate its new head position based on the direction of movement.
Check if the new head position is out of bounds or collides with the snake's body. If so, the game is over.
If the new head position is the same as the food's position, the snake eats the food, its length increases, and new food is generated at another unoccupied location.
If the snake does not eat food, remove the tail segment to maintain the snake's length. The snake's body effectively slides forward.
Update the game board to reflect the snake's new position and the food's location.
Repeat the movement, collision, and food consumption steps continuously until the game ends.

Code Implementation

import random

class SnakeGame:

    def __init__(self, width, height, food_positions):
        self.width = width
        self.height = height
        self.snake = [(0, 0)]
        self.food_positions = food_positions
        self.food_index = 0
        self.score = 0

    def move(self, direction):
        head_row, head_col = self.snake[0]
        if direction == "U":
            new_head = (head_row - 1, head_col)
        elif direction == "D":
            new_head = (head_row + 1, head_col)
        elif direction == "L":
            new_head = (head_row, head_col - 1)
        elif direction == "R":
            new_head = (head_row, head_col + 1)
        else:
            return False

        # Check for game over conditions.
        if (new_head[0] < 0 or new_head[0] >= self.height or
            new_head[1] < 0 or new_head[1] >= self.width or
            new_head in self.snake):
            return False

        self.snake.insert(0, new_head)

        # Check if the snake ate the food.
        if self.food_index < len(self.food_positions) and new_head == self.food_positions[self.food_index]:
            self.score += 1
            self.food_index += 1
            # Increase snake length on eating

        else:
            self.snake.pop()
            # Maintain snake length

        return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The primary operations within the Snake game involve updating the snake's position, checking for collisions (with the boundaries or itself), and placing food. Collision detection and boundary checks are done in constant time. Even when the snake eats food and grows, the growth only increases the snake's body size by a constant factor (1). Placing new food can be considered O(1) on average as it does not scale with snake size. Thus, each move operation takes constant time.

Space Complexity

O(N) – The snake's body is represented as a list of positions on the grid, where N is the maximum length of the snake. In the worst-case scenario, the snake could occupy almost the entire board before eating food, so the list of positions could grow close to the board size. Therefore, the space complexity is directly proportional to the maximum possible length of the snake's body, which we define as N. While the game board also contributes to space, we are analyzing auxiliary space and the board is considered the input.

Edge Cases

Case	How to Handle
Snake initializes outside the board boundaries.	Initialize the snake within the board dimensions, throwing an error if initial position is invalid.
Food spawns outside the board boundaries.	Ensure food generation respects board limits; re-generate food if necessary.
Snake grows so large it fills the entire board.	Handle this as a winning condition, ending the game gracefully.
Initial snake length is longer than the board dimension.	Constrain initial snake length to a reasonable size relative to the board dimensions, or throw an exception.
Game board has zero width or zero height.	Throw an IllegalArgumentException as the game board must have positive dimensions.
Snake tries to move into its own body immediately after initialization.	Ensure initial snake placement and movement direction avoids immediate self-collision.
Game requests an invalid move (e.g., moving backwards without sufficient length).	Disallow invalid moves, either ignoring them or ending the game.
Large number of food objects exist simultaneously and their locations are stored.	Use a data structure that efficiently handles additions/removals, considering performance implications with larger food quantities.