Question

Formatted question description: https://leetcode.ca/all/353.html

Design a Snake game that is played on a device with screen size height x width. 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 a length of 1 unit.

You are given an array food where food[i] = (r_i, c_i) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

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

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).

Implement the SnakeGame class:

SnakeGame(int width, int height, int[][] food) Initializes the object with a screen of size height x width and the positions of the food.
int move(String direction) Returns the score of the game after applying one direction move by the snake. If the game is over, 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
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border

Constraints:

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

Algorithm

We need a one-dimensional array to store the position of the snake body.

As the head of the snake moves forward a step, the tail of the snake also moves forward, and the body in the middle is still in its original position. As a result of the movement, the head of the snake changes to a new position, removing the position of the tail.

What needs attention is whether the position of removing the snake tail is before or after detecting the collision with the snake body.

If it is later, you cannot pass this test case: [[3,3,[[2,0],[0,0]]],["D"],["D"],["U"]] ,
If it is before, there is no problem To detect whether the snake head and the snake body collide, use count(snake.begin(), snake.end(), head)

Code

Java
Python

import java.util.LinkedList;

public class Design_Snake_Game {

    // To represent Snake Game
    public class Game {

        public void main(String[] args) {

            System.out.println("Going to start game");

            Cell initPos = new Cell(0, 0);
            Snake initSnake = new Snake(initPos);
            Board board = new Board(10, 10);
            Game newGame = new Game(initSnake, board);
            newGame.gameOver = false;
            newGame.direction = DIRECTION_RIGHT;

            // We need to update the game at regular intervals,
            // and accept user input from the Keyboard.

            // here I have just called the different methods
            // to show the functionality
            for (int i = 0; i < 5; i++) {
                if (i == 2)
                    newGame.board.generateFood();
                newGame.update();
                if (i == 3)
                    newGame.direction = DIRECTION_RIGHT;
                if (newGame.gameOver)
                    break;
            }
        }


        public static final int DIRECTION_NONE = 0, DIRECTION_RIGHT = 1,
                                DIRECTION_LEFT = -1, DIRECTION_UP = 2, DIRECTION_DOWN = -2;
        private Snake snake;
        private Board board;
        private int direction;
        private boolean gameOver;

        public Game(Snake snake, Board board) {
            this.snake = snake;
            this.board = board;
        }

        public Snake getSnake() {
            return snake;
        }

        public void setSnake(Snake snake) {
            this.snake = snake;
        }

        public Board getBoard() {
            return board;
        }

        public void setBoard(Board board) {
            this.board = board;
        }

        public boolean isGameOver() {
            return gameOver;
        }

        public void setGameOver(boolean gameOver) {
            this.gameOver = gameOver;
        }

        public int getDirection() {
            return direction;
        }

        public void setDirection(int direction) {
            this.direction = direction;
        }

        // We need to update the game at regular intervals,
        // and accept user input from the Keyboard.
        public void update() {
            System.out.println("Going to update the game");
            if (!gameOver) {
                if (direction != DIRECTION_NONE) {
                    Cell nextCell = getNextCell(snake.getHead());

                    if (snake.checkCrash(nextCell)) {
                        setDirection(DIRECTION_NONE);
                        gameOver = true;
                    } else {
                        snake.move(nextCell);
                        if (nextCell.getCellType() == CellType.FOOD) {
                            snake.grow();
                            board.generateFood();
                        }
                    }
                }
            }
        }

        private Cell getNextCell(Cell currentPosition) {
            System.out.println("Going to find next cell");
            int row = currentPosition.getRow();
            int col = currentPosition.getCol();

            if (direction == DIRECTION_RIGHT) {
                col++;
            } else if (direction == DIRECTION_LEFT) {
                col--;
            } else if (direction == DIRECTION_UP) {
                row--;
            } else if (direction == DIRECTION_DOWN) {
                row++;
            }

            Cell nextCell = board.getCells()[row][col];

            return nextCell;
        }


        // To represent a cell of display board.
        public class Cell {

            private final int row, col;
            private CellType cellType;

            public Cell(int row, int col) {
                this.row = row;
                this.col = col;
            }

            public CellType getCellType() {
                return cellType;
            }

            public void setCellType(CellType cellType) {
                this.cellType = cellType;
            }

            public int getRow() {
                return row;
            }

            public int getCol() {
                return col;
            }
        }

        public class Snake {

            private LinkedList<Cell> snakePartList = new LinkedList<>();
            private Cell head;

            public Snake(Cell initPos) {
                head = initPos;
                snakePartList.add(head);
            }

            public void grow() {
                snakePartList.add(head);
            }

            public void move(Cell nextCell) {
                System.out.println("Snake is moving to " +
                    nextCell.getRow() + " " + nextCell.getCol());
                Cell tail = snakePartList.removeLast();
                tail.setCellType(CellType.EMPTY);

                head = nextCell;
                snakePartList.addFirst(head);
            }

            public boolean checkCrash(Cell nextCell) {
                System.out.println("Going to check for Crash");
                for (Cell cell : snakePartList) {
                    if (cell == nextCell) {
                        return true;
                    }
                }

                return false;
            }

            public LinkedList<Cell> getSnakePartList() {
                return snakePartList;
            }

            public void setSnakePartList(LinkedList<Cell> snakePartList) {
                this.snakePartList = snakePartList;
            }

            public Cell getHead() {
                return head;
            }

            public void setHead(Cell head) {
                this.head = head;
            }
        }

        public class Board {

            final int ROW_COUNT, COL_COUNT;
            private Cell[][] cells;

            public Board(int rowCount, int columnCount) {
                ROW_COUNT = rowCount;
                COL_COUNT = columnCount;

                cells = new Cell[ROW_COUNT][COL_COUNT];
                for (int row = 0; row < ROW_COUNT; row++) {
                    for (int column = 0; column < COL_COUNT; column++) {
                        cells[row][column] = new Cell(row, column);
                    }
                }
            }

            public Cell[][] getCells() {
                return cells;
            }

            public void setCells(Cell[][] cells) {
                this.cells = cells;
            }

            public void generateFood() {
                System.out.println("Going to generate food");
                int row = (int) (Math.random() * ROW_COUNT);
                int column = (int) (Math.random() * COL_COUNT);

                cells[row][column].setCellType(CellType.FOOD);
                System.out.println("Food is generated at: " + row + " " + column);
            }
        }
    }

    // Enum for different cell types
    public enum CellType {

        EMPTY,
        FOOD,
        SNAKE_NODE;
    }
}

from collections import deque


class SnakeGame(object):

  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]]
    """
    self.snake = deque([(0, 0)])
    self.snakeSet = set([(0, 0)])
    self.width = width
    self.height = height
    self.food = deque(food)
    self.directions = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
    self.score = 0

  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
    """
    if direction not in self.directions:
      return -1
    di, dj = self.directions[direction]
    ni, nj = self.snake[0][0] + di, self.snake[0][1] + dj

    if ni < 0 or ni >= self.height or nj < 0 or nj >= self.width:
      return -1

    self.snake.appendleft((ni, nj))

    if self.food and [ni, nj] == self.food[0]:
      self.score += 1
      self.food.popleft()
    else:
      self.snakeSet.discard(self.snake.pop())

    if (ni, nj) in self.snakeSet:
      return -1
    self.snakeSet |= {(ni, nj)}

    return self.score

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

353 - Design Snake Game

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions