First red build

The pipeline has been red every morning for a week and nobody knows which night it broke. The archive holds the answer; reading all of it is the problem.

The problem

A build server runs the full suite once a night against the trunk and files a verdict for that night's build: green if the suite passed, red if anything failed. Builds are numbered from 1 in date order.

The break was never repaired inside the window under investigation, so the verdicts read green, green, ..., green, red, red, ..., red. Each verdict lives in its own archive, and pulling one down takes a minute, so the count of verdicts you read is the cost that matters — not the arithmetic around them.

Report the number of the first red build.

Input. nightly — a list of booleans, nightly[i] true when build i + 1 passed.

Output. The number of the earliest red build, or -1 if every build in the window passed.

Example.

nightly = [True, True, False, False, False]   ->  3

Builds 1 and 2 were green, build 3 is the first red night, and the pipeline never recovers after it.

A second example, the two ends of the window:

nightly = [True, True, True, True]            -> -1
nightly = [False, False, False]               ->  1

An all-green window has nothing to report. An all-red one means the break landed before the window opened, so the earliest red build in it is the first.

Constraints.

• 1 <= len(nightly) <= 10^6
• once an entry is false, every later entry is false
• a solution should read at most 20 entries

Hints

Approach

Brute force

Pull verdicts from build 1 forward and stop at the first red one. It reads up to n archives — a million minute-long downloads when the break is recent, which is the common case.

The insight

"Build k is red" is a monotone predicate: false, then true, and never false again — so the archive is already a sorted array of booleans and the answer is the first true.

Being unrepaired inside the window is the precondition, and it is what makes one probe say something about a whole side. A green verdict eliminates its entire prefix, a red one eliminates its entire suffix, so every read halves the candidates. Nothing had to be sorted first: the order lives in the predicate, not in the values.

Algorithm

1. Set lo = 0 and hi = n, where hi == n stands for "no red build seen".
2. While lo < hi, take mid = (lo + hi) // 2 and read that verdict.
3. Green: the break is strictly later, so lo = mid + 1.
4. Red: mid may itself be the first red build, so hi = mid.
5. When the range collapses, lo is the index of the first red build, or n.
6. Return -1 for n, otherwise lo + 1 for the build number.

Complexity

Time O(log n) — each probe halves the range, so a million builds cost at most 20 reads. Space O(1) — two indices, and no copy of the archive.

Solution

"""First red build — binary search for the first true entry of a monotone log."""


def solve(nightly):
    """`nightly[i]` is True when build i + 1 passed. Builds are numbered from 1.

    The break is never repaired inside the window, so the log reads
    green...green red...red. Return the number of the first red build, or -1
    when every build in the window passed.
    """
    lo, hi = 0, len(nightly)
    while lo < hi:                 # invariant: the first red build, if any, is in [lo, hi]
        mid = (lo + hi) // 2
        if nightly[mid]:
            lo = mid + 1           # mid is green, so the break is strictly later
        else:
            hi = mid               # mid is red, and may itself be the first one
    # lo == len(nightly) means the window closed with no red build in it.
    return -1 if lo == len(nightly) else lo + 1

TESTS = [
    (([True, True, False, False, False],), 3),
    (([False, False, False],), 1),
    (([True, True, True, True],), -1),
    (([True],), -1),
    (([False],), 1),
    (([True] * 999 + [False],), 1000),
    (([True, False] + [False] * 6,), 2),
]

Pitfalls

• hi = mid - 1 on a red verdict throws away the build you just proved red. The first example then returns 2, a night that was green.
• Starting hi at n - 1 leaves nowhere to express "no red build". An all-green window of four builds reports 4 rather than -1.
• Returning lo instead of lo + 1 mixes the index up with the build number: the first example gives 2, and an all-red window gives 0.

Variants

• Seed tray footprint — a harder problem built on the same refusal to re-check what is already settled.
• The same first-true search becomes interesting when the verdict has to be computed from the input rather than read out of it.