Snake Game with O(1) Movement

Problem Design the classic Snake game: the snake advances one cell per tick on a bounded grid, grows when it eats food, and the game ends on collision with a wall or with its own body. Advancing the snake must be O(1) regardless of its length.

Requirements

• move(direction) -> GameState — advance one step; returns RUNNING or GAME_OVER
• isSelfCollision(cell) -> bool in O(1)
• spawnFood() — place food on a free cell
• getScore() -> int and getBody() -> List<Cell> for rendering
• No operation may scan the snake body linearly

Areas to design

• The data structures that make both sliding and self-collision O(1).
• The growth-on-eat rule, and the legal "move into the vacating tail" case.
• Input buffering per tick, food spawning on a nearly full board, and the memory trade-off.