# LeetCode 353: Design Snake Game

## Problem Restatement

We need to implement a simplified Snake game.

The screen has size:

```python
height x width
```

The snake starts at the top-left cell:

```python
(0, 0)
```

Its initial length is `1`.

We are given a list of food positions. Food appears one at a time. The second food appears only after the snake eats the first food.

Each call to `move(direction)` moves the snake one cell in one of four directions:

```text
"U" = up
"D" = down
"L" = left
"R" = right
```

After a move:

| Situation | Result |
|---|---|
| Snake hits a wall | Return `-1` |
| Snake hits its own body | Return `-1` |
| Snake eats food | Score increases by `1`, snake length increases by `1` |
| Normal move | Score stays the same |

The method returns the current score after a valid move.

The problem statement specifies the constructor as `SnakeGame(int width, int height, int[][] food)` and the move method as `int move(String direction)`. The snake starts at `(0, 0)`, food positions are given as row-column pairs, and game over happens when the snake goes out of bounds or its head occupies a body cell after moving.

## Input and Output

| Method | Meaning |
|---|---|
| `SnakeGame(width, height, food)` | Initializes the game |
| `move(direction)` | Moves the snake once and returns the score or `-1` |

The food array looks like this:

```python
food = [[1, 2], [0, 1]]
```

That means:

| Food index | Position |
|---|---|
| `0` | `(1, 2)` |
| `1` | `(0, 1)` |

Only the current food is active.

## Examples

Example input:

```python
snakeGame = SnakeGame(3, 2, [[1, 2], [0, 1]])
```

The board has:

```text
height = 2
width = 3
```

So valid rows are:

```text
0, 1
```

Valid columns are:

```text
0, 1, 2
```

The snake starts at:

```python
(0, 0)
```

Now run the moves:

```python
snakeGame.move("R")  # 0
snakeGame.move("D")  # 0
snakeGame.move("R")  # 1
snakeGame.move("U")  # 1
snakeGame.move("L")  # 2
snakeGame.move("U")  # -1
```

Step by step:

| Move | New head | Result |
|---|---:|---|
| `R` | `(0, 1)` | Valid, score `0` |
| `D` | `(1, 1)` | Valid, score `0` |
| `R` | `(1, 2)` | Eats first food, score `1` |
| `U` | `(0, 2)` | Valid, score `1` |
| `L` | `(0, 1)` | Eats second food, score `2` |
| `U` | `(-1, 1)` | Hits wall, return `-1` |

## First Thought: Store the Whole Board

One direct design is to keep a full `height x width` grid.

Each cell could store whether it is empty, occupied by the snake, or contains food.

That works, but the board can be large, and we do not need to inspect every cell.

Each move only changes two places:

1. A new head cell is added.
2. The old tail cell is removed, unless food is eaten.

So we only need to track the snake body.

## Key Insight

The snake body needs two operations:

| Need | Data structure |
|---|---|
| Remove the tail quickly | Deque |
| Add the new head quickly | Deque |
| Check whether a cell is occupied quickly | Hash set |

The deque stores the snake body in order.

We will store the head at the left side and the tail at the right side:

```text
head ... tail
```

For example:

```python
deque([(0, 2), (0, 1), (0, 0)])
```

The occupied set stores the same cells for `O(1)` lookup:

```python
{(0, 2), (0, 1), (0, 0)}
```

The subtle part is self-collision.

Before checking whether the new head collides with the body, we should remove the tail if the snake is not eating food.

Why?

Because moving into the current tail cell is allowed if the tail moves away during the same step.

## Algorithm

Maintain:

| Variable | Meaning |
|---|---|
| `body` | Deque of snake cells, head first |
| `occupied` | Set of cells currently occupied by the snake |
| `food_index` | Index of the next food to eat |
| `score` | Number of food pieces eaten |

For each move:

1. Read the current head.
2. Compute the next head using the direction.
3. Check wall collision.
4. Check whether the next head is the current food.
5. If the snake does not eat food, remove the tail from both `body` and `occupied`.
6. Check whether the next head is already occupied.
7. If occupied, return `-1`.
8. Add the new head to both `body` and `occupied`.
9. If food was eaten, advance `food_index` and increase `score`.
10. Return `score`.

## Correctness

The deque always stores the snake body in head-to-tail order.

At initialization, the snake contains only `(0, 0)`, so the deque and occupied set are correct.

For each valid move, the algorithm computes exactly one new head cell from the given direction. If that cell is outside the grid, the snake has hit a wall, so returning `-1` is correct.

