<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P065-coin-change/ | updated: 2026-10-14 -->

# P065 Coin change

The fewest coins for an amount with any set of coin values, by dynamic programming, set against the greedy largest-coin-first way; how many different handfuls make the amount; and whether a coin set is one where greedy is always right, with the first amount where it is not.

EML-P project `projects/coin-change` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/coin-change` runs it and `eml project verify projects/coin-change` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: coin-change-dp (https://efficientnewlanguage.org/cases/082-coin-change-dp/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
1
0
10001
abc

4
3 3 7
0 5
1 2 3 4 5 6 7 8 9 10 11
5 7
1
3
1
24
3
4

4
4
3
5
```

Screen:

```text
== Coin change ==
The fewest coins for an amount, with any coin values - and when taking the largest coin first is wrong.
Coins: 1, 2, 5, 10, 20, 50, 100, 200 (euro cents).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 0
Pick a number from 1 to 5.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> x
Pick a number from 1 to 5.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 0
Type a whole amount from 1 to 10000.
amount (1 to 10000)> 10001
Type a whole amount from 1 to 10000.
amount (1 to 10000)> abc
Type a whole amount from 1 to 10000.
amount (1 to 10000)> 
Cancelled.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 4
coin values in any order (like 1 3 4)> 3 3 7
Type 1 to 10 different whole values from 1 to 1000.
coin values in any order (like 1 3 4)> 0 5
Type 1 to 10 different whole values from 1 to 1000.
coin values in any order (like 1 3 4)> 1 2 3 4 5 6 7 8 9 10 11
Type 1 to 10 different whole values from 1 to 1000.
coin values in any order (like 1 3 4)> 5 7
Coins: 5, 7.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 3
3 cannot be made from 5, 7.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 24
Fewest: 4 coins, 2 x 7 + 2 x 5.
Greedy gets stuck: after 3 x 7 no coin fits what is left.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 3
Greedy first goes wrong at 10: it gets stuck after 7, but 2 x 5 works.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 4
coin values in any order (like 1 3 4)> 
Cancelled.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 4
coin values in any order (like 1 3 4)> 4
Coins: 4.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 3
With one coin value there is nothing to choose.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 5
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
289
2
200
3
4
1 3 4
1
6
3
4
25 10 1
3
1
30
2
100
5
```

Screen:

```text
== Coin change ==
The fewest coins for an amount, with any coin values - and when taking the largest coin first is wrong.
Coins: 1, 2, 5, 10, 20, 50, 100, 200 (euro cents).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 289
Fewest: 7 coins, 200 + 50 + 20 + 10 + 5 + 2 x 2.
Greedy, largest first, finds the same number: 200 + 50 + 20 + 10 + 5 + 2 x 2.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 2
amount (1 to 10000)> 200
There are 73682 different ways to make 200 from 1, 2, 5, 10, 20, 50, 100, 200 (the order of the coins does not count).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 3
Greedy is always right for 1, 2, 5, 10, 20, 50, 100, 200: no amount below 300 beats it, and a set with a 1 that fails has its first failure below that bound.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 4
coin values in any order (like 1 3 4)> 1 3 4
Coins: 1, 3, 4.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 6
Fewest: 2 coins, 2 x 3.
Greedy, largest first, uses 3: 4 + 2 x 1 - 1 coin more than needed.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 3
Greedy first goes wrong at 6: 4 + 2 x 1 (3) instead of 2 x 3 (2).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 4
coin values in any order (like 1 3 4)> 25 10 1
Coins: 1, 10, 25.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 3
Greedy first goes wrong at 30: 25 + 5 x 1 (6) instead of 3 x 10 (3).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 1
amount (1 to 10000)> 30
Fewest: 3 coins, 3 x 10.
Greedy, largest first, uses 6: 25 + 5 x 1 - 3 coins more than needed.

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 2
amount (1 to 10000)> 100
There are 29 different ways to make 100 from 1, 10, 25 (the order of the coins does not count).

1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit
choice> 5
Bye.
```

## Modules

### main.eml

