Squirrel Simulation

medium math simulation

Problem

A squirrel at (sx, sy) needs to fetch all nuts and drop each at a tree at (tx, ty). It can only carry one at a time. Minimize total distance.

Inputh=5 w=7 tree=[2,2] squirrel=[4,4] nuts=[[3,0],[2,5]]

Output12

Total = 2·sum(2·dist(tree,nut)) − max gain by starting at the nearest nut to the squirrel.

input

def min_distance(h, w, tree, squirrel, nuts):
    def d(a, b): return abs(a[0]-b[0]) + abs(a[1]-b[1])
    base = sum(2 * d(tree, n) for n in nuts)
    return base + min(d(squirrel, n) - d(tree, n) for n in nuts)

function minDistance(h, w, tree, squirrel, nuts) {
  const d = (a, b) => Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
  const base = nuts.reduce((s, n) => s + 2*d(tree, n), 0);
  return base + Math.min(...nuts.map(n => d(squirrel, n) - d(tree, n)));
}

int minDistance(int h, int w, int[] tree, int[] squirrel, int[][] nuts) {
    int base = 0, best = Integer.MAX_VALUE;
    for (int[] n : nuts) {
        int dt = Math.abs(tree[0]-n[0]) + Math.abs(tree[1]-n[1]);
        int ds = Math.abs(squirrel[0]-n[0]) + Math.abs(squirrel[1]-n[1]);
        base += 2 * dt;
        best = Math.min(best, ds - dt);
    }
    return base + best;
}

int minDistance(int h, int w, vector& tree, vector& squirrel, vector>& nuts) {
    int base = 0, best = INT_MAX;
    for (auto& n : nuts) {
        int dt = abs(tree[0]-n[0]) + abs(tree[1]-n[1]);
        int ds = abs(squirrel[0]-n[0]) + abs(squirrel[1]-n[1]);
        base += 2 * dt; best = min(best, ds - dt);
    }
    return base + best;
}

Explanation

The squirrel carries one nut at a time, so after the very first trip it always travels tree → nut → tree for each remaining nut. The whole problem reduces to: which nut should it grab first?

If we imagine starting at the tree for every nut, the cost is a fixed baseline: 2 · dist(tree, nut) summed over all nuts. But the squirrel doesn't start at the tree — it starts at (sx, sy). For the first nut, the trip is dist(squirrel, nut) + dist(tree, nut) instead of 2 · dist(tree, nut).

That swap changes the total by dist(squirrel, nut) - dist(tree, nut). To minimize total distance we pick the nut where this difference is smallest (most negative), so the answer is base + min over nuts of (dist(squirrel, nut) - dist(tree, nut)). All distances are Manhattan (|dx| + |dy|).

Example: tree (2,2), squirrel (4,4), nuts (3,0) and (2,5). Each nut is distance 3 from the tree, so base = 2·(3+3) = 12. The deltas are 5-3 = 2 and 3-3 = 0; the smallest is 0, so the answer is 12 + 0 = 12.

This works because only the first nut's trip differs from the tree-based baseline, so we just choose the most rewarding nut to fetch first.

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