If the new head reaches the active food, the snake grows. The algorithm keeps the old tail, adds the new head, and increments the score. This increases the body length by one, matching the game rule.

If the new head does not reach food, the snake keeps the same length. The algorithm removes the old tail and then adds the new head. This models the body shifting forward by one cell.

The occupied set is updated together with the deque. Therefore, after removing the tail when needed, `occupied` represents exactly the cells that remain occupied before the new head is inserted.

The self-collision check then tests whether the new head occupies a remaining body cell. If it does, the game is over. If it does not, adding the new head produces the correct next snake state.

Therefore each move returns the correct score for valid moves and `-1` for invalid moves.

## Complexity

Let `L` be the current snake length.

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(1)` besides storing input food | `O(1)` extra |
| `move` | `O(1)` | `O(1)` extra |
| Stored snake state | `O(L)` | `O(L)` |

Each move performs constant-time deque and set operations.

## Implementation

```python
from collections import deque

class SnakeGame:

    def __init__(self, width: int, height: int, food: list[list[int]]):
        self.width = width
        self.height = height
        self.food = food
        self.food_index = 0
        self.score = 0

        self.body = deque([(0, 0)])
        self.occupied = {(0, 0)}

        self.delta = {
            "U": (-1, 0),
            "D": (1, 0),
            "L": (0, -1),
            "R": (0, 1),
        }

    def move(self, direction: str) -> int:
        head_row, head_col = self.body[0]
        row_delta, col_delta = self.delta[direction]

        next_head = (
            head_row + row_delta,
            head_col + col_delta,
        )

        next_row, next_col = next_head

        if (
            next_row < 0
            or next_row >= self.height
            or next_col < 0
            or next_col >= self.width
        ):
            return -1

        eats_food = (
            self.food_index < len(self.food)
            and self.food[self.food_index] == [next_row, next_col]
        )

        if not eats_food:
            tail = self.body.pop()
            self.occupied.remove(tail)

        if next_head in self.occupied:
            return -1

        self.body.appendleft(next_head)
        self.occupied.add(next_head)

        if eats_food:
            self.food_index += 1
            self.score += 1

        return self.score
```

## Code Explanation

The snake body is initialized with one cell:

```python
self.body = deque([(0, 0)])
self.occupied = {(0, 0)}
```

The deque lets us add a head and remove a tail in constant time.

The set lets us check body collision in constant time.

Directions are stored as row and column changes:

```python
self.delta = {
    "U": (-1, 0),
    "D": (1, 0),
    "L": (0, -1),
    "R": (0, 1),
}
```

For every move, we compute the new head:

```python
head_row, head_col = self.body[0]
row_delta, col_delta = self.delta[direction]

next_head = (
    head_row + row_delta,
    head_col + col_delta,
)
```

Then we check whether it goes outside the board:

```python
if (
    next_row < 0
    or next_row >= self.height
    or next_col < 0
    or next_col >= self.width
):
    return -1
```

Food is eaten only if the new head reaches the currently active food:

```python
eats_food = (
    self.food_index < len(self.food)
    and self.food[self.food_index] == [next_row, next_col]
)
```

If no food is eaten, the snake length should stay the same. So the old tail leaves the board:

```python
if not eats_food:
    tail = self.body.pop()
    self.occupied.remove(tail)
```

This happens before the self-collision check because moving into the old tail position is allowed when the tail moves away.

Then we check self-collision:

```python
if next_head in self.occupied:
    return -1
```

If the move is valid, insert the new head:

```python
self.body.appendleft(next_head)
self.occupied.add(next_head)
```

If food was eaten, update score and advance to the next food:

```python
if eats_food:
    self.food_index += 1
    self.score += 1
```

## Testing

```python
def run_tests():
    game = SnakeGame(3, 2, [[1, 2], [0, 1]])

    assert game.move("R") == 0
    assert game.move("D") == 0
    assert game.move("R") == 1
    assert game.move("U") == 1
    assert game.move("L") == 2
    assert game.move("U") == -1

    game = SnakeGame(2, 2, [])
    assert game.move("R") == 0
    assert game.move("D") == 0
    assert game.move("L") == 0
    assert game.move("U") == 0

    game = SnakeGame(3, 3, [[0, 1], [0, 2], [1, 2], [1, 1]])
    assert game.move("R") == 1
    assert game.move("R") == 2
    assert game.move("D") == 3
    assert game.move("L") == 4
    assert game.move("U") == -1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style example | Checks food, score, and wall collision |
| Empty food list | Checks normal movement without growth |
| Growth then collision | Checks self-collision after the body becomes longer |