Stochastic bisection

stochastic_bisect.py

import sys
import math

MIN_REL = 688
MAX_REL = 736
N = MAX_REL - MIN_REL + 1

# Parse command line argument: Average time to failure (mean_ttf) in hours
if len(sys.argv) < 2:
    print("Usage: python stochastic_bisect.py <mean_time_to_failure_hours>")
    print("Example: python stochastic_bisect.py 4.5")
    sys.exit(1)

try:
    MEAN_TTF = float(sys.argv[1])
    if MEAN_TTF <= 0:
        raise ValueError
except ValueError:
    print("Error: Average time to failure must be a positive number.")
    sys.exit(1)

# Uniform prior belief: fix is equally likely at any release 688..736
probs = [1.0 / N] * N

def update_probabilities(from_, to, factor):
    """
    Scale probabilities in range [from_, to].
    """
    global probs
    new_probs = list(probs)

    if factor == 0.0:
        print(f"Updating from {from_} to {to} with p=0")
    else:
        print(f"Scaling from {from_} to {to} by p={factor}")

    for rel in range(from_, to + 1):
        new_probs[rel - MIN_REL] *= factor

    total = sum(new_probs)
    if total == 0:
        print("\nError: Contradictory test results encountered!")
        sys.exit(1)

    # Re-normalize
    probs = [p / total for p in new_probs]
    print(probs)

def select_next_test_release():
    cumulative = 0.0
    best_idx = 0
    min_diff = 1.0

    for i in range(N):
        cumulative += probs[i]
        diff = abs(cumulative - 0.5)
        if diff < min_diff:
            min_diff = diff
            best_idx = i

    return best_idx + MIN_REL

def display_top_candidates():
    # probs contain probability of being the boundary
    # Add 1 to print first fixed release
    ranked = sorted([(MIN_REL + i + 1, probs[i]) for i in range(N)], key=lambda x: x[1], reverse=True)
    if ranked[0][1] > 0.9:
        print(f"Fix introduced in release **{ranked[0][0]}** with {ranked[0][1]:.1%} confidence.")
    elif ranked[0][1] > 0.1:
        candidates_str = ", ".join([f"Rel {rel}: {p:.1%}" for rel, p in ranked if p > 0.1])
        print(f"Top candidates: {candidates_str}")
    else:
        print(f"No conclusive result, highest confidence **{ranked[0][1]:.1%}** for release {ranked[0][0]}.")

print(f"=== Stochastic Bisect Started (Mean TTF: {MEAN_TTF} hrs) ===")
print("At each step, enter 'f'/'fail' OR the number of hours ran (e.g., '10' or '4.5').")
print("Type 'q' to quit.\n")

step = 1
while True:
    release_num = select_next_test_release()

    display_top_candidates()
    print(f"Step {step}: Test release **{release_num}**")

    while True:
        user_input = input(f"Release tested: ").strip().lower()
        if user_input == "q":
            sys.exit(0)
        try:
            release_num = int(user_input)
            if release_num < MIN_REL or release_num > MAX_REL:
                raise ValueError
            break

        except ValueError:
            print("  Invalid input. Enter a release number or 'q'.")

    while True:
        user_input = input(f"Result for release {release_num} ['f' or hours]: ").strip().lower()

        if user_input == "q":
            sys.exit(0)
        elif user_input in ["f", "fail"]:
            # If release_num failed, the boundary K CANNOT be before release_num.
            # Zero out hypotheses K < release_num (MIN_REL through release_num - 1)
            update_probabilities(MIN_REL, release_num - 1, 0.0)
            break
        else:
            try:
                duration_hours = float(user_input)
                if duration_hours < 0:
                    raise ValueError

            except ValueError:
                print("  Invalid input. Enter 'f' for failure, a positive number for hours ran, or 'q'.")
                continue

            # If release_num passed, hypotheses K >= release_num (release_num through MAX_REL)
            # represent builds that survived t hours -> scale down by false negative rate.
            # P(PASS) is the Poisson probability of a broken build surviving duration_hours
            p_pass_given_broken = math.exp(-duration_hours / MEAN_TTF)
            if p_pass_given_broken <= 1e-10:
                p_pass_given_broken = 1e-10
            update_probabilities(release_num, MAX_REL, p_pass_given_broken)
            break

    step += 1
    print("-" * 50)