"""Verify motorcycle Question 24 in exact arithmetic. Run with python3 q24_verify.py."""
from fractions import Fraction as F

RANGE_KM = 120
ONE = F(1)


def simulate(n):
    """Drive each leg, transfer fuel and return one rider directly home per stop."""
    fuel = [ONE] * n  # rider 0 delivers the parcel
    position = F(0)
    gap = ONE / (n + 1)  # distances are measured in full-tank ranges
    turnarounds = []
    for count in range(n, 1, -1):
        position += gap
        for rider in range(count):
            fuel[rider] -= gap
            assert 0 <= fuel[rider] <= ONE
        helper = count - 1
        for rider in range(helper):
            top_up = ONE - fuel[rider]
            fuel[helper] -= top_up
            fuel[rider] += top_up
            assert fuel[helper] >= position and fuel[rider] == ONE
        assert fuel[helper] == position
        fuel[helper] -= position
        turnarounds.append(position)
    destination = position + fuel[0]
    fuel[0] = F(0)
    assert all(amount == 0 for amount in fuel)
    assert destination + 2 * sum(turnarounds) == n  # total fuel burned
    return destination


def independent_upper_bound(n):
    """Derive the dual bound from capacity, without assuming full departing tanks.

    Let x[m] be the location where m riders remain, x[n] = 0. The
    supporting riders still in the convoy turn at x[1], ..., x[m-1].
    From x[m] the courier drives D-x[m], while helper j drives
    2*x[j]-x[m]. Thus D + 2*sum(x[j], j<m) - m*x[m] <= m.
    The positive multipliers below cancel every unknown turn point exactly.
    """
    coefficient = [F(0)] * (n + 1)
    distance_coefficient = F(0)
    capacity = F(0)
    suffix_weight = F(0)
    # For variable x[m], later rows contribute 2*suffix_weight,
    # and row m contributes -m*weight. x[n] is known to be zero.
    for m in range(n, 0, -1):
        weight = ONE if m == n else 2 * suffix_weight / m
        assert weight > 0
        coefficient[m] = 2 * suffix_weight - m * weight
        distance_coefficient += weight
        capacity += m * weight
        suffix_weight += weight
    assert all(c == 0 for c in coefficient[1:n])
    return capacity / distance_coefficient


def main():
    for n in range(1, 101):
        achieved = simulate(n)
        ceiling = independent_upper_bound(n)
        assert achieved == ceiling == F(2 * n, n + 1)
        assert achieved * RANGE_KM < 240 < 260
    assert simulate(2) == F(4, 3)
    assert simulate(2) * RANGE_KM == 160
    assert simulate(3) == F(3, 2)
    assert simulate(11) * RANGE_KM == 220
    print('Exact fuel simulation and independent capacity bound agree for n = 1 through 100.')
    print('Answers: 4/3 tank; 160 km; 3/2 tanks; 220 km; impossible (limit 240 km).')


if __name__ == '__main__':
    main()