lonely_king.py

#!/usr/bin/env python

import numpy as np
np.random.seed(124897)
# number of people to start with
num_start = 56000
# number of times to repeat experiment
num_trials = 1000
# some arrays to store individual trial results
rounds_counter = np.zeros(num_trials)
outcome_counter = np.zeros(num_trials)


def subtract_sets(a, b):
    return a - b


def cast_set(a):
    return set(a)


def eliminate_people(choices, num_left):
    # remove people that have been picked
    return len(subtract_sets(cast_set(xrange(num_left)), cast_set(choices)))


def pick_people(num_left):
    # every one pick someone else at random simultaneously, don't pick yourself
    return np.mod((np.arange(num_left) + np.random.randint(1, num_left, size=num_left)), num_left)


def run_trial(num_left):
    round_counter = 0
    # if more than one person left, keep playing
    while num_left > 1:
        # increment round counter for this trial
        round_counter += 1
        num_left = eliminate_people(pick_people(num_left), num_left)
    return num_left, round_counter


for trial in xrange(num_trials):
    # initialize trial
    outcome, num_rounds = run_trial(num_start)
    # save trial outcomue
    outcome_counter[trial] = outcome
    rounds_counter[trial] = num_rounds
print('Average outcome: {:.4f}'.format(np.mean(outcome_counter)))
print('Average number of rounds: {:.4f}'.format(np.mean(rounds_counter)))


# ##### Run

# $ time python -m cProfile -o lonely_king.pstats lonely_king.py

# Average outcome: 0.4670
# Average number of rounds: 10.7860
# real    0m24.988s
# user    0m24.815s
# sys 0m0.127s


# ##### Profile

# import pstats
# p = pstats.Stats('lonely_king.pstats')
# p.strip_dirs().sort_stats('cumulative').print_stats(10)

# Wed Nov 30 14:44:27 2016    lonely_king.pstats
#          109826 function calls (109705 primitive calls) in 24.940 seconds
#    Ordered by: cumulative time
#    List reduced from 554 to 10 due to restriction <10>
#    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
#         1    0.006    0.006   24.940   24.940 lonely_king.py:3(<module>)
#      1000    0.026    0.000   24.760    0.025 lonely_king.py:35(run_trial)
#     10786    2.065    0.000   22.442    0.002 lonely_king.py:30(eliminate_people)
#     21572   11.402    0.001   11.402    0.001 lonely_king.py:26(cast_set)
#     10786    8.970    0.001    8.970    0.001 lonely_king.py:22(subtract_sets)
#     10786    1.208    0.000    2.292    0.000 lonely_king.py:14(pick_people)
#     10786    0.985    0.000    0.985    0.000 {method 'randint' of 'mtrand.RandomState' objects}
#         4    0.120    0.030    0.293    0.073 __init__.py:1(<module>)
#         1    0.003    0.003    0.172    0.172 __init__.py:106(<module>)
#         1    0.000    0.000    0.152    0.152 add_newdocs.py:10(<module>)


# ##### Generate svg of profile

# gprof2dot -f pstats lonely_king.pstats | dot -Tsvg -o lonely_king_profile.svg