Counterweight rig

A theatre fly system carries its load on two arbors, and the rope brake only has to hold what they differ by. Every sandbag has to hang somewhere.

The problem

The crew is loading a counterweight rig. A pile of sandbags of known weight has to go up, and there are two arbors to hang them on: the working arbor and the balance arbor. No bag stays on the floor — each one goes on one arbor or the other.

The brake then holds the difference between the two arbors. A lopsided rig runs away when the brake is released, so the crew wants the split with the smallest difference. Which bags go where does not matter.

Input. sandbags — a list of integers, the weight of each bag in kilograms.

Output. The smallest difference between the two arbors that any assignment of every bag can produce.

Example.

sandbags = [4, 9, 6, 2]   ->  1

The bags weigh 21. Hang 9 and 2 for 11, and 4 and 6 for 10: the brake holds 1. An odd total never splits evenly, so 1 is the floor here.

A second example, which the obvious greedy gets wrong:

sandbags = [8, 7, 6, 5, 4]   ->  0

Loading heaviest first onto whichever arbor is lighter gives 8 against 7, then 8 against 13, then 13 against 13, then 17 against 13 — off by 4. The even split of 8 + 7 against 6 + 5 + 4 exists, and that greedy never looks at it.

Constraints.

• 0 <= len(sandbags) <= 40
• 1 <= sandbags[i] <= 250
• An empty pile is already balanced, so the answer is 0.

Hints

Approach

Brute force

Assign each bag to an arbor and measure: two choices per bag, so 2^40 assignments for the largest pile, around 10^12 splits.

The insight

The difference is total - 2 x (the lighter arbor), so the only question is which loads at or below half the total a set of bags can reach.

Every bag is placed, so the two arbors always sum to total; naming one names the other. A two-sided balancing act becomes a one-sided search for the largest reachable load that does not cross the midpoint. Reachability is what a subset sum row answers, and the row only runs to total // 2 — at most 5000 cells.

Algorithm

1. Take total = sum(sandbags) and half = total // 2.
2. Keep reach, booleans over 0..half, with reach[0] = True.
3. For each weight w, walk load from half down to w, setting reach[load] when reach[load - w] is already set.
4. Counting down keeps a bag from being hung twice: the cell you read still belongs to the previous pass.
5. Let best be the largest reachable load <= half.
6. The answer is total - 2 * best.

Complexity

Time O(n x total) — 40 bags across 5001 cells is about 200,000 updates. Space O(total) — one row of booleans, reused for every bag.

Solution

"""Counterweight rig — subset sum over half the load to close the imbalance."""


def reachable_loads(sandbags, cap):
    """reach[w] is True when some set of the bags weighs exactly w."""
    reach = [False] * (cap + 1)
    reach[0] = True
    for weight in sandbags:
        # Counting down keeps a bag out of its own row: one bag, one use.
        for load in range(cap, weight - 1, -1):
            if reach[load - weight]:
                reach[load] = True
    return reach


def solve(sandbags):
    total = sum(sandbags)
    half = total // 2
    reach = reachable_loads(sandbags, half)
    # invariant: the light arbor carries `best`, the heavy one total - best,
    # so the largest reachable load at or below the midpoint is the best split.
    best = max(load for load in range(half + 1) if reach[load])
    return total - 2 * best

TESTS = [
    (([4, 9, 6, 2],), 1),
    (([8, 7, 6, 5, 4],), 0),
    (([12, 5, 5, 2],), 0),
    (([31, 26, 33, 21, 40],), 5),
    (([8],), 8),
    (([],), 0),
    (([6, 6, 6, 6],), 0),
    (([1, 1, 1],), 1),
]

Pitfalls

• Walking the inner loop upward hangs a bag twice. A 6 kg bag sets reach[6], then load = 12 reads that same fresh cell and marks 12 reachable off one bag. Count down from half.
• Trusting heaviest-first onto the lighter arbor. On [8, 7, 6, 5, 4] it reports 4 when the rig balances exactly.
• Dropping the empty pile. With no bags half is 0, and only the seeded reach[0] keeps the search for best from running over nothing and raising.

Variants

• The clean round bonus — the same single-pass table, holding counts of arrangements instead of reachability.
• The knapsack family — where the descending inner loop comes from, and what changes when a bag may be used twice.