Extensions statistics

realistic_case.py

def simulate(n: int, propagation_flags: list) -> int:
    steps = 0
    expecting_events: int = 0
    for i in range(1, n + 1):
        if propagation_flags[i - 1]:
            steps += expecting_events
            expecting_events += 1

        steps += 3


    return steps

extensions = 1_000
chance_of_requesting_events = 0.25

frequency = 1 // chance_of_requesting_events
propagation_flags = [(i % frequency == 0) for i in range(1, extensions + 1)]

steps = simulate(extensions, propagation_flags)
print(f"Average steps for {extensions} extensions with 25% propagation: {steps}")

verify.py

def simulate(n: int, propagation: bool):
    steps = 0
    for i in range(1, n + 1):
        steps += 3

        if propagation:
            steps += i

    return steps


extensions = 10


def test_extension_range(propagate: bool, maximum: int) -> list[int]:
    return [simulate(i, propagate) for i in range(1, maximum + 1)]


simulated_steps_best = test_extension_range(False, extensions)
simulated_steps_worst = test_extension_range(True, extensions)


def formula_best(n):
    return 3 * n


def formula_worst(n):
    return (4 * n) + (((n - 1) * n) // 2)


# print("Comparing simulation and formula results (best):")
for i, sim_steps in enumerate(simulated_steps_best, start=1):
    formula_result = formula_best(i)
    assert formula_result == sim_steps
    # print(f"(Best) Input: {i}, Simulated: {sim_steps}, Formula: {formula_result}, Match: {sim_steps == formula_result}")

# print("\nComparing simulation and formula results (worst):")
for i, sim_steps in enumerate(simulated_steps_worst, start=1):
    formula_result = formula_worst(i)
    assert formula_result == sim_steps
    # print(f"(Worst) Input: {i}, Simulated: {sim_steps}, Formula: {formula_result}, Match: {sim_steps == formula_result}")

See https://github.com/salve-org/estensione/pull/5 for an explanation of what this means