Solution For Design Snake Game

Problem Statement:

Design a Snake game that is played on a board of size nxn. The snake starts at position [0,0] on the board with a length of 1. The snake can move in four directions – up, down, left, or right. The snake moves one unit per move and grows in length by one unit when it eats a food on the board at a given position. If the snake hits a wall or its own body, the game is over.

Solution:

To solve this problem, we need to maintain the state of the game at different points in time. We can do this by creating a data structure for the board, the snake, and the food.

Board:

The board is a 2D matrix of size nxn. The board can have three states at any given point in time – empty, snake, and food. We can represent these states using integers – 0 for empty, 1 for snake, and 2 for food.

Snake:

The snake is a series of connected cells on the board. We can represent the snake using a double-ended queue (deque) in Python. We can use a deque because adding and removing elements from the front and back of a deque is an O(1) operation. The front of the deque represents the head of the snake and the back of the deque represents the tail of the snake. We can initialize the snake with a length of 1 and starting at position [0,0] on the board.

Food:

The food is a single cell on the board. We can represent the food using a tuple that contains the row and column of the cell.

Gameplay:

To move the snake in a given direction, we need to add a new head to the deque depending on the direction. If the new head is on an empty cell, we remove the tail of the deque to simulate movement. If the new head is on a food cell, we need to keep the tail of the deque to simulate growth and randomly generate a new food location. If the new head is on a snake cell or out of bounds, the game is over.

Implementation:

We can implement the solution using a class called SnakeGame that contains methods to start the game, move the snake, and check the state of the game.

“`
from collections import deque
import random

class SnakeGame:
def init(self, n: int, food: List[List[int]]):
self.board = [[0] * n for _ in range(n)] self.board[0][0] = 1
self.snake = deque([(0, 0)])
self.food = deque(food)
self.score = 0
self.directions = {‘U’:(-1,0), ‘D’:(1,0), ‘L’:(0,-1), ‘R’:(0,1)}

def move(self, direction: str) -> int:
    #get new head position
    row, col = self.snake[0][0] + self.directions[direction][0], \
               self.snake[0][1] + self.directions[direction][1]

    #terminate if out of bounds or on snake cell
    if row < 0 or row >= len(self.board) or col < 0 or col >= len(self.board[0]) \
    or self.board[row][col] == 1 and (row, col) != self.snake[-1]:
        return -1

    #update score and generate new food if at a food cell
    if self.food and [row, col] == self.food[0]:
        self.score += 1
        self.food.popleft()
        self.generate_food()
    else:
        self.board[self.snake[-1][0]][self.snake[-1][1]] = 0 #remove tail if not on food

    #update snake
    self.board[row][col] = 1
    self.snake.appendleft((row, col))

    return self.score

def generate_food(self):
    #generate random food location
    empty_cells = []
    for i in range(len(self.board)):
        for j in range(len(self.board[0])):
            if self.board[i][j] == 0:
                empty_cells.append((i,j))
    if not empty_cells: return
    index = random.randint(0, len(empty_cells)-1)
    self.food.append(empty_cells[index])

“`

The time complexity of the move() method is O(1) because we are only performing constant time operations – checking the new head position, updating the board, updating the deque, and generating new food if needed. The space complexity is O(n^2) because we are using a board of size nxn.

Conclusion:

In this problem, we learned how to design a Snake game using a board, a snake, and food. We implemented the solution using a class and a deque to represent the snake. We also learned how to generate random food locations and check if a move is invalid.

Step by Step Implementation For Design Snake Game

/*

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

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

You are given a list of food's positions in row-column order. When a snake eats the food, its length and the game's score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

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

Example:

Given width = 3, height = 2, and food = [[1,2],[0,1]].

Snake snake = new Snake(width, height, food);

Initially the snake appears at position (0,0) and the food at (1,2).

|S| | |
| | |F|

snake.move("R"); -> Returns 0

| |S| |
| | |F|

snake.move("D"); -> Returns 0

| | | |
| |S|F|

snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )

| |F| |
| |S|S|

snake.move("U"); -> Returns 1

| |F|S|
| | |S|

snake.move("L"); -> Returns 2 (Snake eats the second food)

| |S|S|
| | |S|

snake.move("U"); -> Returns -1 (Game over because snake collides with border)

*/

class SnakeGame {
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    
    int width;
    int height;
    int[][] food;
    Deque snake;
    int foodIndex;
    int score;
    
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        this.snake = new LinkedList<>();
        this.foodIndex = 0;
        this.score = 0;
        this.snake.offerFirst(new int[]{0, 0});
    }
    
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        int[] head = this.snake.peekFirst();
        int[] tail = this.snake.pollLast();
        int[] nextHead = new int[]{head[0], head[1]};
        
        switch (direction) {
            case "U":
                nextHead[0]--;
                break;
            case "L":
                nextHead[1]--;
                break;
            case "R":
                nextHead[1]++;
                break;
            case "D":
                nextHead[0]++;
                break;
        }
        
        if (nextHead[0] < 0 || nextHead[0] >= this.height || nextHead[1] < 0 || nextHead[1] >= this.width) {
            return -1;
        }
        
        if (this.foodIndex < this.food.length && nextHead[0] == this.food[this.foodIndex][0] && nextHead[1] == this.food[this.foodIndex][1]) {
            this.snake.offerLast(tail);
            this.foodIndex++;
            this.score++;
        }
        
        for (int[] cell : this.snake) {
            if (cell[0] == nextHead[0] && cell[1] == nextHead[1]) {
                return -1;
            }
        }
        
        this.snake.offerFirst(nextHead);
        
        return this.score;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

