ballmer.py

'''
www.bloomberg.com/news/videos/2016-11-07/steve-ballmer-on-how-to-pass-an-interview
I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you
whether you're high or low. You get it at the first guess, I give you 5 bucks, 4 bucks, 3, 2, 1, 0,
you pay me a buck, you pay me 2, you pay me 3. And the question is: do you want to play or not?
What is your answer?
'''

import math, random

def binary_search(n, x, custom_start=0):
    left = 1
    right = n
    count = 1
    while left < right:
        mid = custom_start if custom_start>0 and count==1 else (left + right) / 2
        if x==mid:
            break
        if x<mid:
            right = mid - 1
        else:
            left = mid + 1
        count += 1
    return count

def simulation(n, margin, games, ballmer_set, player_set, desc, stat):
    total_guesses = 0
    money = 0
    for i in range(games):
        guesses = binary_search(n, random.choice(ballmer_set), random.choice(player_set))
        money += margin - guesses
        total_guesses += guesses
    stat.append((desc, n, margin, games, money, total_guesses))

def calc_bad_numbers(n, margin):
    bad_numbers = []
    for k in range(1, n+1):
        if binary_search(n, k) > margin:
            bad_numbers.append(k)
    return bad_numbers if bad_numbers!=[] else [n]

def calc_good_starts(n, bad_numbers, margin):
    good_starts = []
    for start in range(1, n+1):
        guesses = 0
        for x in bad_numbers:
            guesses += binary_search(n, x, start)
        if guesses/float(len(bad_numbers)) <= margin:
            good_starts.append(start)
    good_starts = list(set(good_starts))
    return good_starts if good_starts!=[] else [0]

stat = []
for n in [5, 9, 20, 100]:
    games = 10000
    numbers = range(1, n+1)
    starts = [0]
    margin = math.ceil(math.log(n, 2))-1
    bad_numbers = calc_bad_numbers(n, margin)
    good_starts = calc_good_starts(n, bad_numbers, margin)
    simulation(n, margin, games, numbers, starts, 'naive vs naive', stat)
    simulation(n, margin, games, bad_numbers, starts, 'smart vs naive', stat)
    simulation(n, margin, games, bad_numbers, good_starts, 'smart vs smart', stat)
    simulation(n, margin, games, numbers, good_starts, 'naive vs smart', stat)

fmt1 = "%-14s % 8s % 8s % 8s % 10s % 10s % 10s % 10s % 12s"
print(fmt1 % ('desc','n','guesses','margin','games','money','avg.money','avg.guess','penalties'))
fmt2 = "%-14s % 8d % 8d % 8d % 10d % 10d % 10.2f % 10.2f %12s"
for desc, n, margin, games, money, guesses in stat:
    penalty = '%d/%d' % (1+n-2**margin, n)
    print(fmt2 % (desc, n, margin+1, margin, games, money, money/float(games), guesses/float(games), penalty))

'''
desc                  n  guesses   margin      games      money  avg.money  avg.guess    penalties
naive vs naive        5        3        2      10000      -5952      -0.60       2.60          2/5
smart vs naive        5        3        2      10000     -10000      -1.00       3.00          2/5
smart vs smart        5        3        2      10000          4       0.00       2.00          2/5
naive vs smart        5        3        2      10000      -2003      -0.20       2.20          2/5
naive vs naive        9        4        3      10000      -6574      -0.66       3.66          2/9
smart vs naive        9        4        3      10000     -10000      -1.00       4.00          2/9
smart vs smart        9        4        3      10000       1283       0.13       2.87          2/9
naive vs smart        9        4        3      10000        -43      -0.00       3.00          2/9
naive vs naive       20        5        4      10000     -10000      -1.00       5.00         5/20
smart vs naive       20        5        4      10000     -10000      -1.00       5.00         5/20
smart vs smart       20        5        4      10000     -10000      -1.00       5.00         5/20
naive vs smart       20        5        4      10000     -10000      -1.00       5.00         5/20
naive vs naive      100        7        6      10000     -10000      -1.00       7.00       37/100
smart vs naive      100        7        6      10000     -10000      -1.00       7.00       37/100
smart vs smart      100        7        6      10000     -10000      -1.00       7.00       37/100
naive vs smart      100        7        6      10000     -10000      -1.00       7.00       37/100
'''