The Coin Changing Problem
Table of Contents
The Change Problem
The Change Problem (Coin Changing Problem) asks us to convert some amount of money into denominations using the fewest coins.
Input: An integer (money) and an array of d denominations (\(c = c_1, c_2, \ldots, c_d\)) in decreasing order of value (\(c_1 > c_2> \cdots > c_d\)).
Output: A list of d integers \(i_1, i_2, \ldots, i_d\) such that \(c_1 \cdot i_1 + c_2 \cdot i_2 + \cdots + c_d \cdot i_d = money\) and \(i_1 + i_2 + \cdots + i_d\) is as small as possible.
SetUp
Imports
# python
from collections import namedtuple
from functools import partial
# pypi
from expects import contain_exactly, expect, equal
import altair
import pandas
# my stuff
from graeae.visualization.altair_helpers import output_path, save_chart
Setup
ChangeCounts = namedtuple("ChangeCounts", ["coin_counts", "run_count"])
ChangeCountsTable = namedtuple("ChangeCounts", ["coin_counts", "run_count", "table"])
SLUG = "the-coin-changing-problem"
OUTPUT_PATH = output_path(SLUG)
save_it = partial(save_chart, output_path=OUTPUT_PATH)
PlotParameters = namedtuple("PlotParameters", ["height", "width"],
defaults=[525, 750])()
Denominations = namedtuple("Denominations", "US double_dime obsolete",
defaults=[[25, 10, 5, 1],
[25, 20, 10, 5, 1],
[25, 20, 10, 5, 3, 2, 1]])()
The Cashier's Algorithm
The way many cashier's make change for customers is using a greedy approach.
Pseudocode
\begin{algorithm}
\caption{CashiersChange}
\begin{algorithmic}
\INPUT Amount owed ($money$) and a supply of coins ($c$).
\PROCEDURE{CashiersChange}{$money, c$}
\WHILE {\(money > 0\)}
\STATE \(coin \gets\) Coin with the largest denomination that doesn't exceed \(money\).
\STATE Give $coin$ to the customer.
\STATE \(money \gets money - coin\)
\ENDWHILE
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Python Implementation
def cashier_changer(amount: int, denominations: list) -> ChangeCounts:
"""Implements the cashier's method for making change
Args:
amount: the value of the change needed
denominations: values for coins (in descending order)
Returns:
list of coin-counts, number of loops ran
"""
coins = [0] * len(denominations)
remainder = amount
loop_count = 0
for index, denomination in enumerate(denominations):
coin_count = 0
while denomination <= remainder:
coin_count += 1
loop_count += 1
remainder = remainder - denomination
coins[index] = coin_count
return ChangeCounts(coin_counts=coins, run_count=loop_count)
A First Test
Examples from LATPAPS.
def check_coins(answer: list, denominations: list,
expected_coins: int,
expected_total: int) -> None:
"""Check that our answer matches the expected
Args:
answer: list of counts for each denomination
denominations: list of coin denominations available
expected_coins: the expected list of counts for each denomination
expected_total: what the value our coins should add up to
Raises:
AssertionError: something about our answer doesn't match the expected
"""
expect(sum(answer)).to(equal(sum(expected_coins)))
expect(answer).to(contain_exactly(*expected_coins))
expect(sum(count * coin for count, coin in zip(answer, denominations))).to(
equal(expected_total)
)
return
# case 1
money = 2
coins = [10, 5, 1]
actual = cashier_changer(money, coins)
check_coins(actual.coin_counts, coins, [0, 0, 2], money)
print(f"case 1: {actual.run_count}")
# case 2
money = 28
actual = cashier_changer(money, coins)
check_coins(actual.coin_counts, coins, [2, 1, 3], money)
print(f"case 2: {actual.run_count}")
# case 3
money = 99
actual = cashier_changer(money, coins)
check_coins(actual.coin_counts, coins, [9, 1, 4], money)
print(f"case 2: {actual.run_count}")
case 1: 2 case 2: 6 case 2: 14
The number of loops is dependent on the change owed, with an upper limit based on the denominations. In this case if we assume you wouldn't give out more than 99 cents in change then we would cap out at \( 9 \times 10 + 1 \times 5 + 4 \times 1\) = 14 coins/loops.
U.S. Denominations
This is a quick check using the U.S. coins most commonly used by cashiers. By adding a 25 cent piece we reduce the upper limit on the amount of coins needed to \(3 \times 25 + 2 \times 10 + 4 \times 1\) = 9 coins.
print(Denominations.US)
[25, 10, 5, 1]
money = 28
actual = cashier_changer(money, Denominations.US)
check_coins(actual.coin_counts, Denominations.US, [1, 0, 0, 3], money)
money = 14
actual = cashier_changer(money, Denominations.US)
check_coins(actual.coin_counts, Denominations.US, [0, 1, 0, 4], money)
Plotting the Coin Counts/Loops
PLOT_AMOUNTS = list(range(1, 100))
CASHIER_COUNTS = [cashier_changer(amount, Denominations.US).run_count
for amount in PLOT_AMOUNTS]
PLOT_FRAME = pandas.DataFrame({"Amount to Change": PLOT_AMOUNTS,
"Coins": CASHIER_COUNTS})
chart = altair.Chart(PLOT_FRAME).mark_bar().encode(
x=altair.X("Amount to Change", axis=altair.Axis(tickMinStep=1)),
y=altair.Y("Coins", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Coins"]).properties(
title="Cashier's Change Coin Counts (Common U.S. Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "cashiers-change-us-coins")
The Double-Dime
Our cashier algorithm turns out to work for the specific set of coins that cashiers commonly use, but will it work for other coins as well?
According to Wikipedia, there was at one time a proposal in the United States for a twenty-cent piece (and at one time there were half-cent, two-cent, and three-cent coins).If we include the twenty cent piece amongst our denominations, we find that there are cases where the cashier algorithm will miss the optimal solution.
print(Denominations.double_dime)
[25, 20, 10, 5, 1]
money = 40
actual = cashier_changer(money, Denominations.double_dime)
try:
check_coins(actual.coin_counts, Denominations.double_dime, [0, 2, 0, 0, 0], money)
except AssertionError as error:
print(f"AssertionError: {error}")
AssertionError: expected: 3 to equal 2
Because the cashier algorithm always takes the largest possible coins first, it ends up using 25¢ + 10¢ + 5¢ as the solution instead of the optimal 20¢ + 20¢. While it might seem artificial, given the characterization of this as a solution to making change, it's important to note that generalizing the cashier algorithm beyond the curated denominations or even beyond coins specifically leaves it vulnerable to cases where it will fail.
A Greedy Version
As noted, the Cashier's Algorithm is a greedy algorithm, but let's translate it into a silghtly smarter version which uses a little arithmetic to get to the same point.
In Pseudocode
\begin{algorithm}
\caption{GreedyChange}
\begin{algorithmic}
\INPUT An integer ($money$) and an array of $d$ denominations (\(c = c_1, c_2, \ldots, c_d\)) in decreasing order of value (\(c_1 > c_2> \cdots > c_d\)).
\OUTPUT A list of $d$ integers \(i_1, i_2, \ldots, i_d\) such that \(c_1 \cdot i_1 + c_2 \cdot i_2 + \cdots + c_d \cdot i_d = money\) and \(i_1 + i_2 + \cdots + i_d\) is as small as possible.
\PROCEDURE{CashiersChange}{$money, c$}
\STATE $remainder \gets money$
\STATE $d \gets $ \textsc{Length}($c$)
\FOR {$k \in \{1 \ldots d\}$}
\STATE $i_k \gets \lfloor \frac{remainder}{c_k} \rfloor$
\STATE $remainder \gets remainder - c_k \cdot i_k$
\ENDFOR
\RETURN $(i_1, i_2, \ldots, i_d)$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
In Python
def greedy_changer(money: int, denominations: list) -> ChangeCounts:
"""Make change using the fewest coins
Args:
money: the amount to change
denominations: list of coin denominations in decreasing order
Returns:
Number of each denomination needed to make the change, loop-count
"""
coins = [0] * len(denominations)
remainder = money
count = 0
for location, denomination in enumerate(denominations):
coins[location] = remainder // denomination
remainder = remainder - denomination * coins[location]
count += 1
return ChangeCounts(coins, count)
Testing It Out
A First Test
# case 1
money = 2
coins = [10, 5, 1]
actual = greedy_changer(money, coins)
check_coins(actual.coin_counts, coins, [0, 0, 2], money)
# case 2
money = 28
actual = greedy_changer(money, coins)
check_coins(actual.coin_counts, coins, [2, 1, 3], money)
U.S. Denominations
money = 28
actual = greedy_changer(money, Denominations.US)
check_coins(actual.coin_counts, Denominations.US, [1, 0, 0, 3], money)
money = 14
actual = greedy_changer(money, Denominations.US)
check_coins(actual.coin_counts, Denominations.US, [0, 1, 0, 4], money)
The Double-Dime
Looking at the greedy-algorithm you can see that it only has one loop that traverses the denominations of coins - so it is a very quick algorithm, but while our greedy algorithm turns out to work for the specific set of coins that cashiers use, it also falls prey to sometimes missing the optimal solution.
money = 40
actual = greedy_changer(money, Denominations.double_dime)
try:
check_coins(actual.coin_counts, Denominations.double_dime, [0, 2, 0, 0, 0], money)
except AssertionError as error:
print(f"AssertionError: {error}")
AssertionError: expected: 3 to equal 2
Plotting
greedy_counts = [greedy_changer(amount, Denominations.US).run_count
for amount in PLOT_AMOUNTS]
GREEDY_FRAME = PLOT_FRAME.rename(columns={"Coins": "Cashier"})
GREEDY_FRAME["Greedy"] = greedy_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
value_vars=["Greedy", "Cashier"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Cashier's and Greedy Change Coin Counts (Common U.S. Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "cashiers-greedy-change-us-coins")
Since the Cashier works by repeated subtraction instead of division it goes up with the amount of change owed, and so generally does worse than the Greedy changer, except in the cases where it takes fewer coins to make the change than the number of denominations there are. If I had included the fifty cent piece it would have done a little better in the second half of the plot.
A Brute Force Changer
To get around the limitations of the greedy-style of change making we'll figure out all the ways we can make change for a particular amount and pick the solution with the fewest coins.
def brute_changer(money: int, denominations: list) -> ChangeCounts:
"""Make change using the fewest coins
Args:
money: the amount to change
denominations: list of coin denominations in decreasing order
Returns:
Number of each denomination needed to make the change, loop_count
"""
best = float("inf")
number_of_denominations = len(denominations)
counter = 0
for first in range(number_of_denominations):
remainder = money
counts = [0] * number_of_denominations
total = 0
for next_location in range(first, number_of_denominations):
denomination = denominations[next_location]
count = remainder//denomination
remainder = remainder - count * denomination
counts[next_location] = count
total += count
counter += 1
if total < best:
best_counts = counts
best = total
return ChangeCounts(best_counts, counter)
# case 1
money = 2
coins = [10, 5, 1]
actual = brute_changer(money, coins)
check_coins(actual.coin_counts, coins, [0, 0, 2], money)
# case 2
money = 28
actual = brute_changer(money, coins)
check_coins(actual.coin_counts, coins, [2, 1, 3], money)
coins = [25, 10, 5, 1]
money = 28
actual = brute_changer(money, coins)
check_coins(actual.coin_counts, coins, [1, 0, 0, 3], money)
money = 14
actual = brute_changer(money, coins)
check_coins(actual.coin_counts, coins, [0, 1, 0, 4], money)
And now our double-dime case.
money = 40
actual = brute_changer(money, Denominations.double_dime)
check_coins(actual.coin_counts, Denominations.double_dime, [0, 2, 0, 0, 0], money)
print(actual)
ChangeCounts(coin_counts=[0, 2, 0, 0, 0], run_count=15)
The Brute-Force Changer fixes our double-dimes case, and has a constant runtime of:
\[ T(n) = \sum_{i = 1}^{n} = \frac{n(n + 1)}{2} \]
Where \(n\) is the number of denominations, not the input amount.
Let's make sure our functions all agree.
for amount in range(100):
cashiers_change = cashier_changer(amount, Denominations.US).coin_counts
greedy_change = greedy_changer(amount, Denominations.US).coin_counts
brute_change = brute_changer(amount, Denominations.US).coin_counts
check_coins(answer=cashiers_change, denominations=Denominations.US,
expected_coins=greedy_change, expected_total=amount)
check_coins(answer=brute_change, denominations=Denominations.US,
expected_coins=greedy_change, expected_total=amount)
Plotting
Let's compare the three methods we've created so far using the typical U.S. Coins.
brute_counts = [brute_changer(amount, Denominations.US).run_count
for amount in PLOT_AMOUNTS]
GREEDY_FRAME["Brute-Force"] = brute_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
value_vars=["Greedy", "Cashier", "Brute-Force"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Greedy Change & Brute-Force Coin Counts (Common U.S. Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "brute-force-change-us-coins")
The Greedy and Brute-Force methods both have a loop-count based on the number of coin denominations we have. Since we have four denominations (25, 10, 5, and 1) the Greedy method has four loops and the Brute-Force method has ten loops \(\left(^{4(4 + 1)}/_{2} = 10\right)\), so it does a little more calculating but not much, although in this case the benefit it has is wasted since we shouldn't find sub-optimal solutions with the greedy approach and using the coins that we did.
Memoized Changer
def memoized_changer(money: int, denominations: list, table: dict=None,
counter: int=0) -> ChangeCounts:
"""Make change using the fewest coins
Args:
money: the amount to change
denominations: list of coin denominations in decreasing order
table: memoization table (largest denomination, amount to change): best coin counts
counter: number of times the function is called
Returns:
Number of each denomination needed to make the change, call_count
"""
table = dict() if table is None else table
counter += 1
if money == 0:
return ChangeCounts([0] * len(denominations), counter)
if (denominations[0], money) in table:
return ChangeCounts(table[(denominations[0], money)], counter)
last_denomination = len(denominations) - 1
best = float("inf")
best_counts = None
for current, denomination in enumerate(denominations):
count = money//denomination
remaining = money - count * denomination
if current == last_denomination:
if remaining > 0:
count = float("inf")
counts = [count]
counter += 1
else:
counts, counter = memoized_changer(
remaining, denominations[current + 1:], table, counter)
counts = [count] + counts
total_counts = sum(counts)
if total_counts < best:
best = total_counts
best_counts = [0] * current + counts
table[(denomination, money)] = counts
return ChangeCounts(best_counts, counter)
Checking the Memoized Changer
def check_changers(changer: object, amount: int, denominations: list):
"""Check that the changer matches the brute-force solution
Arguments:
changer: change-function to compare to brute-force
amount: cents to change
denominations: descending list of coin-denominations
Raises:
AssertionError: there's a discrepancy somewhere
"""
brute_counts = brute_changer(amount, denominations)
check_counts = changer(amount, denominations)
check_coins(check_counts.coin_counts, denominations, brute_counts.coin_counts, amount)
return
def check_cases(changer: object) -> None:
"""Check the pre-picked cases are okay
Arguments:
changer: the dynamic-programming changer to check
Raises:
AssertionError if something doesn't check out
"""
for amount in range(100):
check_changers(changer, amount, Denominations.US)
check_changers(changer, amount, Denominations.double_dime)
check_changers(changer, amount, Denominations.obsolete)
money = 2
coins = [10, 5, 1]
check_changers(memoized_changer, money, coins)
money = 28
check_changers(memoized_changer, money, coins)
coins = [25, 10, 5, 1]
check_changers(memoized_changer, money, coins)
money = 14
check_changers(memoized_changer, money, coins)
# the double-dimes
coins = [25, 20, 10, 5, 1]
money = 40
check_changers(memoized_changer, money, coins)
return
check_cases(memoized_changer)
Plotting
All the Methods So Far
memoized_counts = [memoized_changer(amount, Denominations.US, {}).run_count
for amount in PLOT_AMOUNTS]
GREEDY_FRAME["Memoized"] = memoized_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
value_vars=["Greedy", "Cashier", "Brute-Force",
"Memoized"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Greedy, Brute-Force & Memoized Change Counts (Common U.S. Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "memoized-change-us-coins")
With a Brute-Force ceiling of 10 loops it's hard to see a marked improvement, given how much easier it is to write the Brute-Force method rather than the memoized one, but let's get rid of the two greedy methods and compare the brute force and memoized with more obsolete coins added in.
Obsolete Coins
First, we'll check to make sure that the brute-force and memoized methods agree on the best coins for making change with our new denominations, which include some that were once used in the United States but aren't any more.
print(Denominations.obsolete)
[25, 20, 10, 5, 3, 2, 1]
Now let's see how the run-times compare.
BRUTE_OBSOLETE = [brute_changer(amount, Denominations.obsolete).run_count
for amount in PLOT_AMOUNTS]
MEMOIZED_OBSOLETE = [memoized_changer(amount, Denominations.obsolete, {}).run_count
for amount in PLOT_AMOUNTS]
OBSOLETE_FRAME = pandas.DataFrame({"Amount to Change": PLOT_AMOUNTS,
"Brute-Force": BRUTE_OBSOLETE,
"Memoized": MEMOIZED_OBSOLETE})
melted = OBSOLETE_FRAME.melt(id_vars=["Amount to Change"],
value_vars=["Brute-Force",
"Memoized"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Brute-Force & Memoized Change Counts (Including Obsolete Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "memoized-change-obsolete")
This time we have seven coin denominations so the brute-force method takes \(^7(8)/_2 = 28\) loops. Now that we have more coins the memoized does slightly (very slightly) worse than the brute-force for larger amounts, but in the examples so far I've been creating a new memo-table for every amount - what happens if we build one table and re-use it as we find the change for new amounts?
OBSOLETE_TABLE = {}
MEMOIZED_OBSOLETE_2 = [memoized_changer(amount,
Denominations.obsolete,
OBSOLETE_TABLE).run_count
for amount in PLOT_AMOUNTS]
OBSOLETE_FRAME_2 = pandas.DataFrame({"Amount to Change": PLOT_AMOUNTS,
"Brute-Force": BRUTE_OBSOLETE,
"Memoized": MEMOIZED_OBSOLETE_2})
melted = OBSOLETE_FRAME_2.melt(id_vars=["Amount to Change"],
value_vars=["Brute-Force",
"Memoized"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Brute-Force & Memoized Change Counts (Obsolete Coins, Re-Used Table)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "memoized-change-obsolete-keep-table")
Re-using the table allows us to avoid some re-calculating and the number of calls eventually drops down to the number of coins we have, the same as the number of loops for the greedy method, although in this case we can handle cases where the greedy method fails.
Even better, now that we have the table built with all our allowed values, we can just look things up and don't need to run the function (although I will here just to make sure nothing funky is going on), so it has a cost of one.
MEMOIZED_OBSOLETE_3 = [memoized_changer(amount,
Denominations.obsolete,
OBSOLETE_TABLE).run_count
for amount in PLOT_AMOUNTS]
OBSOLETE_FRAME_3 = pandas.DataFrame({"Amount to Change": PLOT_AMOUNTS,
"Brute-Force": BRUTE_OBSOLETE,
"Memoized": MEMOIZED_OBSOLETE_3})
melted = OBSOLETE_FRAME_3.melt(id_vars=["Amount to Change"],
value_vars=["Brute-Force",
"Memoized"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Brute-Force & Memoized Change Counts (Obsolete Coins, Pre-Filled Table)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "memoized-change-obsolete-pre-filled-table")
Iterative Dynamic Programming
The idea behind this problem (making change) is to show how Dynamic Programming can eleminate redundant calculations, so this is the point where I'll switch to an iterative approach that uses Dynamic Programming. The iterative, top-down approach works in the opposite direction of the memoized approach, starting with the smallest values and then moving to ever increasing values, storing the outcomes as we go so that we can re-use the lower solutions as the values increase. This is where I was stumped for a while - since the memoized function I used is based on the remainders left over after subtracting a coin's value from it (e.g. 26 cents minus a quarter has a remainder of 1 cent so we use the stored 1-cent solution from the memo-table rather than re-calculating it) in order to create an iterative version we somehow have to store the values in the table before they are needed, but the scheme I used where we iterate over the coin-denominations doesn't work (or it makes it really convoluted to force it to work). From what I can tell this is because I didn't really make a dynamic programming solution with the memoized version. With Dynamic Programming our memo-table should be built around the change we need to give out, so you would have a table with all the possible amounts, not just the ones needed as remainders. This works with our depth-first version because we're starting at the leaf nodes and working back up the tree, but it doesn't work with the iterative version because we don't know ahead of time which remainders we need later on in the table. For example, if we can only use 1-cent and 10-cent coins and we need to make change for 11 cents, then we have to have an entry for 1-cent in the table before we get to figuring out the solution that includes the 10-cent piece. If we need to break 12 cents, though, we need to have an entry for 2 cents before we get to calculating the entry for 10 cents. But how do we know which values we need to enter into the table for the 1-cent piece before we get to the 10 cent piece?
The solution is to fill out the table completely from 1 to the amount to make change for each coin before moving on to the next larger denomination. So, for our 12-cent example we need entries for \(1 \ldots 12\) cents for the 1 cent piece filled out before we move on to calculating the entries for the 10 cent piece so that no matter what remainder we have when we reach the 10-cent piece we can look it up in the table (we actually only need up to 9 cents, but since the denominations aren't fixed doing the trimming once again adds to the complexity more than I'd like). So, I'll just fill out the table and we can see how it goes.
def centaur(amount: int, denominations: list, table: dict=None) -> ChangeCountsTable:
"""Make change using the fewest coins
Warning:
To keep the answers matching the other functions it's assumed that the denominations
are in decreasing order and the solution will also be match a decreasing order
Args:
money: the amount to change
denominations: list of coin denominations in decreasing order
table: memoization table (largest denomination, amount to change): best coin counts
Returns:
Number of each denomination needed to make the change, call_count, lookup table
"""
# the denominations need to be in ascending order, the opposite of the other methods
denominations = list(sorted(denominations))
counter = 0
if not table:
table = {denomination: [None] * (amount + 1) for denomination in denominations}
for index, denomination in enumerate(denominations):
table[denomination][0] = [0] * (index + 1)
best = float("inf")
best_counts = None
for owed in range(amount + 1):
for index, denomination in enumerate(denominations):
counter += 1
count = owed//denomination
remainder = owed - count * denomination
counts = [count]
if index > 0:
counts = table[denominations[index - 1]][remainder] + counts
table[denomination][owed] = counts
if amount == owed and sum(counts) < best:
best = sum(counts)
best_counts = counts + [0] * (len(denominations) - index - 1)
# put solution in descending order to match other functions
best_counts.reverse()
return ChangeCountsTable(best_counts, counter, table)
check_cases(centaur)
Plotting
Since the iterative version works differently from the others the loop-counts aren't really easy to compare.
centaur_counts = [centaur(amount, Denominations.US).run_count
for amount in PLOT_AMOUNTS]
GREEDY_FRAME["Iterative"] = centaur_counts
melted = GREEDY_FRAME.melt(id_vars=["Amount to Change"],
value_vars=["Greedy", "Cashier", "Brute-Force",
"Memoized", "Iterative"],
var_name="Change Method",
value_name="Loop Count")
chart = altair.Chart(melted).mark_line(point=True).encode(
x="Amount to Change",
y=altair.Y("Loop Count", axis=altair.Axis(tickMinStep=1)),
tooltip=["Amount to Change", "Loop Count", "Change Method"],
color="Change Method").properties(
title="Coin Change Counts (Common U.S. Coins)",
width=PlotParameters.width,
height=PlotParameters.height,
)
save_it(chart, "all-change-us-coins")
Since I'm filling out the whole table for the iterative function the loop is dependent on the amount of change owed, not the number of coin-denominations as with the other functions so it increases linearly. There's something I'm missing here as to why either the memoized-version is incorrect or there is an advantage to using the iterative version, but I haven't figured it out yet. The solutions seem to be the same in either case, though, and the linear growth for the number of loops is still tractable so I'll move on for now.