#!/usr/bin/env python
'''
Possible solution for Python Bootcamp day 2 exercise
http://commondatastorage.googleapis.com/classes/BootCamp/homework2.pdf
by Julian "codemonk" Hammer
For future reference, the assignment:
A small monte carlo code to simulate the growth of coins in a cookie jar over
a 1 year period
The following are assumed:
1) you make X purchases each day with petty cash, starting out with only
bills in your pocket (i.e., no change).
2) Each purchase has a random chance of costing some dollar amount plus YY
cents (where YY goes from 0-99).
You always get change in the smallest number of coins possible. For
instance, if you have a purchase of $2.34, then you assume you acquire 66
cents in change (2 quarters, 1 dime, 1 nickel, 1 penny).
3) If you have enough change to cover the YY cents of the current
transaction, you use it.
Otherwise, you accumulate more change. For example, if you have $1.02 in
loose change, and you have a purchase of $10.34, then you use 34 cents
(or as close to it as possible) in coins leaving you with 68 cents.
4) At the end of each day you dump all your coins collected for the day in a
Money Jar.
The homework:
a) What is the average total amount of change accumulated each year (assume
X=5)? What is the 1-sigma scatter about this quantity?
b) What coin (quarter, dime, nickel, penny) are you most likely to
accumulate over time? Second most likely? Does it depend on X?
c) Letâ€™s say you need 8 quarters per week to do laundry. How many quarters
do you have at the end of the year? (if you do not have enough quarters
at the end of each week, use only what you have).
'''
import copy
class Change:
"""
Notes: everything is handled in cents!
you have unlimited founds, but only bills ;)
"""
# Coins: (sorry, no $1 and $.5 coins here)
names = {25: 'quarter',
10: 'dime',
5: 'nickel',
1: 'penny'}
def __init__(self, value=0):
# Coin dict
self.coins = dict([(k,0) for k in self.names.keys()])
if value >= 0:
# We ignore any bills, as that is not change
value = value%100
# for each available coin denomination, decending:
for d in sorted(self.names.keys(), reverse=True):
# use that coin to get as close to amount as possible
# Note: integer arithmetic does the trick here!
self.coins[d] = self.coins[d] + value/d
value -= d*(value/d)
def total_value(self):
"""Returns value of change in cents"""
return sum([k*v for k,v in self.coins.iteritems()])
def total_coins(self):
"""Returns number of coins"""
return sum(self.coins.itervalues())
def get(self, other):
"""Adds *other* to own coin collection.
If *other* is of type Change, the coins will be added,
if it is of type int, the value will be converted to Change and then
added"""
if isinstance(other, Change):
for k in self.coins.keys():
self.coins[k] += other.coins[k]
elif type(other) in [int,long]:
# Money + int
self.get(Change(other))
else:
raise TypeError('Can not add money with type '+str(type(other)))
def give(self, amount):
"""Will give *amount*, by using up as much small change as possible,
but also receiving return change if exact payment was not possible.
"""
# Ignoring bills:
amount = amount%100
# First use up all available coins:
for d in sorted(self.names.keys(), reverse=True):
i = min(self.coins[d], amount/d)
amount -= d*i
self.coins[d] -= i
# Then pay what ever is left by next largest and available coin
for d in sorted(self.names.keys()):
if d >= amount and self.coins[d] > 0:
self.get(d-amount)
amount = 0
break
# Otherwise use $1 bill
if amount > 0:
self.get(100-amount)
def empty(self):
"""Resets states by removing all coins"""
self.coins = dict([(k,0) for k in self.names.keys()])
def __sub__(self, other):
n = self.copy()
n.pay(other)
return n
def __add__(self, other):
n = self.copy()
n.get(other)
return n
def __str__(self):
return "$%.2f in %d coin(s)" % (self.total_value()/100.0,
self.total_coins())
def __repr__(self):
return "<%s %s>" % (self.__class__, str(self))
def copy(self):
return copy.copy(self)
def show(self):
"""Prints a nice summary of the current state"""
for k in sorted(self.names.keys(), reverse=True):
if self.coins[k] > 0:
if self.coins[k] > 1:
print self.coins[k], self.names[k]+'s'
else:
print self.coins[k], self.names[k]
if self.total_value() > 0:
print '-' * len(str(self))
print self
if __name__ == '__main__':
import numpy.random as rand
import numpy
import sys
pocket = Change()
jar = Change()
# Exercise a)
collected_change = []
n = 100
purchases_per_day = 5
for i in xrange(n):
jar.empty()
for j in xrange(365):
for k in xrange(purchases_per_day):
pocket.give(rand.randint(0,100))
jar.get(pocket)
pocket.empty()
collected_change.append(jar.total_value())
if i % 10 == 0:
sys.stdout.write('.')
sys.stdout.flush()
print '',n, 'experiments finished'
print 'Standard deviation was', "$%.2f" % \
(numpy.std(collected_change)/100.0)
print
# Exercise b)
most_coins = []
n = 100
min_purchases = 5
max_purchases = 10
for purchases_per_day in xrange(min_purchases,max_purchases+1):
coins = Change()
for i in xrange(n):
jar.empty()
for j in xrange(365):
for k in xrange(purchases_per_day):
pocket.give(rand.randint(0,100))
jar.get(pocket)
pocket.empty()
coins.get(jar)
if i*k % 100 == 0:
sys.stdout.write('.')
sys.stdout.flush()
# Get two max coins:
max1, max2 = coins.coins.items()[0], (None, 0)
for k,v in coins.coins.iteritems():
if v > max2[1]:
if v > max1[1]:
max2 = max1
max1 = k,v
else:
max2 = k,v
most_coins.append((purchases_per_day, max1[0], max2[0]))
print '', n*max_purchases, 'experiments finished'
print "Purch./day | Most acc. | 2nd most. acc"
print "-----------+-----------+--------------"
for p,m1,m2 in most_coins:
print "% 10d | % 9s | % 13s" % (p,Change.names[m1],Change.names[m2])
print
# Exercise c)
collected_quarters = []
n = 100
purchases_per_day = 5
for i in xrange(n):
jar.empty()
for j in xrange(365):
for k in xrange(purchases_per_day):
pocket.give(rand.randint(0,100))
jar.get(pocket)
pocket.empty()
# Pay for weekly laundry out of jar
if j % 7 == 0:
jar.coins[25] = max(0, jar.coins[25]-8)
collected_quarters.append(jar.coins[25])
if i % 10 == 0:
sys.stdout.write('.')
sys.stdout.flush()
print n, 'experiments finished'
print 'Average collected quarters:', int(numpy.average(collected_quarters))