Solving the Fake Coin problem in Python

By John Lekberg on June 20, 2020.

This week's post is about solving the "Fake Coin" problem. You will learn:

How to create a brute force solution.
How to efficiently reduce the number of comparisons by comparing many coins at once.

Problem statement

There are n identical coins. One coin is fake and weighs less than the real coins. The only way to compare coins is a balance scale.

Your goal is to identify the fake coin.

How I represent the data

When I use the balance scale, the result is either that the scale is balanced, or that one side is heavier. I represent this result using an Enum:

import enum

Scale = enum.Enum(
    "Scale", ["LeftHeavy", "RightHeavy", "Balanced"]
)

I represent the coins using numbers. Since the fake coin weighs less, I use a smaller number for the fake coin:

coin_real = 2
coin_fake = 1

(The specific numbers I chose don't matter, as long as coin_fake < coin_real.)

To create a ranom set of n coins, I have a function that creates a list of coins, then shuffles it:

import random


def random_coins(n):
    """A shuffled list of (n-1) real coins and 1 fake coin."""
    assert n > 0
    coins = [coin_real] * (n - 1) + [coin_fake] * (1)
    random.shuffle(coins)
    return coins

random_coins(10)

[2, 2, 1, 2, 2, 2, 2, 2, 2, 2]

To compare the coins in the balance scale, I have a comparison function that sums the weight of both sides and compares the sums:

def compare(left, right):
    """Weight two collections of coins and return the
    result (a Scale enum).
    """
    delta = sum(right) - sum(left)
    if delta < 0:
        return Scale.LeftHeavy
    elif delta > 0:
        return Scale.RightHeavy
    else:
        return Scale.Balanced

compare([coin_fake], [coin_real])

<Scale.RightHeavy: 2>

Creating a brute force solution

A simple brute force solution will take one coin and compare it to every other coin:

If the scale is balanced, then move onto the next coin.
If the scale is unbalanced, return the lighter coin.

Here's a Python function that implements this:

def find_fake_coin_bf(*, coins, compare):
    """Find the fake coin by using brute force."""
    if len(coins) == 1:
        return coins[0]

    [first, *rest] = coins
    for coin in rest:
        result = compare([first], [coin])
        if result == Scale.LeftHeavy:
            return coin
        elif result == Scale.RightHeavy:
            return first
        elif result == Scale.Balanced:
            pass

    raise RuntimeError("No fake coin found.")

I test this function by generating different sets of random coins and checking that the correct coin is returned:

test_pass = 0
test_fail = 0

for _ in range(100):
    coins = random_coins(20)
    found = find_fake_coin_bf(coins=coins, compare=compare)
    if found == coin_fake:
        test_pass += 1
    else:
        test_fail += 1

print("tests passed:", test_pass)
print("tests failed:", test_fail)

tests passed: 100
tests failed: 0

What's the time complexity of this solution in terms of the number of comparisons? For a collection of n coins,

I make at most n-1 comparisons on the scale.

As a result, the overall time complexity of the function is

O(n) comparisons

Creating a solution that uses less comparisons

Instead of comparing two coins at a time (one in each pan of the balance scale), what if I compared more?

If I have n coins, then I can have two equal piles of ⌊n/2⌋ coins (with some coins leftover).

Here's an algorithm that compares as many coins as possible at once. Starting with n coins:

If there is one coin left, then it is the fake coin.
Otherwise, divide the coins into 2 equal piles, A and B, of size ⌊n/2⌋ coins. Put the remaining n-2⌊n/2⌋ coins into a separate pile, C.
Compare A and B in the balance scale.
- If A is lighter, keep A and discard B and C. Then repeat this process with just pile A.
- If B is lighter, keep B and discard A and C. Then repeat this process with just pile B.
- If the scale is balanced, keep C and discard A and B. Then repeat this process with just pile C.

Here's a Python function that implements this algorithm:

def find_fake_coin_fast(*, coins, compare):
    """Find the fake coin quickly by comparing as
    many coins as possible at once.
    """
    pile = list(coins)
    while len(pile) > 1:
        n = len(pile) // 2
        A = pile[:n]
        B = pile[n : 2 * n]

        result = compare(A, B)
        if result == Scale.LeftHeavy:
            pile = B
        elif result == Scale.RightHeavy:
            pile = A
        elif result == Scale.Balanced:
            C = pile[2 * n :]
            pile = C

    return pile[0]

I test this function by generating different sets of random coins and checking that the correct coin is returned:

test_pass = 0
test_fail = 0

for _ in range(100):
    coins = random_coins(20)
    found = find_fake_coin_fast(
        coins=coins, compare=compare
    )
    if found == coin_fake:
        test_pass += 1
    else:
        test_fail += 1

print("tests passed:", test_pass)
print("tests failed:", test_fail)

tests passed: 100
tests failed: 0

What's the time complexity of this solution in terms of the number of comparisons? For a collection of n coins:

If n=1, then I have the fake coin. This takes O(1) comparisons.
Otherwise, I create three piles, A, B, C, of sizes ⌊n/2⌋ and n-2⌊n/2⌋. This means that

max(#A, #B, #C) ≤ n/2

So, each comparison I make reduces the pile size by (at least) a factor of 2.

As a result, the overall time complexity of the algorithm is

O(log n) comparisons

In conclusion...

In this week's post, you learned how to solve the "Fake Coin" problem using a brute force algorithm. You also learned how to efficiently reduce the pile size by comparing as many coins as possible at once.

My challenge to you:

Modify the algorithm to create piles of size roughly n/3 (instead of n/2). Does this improve the expected number of comparisons to find the fake coin?

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!

(If you spot any errors or typos on this post, contact me via my contact page.)