```eml
# P065 coin change: the fewest coins for an amount with any set of coin
# values, worked out by dynamic programming and set against the greedy
# "largest coin first" way; how many ways there are to make the amount; and
# whether a coin set is one where greedy is always right.
import coins

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def number(s):
    if s == "" or len(s) > 6:
        return -1
    0 => n
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n * 10 + int(c) => n
    return n

def words(s):
    [] => out
    "" => word
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out + [word] => out
            "" => word
        else:
            word + c => word
    return out

def handful(used):
    # [50, 50, 20, 2] -> "2 x 50 + 20 + 2"
    "" => s
    0 => i
    while i < len(used):
        i => j
        while j < len(used) and used[j] == used[i]:
            j + 1 => j
        if s != "":
            s + " + " => s
        if j - i > 1:
            s + str(j - i) + " x " + str(used[i]) => s
        else:
            s + str(used[i]) => s
        j => i
    return s

def set_text(cs):
    "" => s
    for c in cs:
        if s != "":
            s + ", " => s
        s + str(c) => s
    return s

def counted(n, one, many):
    if n == 1:
        return "1 " + one
    return str(n) + " " + many

def ask_amount():
    while True:
        trim(input("amount (1 to 10000)> ")) => answer
        if answer == "":
            return -1
        number(answer) => n
        if n >= 1 and n <= 10000:
            return n
        "Type a whole amount from 1 to 10000." ^0

def make_change(cs):
    ask_amount() => a
    if a == -1:
        "Cancelled." ^0
        return
    coins.fewest(cs, a) => best
    coins.greedy(cs, a) => g
    if best[0] == -1:
        (str(a) + " cannot be made from " + set_text(cs) + ".") ^0
        return
    ("Fewest: " + counted(best[0], "coin", "coins") + ", " + handful(best[1]) + ".") ^0
    if g[0] == -1:
        ("Greedy gets stuck: after " + handful(g[1]) + " no coin fits what is left.") ^0
    elif g[0] == best[0]:
        ("Greedy, largest first, finds the same number: " + handful(g[1]) + ".") ^0
    else:
        ("Greedy, largest first, uses " + str(g[0]) + ": " + handful(g[1]) + " - " + counted(g[0] - best[0], "coin", "coins") + " more than needed.") ^0

def count_ways(cs):
    ask_amount() => a
    if a == -1:
        "Cancelled." ^0
        return
    coins.ways(cs, a) => n
    ("There are " + str(n) + " different ways to make " + str(a) + " from " + set_text(cs) + " (the order of the coins does not count).") ^0

def greedy_check(cs):
    coins.first_greedy_miss(cs) => r
    if len(cs) < 2:
        "With one coin value there is nothing to choose." ^0
    elif r[0] == 0:
        if cs[0] == 1:
            ("Greedy is always right for " + set_text(cs) + ": no amount below " + str(r[1]) + " beats it, and a set with a 1 that fails has its first failure below that bound.") ^0
        else:
            ("Greedy is right for every amount up to " + str(r[1]) + " that " + set_text(cs) + " can make. Without a 1 coin that bound proves nothing beyond itself.") ^0
    else:
        coins.fewest(cs, r[0]) => best
        coins.greedy(cs, r[0]) => g
        if g[0] == -1:
            ("Greedy first goes wrong at " + str(r[0]) + ": it gets stuck after " + handful(g[1]) + ", but " + handful(best[1]) + " works.") ^0
        else:
            ("Greedy first goes wrong at " + str(r[0]) + ": " + handful(g[1]) + " (" + str(g[0]) + ") instead of " + handful(best[1]) + " (" + str(best[0]) + ").") ^0

def new_set():
    while True:
        words(trim(input("coin values in any order (like 1 3 4)> "))) => ws
        if len(ws) == 0:
            return []
        [] => cs
        True => ok
        for w in ws:
            number(w) => n
            if n < 1 or n > 1000:
                False => ok
            else:
                False => seen
                for c in cs:
                    if c == n:
                        True => seen
                if seen:
                    False => ok
                cs + [n] => cs
        if ok and len(cs) <= 10:
            return coins.sorted_down(cs)
        "Type 1 to 10 different whole values from 1 to 1000." ^0

def ascending(cs):
    [] => out
    for k in [0:len(cs) - 1]:
        [cs[k]] + out => out
    return out

"== Coin change ==" ^0
"The fewest coins for an amount, with any coin values - and when taking the largest coin first is wrong." ^0
[1, 2, 5, 10, 20, 50, 100, 200] => cs
("Coins: " + set_text(cs) + " (euro cents).") ^0
True => running
while running:
    "" ^0
    "1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        make_change(cs)
    elif choice == "2":
        count_ways(cs)
    elif choice == "3":
        greedy_check(cs)
    elif choice == "4":
        new_set() => n
        if len(n) == 0:
            "Cancelled." ^0
        else:
            ascending(n) => cs
            ("Coins: " + set_text(cs) + ".") ^0
    elif choice == "5":
        False => running
    else:
        "Pick a number from 1 to 5." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import coins

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def number(s):
    if s == "" or len(s) > 6:
        return -1
    n = 0
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n = n * 10 + int(c)
    return n

def words(s):
    out = []
    word = ""
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out = out + [word]
            word = ""
        else:
            word = word + c
    return out

def handful(used):
    s = ""
    i = 0
    while i < len(used):
        j = i
        while j < len(used) and used[j] == used[i]:
            j = j + 1
        if s != "":
            s = s + " + "
        if j - i > 1:
            s = s + str(j - i) + " x " + str(used[i])
        else:
            s = s + str(used[i])
        i = j
    return s

def set_text(cs):
    s = ""
    for c in cs:
        if s != "":
            s = s + ", "
        s = s + str(c)
    return s

def counted(n, one, many):
    if n == 1:
        return "1 " + one
    return str(n) + " " + many

def ask_amount():
    while True:
        answer = trim(input("amount (1 to 10000)> "))
        if answer == "":
            return -1
        n = number(answer)
        if n >= 1 and n <= 10000:
            return n
        print("Type a whole amount from 1 to 10000.")

def make_change(cs):
    a = ask_amount()
    if a == -1:
        print("Cancelled.")
        return
    best = coins.fewest(cs, a)
    g = coins.greedy(cs, a)
    if best[0] == -1:
        print(str(a) + " cannot be made from " + set_text(cs) + ".")
        return
    print("Fewest: " + counted(best[0], "coin", "coins") + ", " + handful(best[1]) + ".")
    if g[0] == -1:
        print("Greedy gets stuck: after " + handful(g[1]) + " no coin fits what is left.")
    elif g[0] == best[0]:
        print("Greedy, largest first, finds the same number: " + handful(g[1]) + ".")
    else:
        print("Greedy, largest first, uses " + str(g[0]) + ": " + handful(g[1]) + " - " + counted(g[0] - best[0], "coin", "coins") + " more than needed.")

def count_ways(cs):
    a = ask_amount()
    if a == -1:
        print("Cancelled.")
        return
    n = coins.ways(cs, a)
    print("There are " + str(n) + " different ways to make " + str(a) + " from " + set_text(cs) + " (the order of the coins does not count).")

def greedy_check(cs):
    r = coins.first_greedy_miss(cs)
    if len(cs) < 2:
        print("With one coin value there is nothing to choose.")
    elif r[0] == 0:
        if cs[0] == 1:
            print("Greedy is always right for " + set_text(cs) + ": no amount below " + str(r[1]) + " beats it, and a set with a 1 that fails has its first failure below that bound.")
        else:
            print("Greedy is right for every amount up to " + str(r[1]) + " that " + set_text(cs) + " can make. Without a 1 coin that bound proves nothing beyond itself.")
    else:
        best = coins.fewest(cs, r[0])
        g = coins.greedy(cs, r[0])
        if g[0] == -1:
            print("Greedy first goes wrong at " + str(r[0]) + ": it gets stuck after " + handful(g[1]) + ", but " + handful(best[1]) + " works.")
        else:
            print("Greedy first goes wrong at " + str(r[0]) + ": " + handful(g[1]) + " (" + str(g[0]) + ") instead of " + handful(best[1]) + " (" + str(best[0]) + ").")

def new_set():
    while True:
        ws = words(trim(input("coin values in any order (like 1 3 4)> ")))
        if len(ws) == 0:
            return []
        cs = []
        ok = True
        for w in ws:
            n = number(w)
            if n < 1 or n > 1000:
                ok = False
            else:
                seen = False
                for c in cs:
                    if c == n:
                        seen = True
                if seen:
                    ok = False
                cs = cs + [n]
        if ok and len(cs) <= 10:
            return coins.sorted_down(cs)
        print("Type 1 to 10 different whole values from 1 to 1000.")

def ascending(cs):
    out = []
    for k in range(0, len(cs)):
        out = [cs[k]] + out
    return out

print("== Coin change ==")
print("The fewest coins for an amount, with any coin values - and when taking the largest coin first is wrong.")
cs = [1, 2, 5, 10, 20, 50, 100, 200]
print("Coins: " + set_text(cs) + " (euro cents).")
running = True
while running:
    print("")
    print("1) fewest coins  2) number of ways  3) is greedy safe?  4) new coin set  5) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        make_change(cs)
    elif choice == "2":
        count_ways(cs)
    elif choice == "3":
        greedy_check(cs)
    elif choice == "4":
        n = new_set()
        if len(n) == 0:
            print("Cancelled.")
        else:
            cs = ascending(n)
            print("Coins: " + set_text(cs) + ".")
    elif choice == "5":
        running = False
    else:
        print("Pick a number from 1 to 5.")
print("Bye.")
```

