FA-80091 / Typography line breaking / Open access
Justified interword spacing: space budget · case 01
Justified lines come out too wide.
ROOT CAUSE
The space budget subtracts natural spacing again, then treats the leftover as the whole gap.
VERIFIED REPAIR
The budget is target width minus the word widths.
Unsuccessful approach: Excluding the last word from the sum inflates the budget.
Case contract
Input [word widths, target width, is_last, natural space, min space, max space]. Last lines and single-word lines are set ragged with natural spaces. Otherwise distribute target-sum(words) over the gaps: equal share with the remainder units added to the rightmost gaps; a share below min space is ["overfull"]; if any gap would exceed max space fall back to ragged. Return word x positions.
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, target, is_last, sp, lo, hi = x
n = len(words)
gaps = n - 1
def natural():
pos, xx = [], 0
for w in words:
pos.append(xx)
xx += w + sp
return pos
if is_last or gaps == 0:
return natural()
space = target - sum(words) - sp * gaps
per, rem = divmod(space, gaps)
if per < lo:
return ['overfull']
if per + (1 if rem else 0) > hi:
return natural()
pos, xx = [], 0
for k, w in enumerate(words):
pos.append(xx)
if k < gaps:
xx += w + per + (1 if k >= gaps - rem else 0)
return pos
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('regression: space budget', [[9, 8, 5, 8, 9], 51, False, 2, 1, 4], [0, 12, 23, 31, 42]), ('regression: space budget', [[5, 3, 6, 5, 6, 4], 49, False, 3, 3, 5], [0, 9, 16, 26, 35, 45]), ('partial-repair probe', [[6, 2, 9], 19, False, 2, 2, 3], ['overfull']), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[3, 9, 3, 2, 3, 5], 49, True, 2, 2, 6], [0, 5, 16, 21, 25, 30]), ('control layout', [[5], 7, False, 3, 3, 7], [0])], [('regression: space budget', [[8, 7, 6, 6, 6], 52, False, 3, 2, 4], [0, 11, 21, 30, 39]), ('regression: space budget', [[4, 8], 20, False, 3, 1, 5], [0, 7]), ('partial-repair probe', [[2, 6, 2, 7], 22, False, 2, 2, 5], ['overfull']), ('regression: space budget', [[6, 8, 2, 8, 3], 42, False, 3, 1, 5], [0, 9, 21, 27, 39]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[6], 6, False, 2, 1, 4], [0]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41])], [('regression: space budget', [[6, 8, 6, 8, 7], 49, False, 2, 2, 4], [0, 9, 20, 30, 42]), ('regression: space budget', [[3, 6, 3], 26, False, 2, 2, 5], [0, 5, 13]), ('regression: space budget', [[5, 6, 7, 8], 38, False, 2, 2, 5], [0, 9, 19, 30]), ('regression: space budget', [[3, 9, 2, 3], 26, False, 3, 2, 5], [0, 6, 18, 23]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('control layout', [[6], 7, False, 2, 2, 4], [0]), ('control layout', [[9, 8, 3, 8], 40, False, 2, 1, 3], [0, 11, 21, 26])], [('regression: space budget', [[3, 5, 9, 6, 8], 39, False, 2, 2, 5], [0, 5, 12, 23, 31]), ('regression: space budget', [[5, 6, 7, 6, 3], 47, False, 3, 1, 5], [0, 10, 21, 33, 44]), ('regression: space budget', [[2, 2, 4, 5], 19, False, 2, 2, 4], [0, 4, 8, 14]), ('regression: space budget', [[2, 6, 9, 2], 28, False, 2, 2, 3], [0, 5, 14, 26]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41]), ('control layout', [[2, 2], 4, True, 3, 2, 7], [0, 5])], [('regression: space budget', [[5, 4, 3, 2], 23, False, 2, 2, 5], [0, 8, 15, 21]), ('regression: space budget', [[2, 6, 8, 6, 6, 9], 75, False, 2, 1, 6], [0, 4, 12, 22, 30, 38]), ('regression: space budget', [[2, 4, 6, 4, 7, 2], 43, False, 2, 1, 6], [0, 5, 12, 22, 30, 41]), ('regression: space budget', [[5, 7, 5, 6, 9, 5], 43, False, 3, 1, 6], [0, 6, 14, 20, 27, 38]), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2], 6, False, 2, 1, 4], [0]), ('control layout', [[2], 6, False, 3, 1, 5], [0])]]
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 |
|---|---|---|---|
| remainder goes to right gaps | ['overfull'] | [0, 5, 11, 18] | Failed |
| regression: space budget | [0, 10, 19, 25, 34] | [0, 12, 23, 31, 42] | Failed |
| regression: space budget | ['overfull'] | [0, 9, 16, 26, 35, 45] | Failed |
| partial-repair probe | ['overfull'] | ['overfull'] | Passed |
| last line ragged | [0, 5, 11] | [0, 5, 11] | Passed |
| exactly minimum share | ['overfull'] | [0, 4, 8] | Failed |
| control layout | [0, 5, 16, 21, 25, 30] | [0, 5, 16, 21, 25, 30] | Passed |
| control layout | [0] | [0] | Passed |
SHA-256 / 54c34947f02b7b0edaac70e1a03f686b8ef0a8b43be421bc2a0e2c2eb534f472
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
words, target, is_last, sp, lo, hi = x
n = len(words)
gaps = n - 1
def natural():
pos, xx = [], 0
for w in words:
pos.append(xx)
xx += w + sp
return pos
if is_last or gaps == 0:
return natural()
space = target - sum(words[:-1])
per, rem = divmod(space, gaps)
if per < lo:
return ['overfull']
if per + (1 if rem else 0) > hi:
return natural()
pos, xx = [], 0
for k, w in enumerate(words):
pos.append(xx)
if k < gaps:
xx += w + per + (1 if k >= gaps - rem else 0)
return pos
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('regression: space budget', [[9, 8, 5, 8, 9], 51, False, 2, 1, 4], [0, 12, 23, 31, 42]), ('regression: space budget', [[5, 3, 6, 5, 6, 4], 49, False, 3, 3, 5], [0, 9, 16, 26, 35, 45]), ('partial-repair probe', [[6, 2, 9], 19, False, 2, 2, 3], ['overfull']), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[3, 9, 3, 2, 3, 5], 49, True, 2, 2, 6], [0, 5, 16, 21, 25, 30]), ('control layout', [[5], 7, False, 3, 3, 7], [0])], [('regression: space budget', [[8, 7, 6, 6, 6], 52, False, 3, 2, 4], [0, 11, 21, 30, 39]), ('regression: space budget', [[4, 8], 20, False, 3, 1, 5], [0, 7]), ('partial-repair probe', [[2, 6, 2, 7], 22, False, 2, 2, 5], ['overfull']), ('regression: space budget', [[6, 8, 2, 8, 3], 42, False, 3, 1, 5], [0, 9, 21, 27, 39]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[6], 6, False, 2, 1, 4], [0]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41])], [('regression: space budget', [[6, 8, 6, 8, 7], 49, False, 2, 2, 4], [0, 9, 20, 30, 42]), ('regression: space budget', [[3, 6, 3], 26, False, 2, 2, 5], [0, 5, 13]), ('regression: space budget', [[5, 6, 7, 8], 38, False, 2, 2, 5], [0, 9, 19, 30]), ('regression: space budget', [[3, 9, 2, 3], 26, False, 3, 2, 5], [0, 6, 18, 23]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('control layout', [[6], 7, False, 2, 2, 4], [0]), ('control layout', [[9, 8, 3, 8], 40, False, 2, 1, 3], [0, 11, 21, 26])], [('regression: space budget', [[3, 5, 9, 6, 8], 39, False, 2, 2, 5], [0, 5, 12, 23, 31]), ('regression: space budget', [[5, 6, 7, 6, 3], 47, False, 3, 1, 5], [0, 10, 21, 33, 44]), ('regression: space budget', [[2, 2, 4, 5], 19, False, 2, 2, 4], [0, 4, 8, 14]), ('regression: space budget', [[2, 6, 9, 2], 28, False, 2, 2, 3], [0, 5, 14, 26]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41]), ('control layout', [[2, 2], 4, True, 3, 2, 7], [0, 5])], [('regression: space budget', [[5, 4, 3, 2], 23, False, 2, 2, 5], [0, 8, 15, 21]), ('regression: space budget', [[2, 6, 8, 6, 6, 9], 75, False, 2, 1, 6], [0, 4, 12, 22, 30, 38]), ('regression: space budget', [[2, 4, 6, 4, 7, 2], 43, False, 2, 1, 6], [0, 5, 12, 22, 30, 41]), ('regression: space budget', [[5, 7, 5, 6, 9, 5], 43, False, 3, 1, 6], [0, 6, 14, 20, 27, 38]), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2], 6, False, 2, 1, 4], [0]), ('control layout', [[2], 6, False, 3, 1, 5], [0])]]
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 |
|---|---|---|---|
| remainder goes to right gaps | [0, 5, 12, 20] | [0, 5, 11, 18] | Failed |
| regression: space budget | [0, 11, 21, 28, 38] | [0, 12, 23, 31, 42] | Failed |
| regression: space budget | [0, 9, 17, 28, 38, 49] | [0, 9, 16, 26, 35, 45] | Failed |
| partial-repair probe | [0, 8, 12] | ['overfull'] | Failed |
| last line ragged | [0, 5, 11] | [0, 5, 11] | Passed |
| exactly minimum share | [0, 5, 11] | [0, 4, 8] | Failed |
| control layout | [0, 5, 16, 21, 25, 30] | [0, 5, 16, 21, 25, 30] | Passed |
| control layout | [0] | [0] | Passed |
SHA-256 / 1f984f92271ff7369c48b51b4d694f5e6fb1b2579f34fd7b8668593580d44569
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
words, target, is_last, sp, lo, hi = x
n = len(words)
gaps = n - 1
def natural():
pos, xx = [], 0
for w in words:
pos.append(xx)
xx += w + sp
return pos
if is_last or gaps == 0:
return natural()
space = target - sum(words)
per, rem = divmod(space, gaps)
if per < lo:
return ['overfull']
if per + (1 if rem else 0) > hi:
return natural()
pos, xx = [], 0
for k, w in enumerate(words):
pos.append(xx)
if k < gaps:
xx += w + per + (1 if k >= gaps - rem else 0)
return pos
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('regression: space budget', [[9, 8, 5, 8, 9], 51, False, 2, 1, 4], [0, 12, 23, 31, 42]), ('regression: space budget', [[5, 3, 6, 5, 6, 4], 49, False, 3, 3, 5], [0, 9, 16, 26, 35, 45]), ('partial-repair probe', [[6, 2, 9], 19, False, 2, 2, 3], ['overfull']), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[3, 9, 3, 2, 3, 5], 49, True, 2, 2, 6], [0, 5, 16, 21, 25, 30]), ('control layout', [[5], 7, False, 3, 3, 7], [0])], [('regression: space budget', [[8, 7, 6, 6, 6], 52, False, 3, 2, 4], [0, 11, 21, 30, 39]), ('regression: space budget', [[4, 8], 20, False, 3, 1, 5], [0, 7]), ('partial-repair probe', [[2, 6, 2, 7], 22, False, 2, 2, 5], ['overfull']), ('regression: space budget', [[6, 8, 2, 8, 3], 42, False, 3, 1, 5], [0, 9, 21, 27, 39]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('exactly minimum share', [[3, 3, 3], 11, False, 2, 1, 4], [0, 4, 8]), ('control layout', [[6], 6, False, 2, 1, 4], [0]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41])], [('regression: space budget', [[6, 8, 6, 8, 7], 49, False, 2, 2, 4], [0, 9, 20, 30, 42]), ('regression: space budget', [[3, 6, 3], 26, False, 2, 2, 5], [0, 5, 13]), ('regression: space budget', [[5, 6, 7, 8], 38, False, 2, 2, 5], [0, 9, 19, 30]), ('regression: space budget', [[3, 9, 2, 3], 26, False, 3, 2, 5], [0, 6, 18, 23]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('control layout', [[6], 7, False, 2, 2, 4], [0]), ('control layout', [[9, 8, 3, 8], 40, False, 2, 1, 3], [0, 11, 21, 26])], [('regression: space budget', [[3, 5, 9, 6, 8], 39, False, 2, 2, 5], [0, 5, 12, 23, 31]), ('regression: space budget', [[5, 6, 7, 6, 3], 47, False, 3, 1, 5], [0, 10, 21, 33, 44]), ('regression: space budget', [[2, 2, 4, 5], 19, False, 2, 2, 4], [0, 4, 8, 14]), ('regression: space budget', [[2, 6, 9, 2], 28, False, 2, 2, 3], [0, 5, 14, 26]), ('single word line', [[7], 20, False, 2, 1, 4], [0]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2, 5, 3, 7, 9, 7], 44, True, 3, 3, 7], [0, 5, 13, 19, 29, 41]), ('control layout', [[2, 2], 4, True, 3, 2, 7], [0, 5])], [('regression: space budget', [[5, 4, 3, 2], 23, False, 2, 2, 5], [0, 8, 15, 21]), ('regression: space budget', [[2, 6, 8, 6, 6, 9], 75, False, 2, 1, 6], [0, 4, 12, 22, 30, 38]), ('regression: space budget', [[2, 4, 6, 4, 7, 2], 43, False, 2, 1, 6], [0, 5, 12, 22, 30, 41]), ('regression: space budget', [[5, 7, 5, 6, 9, 5], 43, False, 3, 1, 6], [0, 6, 14, 20, 27, 38]), ('last line ragged', [[3, 4, 5], 20, True, 2, 1, 6], [0, 5, 11]), ('remainder goes to right gaps', [[3, 4, 5, 2], 20, False, 2, 1, 4], [0, 5, 11, 18]), ('control layout', [[2], 6, False, 2, 1, 4], [0]), ('control layout', [[2], 6, False, 3, 1, 5], [0])]]
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 |
|---|---|---|---|
| remainder goes to right gaps | [0, 5, 11, 18] | [0, 5, 11, 18] | Passed |
| regression: space budget | [0, 12, 23, 31, 42] | [0, 12, 23, 31, 42] | Passed |
| regression: space budget | [0, 9, 16, 26, 35, 45] | [0, 9, 16, 26, 35, 45] | Passed |
| partial-repair probe | ['overfull'] | ['overfull'] | Passed |
| last line ragged | [0, 5, 11] | [0, 5, 11] | Passed |
| exactly minimum share | [0, 4, 8] | [0, 4, 8] | Passed |
| control layout | [0, 5, 16, 21, 25, 30] | [0, 5, 16, 21, 25, 30] | Passed |
| control layout | [0] | [0] | Passed |
SHA-256 / 98b64dac66f120e6a76ac3135a6ecc7bb31d60ab376a3b499c43068e160783b8
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:50.633440+00:00.
Case digest / a7a1b86aab05dffe551a0633e1e6c8855df4f8adfbf6d32158b7a419af06ca07