Solving an annoying homework problem for @MatLock

coin-problem.py

# @uptownnickbrown

import random
from collections import Counter

# valid coin values
coins = [.01,.02,.05,.10,.20,.50,1.00,2.00]

# run one trial with the appropriate constraints (100 total coins, 5 coin types)
def run_trial(coins):
	validValues = coins
	myCoins = [];
	while (len(myCoins) < 100):
		if (len(set(myCoins))) < 5:
			myCoins.append(random.choice(validValues))
		else:
			myCoins.append(random.choice(list(set(myCoins))))

	value = sum(myCoins)
	valuesInUse = set(myCoins)
	coinsInUse = myCoins
	return value, valuesInUse, coinsInUse

# what are we aiming for here?
target = 39.75

# how many times has it run to find a hit?
trialCount = 0

# keep track of our progress
closestResult = 0
closestResultCoinSet = set([])
closestResultAllCoins = []

# keep trying until we match our target value!
while (abs(closestResult - target) > 0):
	value, valuesInUse, coinsInUse = run_trial(coins)
	print 'Trial result = ' + str(value) + ' using coin values ' + str(sorted(valuesInUse))
	if (abs(value - target) < abs(closestResult - target)):
		closestResult = value
		closestResultCoinSet = valuesInUse
		closestResultAllCoins = coinsInUse
	trialCount = trialCount + 1

# it's a match! how'd we get here?
print '\nWe did it! Result = ' + str(closestResult) + ' using coin values ' + str(sorted(closestResultCoinSet))

breakdown = Counter(coinsInUse)
coinTypes = sorted(breakdown.keys())
print '\nCoin breakdown = '
for coin in coinTypes:
	print str(breakdown[coin]) + ' coins with value ' + str(coin)
	
# how hard was it?
print '\nWow, that was a lot of work. It took ' + str(trialCount) + ' trials to get a match...'