### coins.eml

```eml
# P065 coin change - fewest coins by dynamic programming, the greedy way
# for comparison, and the number of ways. A coin set is a list of distinct
# values from smallest to largest; amounts are whole units.

def fewest(coins, amount):
    # The corpus case coin-change-dp's table, best[v] = the fewest coins that
    # make v, filled from 1 up: best[v] = 1 + the smallest best[v - c] over
    # the coins c that fit. last[v] keeps the coin that did it, so the coins
    # can be read back. Returns [count, coins used largest first], or [-1, []]
    # when no combination makes the amount.
    -1 => none
    [none] * (amount + 1) => best
    [0] * (amount + 1) => last
    0 => best[0]
    for v in [1:amount]:
        for c in coins:
            if c <= v and best[v - c] != none:
                if best[v] == none or best[v - c] + 1 < best[v]:
                    best[v - c] + 1 => best[v]
                    c => last[v]
    if best[amount] == none:
        return [-1, []]
    [] => used
    amount => v
    while v > 0:
        used + [last[v]] => used
        v - last[v] => v
    return [best[amount], sorted_down(used)]

def sorted_down(xs):
    xs[0:len(xs)] => out
    for i in [1:len(out) - 1]:
        out[i] => x
        i => j
        while j > 0 and out[j - 1] < x:
            out[j - 1] => out[j]
            j - 1 => j
        x => out[j]
    return out

def greedy(coins, amount):
    # Always the largest coin that still fits. Returns [count, coins used],
    # or [-1, coins used so far] when it gets stuck short of the amount.
    [] => used
    amount => left
    len(coins) - 1 => k
    while left > 0 and k >= 0:
        if coins[k] <= left:
            used + [coins[k]] => used
            left - coins[k] => left
        else:
            k - 1 => k
    if left > 0:
        return [-1, used]
    return [len(used), used]

def ways(coins, amount):
    # How many different handfuls make the amount, order not counting: take
    # the coins one value at a time, ways[v] += ways[v - c], so each handful
    # is counted once, in the order of the coin set.
    [0] * (amount + 1) => w
    1 => w[0]
    for c in coins:
        for v in [c:amount]:
            w[v] + w[v - c] => w[v]
    return w[amount]

def first_greedy_miss(coins):
    # The smallest amount where greedy does worse than the fewest coins, or
    # gets stuck where coins could make it - searched up to the largest coin
    # plus the next largest. For a set with a 1, a miss exists only if one
    # is below that bound (Kozen and Zaks, 1994). Returns [amount, bound] or
    # [0, bound].
    if len(coins) < 2:
        return [0, 0]
    coins[len(coins) - 1] + coins[len(coins) - 2] => bound
    -1 => none
    [none] * (bound + 1) => best
    0 => best[0]
    for v in [1:bound]:
        for c in coins:
            if c <= v and best[v - c] != none:
                if best[v] == none or best[v - c] + 1 < best[v]:
                    best[v - c] + 1 => best[v]
        if best[v] != none:
            greedy(coins, v) => g
            if g[0] == -1 or g[0] > best[v]:
                return [v, bound]
    return [0, bound]
```

