Using Practice Environments

The previous two lessons concerned a single solution: which pattern is chosen, how it is tested. This lesson carries the question outside a single solution. Practice is repeated work, and repeated work has to have a progress metric, or the work continues without anyone knowing where it is going.

Environments are referred to by type, because what is measured is not the environment itself but the shape of the problem stream it produces. The result comes in two steps: neither the number of problems solved nor how many distinct patterns were seen is a progress metric.

Three Environment Types

In a pool-based practice environment, a large number of problems sit available and the person practicing chooses. Because the choice is free, it drifts toward what is familiar; the pattern distribution reflects the practitioner’s habit. In a timed contest environment, the environment determines the set and the practitioner has to see all of it; the set is small. In an in-house assessment, the number of problems is smallest, the distribution is again not chosen by the practitioner, and the inputs are not prepared in advance.

• AD21 — The pattern set is the shared reference’s five patterns: two pointers, sliding window, greedy, backtracking, memoization. These are the patterns measured throughout the course.
• AD22 — A round is one practice session spent in an environment. Problems per round are fixed by environment type: pool 24, contest 5, assessment 2. Six rounds are measured.
• AD23 — In the pool-based environment, choice weights are 50, 30, 10, 6, 4; in the other two environments the distribution is even. The weight models the practitioner’s tendency to return to a familiar pattern.
• AD24 — Choice is made with the shared reference’s deterministic generator; random is not used.
• AD25 — The balance ratio is the count of the least-seen pattern divided by its share under an even distribution. If all five patterns were seen equally, the ratio would be 1.0000.

"""Pattern diversity across three environment rounds, over the shared reference's five patterns."""
SEED, SECOND = 20260218, 20260219
PATTERNS = ["two pointers", "sliding window", "greedy", "backtracking", "memoization"]
ENVIRONMENTS = [("pool-based practice     ", 24, [50, 30, 10, 6, 4]),
                ("timed contest           ", 5, [20, 20, 20, 20, 20]),
                ("in-house assessment     ", 2, [20, 20, 20, 20, 20])]


def generator(seed):
    d = seed

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


def choose(r, weights):
    x = r(sum(weights))
    for i, w in enumerate(weights):
        if x < w:
            return i
        x -= w
    return len(weights) - 1


def metrics(counts):
    total = sum(counts)
    fair_share = total / len(counts)
    return {"problems": total, "covered": sum(1 for c in counts if c),
            "balance": round(min(counts) / fair_share, 4),
            "top_two": round(sum(sorted(counts)[-2:]) / total, 4)}


def run(seed, rounds=6):
    print(f"seed {seed} , {rounds} rounds")
    print("environment               problems  covered  balance  top two  distribution")
    for ad, per_round, weights in ENVIRONMENTS:
        r = generator(seed)
        counts = [0] * len(PATTERNS)
        for _ in range(rounds * per_round):
            counts[choose(r, weights)] += 1
        o = metrics(counts)
        print(f"{ad}  {o['problems']:7d}  {o['covered']:8d}  {o['balance']:6.4f}"
              f"  {o['top_two']:7.4f}  {counts}")


run(SEED)
print()
run(SECOND)
print()
print("pool-based environment , cumulative round by round (seed 20260218)")
print("round  problems  covered  balance  top two")
r = generator(SEED)
counts = [0] * len(PATTERNS)
for t in range(1, 7):
    for _ in range(24):
        counts[choose(r, ENVIRONMENTS[0][2])] += 1
    o = metrics(counts)
    print(f"{t:3d}  {o['problems']:7d}  {o['covered']:8d}  {o['balance']:6.4f}"
          f"  {o['top_two']:7.4f}")

seed 20260218 , 6 rounds
environment               problems  covered  balance  top two  distribution
pool-based practice           144         5  0.2431   0.7986  [64, 51, 11, 11, 7]
timed contest                  30         5  0.6667   0.5000  [4, 5, 9, 6, 6]
in-house assessment            12         5  0.4167   0.5833  [1, 4, 3, 2, 2]

