Simulator for puzzle from http://fivethirtyeight.com/features/build-your-own-death-star-and-defeat-the-stormtroopers/

riddler-2016-12-23.py

# https://twitter.com/rvcx/status/813081772288278528
# http://fivethirtyeight.com/features/build-your-own-death-star-and-defeat-the-stormtroopers/

from math import sqrt
from random import random

def simulate(n, k, base_rate):
    while n:
        # each storm trooper shoots
        for i in range(n):
            if random() < base_rate:
                return False
        # you shoot
        if random() < k * base_rate * sqrt(n):
            n -= 1
    return True

def sample(size, func):
     return sum(1.0 for x in range(size) if func()) / size

def target(tval, min, max, steps, func):
    for i in range(steps):
        probe = (min + max) / 2.0
        val = func(probe)
        print(probe, val, tval)
        if val < tval:
            min = probe
        else:
            max = probe
    return probe

print(target(0.5, 1, 1000, 10,
             lambda(k): sample(1000,
                               lambda: simulate(9, k, 0.001))))