Coin balance

How to solve the coin balance puzzle programmatically.

puzzles
Author

A. Coady

Published

June 7, 2020

How to solve the coin balance puzzle programmatically.

Given a balance and a set of coins, which are all equal in weight except for one, determine which coin is of different weight in as few weighings as possible.

Twelve-coin problem

A more complex version has twelve coins, eleven or twelve of which are identical. If one is different, we don’t know whether it is heavier or lighter than the others. This time the balance may be used three times to determine if there is a unique coin—and if there is, to isolate it and determine its weight relative to the others. (This puzzle and its solution first appeared in an article in 1945.[2]) The problem has a simpler variant with three coins in two weighings, and a more complex variant with 39 coins in four weighings.

First to model the data:

  • An enum to represent different weights. Following the ternary comparison convention, such as Python 2’s cmp, is convenient.
  • An object to represent the balance. For testing, it will need to be configurable with the target coin and relative weight.
  • An object to represent a coin and its state. A class is tempting, but the most useful data structure would keep the coins grouped by their known (or unknown) state anyway. So any hashable unique identifier is sufficient.
import enum

class Weight(enum.IntEnum):
    LIGHT = -1
    EVEN = 0
    HEAVY = 1

class Balance:
    def __init__(self, coin, weight: Weight):
        self.coin = coin
        self.weight = weight

    def weigh(self, left: set, right: set):
        """Return relative Weight of left side to right side."""
        assert len(left) == len(right)
        if self.coin in left:
            return self.weight
        if self.coin in right:
            return Weight(-self.weight)
        return Weight.EVEN

coins = 'abcdefghijkl'
assert len(coins) == 12
balance = Balance('a', Weight.LIGHT)
assert balance.weigh('a', 'b') == Weight.LIGHT
assert balance.weigh('b', 'c') == Weight.EVEN
assert balance.weigh('b', 'a') == Weight.HEAVY

As is typical with induction puzzles, the constants chosen are just large enough to thwart an iterative approach. The 2 weighing variation would be trivial enough for most people to brute force the solution. Whereas 4 weighings would already be such a large decision tree, it would be tedious to even output. The easier approach is solve the puzzle recursively and more generally, for any number of coins and weighings.

So what can be done in a single weighing? Clearly all weighings must have an equal number of coins on each side, else nothing is learned. If it balances, then the different coin is in the unweighed group. If it doesn’t balance, then the different coin is in the weighed group, but additionally it is known whether each coin would be heavy or light based on which side it was on. This is the crucial insight: there’s a variant recursive puzzle embedded inside this puzzle.

The Towers of Hanoi is a classic puzzle often used in computer science curricula to teach recursion. This one would suitable as a subsequent more advanced problem.

So what can be done with known coins in a single weighing? If it balances, then as before the different coin is in the unweighed group. But if it doesn’t balance, then which way can be used to further narrow the coins. Consider the heavier side; the different coin must be one of the heavy ones on that side, or one of the light ones on the other side. Therefore the coins can be split into 2 equal sized groups by putting equal numbers of heavy coins on each side, and equal numbers of light coins on each side. One obstacle is that if there aren’t an even number, there will need to be filler coins just to balance. But that won’t be a problem after the first weighing.

Now we can implement a solution to the sub-problem, and build the need for filler coins into the balance implementation. A generator is used so that the output of each weighing can be displayed.

import itertools

class Balance:
    def __init__(self, coin, weight: Weight):
        self.coin = coin
        self.weight = weight
        self.filler = set()

    def weigh(self, left: set, right: set):
        """Return relative Weight of left side to right side."""
        assert abs(len(left) - len(right)) <= len(self.filler)
        if self.coin in left:
            return self.weight
        if self.coin in right:
            return Weight(-self.weight)
        return Weight.EVEN

    def find(self, light: set, heavy: set):
        """Recursively find target coin from sets of potentially light and heavy coins."""
        yield light, heavy
        union = light | heavy
        if len(union) <= 1:
            return
        left, right = set(), set()
        # split into 3 groups
        for start, third in enumerate([left, right]):
            for group in (light, heavy):
                third.update(itertools.islice(group, start, None, 3))
        weight = self.weigh(left, right)
        if weight < 0:
            light, heavy = (light & left), (heavy & right)
        elif weight > 0:
            light, heavy = (light & right), (heavy & left)
        else:
            light, heavy = (light - left - right), (heavy - left - right)
        self.filler.update(union - light - heavy)
        yield from self.find(light, heavy)

balance = Balance('a', Weight.LIGHT)
for light, heavy in balance.find(set('abc'), set('def')):
    print(''.join(light), ''.join(heavy))
cba dfe
a e
a

Now with the sub-problem solved, there’s just one thing missing for the main puzzle. In the known case, splitting into 3 equal sized groups is cleary optimal. But in the unknown case, we need to know how many coins to exclude from the weighing. This requires computing how many coins can be handled in the subsolution. Luckily it’s a trivial recurrence relation: n weighings can solve 3 times the number of n - 1 weighings. \[ \prod_{}^n 3 = 3^n \]

class Balance(Balance):
    def solve(self, count: int, coins):
        """Recursively find target coin."""
        if count <= 0:
            return
        weigh = set(itertools.islice(coins, 3 ** (count - 1) - (not self.filler)))
        exclude = set(coins) - weigh
        left, right = (set(itertools.islice(weigh, start, None, 2)) for start in range(2))
        weight = self.weigh(left, right)
        self.filler.update(exclude if weight else weigh)
        if weight < 0:
            yield from self.find(left, right)
        elif weight > 0:
            yield from self.find(right, left)
        else:
            yield from self.solve(count - 1, exclude)

balance = Balance('a', Weight.LIGHT)
for light, heavy in balance.solve(3, coins):
    print(''.join(light), ''.join(heavy))

for coin in coins:
    light, heavy =  list(Balance(coin, Weight.LIGHT).solve(3, coins))[-1]
    assert light == {coin} and not heavy
    light, heavy =  list(Balance(coin, Weight.HEAVY).solve(3, coins))[-1]
    assert not light and heavy == {coin}
dbah fceg
a e
a

The puzzle is solved. There’s one last simplifcation that can be made, but requires a bit more math background. Ideally we wouldn’t need to know the objective number of weighings; the algorithm would just solve any set of coins as efficiently as possible. To do that, the number of coins that can be solved has to be computed. As was done above, but this recurrence relation is more advanced: each weighing can solve 3 ^ n more coins. \[ \sum_{k=0}^{n-1} 3^k = (3^n - 1) / 2 \]

With that calculation inverted, the count can be removed from the interface

import math

class Balance(Balance):
    def solve(self, coins):
        if not coins:
            return
        count = math.ceil(math.log(len(coins) * 2 + 1, 3))
        weigh = set(itertools.islice(coins, 3 ** (count - 1) - (not self.filler)))
        exclude = set(coins) - weigh
        left, right = (set(itertools.islice(weigh, start, None, 2)) for start in range(2))
        weight = self.weigh(left, right)
        self.filler.update(exclude if weight else weigh)
        if weight < 0:
            yield from self.find(left, right)
        elif weight > 0:
            yield from self.find(right, left)
        else:
            yield from self.solve(exclude)

balance = Balance('a', Weight.LIGHT)
for light, heavy in balance.solve(coins):
    print(''.join(light), ''.join(heavy))
dbah fceg
a e
a

Notice the formula indicates it’s possible to do 13 coins in 3 weighings, and it would be with a filler coin to balance out the 9 that need weighing.