= Compute The Change You Want To See =

Today, the circulating coins in the US are the penny, nickel, dime, and
quarter, with cent values 1, 5, 10, 25, respectively. How many different ways
can we choose coins to sum up to a given amount?

For example, there are 4 ways to make 10 cents: ten pennies; one nickel and
five pennies; two nickels; one dime. We'll later find there are 242 ways to
make one dollar, that is, 100 cents.

The above is https://en.wikipedia.org/wiki/Change-making_problem[a well-known
problem] with well-known relatives. One flavour fixes a finite multiset of
coins, rather than provide an endless supply of coins of each type. This is
https://en.wikipedia.org/wiki/Subset_sum_problem[the subset sum problem] with
inputs restricted to positive integers, whose decisional variant is
NP-complete. Another variant asks for the minimum number of coins needed,
a special case of https://en.wikipedia.org/wiki/Knapsack_problem[the knapsack
problem].

Technical interviews frequently test candidates with one of the above problems.
In fact, at one place I worked, interviewers were forbidden to ask these
problems because it was feared they were too well-known, a concern that may be
warranted because several websites reveal how to solve these problems with
dynamic programming.

However, there is one subtlety that seems less well-known. For the particular
variant of the problem we asked, we can do much better than the solution that
is cut-and-pasted all over the web. Exponentially better. See Graham, Knuth,
and Patashnik, _Concrete Mathematics_, Chapter 7.

== Exponential Improvement With Exponents ==

Consider a subset sum problem: how many ways we can pick elements of
\(\{6,6,6,9,9,20\}\) so they sum up to 32? This is equivalent to asking for the
coefficient of \(x^{32}\) in:

+++\[
(1+x^6+x^{12}+x^{18})(1+x^9+x^{18})(1+x^{20})
\]+++

The dynamic programming algorithm for the subset sum problem jumps out.
Coefficients of a polynomial naturally correspond to numbers in an array, and
multiplying by the next polynomial corresponds to updating the array via
dynamic programming.

In our original problem, we may use as many copies of a coin as we want, so we
wind up with formal power series instead of polynomials. For a given \(n\), we
seek the coefficient of \(x^n\) in:

\[
f = (1 + x + x^2 + ...)(1 + x^5 + x^{10} + ...)
(1 + x^{10} + x^{20} + ...)(1 + x^{25} + x^{50} + ...)
\]

We can recursively find the coefficient of \(x^n\) by taking advantage of the
identity:

\[
1 + z + z^2 + ... = 1 + z(1 + z + z^2 + ...)
\]

where we substitute various powers of \(x\) for \(z\).

naive n coins = f (length coins) n where
  f :: Int -> Integer -> Integer
  f _ 0 = 1
  f 0 _ = 0
  f k n = f (k - 1) n + if n < c then 0 else f k (n - c) where
    c = coins!!(k - 1)

naive 100  [1, 5, 10, 25]

Memoization leads to the infamous dynamic programming solution, which is
typically enough to pass the interview. (Haskell's
https://hackage.haskell.org/package/MemoTrie/docs/Data-MemoTrie.html[`Data.MemoTrie`]
lets us do this by replacing all occurrences of `f` on the right-hand side with
`memo2 f`.)

It turns out we're better off with a different identity:

\[
1 + z + z^2 + ... = \frac{1}{1-z}
\]

Differentiating both sides \(m\) times yields the more general:

\[
1 + {m + 1 \choose m} z + {m + 2 \choose m} z^2 + ... = \frac{1}{(1-z)^{m+1}}
\]

We start by rewriting \(f\) as:

+++\[
f = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}
\]+++

The authors of _Concrete Mathematics_ then cleverly observe that we can focus
on multiples of 5 cents; any remainder must with made up with pennies. However,
we want our code to be simple, so forget being clever! We'll brutally bash our
way through.

The lowest common multiple of the exponents is 50, hence every factor in
the denominator is a factor of \(1 - x^{50}\). Thus:

+++\[
f =
\frac{(1+x+...+x^{49})(1+x^5+...+x^{45})(1+x^{10}+...+x^{40})(1+x^{25})}
{(1-x^{50})^4}
\]+++

We expand the numerator, or rather, we get the computer to do it.
The result is a degree-159 polynomial:

\[a_0 + a_1 x + ... + a_{159} x^{159} \]

We represent this polynomial by a list of integers [\(a_0, ..., a_{159}\)].

p .+. q = zipWith (+) (pad p) (pad q)
  where pad = take (length p `max` length q) . (++ repeat 0)
p      .*. [] = []
[]     .*. q  = []
(a:as) .*. q  = map (a *) q .+. (0:(as .*. q))

