Sluice doses

An irrigation canal feeds each field through a bank of sluice gates, and every gate releases a fixed dose. The warden wants the ration met exactly, with as few openings as possible.

The problem

The canal bank has a row of sluice gates. Each gate is calibrated: opening it runs for a set dwell and releases exactly that many litres, given in gates. A gate may be opened as often as the warden likes, and the gates may be used in any combination — the doses simply add up.

A field is due a ration of exactly ration litres. Over-watering damages the crop, so the doses must total the ration precisely; there is no partial opening and no way to shut a gate early.

Report the fewest openings that hit the ration exactly, or -1 if no combination of doses reaches it.

Input. gates — a list of integers, the litres each gate releases per opening. ration — an integer, the litres owed.

Output. The fewest openings totalling exactly ration, or -1.

Example.

gates = [9, 6, 1], ration = 12   ->  2

Two openings of the 6-litre gate. Reaching for the biggest gate first gives 9 + 1 + 1 + 1, four openings — the large dose leaves a remainder that only the small gate can clear.

A second example, where the ration cannot be met:

gates = [5, 9], ration = 13   ->  -1

Five and nine build 5, 9, 10, 14, 15, 18 and so on, but never 13. The warden reports -1 rather than over-watering by a litre.

Constraints.

• 1 <= len(gates) <= 12
• 1 <= gates[i] <= 5000
• 0 <= ration <= 10^4

Hints

Approach

Brute force

Recurse: subtract one gate's dose and solve the rest, trying every gate at every step. With 12 gates and a 1-litre gate available, the tree is 12 to the power of 10000 paths, and the same remaining volume is re-solved down countless branches.

Greedy is the other tempting shortcut — take the biggest gate that fits, repeat — and it is simply wrong. The first example is the counterexample: greedy pays four openings where two will do.

The insight

The fewest openings for a volume depends only on the volume, never on which gates produced it, so one entry per litre from 0 up to the ration is the whole solution.

That independence is the precondition. Take an optimal plan for v and remove one opening of gate g from it: what remains is a plan for v - g, and it must itself be optimal, because a cheaper plan for v - g plus that one opening would beat the plan for v. So best[v] is 1 + min(best[v - g]) over the gates that fit, and reading only entries below v means a single upward pass finishes the table.

Unreachable volumes need a value that cannot be extended into a false answer: mark them infinite, so best[v - g] + 1 stays infinite and never wins a minimum.

Algorithm

1. Make best of length ration + 1, all infinite except best[0] = 0.
2. For each volume v from 1 to ration:
3. For each gate dose g that is at most v, consider best[v - g] + 1.
4. Keep the smallest as best[v].
5. Return best[ration], or -1 if it is still infinite.

Complexity

Time O(ration * len(gates)) — 120000 comparisons at the top of the range. Space O(ration) for the table; the gates themselves add nothing.

Solution

"""Sluice doses — fewest gate openings for an exact ration, filled volume by volume."""

UNREACHABLE = float("inf")


def solve(gates, ration):
    # Invariant: best[v] is the fewest openings totalling exactly v litres, and
    # it depends on v alone — never on which gates produced the earlier litres.
    best = [UNREACHABLE] * (ration + 1)
    best[0] = 0                       # nothing owed costs no openings
    for volume in range(1, ration + 1):
        for dose in gates:
            if dose <= volume and best[volume - dose] + 1 < best[volume]:
                best[volume] = best[volume - dose] + 1
    return -1 if best[ration] == UNREACHABLE else best[ration]

TESTS = [
    (([9, 6, 1], 12), 2),         # greedy largest-first would pay 4
    (([5, 9], 13), -1),
    (([7, 3], 24), 4),
    (([4], 0), 0),                # nothing owed, no openings
    (([5000], 5000), 1),          # the largest dose, met in one opening
    (([2, 4, 6], 7), -1),         # every dose is even, the ration is not
    (([1], 10000), 10000),        # top of the range, one litre at a time
]

Pitfalls

• Taking the largest gate that fits, repeatedly. On [9, 6, 1] with a 12-litre ration that costs 4 openings instead of 2. Greedy is only safe for dose sets with a special structure, and nothing here promises one.
• Filling the table with 0 instead of infinity. Every volume then reports 0 openings, and the unreachable 13 in the second example comes back as 0 rather than -1.
• Forgetting the zero ration. best[0] = 0 is both the base case and the answer when nothing is owed. Seeding it as infinite makes every entry unreachable; returning 1 for it invents an opening nobody made.
• Returning the sentinel. A leftover float("inf") reported as the answer is not -1, and a caller comparing it against an integer count will take it for a very expensive but valid plan.

Variants

• Terrace climbs — the same one-entry-per- position table, counting the arrangements instead of minimising a count.
• The knapsack family — where reusing a gate any number of times sits against the version that allows each item once.