Python projection of coins.eml:

```python
def fewest(coins, amount):
    none = -1
    best = [none] * (amount + 1)
    last = [0] * (amount + 1)
    best[0] = 0
    for v in range(1, amount+1):
        for c in coins:
            if c <= v and best[v - c] != none:
                if best[v] == none or best[v - c] + 1 < best[v]:
                    best[v] = best[v - c] + 1
                    last[v] = c
    if best[amount] == none:
        return [-1, []]
    used = []
    v = amount
    while v > 0:
        used = used + [last[v]]
        v = v - last[v]
    return [best[amount], sorted_down(used)]

def sorted_down(xs):
    out = xs[0:len(xs)]
    for i in range(1, len(out)):
        x = out[i]
        j = i
        while j > 0 and out[j - 1] < x:
            out[j] = out[j - 1]
            j = j - 1
        out[j] = x
    return out

def greedy(coins, amount):
    used = []
    left = amount
    k = len(coins) - 1
    while left > 0 and k >= 0:
        if coins[k] <= left:
            used = used + [coins[k]]
            left = left - coins[k]
        else:
            k = k - 1
    if left > 0:
        return [-1, used]
    return [len(used), used]

def ways(coins, amount):
    w = [0] * (amount + 1)
    w[0] = 1
    for c in coins:
        for v in range(c, amount+1):
            w[v] = w[v] + w[v - c]
    return w[amount]

def first_greedy_miss(coins):
    if len(coins) < 2:
        return [0, 0]
    bound = coins[len(coins) - 1] + coins[len(coins) - 2]
    none = -1
    best = [none] * (bound + 1)
    best[0] = 0
    for v in range(1, bound+1):
        for c in coins:
            if c <= v and best[v - c] != none:
                if best[v] == none or best[v - c] + 1 < best[v]:
                    best[v] = best[v - c] + 1
        if best[v] != none:
            g = greedy(coins, v)
            if g[0] == -1 or g[0] > best[v]:
                return [v, bound]
    return [0, bound]
```