seed 20260219 , 6 rounds
environment               problems  covered  balance  top two  distribution
pool-based practice           144         5  0.1389   0.8194  [76, 42, 16, 6, 4]
timed contest                  30         5  0.6667   0.5667  [8, 4, 9, 4, 5]
in-house assessment            12         5  0.4167   0.6667  [1, 1, 5, 2, 3]

pool-based environment , cumulative round by round (seed 20260218)
round  problems  covered  balance  top two
  1       24         4  0.0000   0.8333
  2       48         5  0.2083   0.7917
  3       72         5  0.2778   0.7639
  4       96         5  0.2604   0.7500
  5      120         5  0.2500   0.7750
  6      144         5  0.2431   0.7986

The first table refutes two metrics at once. The pool-based environment solves 144 problems, the timed contest 30, the in-house assessment 12 — a 12-times difference. Yet the count of covered patterns is 5 in all three: “how many problems did I solve” swings 12 times over; “how many distinct patterns did I see” does not move at all.

The metric that distinguishes them is the distribution. In the pool the balance ratio is 0.2431: the least-seen pattern gets under a quarter of its even-distribution share, and the two most-seen patterns cover 0.7986 of the problems. The timed contest gives 0.6667 with 30 problems — 2.74 times more balanced on five times fewer. The in-house assessment’s 0.4167 comes not from the distribution but from the smallness of the sample.

The third table is the lesson’s most contrarian result. In the pool-based environment, coverage rises to 5 in the second round and never changes again: the 72 problems solved from round three to round six add nothing to it. The balance ratio peaks at 0.2778 in the third round and then falls — 0.2604 in the fourth, 0.2431 in the sixth. As problem count rises, the progress metric declines, because every added problem goes to the two dominant patterns.

The second corpus confirms the ranking: at seed 20260219 the pool gives 0.1389, the contest 0.6667, the assessment 0.4167. The pool’s value drops from 0.2431 to 0.1389 — the absolute value depends on the corpus — but the ordering of the three environments and the size of the gap between pool and contest run the same way on both.

Does the Environment Show the Error

Distribution alone is not enough either. Applying a pattern fifty times does not show what it does when its precondition breaks — the shared reference’s first reading already proved this: two pointers matches the oracle on 40 of 40 inputs when the precondition holds, so someone practicing on inputs that satisfy it never sees the pattern’s wrongness.

What is measured here is the environment’s mix: what percentage of the inputs satisfy the precondition, and how that ratio changes the number of wrong answers seen. Two selection policies are compared.

• AD26 — In the pool-based environment, 90 percent of inputs satisfy the precondition; in the timed contest, 75 percent; in the in-house assessment, 50 percent. In the pool, problems are prepared according to the pattern; in the assessment, the input arrives as it is.
• AD27 — Habitual selection applies the most-practiced pattern to every problem and never tests the precondition.
• AD28 — Precondition-checked selection first checks whether the input is sorted; if it is not, it does not apply the pattern and falls back to the oracle. The check is at most $n-1$ steps and stops at the first out-of-order pair.
• AD29 — 40 problems are solved in each environment, and the target is 11.

"""Two selection policies, against the oracle, across a mix of three environments."""
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 mix(sorted_ratio, seed=SEED, n=40, length=12):
    """sorted_ratio: what percentage of inputs satisfy the precondition."""
    r = generator(seed)
    items = []
    for _ in range(n):
        array = [r(30) - 9 for _ in range(length)]
        items.append(sorted(array) if r(100) < sorted_ratio else array)
    return items


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_two_pointers(array, target, s):
    left, right = 0, len(array) - 1
    while left < right:
        s.count()
        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 habitual_selection(array, target, s):
    """Applies the most-practiced pattern to every problem."""
    return pattern_two_pointers(array, target, s)


def precondition_checked_selection(array, target, s):
    """Tests the precondition first; falls back to the oracle if it does not hold."""
    for i in range(len(array) - 1):
        s.count()
        if array[i] > array[i + 1]:
            return oracle_pairs(array, target, s)
    return pattern_two_pointers(array, target, s)


def measure(policy, items, target=11):
    diverging, policy_steps, oracle_steps = 0, 0, 0
    for array in items:
        s1, s2 = Counter(), Counter()
        a = policy(list(array), target, s1)
        b = oracle_pairs(list(array), target, s2)
        policy_steps, oracle_steps = policy_steps + s1.step, oracle_steps + s2.step
        if a != b:
            diverging += 1
    return diverging, policy_steps, oracle_steps


