## Saturday, July 5, 2014

### Estimating Required Coinage

I would like to code up a simple method of minimizing the number of coins required to give change.  Then I would like see what coins are most likely to be called into usage if change is required from a uniform draw between 1 cent and 499 cents.

```# I use the 200 and 100 for Canadian coins the  Loonies and Twoonies.

# The changer function will do what we want.
# It is based on the concept that if we exhaust our biggest
# currencies first then we will minize coin requirements.
# This might not be the case if we had unusual coinage,
# for instance a 30 cent peice would give 2x30 + 1xto + 1x5 = 75 cents
# while 3x25 would be the preferred route.
# However, since coinage tends to be divisible, in any example I can
# think of using largest coins first always minimizes coin requirements.
changer <- function(value, den) {
# value is the change that must be made
# den is the denominations available
remainder <- value
# Remainder counts how much change is still required to be made for
count <- den
# counts the required instances of each denomination
names(count) <- den
# loops through each of the denominations and removes the required
# coinage
for (i in 1:length(den)) {
count[i] <- floor(remainder/den[i])
remainder <- remainder-count[i]*den[i]
}
count
}

# Define denominations to search through
den <- c(200,100,25,10,5,1)

changer(341,den)
# 200 100  25  10   5   1
# 1   1   1   1   1   1

# Now let's see how many coins are required to make change for
# all possible change between 1 cent and \$4.99 cents.
curcount <- NULL
for (i in 1:499) curcount <- rbind(curcount, changer(i,den))

(meancur <- apply(curcount, 2, mean))
(meancur <- apply(curcount, 2, sum))

#       200       100        25        10         5         1
# 0.8016032 0.4008016 1.5030060 0.8016032 0.4008016 2.0040080
# We can see that the average transaction required .8 2 dollar coins,
# .4 dollars, 1.5 quarters, .8 dimes, .4 nickels, and 2 pennies

(ratiocur <- meancur/sum(meancur))
#        200        100         25         10          5          1
# 0.13559322 0.06779661 0.25423729 0.13559322 0.06779661 0.33898305
# Pennies had the largest ratio of 34% required while 25% of quarters
# were required.

den <- c(25,10,5,1)
curcount <- NULL
for (i in 1:99) curcount <- rbind(curcount, changer(i,den))

(meancur <- apply(curcount, 2, sum))

(meancur <- apply(curcount, 2, mean))
#        25        10         5         1
# 1.5151515 0.8080808 0.4040404 2.0202020

require(plotrix)
labels=c("quarters", "dimes", "nickles", "pennies"),
main="Currency Ratios Required for Change")
```
` `
``` (ratiocur <- meancur/sum(meancur))
#         25         10          5          1
# 0.31914894 0.17021277 0.08510638 0.42553191

# Once again pennies have the highest requirement at 42% of transactions
# while quarters are next with 32%.  Nickles are the least required with
# only 8.5% of the ratio of required coins.

# We might also want to know for what percentage of transactions certain
# coins are required.  We can do this one mostly in our head. Pennies will
# be required whenever change is not divisible by 5, thus ~4/5 times.
# Quarters will be required whenever the change is greater than 24 cents,
# thus ~75/99=757.  Dimes will be required when whatever remains
# after dividing by quarters is greater than 9 cents, thus ~15/25=60%.
# Finally, nickles are required whenever whatever is left after quarters
# and dimes is greater or equal to 5. 25 -> 1,2,3,4,x5,x6,x7,x8,x9,0,1,2,
# 3,4,x5,x6,x7,x8,x9,0,1,2,3,4 so, ~10/25=40%.

# Let's check.
apply(curcount>0, 2, mean)
#        25        10         5         1
# 0.7575758 0.6060606 0.4040404 0.8080808

# Thus we can see that though nickles represent a small portion of the
# optimal ratio of currency in circulation, the do represent a large
# portion of the optimal change patterns required.```
Created by Pretty R at inside-R.org