expand cs m = foldr1 (.*.) $ cofactor <$> cs where
  cofactor c = 1:concat (replicate (div m c - 1) $ replicate (c - 1) 0 ++ [1])

expand [1, 5, 10, 25] 50

As for the denominator, substituting \(z = x^{50}, m = 3\) into
the above identity yields:

+++\[
\frac{1}{(1-x^{50})^4} =
1 + {4 \choose 3} x^{50} + {5 \choose 3} x^{100} + ...
\]+++

Altogether, we can compute the coefficient of \(x^n\) in \(f\) by writing \(n =
50 q + r\) where \(0 \le r < 50\), then computing:

+++\[
{q + 3 \choose 3} a_r
+ {q + 2 \choose 3} a_{r + 50}
+ {q + 1 \choose 3} a_{r + 100}
+ ...
\]+++

The following code automates all this. There are some annoying integer type
conversions: the desired total \(n\) is an `Integer`, but each coin
denomination is an `Int`. This is because the coin values must be fairly small,
as our algorithm is pseudo-polynomial in terms of the coin values, yet is
polynomial in \(\log n\), the space it takes to represent \(n\), and we wish to
show off how easily we can handle large \(n\).

choose :: Integer -> Integer -> Integer
choose n k
  | n < k = 0
  | k == 0 = 1
  | otherwise = n * choose (n - 1) (k - 1) `div` k

count :: Integer -> [Int] -> Integer
count n cs = sum [choose (m + q - i) m * fromIntegral (fx!!k)
    | (k, i) <- zip [r, r+common..length fx - 1] [0..]] where
  m = fromIntegral $ length cs - 1
  (q, rInteger) = divMod n $ fromIntegral common
  r = fromInteger rInteger :: Int
  common = foldr1 lcm cs
  fx = expand cs common

count 100 [1,5,10,25]

_Concrete Mathematics_ walks through an example with the same coins plus a
https://en.wikipedia.org/wiki/Half_dollar_(United_States_coin)[half-dollar
coin], where the goal is to make one million dollars, that is, \(10^8\) cents:

count 100000000 [1,5,10,25,50]

Let's now answer the trillion-dollar question:

count 100000000000000 [1,5,10,25,50]

Our algorithm is polynomial in \(\log n\) hence is unfazed by six extra zeroes.
In contrast, the popular dynamic programming solution would need one million
times more time and space to arrive at the above answer.

== Chickening Out ==

I attended an Australian mathematics training camp in 1994. In those days,
McDonald's sold Chicken McNuggets in boxes of 6, 9, or 20. Some of us were
given an exercise which asked for
https://en.wikipedia.org/wiki/Coin_problem[the greatest number of McNuggets
that cannot be split into the boxes of 6, 9, or 20].

Armed with the answer, we headed to the nearby Macca's, intending to
prank them by asking for exactly 43 Chicken McNuggets. Stereotypes of maths
nerds may be uncomfortably close to the truth, as it took a while for one of us
(I won't name names!) to muster the courage to order, and even then, he only
ordered 25, afraid that 43 would sound too oddly specific. The cashier
immediately realized that 25 was impossible and simply suggested we get 26
instead. Worst. Prank. Ever.

This variant, sometimes called the Frobenius problem, is NP-hard. There exists
an algorithm that is polynomial in the values of the denominations but is
pseudo-polynomial in the number of denominations. The algorithm is perhaps too
abstruse for a short article, let alone a typical coding interview. Luckily,
the McNuggets problem is tiny enough that we can bluntly hammer the problem
with our code to show 43 is the answer:

(`count` [6, 9, 20]) <$> [43..43+6]

There are zero ways of making 43, while there is at least one way to make each
of the next 6 integers. Since one of the box sizes is 6, we can make all
larger numbers.

By the way, I sill remember a time when Australian coins had denominations 1,
2, 5, 10, 20, and 50. They're fun to play with because each features an
Australian animal, except for the 50-cent coin, which features two.

How many ways are there to make a million Aussie dollars?

count 100000000 [1,2,5,10,20,50]

Inflation took away the feathertail glider and frill-necked lizard, and gave us
the one- and two-dollar coins:

count 100000000 [5,10,20,50,100,200]

It is only after writing this article that I discovered my primary school
teacher misled me years ago. She claimed the sugar glider (_Pretaurus
breviceps_) appeared on the one-cent coin, and even made us write about it.
https://en.wikipedia.org/wiki/Australian_one-cent_coin[According to Wikipedia,
it's actually the feathertail glider (_Acrobates pygmaeus_)]. Searching for
"sugar glider 1c" returns some results suggesting that others were fed the same
falsehoods.