• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# ballmer.py

joric Jun 15th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # www.bloomberg.com/news/videos/2016-11-07/steve-ballmer-on-how-to-pass-an-interview
2. # I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you
3. # whether you're high or low. You get it at the first guess, I give you 5 bucks, 4 bucks, 3, 2, 1, 0,
4. # you pay me a buck, you pay me 2, you pay me 3. And the question is: do you want to play or not?
6.
7. import math, random
8.
9. def binary_search(n, x, custom_start=0):
10.     left = 1
11.     right = n
12.     count = 1
13.     while left < right:
14.         mid = custom_start if custom_start>0 and count==1 else (left + right) / 2
15.         if x==mid:
16.             break
17.         if x<mid:
18.             right = mid - 1
19.         else:
20.             left = mid + 1
21.         count += 1
22.     return count
23.
24. def simulation(n, margin, games, ballmer_set, player_set, desc, stat):
25.     total_guesses = 0
26.     money = 0
27.     for i in range(games):
28.         guesses = binary_search(n, random.choice(ballmer_set), random.choice(player_set))
29.         money += margin - guesses
30.         total_guesses += guesses
31.     stat.append((desc, n, margin, games, money, total_guesses))
32.
35.     for k in range(1, n+1):
36.         if binary_search(n, k) > margin:
39.
41.     good_starts = []
42.     for start in range(1, n+1):
43.         guesses = 0
45.             guesses += binary_search(n, x, start)
47.             good_starts.append(start)
48.     good_starts = list(set(good_starts))
49.     return good_starts if good_starts!=[] else [0]
50.
51. stat = []
52. for n in [5, 9, 20, 100]:
53.     games = 10000
54.     numbers = range(1, n+1)
55.     starts = [0]
56.     margin = math.ceil(math.log(n, 2))-1
58.     good_starts = calc_good_starts(n, bad_numbers, margin)
59.     simulation(n, margin, games, numbers, starts, 'naive vs naive', stat)
60.     simulation(n, margin, games, bad_numbers, starts, 'smart vs naive', stat)
61.     simulation(n, margin, games, bad_numbers, good_starts, 'smart vs smart', stat)
62.     simulation(n, margin, games, numbers, good_starts, 'naive vs smart', stat)
63.
64. fmt1 = "%-14s % 8s % 8s % 8s % 10s % 10s % 10s % 10s % 12s"
65. print fmt1 % ('desc','n','guesses','margin','games','money','avg.money','avg.guess','penalties')
66. fmt2 = "%-14s % 8d % 8d % 8d % 10d % 10d % 10.2f % 10.2f %12s"
67. for desc, n, margin, games, money, guesses in stat:
68.     penalty = '%d/%d' % (1+n-2**margin, n)
69.     print fmt2 % (desc, n, margin+1, margin, games, money, money/float(games), guesses/float(games), penalty)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?