class SnakeGame:

    def __init__(self, width, height, food):
        """
        Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
        :type width: int
        :type height: int
        :type food: List[List[int]]
        """
        

    def move(self, direction):
        """
        Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body.
        :type direction: str
        :rtype: int
        """
        


# Your SnakeGame object will be instantiated and called as such:
# obj = SnakeGame(width, height, food)
# param_1 = obj.move(direction)

/**
 * Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
 * @param {number} width
 * @param {number} height
 * @param {number[][]} food
 */
var SnakeGame = function(width, height, food) {
    this.width = width;
    this.height = height;
    this.food = food;
    this.score = 0;
    this.snake = [];
    this.direction = "RIGHT";
    this.head = [0,0];
    this.tail = [0,0];
    
    //initially snake is at position 0,0
    this.snake.push(this.head);
};

/**
 * Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body.
 * @param {string} direction
 * @return {number}
 */
SnakeGame.prototype.move = function(direction) {
    //if direction is not valid, return -1
    if(!["U", "L", "R", "D"].includes(direction)) return -1;
    
    //if direction is valid, change head position according to direction
    if(direction === "U") this.head[0]--;
    else if(direction === "L") this.head[1]--;
    else if(direction === "R") this.head[1]++;
    else if(direction === "D") this.head[0]++;
    
    //if head position is outside boundary, return -1
    if(this.head[0] < 0 || this.head[0] >= this.height || this.head[1] < 0 || this.head[1] >= this.width) return -1;
    
    //if head position is same as tail position, remove tail from snake
    if(this.head[0] === this.tail[0] && this.head[1] === this.tail[1]) this.snake.pop();
    
    //if head position is same as any food position, remove that food from list and increment score
    if(this.food.length && this.food[0][0] === this.head[0] && this.food[0][1] === this.head[1]) {
        this.score++;
        this.food.shift();
    }
    
    //if head position is same as any snake body position, return -1
    for(let i=0; i
/*

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

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

You are given a list of food's positions in row-column order. When a snake eats the food, its length and the game's score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

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

Example:

Given width = 3, height = 2, and food = [[1,2],[0,1]].

Snake snake = new Snake(width, height, food);

Initially the snake appears at position (0,0) and the food at (1,2).

|S| | |

| | |F|

snake.move("R"); -> Returns 0

| |S| |

| | |F|

snake.move("D"); -> Returns 0

| | | |

| |S|F|

snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )

| |F| |

| |S|S|

snake.move("U"); -> Returns 1

| |F|S|

| | |S|

snake.move("L"); -> Returns 2 (Snake eats the second food)

| |S|S|

| | |S|

snake.move("U"); -> Returns -1 (Game over because snake collides with border)

*/

class SnakeGame {

public:

/** Initialize your data structure here.

@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */

SnakeGame(int width, int height, vector> food) {

}

/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */

int move(string direction) {

}

};

/**

* Your SnakeGame object will be instantiated and called as such:

* SnakeGame obj = new SnakeGame(width, height, food);

* int param_1 = obj.move(direction);

*/
using System; 
using System.Collections.Generic; 

public class SnakeGame { 

/** Initialize your data structure here. 
    @param width - screen width 
    @param height - screen height 
    @param food - A list of food positions 
    E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */ 
    public SnakeGame(int width, int height, int[][] food) { 
        this.width = width; 
        this.height = height; 
        this.food = food; 
        this.score = 0; 
        this.snake = new LinkedList(); 
        this.snake.AddFirst(new int[] {0, 0}); 
        this.foodIndex = 0; 
    } 
    
    /** Moves the snake. 
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */ 
    public int Move(string direction) { 
        int[] head = this.snake.First.Value; 
        int[] newHead = new int[] {head[0], head[1]}; 
        switch (direction) { 
            case "U": 
                newHead[0]--; 
                break; 
            case "L": 
                newHead[1]--; 
                break; 
            case "R": 
                newHead[1]++; 
                break; 
            case "D": 
                newHead[0]++; 
                break; 
        } 
        if (newHead[0] < 0 || newHead[0] >= this.height || newHead[1] < 0 || newHead[1] >= this.width || this.snake.Contains(newHead)) { 
            return -1; 
        } 
        if (this.foodIndex < this.food.GetLength(0) && newHead[0] == this.food[this.foodIndex][0] && newHead[1] == this.food[this.foodIndex][1]) { 
            this.snake.AddFirst(newHead); 
            this.foodIndex++; 
            return ++this.score; 
        } 
        this.snake.AddFirst(newHead); 
        this.snake.RemoveLast(); 
        return this.score; 
    } 
    
    private int width; 
    private int height; 
    private int[][] food; 
    private int score; 
    private LinkedList snake; 
    private int foodIndex; 
} 

/** 
 * Your SnakeGame object will be instantiated and called as such: 
 * SnakeGame obj = new SnakeGame(width, height, food); 
 * int param_1 = obj.Move(direction); 
 */