Minimizing Change

In Algorithm Design with Haskell by Richard Bird and Jeremy Gibbons, one of the examples of greedy algorithms on lists is giving change in coins. Given an amount of change (the amount due subtracted from the amount paid), the cashier (or cash register) must determine which coins should be used to make up the change.

In this problem, candidate solutions are lists of counts of each denomination of coin that have a total value equal to the target amount of change. A solution should minimize a cost function, which is often the total number of coins but could alternatively be the total weight of the change. A common greedy algorithm for minimizing the total number of coins is to give the customer the coin of the largest denomination less than the remaining amount until the target amount has been reached. The authors point out that this does not provide an optimal solution in all cases, depending on the denominations of coins used.

This reminds of me a similar problem, which demonstrates why I prefer the denominations of coins used in Japan over those used in the United States. The problem is from the point of view of the customer: given whatever coins that the customer has, what amount should be paid in order to minimize the total number of coins that the customer has after receiving the change?

Pretty much everybody does this to some extent. If the amount due is 196 yen, then paying 201 yen instead of just 200 yen results in only receiving a single 5-yen coin in change instead of four 1-yen coins. Similarly, people in the United States pay an extra cent to avoid receiving four cents in change, and people in the UK pay an extra pence in order to avoid receiving four pence in change.

When I first came to Japan, I was accustomed to collecting excess change. After a year of studying abroad, I had a large jar of coins that I needed to use before returning to the U.S. To my surprise, banks as well as the post office refused to exchange the coins for bills. Some places in the U.S. have machines for the purpose, but I have never seen one in Japan. I ended up dumping the coins into a UNICEF donation box at a convenience store.

When I returned to Japan, I decided to manage my coins instead of let them accumulate. I found that it is actually quite simple to minimize the total number of coins that I possess. It is simple because of the denominations commonly used.

In spite of its simplicity, the algorithm for determining what coins to pay sounds complicated when it is described. It is easiest to understand through an example. Consider a scenario where 276 yen is due and the customer has the following coins.

Each denomination can be considered separately, though it is convenient to think about denominations for the same decimal place together.

1. The last digit of 276 is 6, which is optimally covered with a single 1-yen coin and a single 5-yen coin. The customer has two 1-yen coins but no 5-yen coins, so she includes one 1-yen coin in her payment, leaving 275 yen left to be paid.
2. The last two digits of 275 is 75, which is optimally covered using three 10-yen coins and a single 50-yen coin. The customer has four 10-yen coins but no 50-yen coins, so she includes three 10-yen coins in her payment, leaving 245 yen left to be paid.
3. The remaining 245 yen is optimally covered using three 100-yen coins. The customer only has two 100-yen coins, however, so she covers it with a 500-yen coin.

In this example, the customer pays a 1-yen coin, three 10-yen coins, and a 500-yen coin, paying a total of 531 yen. The cashier then gives 255 yen in change: two 100-yen coins, one 50-yen coin, and one 5-yen coin.

After the transaction is complete, the customer has eight coins. For comparison, consider what happens if the customer pays with just the 500-yen coin, receiving 224 yen in change. After the transaction is complete, the customer would have 16 coins!

Note that one should never have more than four 1-yen coins because five 1-yen coins is equivalent in value to a single 5-yen coin. The maximum number of coins of each denomination that one should possess is shown in the first table above. In the last scenario, the customer has six 1-yen coins and six 10-yen coins, both in excess.

The code for this mental process, implemented in Change.hs, is inelegant and makes it look even more complicated, unfortunately.

payment
  :: (Int, Int, Int, Int, Int, Int)
  -> Int
  -> Maybe (Int, Int, Int, Int, Int, Int)
payment (c1, c5, c10, c50, c100, c500) due =
    let (c1', dueA) =
          case due `mod` 5 of
            n
              | n > 0 && n <= c1 -> (n, due - n)
              | otherwise        -> (0, due)
        (c5', dueB) =
          case dueA `mod` 10 of
            n
              | n > 0 && n <= 5 && c5 > 0 -> (1, dueA - 5)
              | otherwise                 -> (0, dueA)
        (c10', dueC) =
          case ceiling (fromIntegral dueB / 10 :: Float) `mod` 5 of
            n
              | n > 0 && n <= c10 -> (n, dueB - n * 10)
              | otherwise         -> (0, dueB)
        (c50', dueD) =
          case dueC `mod` 100 of
            n
              | n > 0 && n <= 50 && c50 > 0 -> (1, dueC - 50)
              | otherwise                   -> (0, dueC)
        (c100', dueE) =
          case ceiling (fromIntegral dueD / 100 :: Float) `mod` 5 of
            n
              | n > 0 && n <= c100 -> (n, dueD - n * 100)
              | otherwise          -> (0, dueD)
        (c500', dueF) =
          case dueE `mod` 1000 of
            n
              | n > 0 && n <= 500 && c500 > 0 -> (1, dueE - 500)
              | otherwise                     -> (0, dueE)
    in  if dueF <= 0
          then Just (c1', c5', c10', c50', c100', c500')
          else Nothing

There are a few properties of Japanese currency denominations that make this work. This type of algorithm is possible because the value of each denomination is an exact multiple of the value of the greatest smaller denomination. (For example, 50 yen is exactly 5 times 10 yen.) It is particularly easy to perform mentally because the denominations align with decimal place values. It turns out that many people in Japan manage coins in this way.

In contrast, commonly used U.S. currency denominations do not have either of these properties. For example, the value of a quarter (25 cents) is not evenly divisible by the value of a dime (10 cents).

Consider a scenario where a customer who has a dollar bill and two dimes needs to pay $0.90 (90 cents). If she just pays a dollar, she gets a dime in change. This results in having three dimes, which is not optimal because 30 cents can be represented using two coins: a quarter and a nickel (5 cents). If the customer were to hand over the dollar bill and both dimes, then 30 cents would be due in change and could be given as a quarter and nickel. Paying $1.20 when $0.90 is due would probably confuse most cashiers, however!

I have minimized change when making payments in Japan for about twenty years, and I have very rarely had problems. (Occasionally a cashier will not understand and think that I am making a mistake.) I almost always have problems when minimizing change in the U.S., however. (Cashiers often assume that I am a foreigner who does not yet understand U.S. currency.) I have therefore resigned to accumulating coins in the U.S. If I lived there, I would probably roll coins for exchange at a bank. At any rate, I much prefer the denominations used in Japan.