coins.rb

def denoms()
  [25, 10, 5, 1]
end

# we want to build a table which
# has the amount of cents, and an
# object containing two properties.
# {
#   31 => {
#     :count => 3,
#     :coins => { 25 => 1, 10 => 0, 5 => 1, 1 => 1 }
#   }
# }

def change_dyn(cents, table)
  return nil if cents < 0
  return table[cents] unless table[cents].nil?
  #puts cents
  
  bestTup = denoms.map do |denom|
    my_cents = cents - denom
    result = change_dyn(my_cents, table)
    [denom, result] unless result.nil?
  end.reject(&:nil?).sort_by do |entryTuple|
    #puts "Entry: #{entryTuple}"
    entryTuple[1][:count]
  end.first
  
  best = bestTup[1].clone
  #puts "Best: #{best}"
  best[:count] = best[:count] + 1
  bestDenom = bestTup[0]
  #puts "Best Denom: #{bestDenom}"
  coins = best[:coins].clone
  coins[bestDenom] = coins[bestDenom] + 1
  #best[:coins][bestDenom] = best[:coins][bestDenom] + 1
  table[cents] = {
    count: best[:count] + 1,
    coins: coins
  }
  #puts table
  table[cents]
end

def empty_change
  denoms.reduce({}) do |mem, denom|
    mem[denom] = 0
    mem
  end
end

def change_tbl_init
  coins_init = empty_change
    
  denoms.reduce({
    count: 0,
    coins: coins_init.clone
  }) do |mem, item|
    coins = coins_init.clone
    coins[item] = 1
    
    mem[item] = {
      count: 1,
      coins: coins      
    }
    mem
  end
end

def reduce_by_quarters(cents)  
  quarters = (cents / 25).to_i  
  if quarters > 1    
    {
      quarters: quarters - 1,
      cents: cents - (quarters - 1) * 25    }  else    {
      quarters: 0, 
      cents: cents    
      }  
  end
end 
def change(cents)  
  return empty_change if cents <= 0   
  tbl = change_tbl_init  
  reduction = reduce_by_quarters(cents)  
  result = change_dyn(reduction[:cents], tbl)    
  result[:coins][25] = result[:coins][25] + reduction[:quarters]  
  result[:coins]
end