#!/usr/bin/python

import random
import numpy

class Devil:
    def init(m):
        m.versions = 1024
        # Costs in minutes
        m.cost_compile = 6
        m.cost_test = 1
        # Penalty for wrongly identifying a commit.
        m.cost_failure = 1000
        # 0. == nicely behaved bug which always triggers
        m.p_false_success = .5
        m.verbose = 2

    def init_run(m):
        m.broken = random.randint(0, m.versions-1)
        m.tests = 0
        m.last_ver = -1
        m.cost = 0

    def test_failed(m, ver):
        m.tests += 1
        if ver != m.last_ver:
            m.cost += m.cost_compile
        m.cost += m.cost_test
        m.last_ver = ver
        if m.verbose > 1:
            print "   testing version ", ver, "(tests %d, cost %d)" % (m.tests, m.cost),
        if ver >= m.broken:
            if m.verbose > 1:
                print "(bad)",
            if random.random() > m.p_false_success:
                if m.verbose > 1:
                    print "FAIL"
                return 1
        if m.verbose > 1:
            print "pass"
        return 0

    def evaluate(m):
        ver = m.run()
        if ver == m.broken:
            if m.verbose:
                print "success"
        else:
            if m.verbose:
                print "FAILURE"
            m.cost += m.cost_failure

class Bisector(Devil):
    def init_run(m):
        Devil.init_run(m)
        m.good = 0
        m.bad = m.versions-1

    def run(m):
        while m.good+1 < m.bad:
            ver = (m.good + m.bad) / 2
            p_bad = 1
            failed = 0
            while p_bad > .01:
                if m.test_failed(ver):
                    m.bad = ver
                    failed = 1
                    break
                p_bad *= m.p_false_success
            if not failed:
                m.good = ver
        return m.bad

class Trisector(Devil):
    def init_run(m):
        Devil.init_run(m)
        m.good = 0
        m.bad = m.versions-1

    def run(m):
        while m.good+1 < m.bad:
            ver = (m.good*6 + m.bad*14) / 20
            p_bad = 1
            failed = 0
            while p_bad > .01:
                if m.test_failed(ver):
                    m.bad = ver
                    failed = 1
                    break
                p_bad *= m.p_false_success
            if not failed:
                m.good = ver
        return m.bad


class Strange(Devil):
    def init_run(m):
        Devil.init_run(m)
        m.good = 0
        m.bad = m.versions-1
        m.prob_bad = numpy.zeros([m.versions], float)
        m.prob_bad[:m.versions] = .9

    def ask_for(m, ver):
        if m.test_failed(ver):
            m.bad = ver
            m.prob_bad[:ver+1] /= m.prob_bad[ver]
            m.prob_bad[ver:] = 1
            return

        m.prob_bad[:ver+1] *= m.p_false_success
        m.good = ver

    def last_good(m, prob):
        g = 0
        for i in range(m.bad):
            if m.prob_bad[i] <= prob:
                g = i
        return g

    def run(m):

        while m.last_good(.01)+1 < m.bad:
            if m.verbose > 1:
                print m.prob_bad
            m.good = m.last_good(.5)
            ver = (m.good*10 + m.bad*10) / 20
            m.ask_for(ver)
            m.good = m.last_good(.1)
            ver = (m.good*10 + m.bad*10) / 20
            m.ask_for(ver)


        return m.bad

def monte_carlo(bis, tries = 30000):
    total_cost = 0.
    total_tests = 0.
    for i in range(tries):
        bis.init_run()
        if tries > 500:
            bis.verbose = 0
        bis.evaluate()
        total_cost += bis.cost
        total_tests += bis.tests

    print "-----"
    print bis.versions, "versions bug with probability of ", bis.p_false_success, " false success, monte carlo of ", tries, " tries"
    print "Assume compilation takes ", bis.cost_compile, "minutes and test takes", bis.cost_test, "minutes"
    print "Average cost ", total_cost / tries, "minutes"
    print "Average tests ", total_tests / tries

print "Bisector on reliable bug"
bis = Bisector()
bis.init()
bis.p_false_success = 0
monte_carlo(bis)

print "Bisector"
bis = Bisector()
bis.init()
monte_carlo(bis)

print "Trisector"
bis = Trisector()
bis.init()
monte_carlo(bis)

print "Strange"
bis = Strange()
bis.init()
monte_carlo(bis, 3000)