Solution Verification

The previous lesson showed that a solution fitting the step budget does not make it correct: the candidate spending the fewest steps diverged from the oracle on 18 of 40 inputs. That number 18 came from a corpus already in hand and was never questioned. This lesson does that questioning — which inputs a comparison is run against is as decisive as the comparison itself.

Test-writing discipline, edge-case thinking, and review habits were built in other courses and are not repeated here. What this lesson adds is a single thing: the oracle — counting correctness not against an opinion but against a second solution’s answer.

The Verification Procedure

The procedure has three steps, and their order does not change. First, a set of inputs is generated. Second, both the solution under test and the oracle are run on the same inputs. Third, the inputs on which the two answers differ are counted. The output is a number: diverging inputs. If it is zero, no proof was found in that set; if it is above zero, the solution is wrong and a concrete example is in hand.

• AD11 — The solution under test is two pointers on a sorted array. The precondition holds on every input; this lesson tests not the precondition but the implementation.
• AD12 — Five defective versions are produced by hand, and each defect is a one-line change: the end condition, the starting position, the ending position, the direction of movement, an empty input.
• AD13 — If a version crashes, that too counts as a divergence; a crash is less dangerous than a silent wrong answer, but it is still a divergence.
• AD14 — The random corpus is 40 inputs, each carrying exactly 12 values; the target also comes from the same generator and ranges from $-18$ to $22$.
• AD15 — The edge-case set is 12 inputs and is built by hand: an empty array, one element, two elements, only repeated values, values at the extremes, an unreachable target.

"""Five defective versions, two separate input sets, against the oracle."""
SEED, SECOND = 20260218, 20260219


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


class Counter:
    def __init__(self):
        self.step = 0

    def count(self, n=1):
        self.step += n


