Problem Reading and Constraint Analysis

The previous topic worked with named problems: the knapsack, the traveling salesman, n queens. The shape of these problems was given; the question asked was which approach solved them. In practice the situation is reversed. There is a piece of text in hand, a few numbers appear inside it, and which pattern is suitable is never stated. What selects the pattern is not the problem’s name but its constraints.

This lesson turns constraint reading into a procedure and measures where that procedure works and where it turns into guessing. The result runs two ways: input size genuinely eliminates large families of solutions, but it does not choose among the ones that remain — and when a constraint is misread, the solution that emerges can be the cheapest of all of them, and still be wrong.

From Input Size to a Step Budget

Constraint reading is a single calculation: the largest input size in the problem text is taken, an upper bound is placed on the number of steps that can be spent at that size, and each candidate solution’s fit within that bound is computed. The bound is called the step budget. Asymptotic notation itself was built in the Algorithm Analysis topic of the Algorithms course and is not repeated here; what happens here is turning the notation into a decision criterion.

• AD1 — The step budget is the most steps a solution can spend and still count as acceptable. In this lesson the budget is 10⁸ steps and is taken as a constant.
• AD2 — The budget is computed over the worst case. An average input does not enter the calculation; the purpose of the calculation is to eliminate a solution, not to praise one.
• AD3 — A lookup in a hash table is one step, an insertion is one step. Both are constant.
• AD4 — A sort’s step count is the actual number of comparisons made, and it is measured by counting them. The sorting algorithms themselves were built in the Algorithms course and are used here.
• AD5 — The worst-case input is produced like this: every value is even, the target is odd. Then no pair can give the target, and every solution is forced to run to the end.

The problem is this: does an array contain two distinct positions whose sum equals the target. There are three candidates. Brute force tries every pair; it is this course’s oracle. The second candidate sorts the array and scans it with two pointers. The third keeps a hash table in a single pass.

"""How the step count of three solutions to the same problem behaves on the worst-case input."""
from functools import cmp_to_key

SEED = 20260218


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 worst_case_input(n, seed=SEED):
    """All values even, target odd: no pair can give the target."""
    array = [2 * i for i in range(n)]
    r = generator(seed)
    for i in range(n - 1, 0, -1):
        j = r(i + 1)
        array[i], array[j] = array[j], array[i]
    return array


