Design Snake Game - Leetcode Solution

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.

1