#!/usr/bin/env python
coins = [1, 5, 10, 25] # North America
#coins = [1, 2, 5, 10, 20, 50] # Europe

def best_payment(coins, goal, bail):
  # Given the available mixture of coins,
  # what is the minimum number of coins required to reach the goal?
  # Bail is the point where we give up, because a better solution has previously been found.
  # Recursive.
  if bail < 1:
    return 999 # Forget it, someone else has already found a better solution
  if goal == 0:
    return 0 # Exact match
  if len(coins) == 1:
    return goal # Assuming that the smallest coin is a penny.
  this_coin = goal/coins[0] # Integer division
  best_run = 999
  while this_coin >= 0:
    bp = this_coin + best_payment(coins[1:], goal - this_coin*coins[0], bail - this_coin)
    if bp < best_run:
      best_run = bp
      if bp < bail - this_coin:
        bail = bp
    this_coin -= 1
  # print coins, goal, "=", best_run
  return best_run

def test_coinset(coins):
  # Given the available coins, what is the average number of coins
  # needed to complete every transaction from 1 to 99?
  coins.sort()
  print "Coins:", coins
  if coins[0] != 1:
    print "This program requires that the currency has a penny."
    return 0
  coins.reverse()
  total = 0
  for x in range(1, 100):
    bp = best_payment(coins, x, 100)
    total += bp
    print x, "->", bp
  print "Average:", total/99.0
  return total/99.0

test_coinset(coins)