def oracle_pairs(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_sort_two_pointer(array, target, s):
    def compare(a, b):
        s.count()
        return -1 if a < b else (1 if a > b else 0)
    sorted_array = sorted(array, key=cmp_to_key(compare))
    left, right = 0, len(sorted_array) - 1
    while left < right:
        s.count()
        total = sorted_array[left] + sorted_array[right]
        if total == target:
            return True
        left, right = (left + 1, right) if total < target else (left, right - 1)
    return False


def pattern_hash_table(array, target, s):
    seen = set()
    for x in array:
        s.count()
        if target - x in seen:
            return True
        s.count()
        seen.add(x)
    return False


print("n      brute force   sort+two pointer   hash table")
for n in (4, 8, 32, 128, 512, 2048):
    d = worst_case_input(n)
    s1, s2, s3 = Counter(), Counter(), Counter()
    oracle_pairs(d, 7, s1)
    pattern_sort_two_pointer(d, 7, s2)
    pattern_hash_table(d, 7, s3)
    print(f"{n:5d}  {s1.step:11d}  {s2.step:19d}  {s3.step:11d}")
print()
for ad, pattern in (("sort+two pointer", pattern_sort_two_pointer),
                    ("hash table      ", pattern_hash_table)):
    for n in range(2, 40):
        d = worst_case_input(n)
        s1, s2 = Counter(), Counter()
        oracle_pairs(d, 7, s1)
        pattern(d, 7, s2)
        if s2.step < s1.step:
            print(f"{ad} first n where it beats brute force: {n}"
                  f"  (pattern {s2.step} , oracle {s1.step})")
            break

n      brute force   sort+two pointer   hash table
    4            6                   10            8
    8           28                   22           16
   32          496                  152           64
  128         8128                  861          256
  512       130816                 4483         1024
 2048      2096128                22015         4096

sort+two pointer first n where it beats brute force: 8  (pattern 22 , oracle 28)
hash table       first n where it beats brute force: 6  (pattern 12 , oracle 15)

The table’s first row is constraint reading’s most overlooked result: at n=4, brute force is the cheapest of the three solutions — 6 steps, against the hash table’s 8 and the sorting pattern’s 10. The sorting pattern only becomes cheaper than the oracle at n=8, the hash table at n=6. Brute force is not a poor choice at small input sizes; what is poor is choosing it without knowing at which size it stops being one.

Budget Calculation at Four Input Sizes

The measurement above goes up to 2048, but constraint reading has to make a decision up to 10⁸, and actually running brute force at that size is not an option. For this reason the budget calculation is done with a formula validated against the measured count: first it is checked whether the formula holds at small n, then the formula is carried to large n.

• AD6 — Brute force’s worst-case step count is estimated as $n(n-1)/2$, the hash table’s as $2n$, the sorting pattern’s as $n\log_2 n + n$.
• AD7 — A formula can be used in the budget calculation only as long as it does not fall below the measured step count. A formula that understates is not accepted.

"""Does the estimate formula hold against the measured step count, and the budget
calculation at four input sizes."""
from math import log2

MEASURED = {8: (28, 22, 16), 32: (496, 152, 64), 128: (8128, 861, 256),
            512: (130816, 4483, 1024), 2048: (2096128, 22015, 4096)}
BUDGET = 10 ** 8


def estimate(n):
    return (n * (n - 1) // 2, int(n * log2(n)) + n, 2 * n)


print("n      brute force         sort+two pointer        hash table")
print("       measured  estimate  m/e   measured  estimate  m/e   measured  estimate")
for n, (a, b, c) in MEASURED.items():
    ta, tb, tc = estimate(n)
    print(f"{n:5d}  {a:7d}  {ta:6d}  {a / ta:.2f}  {b:8d}  {tb:6d}  {b / tb:.2f}"
          f"  {c:8d}  {tc:6d}")
print()
print(f"step budget: {BUDGET}")
print("n            brute force     sort+two pointer   hash table")
for n in (10 ** 3, 10 ** 5, 10 ** 6, 10 ** 8):
    ta, tb, tc = estimate(n)
    d = [("fits" if t <= BUDGET else "no fit") for t in (ta, tb, tc)]
    print(f"{n:<11d}  {ta:.2e} {d[0]:6s}  {tb:.2e} {d[1]:6s}  {tc:.2e} {d[2]:6s}")

n      brute force         sort+two pointer        hash table
       measured  estimate  m/e   measured  estimate  m/e   measured  estimate
    8       28      28  1.00        22      32  0.69        16      16
   32      496     496  1.00       152     192  0.79        64      64
  128     8128    8128  1.00       861    1024  0.84       256     256
  512   130816  130816  1.00      4483    5120  0.88      1024    1024
 2048  2096128  2096128  1.00     22015   24576  0.90      4096    4096

step budget: 100000000
n            brute force     sort+two pointer   hash table
1000         5.00e+05 fits    1.10e+04 fits    2.00e+03 fits  
100000       5.00e+09 no fit  1.76e+06 fits    2.00e+05 fits  
1000000      5.00e+11 no fit  2.09e+07 fits    2.00e+06 fits  
100000000    5.00e+15 no fit  2.76e+09 no fit  2.00e+08 no fit

The top table confirms the formula. For brute force, measured and estimated are identical (ratio 1.00); the same for the hash table. For the sorting pattern the ratio rises from 0.69 to 0.90: the formula overstates the true comparison count at every n, that is, it errs on the safe side, satisfying AD7. The amount of overstatement is not constant — at small n the estimate is 1.45 times the measurement, at n=2048 it is 1.12 times. This is the point where constraint reading turns into guessing: the formula used carries a coefficient, and until that coefficient is measured, the budget calculation is a guess.

The bottom table is the four sizes this lesson asked for. At n=1,000, all three solutions fit the budget; constraint reading eliminates nothing here, and the choice is left to another criterion. At n=100,000, brute force is eliminated at 5.00·10⁹ steps, leaving two candidates. At n=1,000,000 the table stays the same. At n=10⁸, none of the three fit — even the hash table, the cheapest, asks for 2.00·10⁸ steps, twice the budget. This last row is constraint reading’s most useful output: if not even a single-pass solution fits at that size, the problem text must be giving another constraint, and it has not been read.

When a Constraint Is Misread

The entire calculation above assumed one thing: that all three candidates give the correct answer. Until that assumption is tested, the budget calculation cannot select a solution. The course’s rule applies here as well — a pattern whose precondition is not tested against the oracle is not considered measured.

A fourth candidate is added. Someone who thinks the problem text says “values do not exceed 20” can keep an array marking the range 0..20 and answer in a single pass. What was missed is that the text does not state a lower bound, and values can be negative.

• AD8 — The corpus is the shared reference’s corpus: 40 inputs, each with 12 values, values ranging from −9 to 20. The target is 11.
• AD9 — The wrong constraint reading silently skips an out-of-range value; it does not crash, it returns an answer.
• AD10 — The second corpus is produced with seed 20260219, and whether the diverging-input ratio stays in the same order of magnitude is written down.

"""The budget calculation does not choose the pattern, the oracle does. Two corpora."""
from functools import cmp_to_key

SEED, SECOND, LENGTH, CORPUS_SIZE = 20260218, 20260219, 12, 40


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 corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    r = generator(seed)
    return [{"no": i + 1, "array": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


def oracle_pairs(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_sort_two_pointer(array, target, s):
    def compare(a, b):
        s.count()
        return -1 if a < b else (1 if a > b else 0)
    sorted_array = sorted(array, key=cmp_to_key(compare))
    left, right = 0, len(sorted_array) - 1
    while left < right:
        s.count()
        total = sorted_array[left] + sorted_array[right]
        if total == target:
            return True
        left, right = (left + 1, right) if total < target else (left, right - 1)
    return False


def pattern_hash_table(array, target, s):
    seen = set()
    for x in array:
        s.count()
        if target - x in seen:
            return True
        s.count()
        seen.add(x)
    return False


def pattern_counting_array(array, target, s, upper=20):
    """WRONG CONSTRAINT READING: values are assumed to be in the range 0..upper."""
    present = [False] * (upper + 1)
    for x in array:
        s.count()
        if 0 <= x <= upper:
            complement = target - x
            if 0 <= complement <= upper and present[complement]:
                return True
            present[x] = True
    return False


def measure(pattern, items, target):
    diverging, pattern_steps, oracle_steps = [], 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        a = pattern(k["array"], target, s1)
        b = oracle_pairs(k["array"], target, s2)
        pattern_steps, oracle_steps = pattern_steps + s1.step, oracle_steps + s2.step
        if a != b:
            diverging.append(k["no"])
    return {"diverging": len(diverging), "first_diverging": diverging[:5],
            "pattern_step": pattern_steps, "oracle_step": oracle_steps}


for seed in (SEED, SECOND):
    print(f"corpus seed {seed} , 40 inputs x 12 values , target 11")
    K = corpus(seed)
    for ad, pattern in (("sort+two pointer", pattern_sort_two_pointer),
                        ("hash table          ", pattern_hash_table),
                        ("counting (wrong constraint)", pattern_counting_array)):
        print(f"  {ad}", measure(pattern, K, 11))
    print()

corpus seed 20260218 , 40 inputs x 12 values , target 11
  sort+two pointer {'diverging': 0, 'first_diverging': [], 'pattern_step': 1398, 'oracle_step': 866}
  hash table           {'diverging': 0, 'first_diverging': [], 'pattern_step': 486, 'oracle_step': 866}
  counting (wrong constraint) {'diverging': 18, 'first_diverging': [4, 10, 13, 14, 15], 'pattern_step': 396, 'oracle_step': 866}

corpus seed 20260219 , 40 inputs x 12 values , target 11
  sort+two pointer {'diverging': 0, 'first_diverging': [], 'pattern_step': 1441, 'oracle_step': 970}
  hash table           {'diverging': 0, 'first_diverging': [], 'pattern_step': 566, 'oracle_step': 970}
  counting (wrong constraint) {'diverging': 17, 'first_diverging': [3, 4, 6, 7, 8], 'pattern_step': 391, 'oracle_step': 970}

Three numbers side by side. Oracle: 866 steps, correct on 40 of 40 inputs. Patterns: the hash table 486 steps, the sorting pattern 1398 steps, the wrong constraint reading 396 steps. Diverging inputs: 0 for the first two, 18 for the wrong reading — that is, a different answer than the oracle on 18 of 40 inputs, a ratio of 0.4500.

The result says two things. First, step-count ranking is not correctness ranking: the candidate that spends the fewest steps (396) is exactly the one that gives the wrong answer. Second, at n=12 the sorting pattern is 1.61 times costlier than the oracle (1398 against 866). The budget calculation had selected this pattern for large n; at the actual input size of 12, that same choice is worse than the oracle. The budget calculation is a tool for elimination, not a tool for selection.

The second corpus confirms the result: diverging inputs drop from 18 to 17 (ratio 0.4250), staying in the same order of magnitude; the two correct patterns give 0 diverging inputs there as well. The shared reference’s first reading had already shown two pointers to be wrong on 25 of 40 inputs on an unsorted input; the 18 here is the constraint-reading side of the same rule — the pattern is correct, the reading is not.

Summary

• Constraint reading is the operation of deriving a step budget from input size and eliminating candidates with it; in this lesson the budget is 10⁸ steps and the calculation is always done over the worst case.
• Measurement vindicates brute force at small input: at n=4, the cheapest of the three solutions is brute force with 6 steps; the hash table only beats it at n=6, the sorting pattern at n=8.
• The budget leaves a different number of candidates at four sizes: at n=1,000 all three fit, at n=100,000 and n=1,000,000 brute force is eliminated, at n=10⁸ none fit — even the hash table asks for 2.00·10⁸ steps.
• Until a formula is validated against measurement, the budget calculation is a guess: for the sorting pattern the estimate is 1.45 times the measurement at n=8, 1.12 times at n=2048; for brute force and the hash table the ratio is exactly 1.00.
• Comparison against the oracle says what the budget calculation cannot: the candidate spending the fewest steps (396 steps) gives the wrong answer on 18 of 40 inputs, 17 on the second corpus; the two correct patterns give 0 diverging inputs on both corpora.
• At the real input size, budget ranking can reverse: at n=12 the sorting pattern is 1.61 times costlier than the oracle. The budget calculation eliminates, it does not select.

Next Step

In this lesson the oracle was used once, and it caught a wrong constraint reading on 18 inputs. But those 18 inputs came from a corpus already in hand; a different corpus would have caught a different number. The next lesson takes up exactly this dependency: which inputs should a solution be compared against the oracle on, how many times do edge cases show up in a randomly generated corpus, and once a diverging input is found, how is it shrunk down to its smallest form. The measure remains a count: how many of the deliberately broken versions are caught by which corpus.