FA-80286 / Typography line breaking / Open access
Balanced headline wrapping: line count target · case 01
Balancing collapses to the original ragged wrap.
ROOT CAUSE
The search demands strictly fewer lines than the greedy wrap.
VERIFIED REPAIR
Accept widths that keep the same line count.
Unsuccessful approach: Allowing one extra line makes the headline taller.
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 < 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: line count target', [['the', 'type', 'of', 'kerning', 'at', 'measure', 'ink', 'of', 'grid'], 17], ['the type of', 'kerning at', 'measure ink', 'of grid']), ('partial-repair probe', [['grid', 'serif', 'type', 'on', 'on'], 26], ['grid serif type on on']), ('partial-repair probe', [['measure', 'measure', 'of', 'a', 'on', 'at'], 11], ['measure', 'measure of', 'a on at']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['kerning', 'baseline'], 13], ['kerning', 'baseline']), ('control layout', [['grid', 'baseline', 'at', 'type', 'at', 'is', 'baseline', 'is'], 6], ['overflow']), ('control layout', [['grid', 'is', 'kerning', 'grid'], 10], ['grid is', 'kerning', 'grid'])], [('regression: line count target', [['is', 'grid', 'type', 'ink', 'x', 'grid', 'grid'], 16], ['is grid type', 'ink x grid grid']), ('regression: line count target', [['grid', 'baseline', 'grid', 'measure', 'x', 'is'], 20], ['grid baseline', 'grid measure x is']), ('partial-repair probe', [['grid', 'is', 'type', 'ink', 'serif', 'x'], 25], ['grid is type ink serif x']), ('partial-repair probe', [['a', 'of', 'is'], 27], ['a of is']), ('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', [['baseline', 'kerning', 'ink', 'is', 'baseline'], 10], ['baseline', 'kerning', 'ink is', 'baseline']), ('control layout', [['x', 'of', 'kerning', 'ink'], 9], ['x of', 'kerning', 'ink'])], [('regression: line count target', [['a', 'measure', 'serif', 'x', 'at', 'a', 'serif'], 23], ['a measure serif', 'x at a serif']), ('regression: line count target', [['measure', 'serif', 'at', 'at', 'kerning', 'x'], 23], ['measure serif', 'at at kerning x']), ('regression: line count target', [['grid', 'grid', 'on', 'measure', 'measure', 'of', 'grid'], 19], ['grid grid on', 'measure measure', 'of grid']), ('regression: line count target', [['type', 'measure', 'baseline', 'type', 'a'], 25], ['type measure', 'baseline type a']), ('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', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('control layout', [['kerning', 'on', 'the'], 9], ['kerning', 'on the'])], [('regression: line count target', [['grid', 'grid', 'measure', 'x'], 18], ['grid grid', 'measure x']), ('regression: line count target', [['is', 'measure', 'the', 'grid', 'is', 'a', 'kerning', 'baseline'], 22], ['is measure the grid', 'is a kerning baseline']), ('partial-repair probe', [['at', 'a', 'ink', 'at', 'ink'], 20], ['at a ink at ink']), ('partial-repair probe', [['baseline', 'grid', 'type', 'kerning', 'grid'], 10], ['baseline', 'grid type', 'kerning', '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', 'baseline', 'a', 'measure', 'is'], 5], ['overflow']), ('control layout', [['is', 'ink', 'on', 'serif', 'serif', 'baseline', 'ink', 'baseline', 'baseline'], 5], ['overflow'])], [('regression: line count target', [['ink', 'grid', 'serif', 'type', 'baseline', 'the', 'baseline'], 29], ['ink grid serif type', 'baseline the baseline']), ('regression: line count target', [['x', 'on', 'measure', 'baseline', 'on', 'the'], 23], ['x on measure', 'baseline on the']), ('partial-repair probe', [['the', 'of', 'ink', 'ink', 'grid', 'is'], 27], ['the of ink ink grid is']), ('partial-repair probe', [['the', 'of', 'the', 'baseline'], 28], ['the of the baseline']), ('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', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('control layout', [['kerning', 'the'], 6], ['overflow'])]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| two balanced lines | ['the type grid is on', 'serif'] | ['the type grid', 'is on serif'] | Failed |
| regression: line count target | ['the type of', 'kerning at', 'measure ink of', 'grid'] | ['the type of', 'kerning at', 'measure ink', 'of grid'] | Failed |
| partial-repair probe | ['grid serif type on on'] | ['grid serif type on on'] | Passed |
| partial-repair probe | ['measure', 'measure of', 'a on at'] | ['measure', 'measure of', 'a on at'] | Passed |
| word exactly the width | ['baseline', 'x'] | ['baseline', 'x'] | Passed |
| control layout | ['kerning', 'baseline'] | ['kerning', 'baseline'] | Passed |
| control layout | ['overflow'] | ['overflow'] | Passed |
| control layout | ['grid is', 'kerning', 'grid'] | ['grid is', 'kerning', 'grid'] | Passed |
SHA-256 / e28dc27d07e7af41d7061c5545bfc7485585b961f5535a28503076f5dacc378d
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 < hi:
mid = (lo + hi) // 2
c = lines_for(mid)
if c is not None and c <= target + 1:
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: line count target', [['the', 'type', 'of', 'kerning', 'at', 'measure', 'ink', 'of', 'grid'], 17], ['the type of', 'kerning at', 'measure ink', 'of grid']), ('partial-repair probe', [['grid', 'serif', 'type', 'on', 'on'], 26], ['grid serif type on on']), ('partial-repair probe', [['measure', 'measure', 'of', 'a', 'on', 'at'], 11], ['measure', 'measure of', 'a on at']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['kerning', 'baseline'], 13], ['kerning', 'baseline']), ('control layout', [['grid', 'baseline', 'at', 'type', 'at', 'is', 'baseline', 'is'], 6], ['overflow']), ('control layout', [['grid', 'is', 'kerning', 'grid'], 10], ['grid is', 'kerning', 'grid'])], [('regression: line count target', [['is', 'grid', 'type', 'ink', 'x', 'grid', 'grid'], 16], ['is grid type', 'ink x grid grid']), ('regression: line count target', [['grid', 'baseline', 'grid', 'measure', 'x', 'is'], 20], ['grid baseline', 'grid measure x is']), ('partial-repair probe', [['grid', 'is', 'type', 'ink', 'serif', 'x'], 25], ['grid is type ink serif x']), ('partial-repair probe', [['a', 'of', 'is'], 27], ['a of is']), ('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', [['baseline', 'kerning', 'ink', 'is', 'baseline'], 10], ['baseline', 'kerning', 'ink is', 'baseline']), ('control layout', [['x', 'of', 'kerning', 'ink'], 9], ['x of', 'kerning', 'ink'])], [('regression: line count target', [['a', 'measure', 'serif', 'x', 'at', 'a', 'serif'], 23], ['a measure serif', 'x at a serif']), ('regression: line count target', [['measure', 'serif', 'at', 'at', 'kerning', 'x'], 23], ['measure serif', 'at at kerning x']), ('regression: line count target', [['grid', 'grid', 'on', 'measure', 'measure', 'of', 'grid'], 19], ['grid grid on', 'measure measure', 'of grid']), ('regression: line count target', [['type', 'measure', 'baseline', 'type', 'a'], 25], ['type measure', 'baseline type a']), ('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', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('control layout', [['kerning', 'on', 'the'], 9], ['kerning', 'on the'])], [('regression: line count target', [['grid', 'grid', 'measure', 'x'], 18], ['grid grid', 'measure x']), ('regression: line count target', [['is', 'measure', 'the', 'grid', 'is', 'a', 'kerning', 'baseline'], 22], ['is measure the grid', 'is a kerning baseline']), ('partial-repair probe', [['at', 'a', 'ink', 'at', 'ink'], 20], ['at a ink at ink']), ('partial-repair probe', [['baseline', 'grid', 'type', 'kerning', 'grid'], 10], ['baseline', 'grid type', 'kerning', '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', 'baseline', 'a', 'measure', 'is'], 5], ['overflow']), ('control layout', [['is', 'ink', 'on', 'serif', 'serif', 'baseline', 'ink', 'baseline', 'baseline'], 5], ['overflow'])], [('regression: line count target', [['ink', 'grid', 'serif', 'type', 'baseline', 'the', 'baseline'], 29], ['ink grid serif type', 'baseline the baseline']), ('regression: line count target', [['x', 'on', 'measure', 'baseline', 'on', 'the'], 23], ['x on measure', 'baseline on the']), ('partial-repair probe', [['the', 'of', 'ink', 'ink', 'grid', 'is'], 27], ['the of ink ink grid is']), ('partial-repair probe', [['the', 'of', 'the', 'baseline'], 28], ['the of the baseline']), ('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', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('control layout', [['kerning', 'the'], 6], ['overflow'])]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| two balanced lines | ['the type', 'grid is', 'on serif'] | ['the type grid', 'is on serif'] | Failed |
| regression: line count target | ['the type', 'of kerning', 'at measure', 'ink of', 'grid'] | ['the type of', 'kerning at', 'measure ink', 'of grid'] | Failed |
| partial-repair probe | ['grid serif', 'type on on'] | ['grid serif type on on'] | Failed |
| partial-repair probe | ['measure', 'measure', 'of a on', 'at'] | ['measure', 'measure of', 'a on at'] | Failed |
| word exactly the width | ['baseline', 'x'] | ['baseline', 'x'] | Passed |
| control layout | ['kerning', 'baseline'] | ['kerning', 'baseline'] | Passed |
| control layout | ['overflow'] | ['overflow'] | Passed |
| control layout | ['grid is', 'kerning', 'grid'] | ['grid is', 'kerning', 'grid'] | Passed |
SHA-256 / ffc1079f01086578852321c2b0688dbb297ebbf0a0f81e1762a9ec754deede2e
3 / The verified repair
Exit 0"""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 < 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: line count target', [['the', 'type', 'of', 'kerning', 'at', 'measure', 'ink', 'of', 'grid'], 17], ['the type of', 'kerning at', 'measure ink', 'of grid']), ('partial-repair probe', [['grid', 'serif', 'type', 'on', 'on'], 26], ['grid serif type on on']), ('partial-repair probe', [['measure', 'measure', 'of', 'a', 'on', 'at'], 11], ['measure', 'measure of', 'a on at']), ('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('control layout', [['kerning', 'baseline'], 13], ['kerning', 'baseline']), ('control layout', [['grid', 'baseline', 'at', 'type', 'at', 'is', 'baseline', 'is'], 6], ['overflow']), ('control layout', [['grid', 'is', 'kerning', 'grid'], 10], ['grid is', 'kerning', 'grid'])], [('regression: line count target', [['is', 'grid', 'type', 'ink', 'x', 'grid', 'grid'], 16], ['is grid type', 'ink x grid grid']), ('regression: line count target', [['grid', 'baseline', 'grid', 'measure', 'x', 'is'], 20], ['grid baseline', 'grid measure x is']), ('partial-repair probe', [['grid', 'is', 'type', 'ink', 'serif', 'x'], 25], ['grid is type ink serif x']), ('partial-repair probe', [['a', 'of', 'is'], 27], ['a of is']), ('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', [['baseline', 'kerning', 'ink', 'is', 'baseline'], 10], ['baseline', 'kerning', 'ink is', 'baseline']), ('control layout', [['x', 'of', 'kerning', 'ink'], 9], ['x of', 'kerning', 'ink'])], [('regression: line count target', [['a', 'measure', 'serif', 'x', 'at', 'a', 'serif'], 23], ['a measure serif', 'x at a serif']), ('regression: line count target', [['measure', 'serif', 'at', 'at', 'kerning', 'x'], 23], ['measure serif', 'at at kerning x']), ('regression: line count target', [['grid', 'grid', 'on', 'measure', 'measure', 'of', 'grid'], 19], ['grid grid on', 'measure measure', 'of grid']), ('regression: line count target', [['type', 'measure', 'baseline', 'type', 'a'], 25], ['type measure', 'baseline type a']), ('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', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('control layout', [['kerning', 'on', 'the'], 9], ['kerning', 'on the'])], [('regression: line count target', [['grid', 'grid', 'measure', 'x'], 18], ['grid grid', 'measure x']), ('regression: line count target', [['is', 'measure', 'the', 'grid', 'is', 'a', 'kerning', 'baseline'], 22], ['is measure the grid', 'is a kerning baseline']), ('partial-repair probe', [['at', 'a', 'ink', 'at', 'ink'], 20], ['at a ink at ink']), ('partial-repair probe', [['baseline', 'grid', 'type', 'kerning', 'grid'], 10], ['baseline', 'grid type', 'kerning', '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', 'baseline', 'a', 'measure', 'is'], 5], ['overflow']), ('control layout', [['is', 'ink', 'on', 'serif', 'serif', 'baseline', 'ink', 'baseline', 'baseline'], 5], ['overflow'])], [('regression: line count target', [['ink', 'grid', 'serif', 'type', 'baseline', 'the', 'baseline'], 29], ['ink grid serif type', 'baseline the baseline']), ('regression: line count target', [['x', 'on', 'measure', 'baseline', 'on', 'the'], 23], ['x on measure', 'baseline on the']), ('partial-repair probe', [['the', 'of', 'ink', 'ink', 'grid', 'is'], 27], ['the of ink ink grid is']), ('partial-repair probe', [['the', 'of', 'the', 'baseline'], 28], ['the of the baseline']), ('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', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('control layout', [['kerning', 'the'], 6], ['overflow'])]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| two balanced lines | ['the type grid', 'is on serif'] | ['the type grid', 'is on serif'] | Passed |
| regression: line count target | ['the type of', 'kerning at', 'measure ink', 'of grid'] | ['the type of', 'kerning at', 'measure ink', 'of grid'] | Passed |
| partial-repair probe | ['grid serif type on on'] | ['grid serif type on on'] | Passed |
| partial-repair probe | ['measure', 'measure of', 'a on at'] | ['measure', 'measure of', 'a on at'] | Passed |
| word exactly the width | ['baseline', 'x'] | ['baseline', 'x'] | Passed |
| control layout | ['kerning', 'baseline'] | ['kerning', 'baseline'] | Passed |
| control layout | ['overflow'] | ['overflow'] | Passed |
| control layout | ['grid is', 'kerning', 'grid'] | ['grid is', 'kerning', 'grid'] | Passed |
SHA-256 / 183cad133d66d1dcc9df7adb9a15ea154b160be1f63cc9281207bc6f124a5ca2
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.292670+00:00.
Case digest / 8de08a83be2d9a86fa9434dce4b7622fc34635abd044e53e58123a7785995c47