1. i realize you like to simulate things BUT sometimes it is not the right thing to do.

in this case your changer function doesn't produce the correct exact change for all case.

this is a prime example of where to use dynamic programing (DP).

here is a short code to demonstrate
(sorry it is text format)

note that your results are larger than DP gives it would be nice to see where it is different

rm(list=ls())
### how many coins make exact change?
###

### input 1, available denominations
### exact change for values up to n.values (input 2)
### output is a matrix
### nrows = number of values
### ncolumns = number of denominations
### e.g. mat[45,3] is how many coins of value denomination
### are needed to make 45

find.exact.change <- function(n.values,denominations) {
n.dens <- length(denominations)

exactCoin <- matrix(-1,nrow=n.values,ncol=n.dens)
colnames(exactCoin) <- denominations
### loop over all possible values

for (i.value in 1:n.values) {
## the maximum possible number of coins
n.coins <- i.value/min(denominations) + 1
n.coins.now <- n.coins
v.coins <- exactCoin[i.value,]
## we are going to search what happens when you
## use given denomination and then
## look-up the remaining value (in the lookup table)

for (i.denom in denominations) {
new.value <- i.value - i.denom
### look up whaat change is needed for the 'new.value'
if (new.value > 0) {
## change for the reminder
v.coins.now <- exactCoin[new.value,]
## plus the new coin
v.coins.now[as.character(i.denom)] <- 1 + v.coins.now[as.character(i.denom)]
## number of coins needed is
n.coins.now <- sum(v.coins.now)
}
### if this denomination gives exact change report it
if (new.value == 0) {
n.coins.now <- 1
v.coins.now <- rep(0,n.dens)
names(v.coins.now) <- denominations
v.coins.now[as.character(i.denom)] <- 1
}
### if n.coins is better keep it
if (n.coins.now < n.coins) {
v.coins <- v.coins.now
n.coins <- n.coins.now
}
} ## end loop for i.denomination
exactCoin[i.value,] <- v.coins
} ## end loop for i.value

return(exactCoin)
}

denominations <- c(25,10,5,1)
n.values <- 99
change.mat <- find.exact.change(n.values,denominations)
print(apply(change.mat,2,sum))

denominations <- c(200,100,25,10,5,1)
n.values <- 499
change.mat <- find.exact.change(n.values,denominations)
print(apply(change.mat,2,sum))

1. Dear Commenter,

I am very happy that you have written this lengthy response to my original post. In my post I stated that I was not sure if my procedure would work for all coin value options but that I was sure it would work for the common ones. I am still sure but even more so after your response. The reason is because using DP as you have has produced identical results to my original code.

# Summing by currency choice, simple selection algorithm
(sumcur <- apply(curcount, 2, sum))
200 100 25 10 5 1
400 200 750 400 200 1000

# DP algorithm you present
print(apply(change.mat,2,sum))
200 100 25 10 5 1
400 200 750 400 200 1000

As you can see the more rigorous model (DP) has produced the same results. I commend you on your diligence however I think it is worth thinking things through a bit more before throwing the toolbox at every problem that comes your way.

If my algorithm had failed to produce optimal results I should think that you would easily have been able to provide a counter example for a change value in which using smaller change would be better than always going with the largest available.

Failing to do this simpler task, I chose to stop there before spending my time conceptualizing a more complex procedure.

Cheers,
Francis

2. Francis,

it was not my intent to prove anything was wrong with your simulation or the changer function. But as you write in the intro there are cases where your algorithm doesn't work. And my thought was that DP will work in this case. And so i coded it.

I find it interesting that your algorithm works for all possible values.

here is new challenge - for which denominations your changer will always give the correct answer. for example c(30,25,10,5,1) is not correct all the time but c(25,10,5,1) is.

keep up your good work on this blog

cheers

3. Thanks for the qualifier and the original comment!