ENVIRONMENTS = [("pool-based practice     ", 90), ("timed contest           ", 75),
                ("in-house assessment     ", 50)]

for seed in (SEED, SECOND):
    print(f"seed {seed} , 40 problems per environment , target 11")
    print("environment               sorted  habitual        precondition check   oracle")
    print("                          inputs  diverging  step  diverging  step      step")
    for ad, ratio in ENVIRONMENTS:
        K = mix(ratio, seed)
        s = sum(1 for d in K if d == sorted(d))
        a1, k1, h1 = measure(habitual_selection, K)
        a2, k2, _ = measure(precondition_checked_selection, K)
        print(f"{ad}  {s:6d}  {a1:7d}  {k1:4d}   {a2:7d}  {k2:4d}      {h1:4d}")
    print()

seed 20260218 , 40 problems per environment , target 11
environment               sorted  habitual        precondition check   oracle
                          inputs  diverging  step  diverging  step      step
pool-based practice           34        5   165         0   600       834
timed contest                 29        8   199         0   681       914
in-house assessment           17       15   255         0   754       856

seed 20260219 , 40 problems per environment , target 11
environment               sorted  habitual        precondition check   oracle
                          inputs  diverging  step  diverging  step      step
pool-based practice           36        2   213         0   609      1055
timed contest                 31        4   238         0   691      1079
in-house assessment           22       10   296         0   823      1161

Three numbers side by side. Oracle: 834 steps in the pool mix, correct on 40 of 40 inputs. Pattern: habitual selection 165 steps, precondition-checked selection 600 steps. Diverging inputs: habitual selection gives 5 in the pool, 8 in the contest, 15 in the assessment; the precondition check gives 0 in all three.

The first reading concerns the environment. Same policy, same pattern, same problem count — yet the wrong answers it sees rise from 5 to 15, three times over. The cause is the environment’s input mix: 34 of 40 pool inputs satisfy the precondition, against 17 in the assessment. Working with prepared inputs means seeing a pattern’s wrongness less, and seeing it less is not the same as fixing it.

The second reading concerns the policy. The precondition check gives 0 diverging inputs in all three environments; the cost is rising from 165 to 600 steps in the pool mix, that is, 3.64 times. It still stays below the oracle’s 834 steps: correctness is bought not at brute force’s price, but at 72 percent of it. The second corpus gives the same ranking (2, 4, 10) and the same 0 diverging inputs; the absolute numbers depend on the corpus, the ranking does not.

What follows is repeated practice’s progress metric, made of three numbers: how many patterns were seen, the distribution’s balance ratio, and how many were seen with their precondition broken. Problems solved gives none of these three.

Summary

• Environments separate by type: in pool-based practice the practitioner chooses the distribution; in the timed contest and in-house assessment the environment chooses and the set is small.
• The number of problems solved separates the environments by a factor of 12 (144, 30, 12), but the covered-pattern count is 5 in all three; neither metric shows progress.
• The distinguishing metric is the distribution: in the pool the balance ratio is 0.2431 and the two dominant patterns cover 0.7986 of the problems; the timed contest gives 0.6667 with five times fewer problems.
• Coverage rises to 5 in the second round and freezes; the balance ratio peaks at 0.2778 in the third round and then declines to 0.2431 — adding problems can make the metric worse.
• The environment’s input mix determines how much wrongness is seen: the same policy produces 5, 8, and 15 diverging inputs in the pool, contest, and assessment.
• Precondition-checked selection gives 0 diverging inputs in all three environments; its cost rises from 165 to 600 steps, 72 percent of the oracle’s 834.

Course Wrap-Up

Twenty-three lessons asked a single question: what does choosing a pattern mean accepting. Every lesson answered with three numbers. The oracle was always brute force and always correct — but not always expensive: the Longest Path Problem lesson measured the oracle at 562 steps against the pattern’s 3626 on eight vertices, and showed the threshold sits at ten. The pattern usually spent fewer steps. Diverging inputs counted how many inputs the pattern answered differently than the oracle. The course’s rule: a pattern’s number is not the steps it saves, but how many wrong answers it gives once its precondition breaks.

