# The Dowry Problem (Part 2)

a guest
Jul 7th, 2018
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1529778760
2. import random
3.
4. NUM_GAMES = 100000
5. NUM_SLIPS = 200
6.
7. def main():
8.   print 'NUM_GAMES = %d, NUM_SLIPS = %d' % (NUM_GAMES, NUM_SLIPS)
9.   print_win_ratios([
10.     RandomStrategy(),
11.     RmsStrategy(),
12.     RmsStrategyWithWiggle(-.001),
13.     RmsStrategyWithWiggle(-.002),
14.     RmsStrategyWithWiggle(-.003),
15.     RmsStrategyWithWiggle(-.004),
16.     TowrStrategy(),
17.   ])
18.
19. def print_win_ratios(strategies):
20.   num_wins = [0 for j in range(len(strategies))]
21.   for i in range(NUM_GAMES):
22.     slips = [random.random() for i in range(NUM_SLIPS)]
23.     for j in range(len(strategies)):
24.       if play_game(strategies[j], slips):
25.         num_wins[j] += 1
26.   for j in range(len(strategies)):
27.     win_ratio = num_wins[j] / (NUM_GAMES + 0.0)
28.     print '%s: win ratio = %0.4f' % (strategies[j].name(), win_ratio)
29.
30. def play_game(strategy, slips):
31.   winning_slip_index = slips.index(max(slips))
32.
33.   # Play the game.
34.   strategy.new_game(len(slips))
35.   for i in range(len(slips)):
36.     strategy_chose = strategy.should_choose(i, slips[i])
37.     if strategy_chose:
38.       # Game ends, return if the strategy won.
39.       return i == winning_slip_index
40.
41.   # The strategy didn't choose.
42.   return False
43.
44. # Choose a random index and choose it, no matter what its value.
45. class RandomStrategy:
46.   def __init__(self):
47.     self.slip_choice_index = 0
48.
49.   def name(self):
50.     return 'RandomStrategy'
51.
52.   def new_game(self, num_slips):
53.     self.slip_choice_index = random.randint(0, num_slips - 1)
54.
55.   def should_choose(self, slip_index, slip):
56.     return slip_index == self.slip_choice_index
57.
58. # Choose a slip if it is greater than a given cutoff. The cutoffs are indexed on
59. # the sample index and are computed from the number of slips.
60. class CutoffStrategy:
61.   def __init__(self, my_name, cutoff_lambda):
62.     self.my_name = my_name
63.     self.cutoff_lambda = cutoff_lambda
64.     self.cutoffs = []
65.     self.num_slips = 0
66.     self.best_so_far = 0
67.
68.   def name(self):
69.     return self.my_name
70.
71.   def new_game(self, num_slips):
72.     self.cutoffs = self.cutoff_lambda(num_slips)
73.     self.num_slips = num_slips
74.     self.best_so_far = 0
75.
76.   def should_choose(self, slip_index, slip):
77.     if self.best_so_far > slip:
78.       # If we've seen better before, we can't choose this one.
79.       return False
80.     self.best_so_far = slip
81.     if slip >= self.cutoffs[slip_index]:
82.       return True
83.     if slip_index == self.num_slips - 1:
84.       # Last slip, might as well guess.
85.       return True
86.
87. # Choose the first slip greater than (num_slips - 1) / (num_slips) + wiggle.
88. class RmsStrategyWithWiggle(CutoffStrategy):
89.   def __init__(self, wiggle):
90.     CutoffStrategy.__init__(
91.         self,
92.         'RmsStrategyWithWiggle%.3f' % wiggle,
93.         lambda num_slips: [
94.           ((num_slips - 1.0) / num_slips) + wiggle for i in range(num_slips)
95.         ])
96.
97. # Choose the first slip greater than (num_slips - 1) / (num_slips).
98. class RmsStrategy(CutoffStrategy):
99.   def __init__(self):
100.     CutoffStrategy.__init__(
101.         self,
102.         'RmsStrategy',
103.         lambda num_slips: [
104.           (num_slips - 1.0) / num_slips for i in range(num_slips)
105.         ])
106.
107. # Choose a slip if there's a >=50% chance of there being a better one later.
108. class TowrStrategy(CutoffStrategy):
109.   def __init__(self):
110.     CutoffStrategy.__init__(
111.         self,
112.         'TowrStrategy',
113.         lambda num_slips: [
114.           0.5 ** (1.0 / (num_slips - i - 1)) if i < num_slips - 1 else 0
115.               for i in range(num_slips)
116.         ])
117.
118. if __name__ == '__main__':
119.   main()