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?
  5. # What is your answer?
  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.  
  33. def calc_bad_numbers(n, margin):
  34.     bad_numbers = []
  35.     for k in range(1, n+1):
  36.         if binary_search(n, k) > margin:
  37.             bad_numbers.append(k)
  38.     return bad_numbers if bad_numbers!=[] else [n]
  39.  
  40. def calc_good_starts(n, bad_numbers, margin):
  41.     good_starts = []
  42.     for start in range(1, n+1):
  43.         guesses = 0
  44.         for x in bad_numbers:
  45.             guesses += binary_search(n, x, start)
  46.         if guesses/float(len(bad_numbers)) <= margin:
  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
  57.     bad_numbers = calc_bad_numbers(n, margin)
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top