Wax pours

A candle studio has a bench of leftover wax blocks and a row of identical moulds. Either the blocks fill every mould to the same line, or they do not.

The problem

Each block has a whole-gram weight and must go into exactly one mould — blocks are not cut, remelted or shared. There are moulds moulds on the bench, all the same size, and the studio wants every mould to end up holding the same total weight, with no block left over.

Report whether that is possible. Not how, not how many ways — just whether the bench of blocks can be split into moulds groups of equal weight, every block used.

Input. blocks — a list of integers, the weight in grams of each leftover block. moulds — an integer, how many moulds must be filled.

Output. True if the blocks split into moulds groups of equal total weight, False otherwise.

Example.

blocks = [6, 2, 4, 5, 3, 4], moulds = 3   ->  True

The bench weighs 24 g, so each mould needs 8 g: 6+2, 4+4, 5+3.

A second example, where the arithmetic works but the blocks do not:

blocks = [6, 2, 4, 5, 3, 4], moulds = 4   ->  False

24 divides by 4, so each mould would need 6 g. The 6 g block fills one and 2+4 fills another, but 5, 3 and 4 are left and no group of them weighs 6. Divisibility is necessary and not sufficient.

Constraints.

• 1 <= len(blocks) <= 16
• 1 <= blocks[i] <= 10^4
• 1 <= moulds <= 16

Hints

Approach

Brute force

Assign every block to one of the moulds and check the totals: moulds^n assignments, which for 16 blocks and 4 moulds is 4·10⁹ — and it re-explores the same used-sets over and over through different orderings.

The insight

Pour into one mould at a time, and the whole history collapses to a bitmask: the fill level of the open mould is (weight of the used set) mod target.

If you always finish the open mould before starting the next, the poured blocks have a total of used_weight, and that weight is k full moulds plus whatever sits in the open one. So used_weight % target is the open level — it does not matter which blocks went where, only which are gone. That collapses the moulds^n orderings into 2ⁿ states, and reaching the full mask means the last mould closed exactly.

Algorithm

1. If the bench total is not divisible by moulds, return False.
2. Set target = total // moulds. If any block is heavier than target, return False.
3. Precompute weight[mask], the total weight of each used-set.
4. Mark mask 0 reachable. Walk masks in increasing order.
5. For a reachable mask, the open mould holds weight[mask] % target. For each unused block that fits in the space left, mark the extended mask reachable.
6. Return whether the full mask is reachable.

Complexity

Time O(2ⁿ · n) — one pass per mask, one attempt per unused block, about a million steps at n = 16. Space O(2ⁿ) for the reachability and weight tables.

Solution

"""Wax pours — bitmask DP over the set of blocks already poured."""


def subset_weights(blocks):
    """weight[mask] = total grams of the blocks selected by mask."""
    weight = [0] * (1 << len(blocks))
    for mask in range(1, 1 << len(blocks)):
        low = mask & -mask                    # lowest set bit
        weight[mask] = weight[mask ^ low] + blocks[low.bit_length() - 1]
    return weight


def solve(blocks, moulds):
    total = sum(blocks)
    if moulds <= 0 or total % moulds:
        return False
    target = total // moulds
    if any(block > target for block in blocks):
        return False

    n = len(blocks)
    weight = subset_weights(blocks)
    reachable = [False] * (1 << n)
    reachable[0] = True

    for mask in range(1 << n):
        if not reachable[mask]:
            continue
        # Moulds are sealed in order, so the open one holds exactly this much:
        # everything poured so far, minus the whole moulds already closed.
        open_level = weight[mask] % target
        for i, block in enumerate(blocks):
            if mask >> i & 1:
                continue
            if open_level + block <= target:  # never let a mould overflow
                reachable[mask | 1 << i] = True

    return reachable[(1 << n) - 1]

TESTS = [
    (([6, 2, 4, 5, 3, 4], 3), True),
    (([6, 2, 4, 5, 3, 4], 4), False),
    (([6, 2, 4, 5, 3, 4], 1), True),
    (([7, 7, 7, 7], 4), True),
    (([9, 1, 1, 1], 2), False),      # 12 splits evenly, but 9 > the 6 g target
    (([5, 5, 5], 5), False),         # more moulds than blocks
    (([4], 1), True),
    (([10000] * 16, 8), True),
]

Pitfalls

• Trying to track "how full is each mould" as the state. That multiplies the state space by the ordering of the moulds and blows past any memory budget; the moulds are identical, so only the used-set matters.
• Skipping the block > target check. Nothing in the mask walk rejects an over-heavy block early, so you spend the full 2ⁿ scan to return False on an input a single comparison settles.
• Not fitting the block into the space left. Allowing open + block > target lets a mould overflow into the next, and the mask still reaches the end — [9, 1, 1, 1] with two moulds would report True.

Variants

• Teeth on the wheels — also splits a total into parts, but the parts are free and you maximise their product rather than forcing them equal.
• Linear DP — the one-index version of the same idea: choose a state that makes the future independent of how you got there.