Lesson	Oracle (steps)	Pattern (steps)	Diverging inputs / cost
Brute Force	exhaustive count 2640	early exit 866	early exit 0; sampling 14 at 406
Divide and Conquer	3120	linear combine step 2680	0; incomplete combine step 40/40 at 920
Greedy Algorithms	bottom-up	greedy	827 of 969 systems (0.8535); largest excess 16 coins
Dynamic Programming	163,840	full-key memoization 2440 (67.15 times fewer)	0; missing key 39/40; with no overlap, 19 memo entries wasted
Backtracking	without pruning 960,800 nodes, n=7	with pruning 552 nodes	1740.6 times, ratio grows with n (72.3 → 8156.2); over-pruning gives 0 solutions
Randomization	780	verified sampling 944–1056	0; unverified, at 200, 40/40 once the precondition breaks
Two Pointers	972	154 (6.31 times fewer)	25/40 unsorted, speedup drops to 2.33 times
Sliding Window	2396	867 (2.76 times fewer)	10/40 with negatives, in fewer steps
Fast and Slow Pointer	480	299	14/40 on the second edge case; steps never change
Interval Merging	sorting by start: 40/40 correct	2154	29/40 sorting by end, 40/40 by length and unsorted
Cyclic Sort	1..n, no duplicates	comparison-free	with duplicates, plain 40/40; guarded 39/40; missing case 0/40
Two Heaps	480 median	with rebalancing step 1261	unbalanced 295/480 wrong; rebalancing is more than half the pattern (1261/550)
K-th Element	four k values x 40 inputs	k-sized heap	0/40; “k-th distinct value” is a separate question: 27/40
Grid Traversal	same connectivity 40/40	connected component	38/40 once the definitions diverge
Knapsack	fractional variant 100,800	greedy 174	fractional 0/40; the same order in 0/1 gives 5/40, loss 7
Travelling Salesman	352,800 (20 samples)	nearest neighbor 560	17/20; average deviation 9.3, worst 33.33; two-opt 2/20
Longest Path	acyclic 40/40	relaxation procedure	with a cycle 38/40; largest overestimate 228
N Queens	with pruning 2057 nodes, n=8	with symmetry breaking 1029	ratio 2.00, constant across five sizes; pruning’s grows, symmetry’s does not
Knight’s Tour and Maze	path model 90,111	cell model 25	ratio 3604, diverging 0
Hamiltonian Paths	counting 29,270	decision 1526	ratio 19.18; in every case with no path, decision = counting
Problem Reading and Constraint	866	hash table 486, sorting pattern 1398, counting 396	the wrong constraint reading diverges on 18 of 40 inputs (17 on the second corpus); at n=10<sup>8</sup> none of the three solutions fit the budget
Solution Verification	brute force, 1596 across 52 inputs	correct two pointers 329	40 random inputs catch 4 of 5 defects, 12 edge cases catch all 5; against an oracle sharing the same defect, diverging drops from 3 to 0
Practice Environments	834	habitual selection 165, precondition check 600	5 diverging in the pool, 8 in the contest, 15 in the assessment; precondition check gives 0 diverging but 3.64 times the steps

The table’s second reading matters more than its first: speedup brings a pattern closer to being wrong, and sometimes it does not even speed things up. Two pointers’ speedup drops to 2.33 times on an unsorted input while it is wrong on 25 inputs; greedy over-answers on 827 of 969 systems; memoization wastes 19 entries with no overlap. None of this was hidden: not knowing when a pattern goes wrong means not knowing when to choose it.

The third and lasting result concerns the oracle itself: brute force is not a baseline, it is an oracle. Every number in the course was written because of it. In the final lesson this became a habit: counting correctness against a second solution’s answer, not an opinion.

The next course, Theory of Computation, takes up the question left in the oracle’s shadow. The traveling salesman and Hamiltonian paths lessons explicitly deferred “why is this problem hard.” What will be asked there is whether not knowing anything better than brute force is, for some problems, a fact about our knowledge or about the problems themselves. The answer comes through decidability, reduction, and complexity classes.