The optimal denominations for a currency to reduce the

optimal_currency.rb

#denom = popular_usd_denom = [100_00, 50_00, 20_00, 10_00, 5_00, 1_00, 25, 10, 5, 1]
#denom = official_usd_denom = [100_00, 50_00, 20_00, 10_00, 5_00, 2_00, 1_00, 50, 25, 10, 5, 1]
#denom = power2_denom = [64_00, 32_00, 16_00, 8_00, 4_00, 2_00, 1_00, 32, 16, 8, 4, 2, 1]
denom = power3_denom = [27_00, 9_00, 3_00, 1_00, 27, 9, 3, 1]
#denom = power4_denom = [64_00, 16_00, 4_00, 1_00, 64, 16, 4, 1]

total_prices = 100_00
needed = Array.new(total_prices, 0)

denom_count = denom.size
puts denom_count

1.upto(100_00) do |i|
  val = i
  denom.each do |den|
    if den <= val
      needed[i-1] += (val / den)
      val -= den * (val / den)
    end
  end
  puts "$#{i}: #{needed[i-1]}"
end

puts "Number of bill + coin denominations: #{denom_count}"
average = needed.inject(0) {|total, c| total += c} / total_prices.to_f
puts "Average demoninations needed for purchase price: #{average}"
distribution = Hash.new(0)
needed.each {|c| distribution[c] += 1}
distribution.each_pair do |k, v|
  puts "Denominations needed (bills + coins): #{k} and occurrences: #{v}"
end