def random_corpus(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [(sorted(r(30) - 9 for _ in range(length)), r(41) - 18)
            for _ in range(n)]


EDGE_CASES = [([], 11), ([5], 10), ([5], 5), ([5, 6], 11), ([5, 6], 10),
              ([7, 7], 14), ([-9, -9], -18), ([0, 0, 0], 0), ([-9, 20], 11),
              ([1, 2, 3, 4], 3), ([1, 2, 3, 4], 7), ([2, 2, 2, 2], 4)]


def oracle(array, target, s):
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.count()
            if array[i] + array[j] == target:
                return True
    return False


def pattern_two_pointers(array, target, s, defect=None):
    """defect=None is the correct version. Each defect is one line."""
    left = 1 if defect == "K2" else 0
    right = (len(array) - 2) if defect == "K3" else (len(array) - 1)
    if defect == "K5":
        array[0]                                   # does not account for an empty array
    while (left <= right) if defect == "K1" else (left < right):
        s.count()
        total = array[left] + array[right]
        if total == target:
            return True
        forward = (total > target) if defect == "K4" else (total < target)
        left, right = (left + 1, right) if forward else (left, right - 1)
    return False


DEFECTS = [(None, "correct version"), ("K1", "left <= right"), ("K2", "first element skipped"),
           ("K3", "last element skipped"), ("K4", "directions reversed"),
           ("K5", "empty array uncounted")]


def measure(defect, items):
    diverging, pattern_steps, oracle_steps = 0, 0, 0
    for array, target in items:
        s1, s2 = Counter(), Counter()
        try:
            a = pattern_two_pointers(list(array), target, s1, defect)
        except IndexError:
            a = "crashed"
        b = oracle(list(array), target, s2)
        pattern_steps, oracle_steps = pattern_steps + s1.step, oracle_steps + s2.step
        if a != b:
            diverging += 1
    return diverging, pattern_steps, oracle_steps


R = random_corpus()
print(f"random corpus {len(R)} inputs x 12 values | "
      f"edge case set {len(EDGE_CASES)} inputs")
print("defect                    random  edge  pattern steps  oracle steps")
for k, ad in DEFECTS:
    ar, akr, ahr = measure(k, R)
    ak, akk, ahk = measure(k, EDGE_CASES)
    print(f"{ad:22s}  {ar:8d}  {ak:5d}  {akr + akk:10d}  {ahr + ahk:10d}")
print()
Y = random_corpus(SECOND)
print("second corpus 20260219 , random set:",
      {ad: measure(k, Y)[0] for k, ad in DEFECTS})

random corpus 40 inputs x 12 values | edge case set 12 inputs
defect                    random  edge  pattern steps  oracle steps
correct version                0      0         329        1596
left <= right                  3      2         344        1596
first element skipped          4      5         297        1596
last element skipped           3      5         317        1596
directions reversed           25      2         423        1596
empty array uncounted          0      1         329        1596

second corpus 20260219 , random set: {'correct version': 0, 'left <= right': 2, 'first element skipped': 2, 'last element skipped': 2, 'directions reversed': 27, 'empty array uncounted': 0}

Three numbers side by side. Oracle: 1596 steps across all 52 inputs, correct on every one of them. Pattern: the correct version, 329 steps, that is, 4.85 times fewer than the oracle. Diverging inputs: 0 for the correct version in both sets; between 0 and 25 for the five defective versions.

The table’s real finding is in the last row. With 40 inputs, the random corpus catches four of the five defects and never catches the fifth — the version that does not account for an empty input. The reason is procedural, not bad luck: every input in the corpus carries exactly 12 values, so an empty or single-element input never exists in that set. One defect class is structurally unreachable because of the shape of the input generator, and raising the corpus from 40 to 400 does not change this.

The edge-case set does the opposite: 12 inputs catch all five of the five defects. Yield per input is 4 out of 40 versus 5 out of 12 — 0.1000 against 0.4167. On the other hand, the edge-case set alone is not enough either: it catches the direction-reversed version on only 2 inputs, while the random corpus catches it on 25. The two sets see different defect classes, and neither substitutes for the other.

The second corpus confirms the result: with seed 20260219, the numbers come out 2, 2, 2, 27, 0 — four defects are caught again, the empty-input defect slips through again, and the direction-reversed version’s dominance continues. The diverging-input ratio stays in the same order of magnitude; the result does not depend on the corpus.

Shrinking a Diverging Input

Once a divergence is found, a 12-value array is in hand, and which property of that array triggers the defect is not clear. Shrinking resolves this: a value is removed from the input; if the divergence persists, the smaller form is kept; if not, the value is put back. The operation repeats until no removal preserves the divergence.

• AD16 — Shrinking only removes values; it never adds or changes a value. The result is a subsequence of the starting input.
• AD17 — One attempt means running both the defective version and the oracle once on the candidate input.
• AD18 — Shrinking’s result is locally smallest: it cannot be shrunk further by removing one value. It is not claimed to be the smallest among all possible subsequences.

"""Shrinking a diverging input down to its smallest form."""
from math import comb

SEED = 20260218


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def random_corpus(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [(sorted(r(30) - 9 for _ in range(length)), r(41) - 18)
            for _ in range(n)]


def oracle(array, target):
    return any(array[i] + array[j] == target
               for i in range(len(array)) for j in range(i + 1, len(array)))


def pattern_two_pointers(array, target, defect=None):
    left = 1 if defect == "K2" else 0
    right = (len(array) - 2) if defect == "K3" else (len(array) - 1)
    if defect == "K5":
        array[0]
    while (left <= right) if defect == "K1" else (left < right):
        total = array[left] + array[right]
        if total == target:
            return True
        forward = (total > target) if defect == "K4" else (total < target)
        left, right = (left + 1, right) if forward else (left, right - 1)
    return False


def diverges(array, target, defect):
    try:
        return pattern_two_pointers(list(array), target, defect) != oracle(array, target)
    except IndexError:
        return True


def shrink(array, target, defect):
    """One value is removed; if divergence persists, the removed form is kept."""
    attempts = 0
    progressed = True
    while progressed:
        progressed = False
        for i in range(len(array)):
            candidate = array[:i] + array[i + 1:]
            attempts += 1
            if diverges(candidate, target, defect):
                array, progressed = candidate, True
                break
    return array, attempts


R = random_corpus()
print("defect  first diverging input no  length  shrunk  attempts  smallest input")
for defect in ("K1", "K2", "K3", "K4"):
    for no, (array, target) in enumerate(R, 1):
        if diverges(array, target, defect):
            shrunk, attempts = shrink(array, target, defect)
            print(f"{defect:5s}  {no:20d}  {len(array):7d}  {len(shrunk):8d}"
                  f"  {attempts:6d}  {shrunk} target {target}")
            break
print()
print("number of sorted length-12 inputs (values -9..20):", comb(41, 12))
print("the 52-input set sees", f"{52 / comb(41, 12):.1e}", "of this space")

defect  first diverging input no  length  shrunk  attempts  smallest input
K1                        1       12         1      23  [-8] target -16
K2                       17       12         2      31  [-8, -5] target -13
K3                        7       12         2      21  [-5, 16] target 11
K4                        4       12         3      20  [-3, 18, 20] target 15

number of sorted length-12 inputs (values -9..20): 7898654920
the 52-input set sees 6.6e-09 of this space

All four diverging inputs drop from 12 values to 1, 2, and 3 values, and this happens in 20 to 31 attempts. What shrinking earns is not fewer steps but readability: someone looking at [-3, 18, 20] with target 15 can see directly why the direction-reversed version goes wrong; the same information is hidden inside a 12-value array.

The first row ties the two sections together. The defective version with a broken end condition has a smallest diverging input that is a single-element array: [-8], target $-16$. That single-element input was written by hand in the edge-case set in the previous section. In other words, shrinking spontaneously produces some of the hand-built edge cases — starting from a random 12-value input and arriving at the same place. An edge-case list does not have to be a product of intuition; it can be derived from a diverging input.

Oracle Independence

The whole procedure rests on the oracle’s correctness. If the oracle is wrong, the diverging-input count comes out wrong, and it comes out wrong in the most dangerous direction: zero. If the oracle shares the same blind spot as the solution under test, both give the same wrong answer, and the comparison finds nothing.

• AD19 — The oracle must not be derived from the same idea as the solution under test. Brute force carries this property, because it uses no pattern assumption.
• AD20 — An oracle sharing the same blind spot produces 0 diverging inputs against the solution under test; that zero is not a proof of correctness, it is a sign of dependence.

"""Oracle independence: two solutions sharing the same blind spot give 0 diverging inputs."""
SEED = 20260218


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def random_corpus(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [(sorted(r(30) - 9 for _ in range(length)), r(41) - 18)
            for _ in range(n)]


def scan(array, target):
    return any(array[i] + array[j] == target
               for i in range(len(array)) for j in range(i + 1, len(array)))


def oracle_correct(array, target):
    return scan(array, target)


def oracle_defective(array, target):
    """Same blind spot: the last element is never looked at."""
    return scan(array[:-1], target)


def pattern_defective(array, target):
    """Two pointers never sees the last element."""
    left, right = 0, len(array) - 2
    while left < right:
        total = array[left] + array[right]
        if total == target:
            return True
        left, right = (left + 1, right) if total < target else (left, right - 1)
    return False


def diverging_count(a, b, items):
    return sum(1 for array, target in items if a(array, target) != b(array, target))


R = random_corpus()
print("two solutions compared              diverging inputs / 40")
print("defective pattern  -  correct oracle    ", diverging_count(pattern_defective, oracle_correct, R))
print("defective pattern  -  defective oracle  ", diverging_count(pattern_defective, oracle_defective, R))
print("defective oracle   -  correct oracle    ", diverging_count(oracle_defective, oracle_correct, R))

two solutions compared              diverging inputs / 40
defective pattern  -  correct oracle     3
defective pattern  -  defective oracle   0
defective oracle   -  correct oracle     3

The same defective pattern, on the same 40 inputs, gives 3 against one oracle and 0 against another. The zero in the middle row reads like good news, and it is not: neither the pattern nor the oracle sees the last element, both give the same wrong answer on the same inputs, and the difference the procedure measures goes blind exactly where there is no procedural difference to find. The third row shows that the defective oracle itself is wrong on 3 inputs — the error was there, the measurement could not see it.

This is the measured justification for why brute force remains this course’s oracle. It carries no pattern assumption: it does not assume order, sign, range, or uniqueness. Turning a sped-up version of a pattern into the oracle means carrying the assumption the speedup rests on straight into the measurement.

What Zero Diverging Inputs Proves

The correct version gave 0 diverging inputs in both sets. This does not prove the version is correct, and it cannot be written that way. The last two lines say why not: the number of sorted, length-12 inputs with values between $-9$ and $20$ is 7,898,654,920, and the 52-input set sees 6.6·10^-9 of that space. Considering that the target also takes 41 distinct values, the ratio shrinks further still.

For this reason, verification’s output is two different sentences, and they must not be conflated. If diverging inputs is greater than zero: the solution is wrong, a proof is in hand, and the proof can be made readable by shrinking. If diverging inputs is zero: no defect was found in this set — the defect is not absent, it was not found. The strength of the second sentence grows not with the size of the set but with the defect classes it covers; 40 random inputs could not have caught the empty-input defect even raised to 400, while 12 hand-built inputs caught it in one line.

Summary

• The verification procedure has three steps: generate a corpus, run the oracle on the same inputs, count the inputs where the two answers diverge. The output is a number, not an opinion.
• A 40-input random corpus catches four of five defects; it cannot catch the defect that does not account for an empty input, because every input in the corpus carries exactly 12 values and that defect class is structurally unreachable.
• A 12-input edge-case set catches all five of the five defects; yield per input is 0.1000 against 0.4167. But it catches the direction-reversed version on only 2 inputs, while the random corpus catches it on 25 — the two sets do not substitute for each other.
• The second corpus gives the same result (2, 2, 2, 27, 0). A diverging input drops from 12 values to 1–3 values through single-value removal attempts, taking 20–31 attempts; the broken-end-condition version’s smallest diverging input is [-8], one of the hand-written edge cases.
• If the oracle shares the same blind spot as the solution under test, diverging inputs drops from 3 to 0; that zero is not correctness, it is a sign of dependence. Brute force remains the oracle because it carries no pattern assumption.
• Zero diverging inputs is not proof of correctness: the 52-input set sees 6.6·10^-9 of the 7,898,654,920-input space.

Next Step

Two lessons tied how a solution is chosen and how it is tested to a number. One question remains, and it does not concern a single solution: how does someone doing this work over and over know they are making progress. The next lesson separates the types of practice environments and counts repeated practice’s progress metric over the shared reference’s pattern set. What gets measured is surprising: the number of problems solved is not a progress metric, and why not is counted separately across three environment types.