Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 messagescoins.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (23 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (18 lines)
1
289
2
200
3
4
1 3 4
1
6
3
4
25 10 1
3
1
30
2
100
5
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (coins.py)
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]