# LeetCode 573: Squirrel Simulation

## Problem Restatement

We are given a garden grid with a tree, a squirrel, and several nuts.

The squirrel must collect all nuts and put them under the tree one by one.

The squirrel can carry at most one nut at a time. It can move one cell at a time in four directions: up, down, left, and right.

Return the minimum total distance the squirrel must move.

The problem gives `height`, `width`, `tree`, `squirrel`, and `nuts`. There is at least one nut, and the given positions do not overlap. The example `height = 5`, `width = 7`, `tree = [2,2]`, `squirrel = [4,4]`, `nuts = [[3,0], [2,5]]` has output `12`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Garden size, tree position, squirrel position, and nut positions |
| Output | Minimum total movement distance |
| Movement | One step up, down, left, or right |
| Carry rule | The squirrel can carry at most one nut |
| Goal | Move every nut to the tree |

Example function shape:

```python
def minDistance(
    height: int,
    width: int,
    tree: list[int],
    squirrel: list[int],
    nuts: list[list[int]],
) -> int:
    ...
```

## Examples

Example 1:

```python
height = 5
width = 7
tree = [2, 2]
squirrel = [4, 4]
nuts = [[3, 0], [2, 5]]
```

Distance from nut `[3, 0]` to the tree:

```python
abs(3 - 2) + abs(0 - 2) = 3
```

Distance from nut `[2, 5]` to the tree:

```python
abs(2 - 2) + abs(5 - 2) = 3
```

If the squirrel starts at the tree for every nut, the total would be:

```python
2 * 3 + 2 * 3 = 12
```

But the squirrel does not start at the tree. It starts at `[4, 4]`.

If it picks nut `[2, 5]` first:

```python
squirrel to nut = abs(4 - 2) + abs(4 - 5) = 3
nut to tree = 3
```

Then it returns to the tree and collects the other nut with a round trip:

```python
2 * 3 = 6
```

Total:

```python
3 + 3 + 6 = 12
```

So the answer is:

```python
12
```

Example 2:

```python
height = 1
width = 3
tree = [0, 1]
squirrel = [0, 0]
nuts = [[0, 2]]
```

There is one nut.

The squirrel goes from `[0, 0]` to `[0, 2]`, then from `[0, 2]` to the tree `[0, 1]`.

Total:

```python
2 + 1 = 3
```

So the answer is:

```python
3
```

## First Thought: Try Every Nut Order

A direct solution is to try every order in which the squirrel could collect the nuts.

For each order, simulate the movement and keep the smallest total distance.

This is correct, but it is too slow.

If there are `n` nuts, there are:

```python
n!
```

possible orders.

The constraints allow thousands of nuts in common formulations of the problem, so trying all orders is impossible.

## Key Insight

Only the first trip is special.

After the squirrel collects the first nut and drops it under the tree, the squirrel is at the tree.

From then on, every remaining nut costs:

```python
tree -> nut -> tree
```

So every remaining nut contributes:

```python
2 * distance(nut, tree)
```

The only decision is which nut to collect first.

For the first nut, the cost is:

```python
distance(squirrel, nut) + distance(nut, tree)
```

Instead of:

```python
2 * distance(nut, tree)
```

So compared with the baseline, choosing a nut first changes the total by:

```python
distance(squirrel, nut) - distance(nut, tree)
```

We want this adjustment to be as small as possible.

Equivalently, we want to maximize the saving:

```python
distance(nut, tree) - distance(squirrel, nut)
```

This is the standard linear solution: compute the total round-trip distance from the tree to every nut, then subtract the best first-trip saving.

## Manhattan Distance

Because the squirrel moves only in four directions, the shortest distance between two grid positions is Manhattan distance:

```python
abs(r1 - r2) + abs(c1 - c2)
```

For example:

```python
[4, 4] to [2, 5]
```

has distance:

```python
abs(4 - 2) + abs(4 - 5) = 3
```

## Algorithm

1. Define a helper function `dist(a, b)` for Manhattan distance.
2. Initialize:
   ```python id="zuijgv"
   total = 0
   best_saving = -infinity
   ```
3. For each nut:
   1. Compute `tree_dist = dist(nut, tree)`.
   2. Compute `squirrel_dist = dist(nut, squirrel)`.
   3. Add `2 * tree_dist` to `total`.
   4. Update:
      ```python id="mck6mn"
      best_saving = max(best_saving, tree_dist - squirrel_dist)
      ```
4. Return:
   ```python id="3gnkz7"
   total - best_saving
   ```

## Correctness

Assume the squirrel chooses some nut `x` first.

For this first nut, the squirrel moves from its starting position to `x`, then from `x` to the tree.

The cost is:

```python
dist(squirrel, x) + dist(x, tree)
```

After that, the squirrel is at the tree.

For every other nut `y`, the squirrel must go from the tree to `y`, then return from `y` to the tree. The cost is:

```python
2 * dist(y, tree)
```

So for a fixed first nut `x`, the total cost is:

```python
sum(2 * dist(nut, tree) for every nut)
- dist(x, tree)
+ dist(squirrel, x)
```

The first large sum is the same no matter which nut is chosen first.

Therefore, minimizing the total cost is equivalent to minimizing:

```python
dist(squirrel, x) - dist(x, tree)
```

or equivalently maximizing:

```python
dist(x, tree) - dist(squirrel, x)
```

The algorithm checks every nut as the possible first nut and chooses the maximum saving. Therefore, it returns the minimum possible total distance.

## Complexity

Let `n` be the number of nuts.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each nut is processed once |
| Space | `O(1)` | Only a few integer variables are stored |

## Implementation

```python
class Solution:
    def minDistance(
        self,
        height: int,
        width: int,
        tree: list[int],
        squirrel: list[int],
        nuts: list[list[int]],
    ) -> int:
        def dist(a: list[int], b: list[int]) -> int:
            return abs(a[0] - b[0]) + abs(a[1] - b[1])

        total = 0
        best_saving = float("-inf")

        for nut in nuts:
            tree_dist = dist(nut, tree)
            squirrel_dist = dist(nut, squirrel)

            total += 2 * tree_dist
            best_saving = max(best_saving, tree_dist - squirrel_dist)

        return total - best_saving
```

## Code Explanation

The helper function computes Manhattan distance:

```python
def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
```

For each nut, we first compute its normal round-trip cost from the tree:

```python
total += 2 * tree_dist
```

This assumes every trip starts at the tree.

Then we compute the saving if this nut is collected first:

```python
tree_dist - squirrel_dist
```

If this value is large, choosing this nut first saves more distance.

Finally:

```python
return total - best_saving
```

subtracts the best first-trip saving from the baseline total.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minDistance(
        5,
        7,
        [2, 2],
        [4, 4],
        [[3, 0], [2, 5]],
    ) == 12

    assert s.minDistance(
        1,
        3,
        [0, 1],
        [0, 0],
        [[0, 2]],
    ) == 3

    assert s.minDistance(
        3,
        3,
        [1, 1],
        [1, 1],
        [[0, 0], [2, 2]],
    ) == 8

    assert s.minDistance(
        4,
        4,
        [0, 0],
        [3, 3],
        [[0, 1], [3, 0]],
    ) == 10

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Main sample | Checks the best first nut choice |
| Single nut | Only one trip from squirrel to nut to tree |
| Squirrel starts at tree | No special starting advantage |
| Multiple nuts with different savings | Checks greedy first-nut selection |