The machine runs a snake on a width × height grid. The snake occupies a deque of (row, col) cells, head first. Each move(direction) call advances the head one cell; the machine must decide three outcomes: the snake eats food and grows, the snake moves normally, or the game ends.
Order matters. Compute the new head cell from the direction vector, returning −1 if it leaves [0, width) × [0, height). For self-collision the tail moves away this turn, so the head may legally land on the tail's current cell only if no food is eaten. The clean way: pop the tail, test whether the new head is in the occupied set, then push the head — the tail cell is freed before the check, so landing on it is legal.
After the move, compare the head against food[0]. On a match: pop the food, restore the tail (length +1). No match: the tail stays popped. Score is food eaten.
Two structures keep every move O(1) amortized: the deque for the body and a set of occupied cells for collision tests. They must be updated in lockstep — a classic failure mode is the set drifting out of sync, letting the snake pass through itself.
Edge cases: food under the tail at move time (eating restores the tail cell, so the snake keeps its length and the food is gone); no food left; a move that would both eat food and hit the wall — wall collision wins, return −1 first.
class SnakeGame:
def __init__(self, width, height, food):
self.w, self.h, self.food = width, height, food
self.body = deque([(0, 0)])
self.occupied = {(0, 0)}
self.score = 0
def move(self, direction):
dr, dc = {"U": (-1,0), "D": (1,0), "L": (0,-1), "R": (0,1)}[direction]
r, c = self.body[0]
nr, nc = r + dr, c + dc
if not (0 <= nr < self.h and 0 <= nc < self.w):
return -1
self.occupied.remove(self.body.pop())
if (nr, nc) in self.occupied:
return -1
self.body.appendleft((nr, nc))
self.occupied.add((nr, nc))
if self.food and [nr, nc] == self.food[0]:
self.food.pop(0)
self.score += 1
self.occupied.add(self.body[-1])
self.body.append(self.body[-1])
return self.score