Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solving an annoying homework problem for @MatLock
# @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...'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment