Problem 3: DOLLARS AND CENTS (536 Puzzles and Curious Problems, Henry Ernest, Dudeney)

May 31, 2014, 11:15 PM

# Problem 3: DOLLARS AND CENTS (536 Puzzles and Curious Problems, Henry Ernest, Dudeney)

# What is the largest sum of money-all in current coins and no silver dollars-that 
# I could have in my pocket without being able to give change 
# for a dollar, half dollar, quarter, dime, or nickel?

max.cash= function(){
  s= expand.grid(half= 0:2, quarter= 0:2, dime= 0:5, nickel= 0:2, penny= 0:10)
  try.cash= function(s, row) {
    c(rep(50, s[row,1]), rep(25, s[row,2]), rep(10, s[row,3]), rep(5, s[row,4]), rep(1, s[row,5]))}
  partial.sum= function(x) {
    inner= function(x) {
      if (length(x)) {
        y= Recall(x[-1])
        c(y + 0, y + x[1])
      } else 0
    }
    sort(unique(inner(x)[-1]))
  }  
  changeable= function(coins){
    ans=vector()
    for (coin in c(5, 10, 25, 50, 100)) ans= c(ans, coin%in%partial.sum(coins) & !(coin %in% coins))
    any(ans)
  }  
  ans=list(value=0, coins="")
  for (row in 1:nrow(s)) {
    cash=try.cash(s, row)
    if(!changeable(cash)) {
      value= sum(cash)
      if(value > ans$value) {
        ans$value= value
        ans$coins= paste(cash, collapse=" ")
      }
    }
  }
  ans
}

max.cash()

$value
[1] 119

$coins
[1] "50 25 10 10 10 10 1 1 1 1"