Skip to content

Instantly share code, notes, and snippets.

@christianp
Last active August 29, 2015 14:02
Show Gist options
  • Save christianp/aedacece3f61a5a8a225 to your computer and use it in GitHub Desktop.
Save christianp/aedacece3f61a5a8a225 to your computer and use it in GitHub Desktop.
If sticker collectors pool their acquisitions, how much quicker do they finish their collections (and more cheaply)?
Album has 638 stickers
50 trials for each pool size
Collectors Waste Waste per collector
1 4054.360000 4054.360000
2 4748.840000 2374.420000
3 5328.000000 1776.000000
4 5586.160000 1396.540000
5 6429.320000 1285.864000
6 6675.840000 1112.640000
7 7084.840000 1012.120000
8 7562.240000 945.280000
9 7915.680000 879.520000
10 8062.480000 806.248000
11 8306.360000 755.123636
12 8833.440000 736.120000
13 9035.560000 695.043077
14 9267.680000 661.977143
15 9472.320000 631.488000
16 9770.920000 610.682500
17 10126.520000 595.677647
18 10243.560000 569.086667
19 10334.920000 543.943158
20 10861.760000 543.088000
Waste is the number of excess stickers
import random
class Collection:
def __init__(self,num_stickers):
self.num_stickers = num_stickers
def pack(self):
return [random.randrange(self.num_stickers) for i in range(6)]
class Album:
def __init__(self,collection):
self.collection = collection
self.got = [False]*self.collection.num_stickers
def finished(self):
return False not in self.got
def collect(collection,num_albums):
albums = [Album(collection) for i in range(num_albums)]
doubles = []
done = False
while sum(album.finished() for album in albums)<num_albums:
pack = collection.pack()
for sticker in pack:
double = True
for album in albums:
if not album.got[sticker]:
album.got[sticker] = True
double = False
break
if double:
doubles.append(sticker)
return len(doubles)/len(albums)
if __name__ == '__main__':
num_stickers = 638
num_trials = 50
collection = Collection(num_stickers)
print("Album has %i stickers" % num_stickers)
print("%i trials for each pool size" % num_trials)
print('Collectors\tWaste\t\tWaste per collector')
for i in range(1,21):
mean = sum(collect(collection,i) for j in range(num_trials))/num_trials
print('%i\t\t%f\t%f' %(i,mean*i,mean))
print("Waste is the number of excess stickers")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment