Design Snake Game — Deque-Based State Machine

Problem

Design a snake game on a width × height grid:

Snake starts at (0,0), moves in directions U/D/L/R
Food appears at given positions sequentially
move(direction) — move one step, return score (-1 if game over)
Score = number of food items eaten; snake grows by 1 when food eaten

Key Insight — Deque + HashSet

Deque stores body positions in order (head at front, tail at back)
HashSet enables O(1) self-collision check
On each move: compute new head, check walls/self, add head, remove tail (unless eating)

Before: head=[0,1] tail=[0,0]  move R
New head = [0,2]
Check: in bounds? not in body set?
Add [0,2] to front; remove [0,0] from back (if no food)

Solutions

Python

from collections import deque

class SnakeGame:
    def __init__(self, width, height, food):
        self.w = width
        self.h = height
        self.food = food
        self.fi = 0
        self.snake = deque([[0, 0]])
        self.body = {(0, 0)}
        self.dirs = {'U': (-1,0), 'D': (1,0), 'L': (0,-1), 'R': (0,1)}

    def move(self, direction: str) -> int:
        dr, dc = self.dirs[direction]
        r, c = self.snake[0]
        nr, nc = r + dr, c + dc
        if nr < 0 or nr >= self.h or nc < 0 or nc >= self.w:
            return -1
        tail = self.snake[-1]
        if self.fi < len(self.food) and [nr, nc] == self.food[self.fi]:
            self.fi += 1
        else:
            self.snake.pop()
            self.body.remove((tail[0], tail[1]))
        if (nr, nc) in self.body:
            return -1
        self.snake.appendleft([nr, nc])
        self.body.add((nr, nc))
        return self.fi

JavaScript

class SnakeGame {
    constructor(width, height, food) {
        this.w = width; this.h = height; this.food = food; this.fi = 0;
        this.snake = [[0, 0]];
        this.body = new Set(["0,0"]);
        this.dirs = {U:[-1,0], D:[1,0], L:[0,-1], R:[0,1]};
    }
    move(dir) {
        const [dr, dc] = this.dirs[dir];
        const [r, c] = this.snake[0];
        const [nr, nc] = [r+dr, c+dc];
        if (nr < 0 || nr >= this.h || nc < 0 || nc >= this.w) return -1;
        const tail = this.snake[this.snake.length - 1];
        if (this.fi < this.food.length && this.food[this.fi][0]===nr && this.food[this.fi][1]===nc) {
            this.fi++;
        } else {
            this.snake.pop();
            this.body.delete(tail[0]+","+tail[1]);
        }
        if (this.body.has(nr+","+nc)) return -1;
        this.snake.unshift([nr, nc]);
        this.body.add(nr+","+nc);
        return this.fi;
    }
}

Java

import java.util.*;
class SnakeGame {
    int w, h, fi = 0, score = 0;
    int[][] food;
    Deque<int[]> snake = new ArrayDeque<>();
    Set<String> body = new HashSet<>();
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    Map<String,Integer> dm = Map.of("U",0,"D",1,"L",2,"R",3);
    public SnakeGame(int width, int height, int[][] food) {
        w = width; h = height; this.food = food;
        snake.addFirst(new int[]{0,0}); body.add("0,0");
    }
    public int move(String dir) {
        int[] d = dirs[dm.get(dir)];
        int nr = snake.peekFirst()[0]+d[0], nc = snake.peekFirst()[1]+d[1];
        if (nr<0||nr>=h||nc<0||nc>=w) return -1;
        int[] tail = snake.peekLast();
        if (fi<food.length && food[fi][0]==nr && food[fi][1]==nc) { fi++; score++; }
        else { snake.pollLast(); body.remove(tail[0]+","+tail[1]); }
        if (body.contains(nr+","+nc)) return -1;
        snake.addFirst(new int[]{nr,nc}); body.add(nr+","+nc);
        return score;
    }
}

C++

#include <deque>
#include <set>
#include <vector>
#include <string>
using namespace std;
class SnakeGame {
    int w, h, fi=0;
    vector<vector<int>> food;
    deque<pair<int,int>> snake;
    set<pair<int,int>> body;
    map<string,pair<int,int>> dirs = {{"U",{-1,0}},{"D",{1,0}},{"L",{0,-1}},{"R",{0,1}}};
public:
    SnakeGame(int width, int height, vector<vector<int>>& food): w(width),h(height),food(food) {
        snake.push_front({0,0}); body.insert({0,0});
    }
    int move(string dir) {
        auto [dr,dc] = dirs[dir];
        auto [r,c] = snake.front();
        int nr=r+dr, nc=c+dc;
        if (nr<0||nr>=h||nc<0||nc>=w) return -1;
        auto tail = snake.back();
        if (fi<(int)food.size()&&food[fi][0]==nr&&food[fi][1]==nc) fi++;
        else { snake.pop_back(); body.erase(tail); }
        if (body.count({nr,nc})) return -1;
        snake.push_front({nr,nc}); body.insert({nr,nc});
        return fi;
    }
};

C

/* C: circular buffer for snake positions, 2D visited array for body */

Complexity

Operation	Time	Space
move	O(1)	O(N)