Design Snake Game

medium design queue hash set

Problem

Design a Snake game on a w×h grid. Each move(direction) returns the score after the move or -1 if the snake hits a wall or itself.

Inputw=3, h=2, food=[[1,2],[0,1]]; moves="RDRUL"

Output[0,0,1,1,2]

Hitting food extends the snake; running off-grid returns -1.

food (r,c ;)

moves (UDLR)

from collections import deque
class SnakeGame:
    def __init__(self, w, h, food):
        self.w, self.h, self.food = w, h, food
        self.fi = 0
        self.body = deque([(0, 0)])
        self.occ = {(0, 0)}
        self.score = 0
    def move(self, d):
        dr, dc = {"U":(-1,0), "D":(1,0), "L":(0,-1), "R":(0,1)}[d]
        hr, hc = self.body[0]
        nr, nc = hr + dr, hc + dc
        tail = self.body[-1]
        # leaving tail (might re-enter): preview occupancy
        if not (0 <= nr < self.h and 0 <= nc < self.w):
            return -1
        if self.fi < len(self.food) and [nr, nc] == self.food[self.fi]:
            self.score += 1; self.fi += 1
        else:
            self.body.pop(); self.occ.discard(tail)
        if (nr, nc) in self.occ: return -1
        self.body.appendleft((nr, nc)); self.occ.add((nr, nc))
        return self.score

class SnakeGame {
  constructor(w, h, food) {
    this.w = w; this.h = h; this.food = food; this.fi = 0;
    this.body = [[0, 0]]; this.occ = new Set(["0,0"]); this.score = 0;
  }
  move(d) {
    const [dr, dc] = {U:[-1,0], D:[1,0], L:[0,-1], R:[0,1]}[d];
    const [hr, hc] = this.body[0];
    const nr = hr + dr, nc = hc + dc;
    if (nr < 0 || nr >= this.h || nc < 0 || nc >= this.w) return -1;
    if (this.fi < this.food.length && this.food[this.fi][0] === nr && this.food[this.fi][1] === nc) {
      this.score++; this.fi++;
    } else {
      const tail = this.body.pop();
      this.occ.delete(tail.join(","));
    }
    if (this.occ.has(nr + "," + nc)) return -1;
    this.body.unshift([nr, nc]); this.occ.add(nr + "," + nc);
    return this.score;
  }
}

class SnakeGame {
    int w, h; int[][] food; int fi = 0, score = 0;
    Deque body = new ArrayDeque<>();
    Set occ = new HashSet<>();
    public SnakeGame(int w, int h, int[][] food) {
        this.w = w; this.h = h; this.food = food;
        body.add(new int[]{0, 0}); occ.add(0);
    }
    public int move(String d) {
        int[] D = switch (d) { case "U" -> new int[]{-1, 0}; case "D" -> new int[]{1, 0}; case "L" -> new int[]{0, -1}; default -> new int[]{0, 1}; };
        int[] head = body.peekFirst();
        int nr = head[0] + D[0], nc = head[1] + D[1];
        if (nr < 0 || nr >= h || nc < 0 || nc >= w) return -1;
        if (fi < food.length && food[fi][0] == nr && food[fi][1] == nc) { score++; fi++; }
        else { int[] tail = body.pollLast(); occ.remove(tail[0] * w + tail[1]); }
        int key = nr * w + nc;
        if (occ.contains(key)) return -1;
        body.addFirst(new int[]{nr, nc}); occ.add(key);
        return score;
    }
}

class SnakeGame {
    int w, h, fi = 0, score = 0;
    vector> food;
    deque> body;
    set> occ;
public:
    SnakeGame(int w, int h, vector>& food) : w(w), h(h), food(food) {
        body.push_back({0, 0}); occ.insert({0, 0});
    }
    int move(string d) {
        int dr = d == "U" ? -1 : d == "D" ? 1 : 0;
        int dc = d == "L" ? -1 : d == "R" ? 1 : 0;
        auto [hr, hc] = body.front();
        int nr = hr + dr, nc = hc + dc;
        if (nr < 0 || nr >= h || nc < 0 || nc >= w) return -1;
        if (fi < (int)food.size() && food[fi][0] == nr && food[fi][1] == nc) { score++; fi++; }
        else { auto t = body.back(); body.pop_back(); occ.erase(t); }
        if (occ.count({nr, nc})) return -1;
        body.push_front({nr, nc}); occ.insert({nr, nc});
        return score;
    }
};

Explanation

The snake is just a line of cells that grows from the head and shrinks at the tail. The neat trick is to store the body in a deque (so you can add a head and drop a tail in O(1)) plus a set of occupied cells so collision checks are instant.

Each move(d) computes the new head position by adding the direction offset to the current head. If that lands outside the grid, the game is over and we return -1.

Next we decide about the tail. If the new head is sitting on the next food, the snake grows: we bump the score and advance the food index, and we do not remove the tail. Otherwise there is no food, so we pop the tail off the deque and remove it from the occupied set.

After that we check self-collision: if the new head cell is still in occ, the snake bit itself, so return -1. Removing the tail first matters here — the snake is allowed to move into the square its tail just vacated. Otherwise we push the new head onto the front, mark it occupied, and return the score.

Example on a 3×2 grid with food [[1,2],[0,1]] and moves RDRUL: the first moves return score 0, then eating the food at (1,2) bumps the score to 1, and a later food brings it to 2, giving [0,0,1,1,2].

Time: O(1) per move Space: O(n)