FAILURE MAP
← Case archive

FA-80306 / Typography line breaking / Open access

Balanced headline wrapping: search termination · case 01

Balanced widths come out one column too wide.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The binary search stops when the bounds are adjacent, before testing the lower one.

THE FAILURE

The binary search stops when the bounds are adjacent, before testing the lower one.

Unsuccessful approach: Stopping when bounds differ by two is also premature.

Case contract

Input [words, width]. Let L be the greedy line count at width (["overflow"] if a word is wider). Find the smallest width w (>= longest word) whose greedy wrap needs no more than L lines, then return the greedy wrap at w.

Why this case matters

Line breaking decides where paragraphs wrap on screen and in print; a wrong decision point shifts every following line.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    words, width = x
    def lines_for(w):
        count, cur = 0, -1
        for t in words:
            if len(t) > w:
                return None
            if cur == -1:
                cur = len(t)
                count = 1
            elif cur + 1 + len(t) <= w:
                cur += 1 + len(t)
            else:
                count += 1
                cur = len(t)
        return count
    target = lines_for(width)
    if target is None:
        return ['overflow']
    lo = max(len(t) for t in words)
    hi = width
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        c = lines_for(mid)
        if c is not None and c <= target:
            hi = mid
        else:
            lo = mid + 1
    out, cur = [], ''
    for t in words:
        cand = t if not cur else cur + ' ' + t
        if len(cand) <= lo:
            cur = cand
        else:
            out.append(cur)
            cur = t
    out.append(cur)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('regression: search termination', [['type', 'on', 'the', 'is', 'ink', 'of', 'grid'], 21], ['type on the is', 'ink of grid']), ('regression: search termination', [['the', 'at', 'grid', 'baseline', 'serif'], 29], ['the at grid baseline serif']), ('regression: search termination', [['at', 'x', 'ink', 'at', 'the', 'is'], 5], ['at x', 'ink', 'at', 'the', 'is']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['at', 'serif', 'at', 'measure', 'measure', 'grid'], 21], ['at serif at measure', 'measure grid']), ('control layout', [['at', 'is', 'the', 'ink', 'x', 'measure', 'grid', 'at', 'grid'], 18], ['at is the ink', 'x measure', 'grid at grid']), ('control layout', [['kerning', 'x', 'ink', 'the', 'on', 'grid', 'x', 'grid'], 8], ['kerning', 'x ink', 'the on', 'grid x', 'grid'])], [('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('regression: search termination', [['is', 'on', 'of', 'of', 'serif', 'baseline', 'kerning'], 23], ['is on of of serif', 'baseline kerning']), ('partial-repair probe', [['x', 'x'], 11], ['x x']), ('partial-repair probe', [['serif', 'ink', 'x', 'ink', 'kerning', 'a'], 9], ['serif ink', 'x ink', 'kerning a']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['the', 'a', 'on'], 11], ['the a on']), ('control layout', [['x', 'x', 'the', 'on', 'of'], 15], ['x x the on of']), ('control layout', [['grid', 'the', 'at'], 16], ['grid the at'])], [('regression: search termination', [['baseline', 'is', 'the', 'grid', 'on'], 29], ['baseline is the grid on']), ('regression: search termination', [['of', 'x', 'at', 'grid', 'measure', 'at', 'the', 'at', 'the'], 10], ['of x at', 'grid', 'measure at', 'the at the']), ('partial-repair probe', [['on', 'a', 'measure'], 18], ['on a measure']), ('partial-repair probe', [['on', 'grid', 'a', 'at', 'ink'], 16], ['on grid a at ink']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['x', 'a'], 26], ['x a']), ('control layout', [['of', 'x', 'grid', 'baseline', 'kerning'], 22], ['of x grid', 'baseline kerning'])], [('regression: search termination', [['ink', 'grid', 'ink', 'the', 'grid', 'ink', 'is'], 8], ['ink grid', 'ink the', 'grid ink', 'is']), ('regression: search termination', [['is', 'grid', 'type', 'ink', 'x', 'grid', 'grid'], 16], ['is grid type', 'ink x grid grid']), ('regression: search termination', [['type', 'kerning', 'grid', 'of', 'a'], 20], ['type kerning', 'grid of a']), ('partial-repair probe', [['at', 'at', 'at', 'grid'], 29], ['at at at grid']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['x', 'x', 'the', 'on', 'of'], 15], ['x x the on of']), ('control layout', [['type', 'ink', 'measure', 'the', 'x', 'the'], 23], ['type ink measure', 'the x the'])], [('regression: search termination', [['ink', 'baseline', 'the', 'kerning', 'of', 'kerning'], 18], ['ink baseline the', 'kerning of kerning']), ('regression: search termination', [['of', 'measure', 'x', 'at', 'a', 'on', 'serif', 'on', 'serif'], 20], ['of measure x at a', 'on serif on serif']), ('partial-repair probe', [['kerning', 'measure', 'on', 'a', 'on', 'of', 'of', 'serif', 'type'], 17], ['kerning measure', 'on a on of of', 'serif type']), ('regression: search termination', [['of', 'the', 'ink', 'serif'], 15], ['of the', 'ink serif']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['x', 'kerning', 'serif', 'is', 'baseline', 'baseline', 'on', 'grid'], 17], ['x kerning serif', 'is baseline', 'baseline on grid']), ('control layout', [['x', 'kerning', 'of', 'grid'], 14], ['x kerning', 'of grid'])]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
two balanced lines['the type', 'grid is on', 'serif']['the type grid', 'is on serif']Failed
regression: search termination['type on the', 'is ink of', 'grid']['type on the is', 'ink of grid']Failed
regression: search termination['the at grid baseline', 'serif']['the at grid baseline serif']Failed
regression: search termination['at', 'x', 'ink', 'at', 'the', 'is']['at x', 'ink', 'at', 'the', 'is']Failed
word exactly the width['baseline', 'x']['baseline', 'x']Passed
control layout['at serif at measure', 'measure grid']['at serif at measure', 'measure grid']Passed
control layout['at is the ink', 'x measure', 'grid at grid']['at is the ink', 'x measure', 'grid at grid']Passed
control layout['kerning', 'x ink', 'the on', 'grid x', 'grid']['kerning', 'x ink', 'the on', 'grid x', 'grid']Passed

SHA-256 / e8601b13465c9aa9a01aff437afd59ed7ec0826afc428b6aaa5a8ce58851fe98

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    words, width = x
    def lines_for(w):
        count, cur = 0, -1
        for t in words:
            if len(t) > w:
                return None
            if cur == -1:
                cur = len(t)
                count = 1
            elif cur + 1 + len(t) <= w:
                cur += 1 + len(t)
            else:
                count += 1
                cur = len(t)
        return count
    target = lines_for(width)
    if target is None:
        return ['overflow']
    lo = max(len(t) for t in words)
    hi = width
    while lo + 2 < hi:
        mid = (lo + hi) // 2
        c = lines_for(mid)
        if c is not None and c <= target:
            hi = mid
        else:
            lo = mid + 1
    out, cur = [], ''
    for t in words:
        cand = t if not cur else cur + ' ' + t
        if len(cand) <= lo:
            cur = cand
        else:
            out.append(cur)
            cur = t
    out.append(cur)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('regression: search termination', [['type', 'on', 'the', 'is', 'ink', 'of', 'grid'], 21], ['type on the is', 'ink of grid']), ('regression: search termination', [['the', 'at', 'grid', 'baseline', 'serif'], 29], ['the at grid baseline serif']), ('regression: search termination', [['at', 'x', 'ink', 'at', 'the', 'is'], 5], ['at x', 'ink', 'at', 'the', 'is']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['at', 'serif', 'at', 'measure', 'measure', 'grid'], 21], ['at serif at measure', 'measure grid']), ('control layout', [['at', 'is', 'the', 'ink', 'x', 'measure', 'grid', 'at', 'grid'], 18], ['at is the ink', 'x measure', 'grid at grid']), ('control layout', [['kerning', 'x', 'ink', 'the', 'on', 'grid', 'x', 'grid'], 8], ['kerning', 'x ink', 'the on', 'grid x', 'grid'])], [('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('regression: search termination', [['is', 'on', 'of', 'of', 'serif', 'baseline', 'kerning'], 23], ['is on of of serif', 'baseline kerning']), ('partial-repair probe', [['x', 'x'], 11], ['x x']), ('partial-repair probe', [['serif', 'ink', 'x', 'ink', 'kerning', 'a'], 9], ['serif ink', 'x ink', 'kerning a']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['the', 'a', 'on'], 11], ['the a on']), ('control layout', [['x', 'x', 'the', 'on', 'of'], 15], ['x x the on of']), ('control layout', [['grid', 'the', 'at'], 16], ['grid the at'])], [('regression: search termination', [['baseline', 'is', 'the', 'grid', 'on'], 29], ['baseline is the grid on']), ('regression: search termination', [['of', 'x', 'at', 'grid', 'measure', 'at', 'the', 'at', 'the'], 10], ['of x at', 'grid', 'measure at', 'the at the']), ('partial-repair probe', [['on', 'a', 'measure'], 18], ['on a measure']), ('partial-repair probe', [['on', 'grid', 'a', 'at', 'ink'], 16], ['on grid a at ink']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['x', 'a'], 26], ['x a']), ('control layout', [['of', 'x', 'grid', 'baseline', 'kerning'], 22], ['of x grid', 'baseline kerning'])], [('regression: search termination', [['ink', 'grid', 'ink', 'the', 'grid', 'ink', 'is'], 8], ['ink grid', 'ink the', 'grid ink', 'is']), ('regression: search termination', [['is', 'grid', 'type', 'ink', 'x', 'grid', 'grid'], 16], ['is grid type', 'ink x grid grid']), ('regression: search termination', [['type', 'kerning', 'grid', 'of', 'a'], 20], ['type kerning', 'grid of a']), ('partial-repair probe', [['at', 'at', 'at', 'grid'], 29], ['at at at grid']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['x', 'x', 'the', 'on', 'of'], 15], ['x x the on of']), ('control layout', [['type', 'ink', 'measure', 'the', 'x', 'the'], 23], ['type ink measure', 'the x the'])], [('regression: search termination', [['ink', 'baseline', 'the', 'kerning', 'of', 'kerning'], 18], ['ink baseline the', 'kerning of kerning']), ('regression: search termination', [['of', 'measure', 'x', 'at', 'a', 'on', 'serif', 'on', 'serif'], 20], ['of measure x at a', 'on serif on serif']), ('partial-repair probe', [['kerning', 'measure', 'on', 'a', 'on', 'of', 'of', 'serif', 'type'], 17], ['kerning measure', 'on a on of of', 'serif type']), ('regression: search termination', [['of', 'the', 'ink', 'serif'], 15], ['of the', 'ink serif']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['x', 'kerning', 'serif', 'is', 'baseline', 'baseline', 'on', 'grid'], 17], ['x kerning serif', 'is baseline', 'baseline on grid']), ('control layout', [['x', 'kerning', 'of', 'grid'], 14], ['x kerning', 'of grid'])]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
two balanced lines['the type', 'grid is on', 'serif']['the type grid', 'is on serif']Failed
regression: search termination['type on the', 'is ink of', 'grid']['type on the is', 'ink of grid']Failed
regression: search termination['the at grid baseline', 'serif']['the at grid baseline serif']Failed
regression: search termination['at', 'x', 'ink', 'at', 'the', 'is']['at x', 'ink', 'at', 'the', 'is']Failed
word exactly the width['baseline', 'x']['baseline', 'x']Passed
control layout['at serif at measure', 'measure grid']['at serif at measure', 'measure grid']Passed
control layout['at is the ink', 'x measure', 'grid at grid']['at is the ink', 'x measure', 'grid at grid']Passed
control layout['kerning', 'x ink', 'the on', 'grid x', 'grid']['kerning', 'x ink', 'the on', 'grid x', 'grid']Passed

SHA-256 / 278f1204774fe6cf7bb733aa5d5f33782fa00c5efea26a19e8d63c7faf6b9b95

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

A deterministic toy typesetting model with integer widths and a stipulated rule set; it does not claim conformance to any engine. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:52.803753+00:00.

Case digest / 5197e3e2b64ba9d60fe8fa2da481e5e8dfb78c1ee3c38d89a456e9f5ad68f47a