Problem statement

https://leetcode.com/problems/design-snake-game/

Solution

Let us keep the following pieces of information:

  1. self.occup is set of occupied cells by snake.
  2. self.snake is snake itself in the form of queue.
  3. self.food is inversed list of food, so we always will look at the last element.
  4. self.dir is dictionary of directions
  5. self.score is current score we have.

Then each time we check where new position of head of the snake should be and if it is outside borders, we return -1. Also we need to check case of sell-cross, be careful about the case of $4$-elements snake, which will not kill itself: when we arrive at the place of head, tail already not there anymore. Next, we check if new cell has food or not: if it has, then increase score and remove element from food list. Else, remove old position of tail from queue and self.occup. Finally, add new position to queue and self.occup.

Complexity

Time complexity of init is just $O(1)$, as well as for move function. Space compplexity is $O(score)$, where score is maximum score snake will reach, it is bounded by $W\cdot H$ and $N$: ammount of food as well.

Code

class SnakeGame:
    def __init__(self, width, height, food):
        self.w, self.h = width, height
        self.occup = set([(0, 0)])
        self.snake = deque([(0, 0)])
        self.food = food[::-1]
        self.dir = {"D": (0, 1), "U": (0, -1), "R": (1, 0), "L": (-1, 0)}
        self.score = 0      

    def move(self, direction):
        x, y = self.snake[-1]
        dx, dy = self.dir[direction]
        if x+dx < 0 or x+dx >= self.w or y+dy < 0 or y+dy >= self.h:
            return -1
        
        if (x+dx, y+dy) in self.occup and (x+dx, y+dy) != self.snake[0]:
            return -1   
        
        if self.food and self.food[-1] == [y + dy, x + dx]:
            self.score += 1
            self.food.pop()
        else:
            old = self.snake.popleft()
            self.occup.remove(old)
            
        self.snake.append((x+dx, y+dy))
        self.occup.add((x+dx, y+dy))
            
        return self.score