## README

# P065 - Coin change

The fewest coins that make an amount, for any set of coin values. They are
worked out by dynamic programming and set against the greedy way of
taking the largest coin that fits. The program also counts how many
different handfuls make the amount, and says whether a coin set is one
where greedy is always right - and if not, the first amount where it goes
wrong. It starts with the euro coins: 1, 2, 5, 10, 20, 50, 100 and 200
cents.

- `main.eml` - the menu, reading amounts and coin sets, and the messages
- `coins.eml` - fewest coins, greedy, the number of ways, and the first
  amount greedy gets wrong

How each part works:

- Fewest coins: as in the corpus case `coin-change-dp`, a table holds the
  fewest coins for every amount from 1 up. Each is one more than the best
  of the amounts one coin smaller. Remembering which coin did it lets the
  coins be read back. This is right for any coin set. With 1, 3 and 4,
  greedy pays 6 as 4 + 1 + 1, three coins, where 3 + 3 takes two.
- Greedy may also get stuck: with 5 and 7 it pays 24 as 7 + 7 + 7 and has
  3 left over, though 7 + 7 + 5 + 5 works.
- Number of ways: take the coin values one at a time and add, for every
  amount, the ways to make it without that coin to the ways with it.
  Each handful is then counted once, whatever order its coins are in.
- Is greedy safe: search for the first amount where greedy does worse, up
  to the largest coin plus the next largest. For a set that has a 1, Kozen
  and Zaks (1994) showed that if greedy ever goes wrong, it first does so
  below that bound - so no failure there means none at all. For a set
  without a 1 the program says the search proves nothing beyond the
  bound.

What is checked: menu choices 1 to 5; amounts from 1 to 10000; a coin set
of 1 to 10 different values from 1 to 1000, in any order. An empty answer
cancels.

Sessions: `sessions/basic.in` gives:
- 289 in euro cents: 7 coins either way;
- 73,682 ways to make 200 from the euro coins, and the euro set checked
  as greedy-safe;
- the set 1, 3, 4: 6 takes 2 coins, and greedy's 3 coins is its first
  failure;
- the set 1, 10, 25: greedy first fails at 30, 25 + 5 x 1 against
  3 x 10, and there are 29 ways to make 100.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- amounts 0, 10001 and abc;
- the coin sets "3 3 7" with a repeated value, "0 5", and eleven values;
- the set 5, 7: 3 cannot be made, greedy gets stuck on 24, and it first
  goes wrong at 10;
- a cancelled set, and the single coin 4.

Built on the verified corpus case `coin-change-dp` (the fewest-coins table
filled from 1 up, right where greedy is not).