FA-80291 / Typography line breaking / Open access

Balanced headline wrapping: overwide word test · case 01

Words exactly as wide as a candidate width are rejected.

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

ROOT CAUSE

The overwide test uses >=.

VERIFIED REPAIR

Reject only words wider than the candidate width.

Unsuccessful approach: Allowing one character overflow accepts impossible widths.

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 = [[('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['ink', 'x'], 28], ['ink x']), ('control layout', [['measure', 'on', 'kerning'], 13], ['measure on', 'kerning']), ('control layout', [['kerning', 'x', 'is'], 27], ['kerning x is'])], [('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('partial-repair probe', [['type', 'the', 'measure', 'kerning', 'is'], 6], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('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'], 11], ['x x']), ('control layout', [['on', 'serif', 'measure', 'ink', 'a', 'on', 'x', 'of'], 22], ['on serif measure', 'ink a on x of'])], [('regression: overwide word test', [['at', 'grid', 'measure', 'a', 'x', 'is', 'baseline', 'is'], 10], ['at grid', 'measure', 'a x is', 'baseline', 'is']), ('regression: overwide word test', [['x', 'baseline', 'is', 'ink', 'type', 'measure', 'on', 'a', 'the'], 8], ['x', 'baseline', 'is ink', 'type', 'measure', 'on a the']), ('partial-repair probe', [['on', 'a', 'grid', 'ink', 'baseline'], 7], ['overflow']), ('partial-repair probe', [['measure', 'x'], 6], ['overflow']), ('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', 'a', 'on', 'x', 'of', 'the', 'a', 'grid'], 16], ['kerning a on x', 'of the a grid']), ('control layout', [['at', 'baseline', 'baseline', 'grid', 'a', 'on', 'baseline', 'of'], 21], ['at baseline baseline', 'grid a on baseline of'])], [('regression: overwide word test', [['is', 'is', 'the', 'serif'], 5], ['is is', 'the', 'serif']), ('regression: overwide word test', [['on', 'baseline'], 8], ['on', 'baseline']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['at', 'type', 'is', 'baseline', 'ink'], 7], ['overflow']), ('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', [['the', 'ink', 'a'], 19], ['the ink a']), ('control layout', [['a', 'baseline', 'type'], 6], ['overflow'])], [('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('partial-repair probe', [['kerning', 'serif', 'of', 'grid', 'serif', 'on', 'grid', 'x'], 6], ['overflow']), ('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', [['the', 'on', 'at', 'of', 'is', 'measure', 'type'], 10], ['the on', 'at of is', 'measure', 'type']), ('control layout', [['type', 'at', 'ink', 'of', 'measure'], 14], ['type at ink', 'of measure'])]]
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
word exactly the width	`['overflow']`	`['baseline', 'x']`	Failed
regression: overwide word test	`['grid', 'serif', 'serif', 'grid x', 'of']`	`['grid', 'serif', 'serif', 'grid', 'x of']`	Failed
partial-repair probe	`['overflow']`	`['overflow']`	Passed
partial-repair probe	`['overflow']`	`['overflow']`	Passed
two balanced lines	`['the type grid', 'is on serif']`	`['the type grid', 'is on serif']`	Passed
control layout	`['ink x']`	`['ink x']`	Passed
control layout	`['measure on', 'kerning']`	`['measure on', 'kerning']`	Passed
control layout	`['kerning x is']`	`['kerning x is']`	Passed

SHA-256 / f795ba468781141313afa21cd4b35dda0c8c2020b232b623f6cdafe7472ffb92

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 + 1:
                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 = [[('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['ink', 'x'], 28], ['ink x']), ('control layout', [['measure', 'on', 'kerning'], 13], ['measure on', 'kerning']), ('control layout', [['kerning', 'x', 'is'], 27], ['kerning x is'])], [('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('partial-repair probe', [['type', 'the', 'measure', 'kerning', 'is'], 6], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('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'], 11], ['x x']), ('control layout', [['on', 'serif', 'measure', 'ink', 'a', 'on', 'x', 'of'], 22], ['on serif measure', 'ink a on x of'])], [('regression: overwide word test', [['at', 'grid', 'measure', 'a', 'x', 'is', 'baseline', 'is'], 10], ['at grid', 'measure', 'a x is', 'baseline', 'is']), ('regression: overwide word test', [['x', 'baseline', 'is', 'ink', 'type', 'measure', 'on', 'a', 'the'], 8], ['x', 'baseline', 'is ink', 'type', 'measure', 'on a the']), ('partial-repair probe', [['on', 'a', 'grid', 'ink', 'baseline'], 7], ['overflow']), ('partial-repair probe', [['measure', 'x'], 6], ['overflow']), ('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', 'a', 'on', 'x', 'of', 'the', 'a', 'grid'], 16], ['kerning a on x', 'of the a grid']), ('control layout', [['at', 'baseline', 'baseline', 'grid', 'a', 'on', 'baseline', 'of'], 21], ['at baseline baseline', 'grid a on baseline of'])], [('regression: overwide word test', [['is', 'is', 'the', 'serif'], 5], ['is is', 'the', 'serif']), ('regression: overwide word test', [['on', 'baseline'], 8], ['on', 'baseline']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['at', 'type', 'is', 'baseline', 'ink'], 7], ['overflow']), ('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', [['the', 'ink', 'a'], 19], ['the ink a']), ('control layout', [['a', 'baseline', 'type'], 6], ['overflow'])], [('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('partial-repair probe', [['kerning', 'serif', 'of', 'grid', 'serif', 'on', 'grid', 'x'], 6], ['overflow']), ('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', [['the', 'on', 'at', 'of', 'is', 'measure', 'type'], 10], ['the on', 'at of is', 'measure', 'type']), ('control layout', [['type', 'at', 'ink', 'of', 'measure'], 14], ['type at ink', 'of measure'])]]
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
word exactly the width	`['baseline', 'x']`	`['baseline', 'x']`	Passed
regression: overwide word test	`['grid', 'serif', 'serif', 'grid', 'x of']`	`['grid', 'serif', 'serif', 'grid', 'x of']`	Passed
partial-repair probe	`['is ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of is']`	`['overflow']`	Failed
partial-repair probe	`['a serif', 'baseline', 'ink at', 'measure', 'baseline']`	`['overflow']`	Failed
two balanced lines	`['the type grid', 'is on serif']`	`['the type grid', 'is on serif']`	Passed
control layout	`['ink x']`	`['ink x']`	Passed
control layout	`['measure on', 'kerning']`	`['measure on', 'kerning']`	Passed
control layout	`['kerning x is']`	`['kerning x is']`	Passed

SHA-256 / cd0b6958a53ab8cd34d2f3c5950519f98f10db083f106389eb1f11e12b2bf29e

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 = [[('word exactly the width', [['baseline', 'x'], 8], ['baseline', 'x']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('two balanced lines', [['the', 'type', 'grid', 'is', 'on', 'serif'], 22], ['the type grid', 'is on serif']), ('control layout', [['ink', 'x'], 28], ['ink x']), ('control layout', [['measure', 'on', 'kerning'], 13], ['measure on', 'kerning']), ('control layout', [['kerning', 'x', 'is'], 27], ['kerning x is'])], [('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('partial-repair probe', [['type', 'the', 'measure', 'kerning', 'is'], 6], ['overflow']), ('partial-repair probe', [['a', 'serif', 'baseline', 'ink', 'at', 'measure', 'baseline'], 7], ['overflow']), ('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'], 11], ['x x']), ('control layout', [['on', 'serif', 'measure', 'ink', 'a', 'on', 'x', 'of'], 22], ['on serif measure', 'ink a on x of'])], [('regression: overwide word test', [['at', 'grid', 'measure', 'a', 'x', 'is', 'baseline', 'is'], 10], ['at grid', 'measure', 'a x is', 'baseline', 'is']), ('regression: overwide word test', [['x', 'baseline', 'is', 'ink', 'type', 'measure', 'on', 'a', 'the'], 8], ['x', 'baseline', 'is ink', 'type', 'measure', 'on a the']), ('partial-repair probe', [['on', 'a', 'grid', 'ink', 'baseline'], 7], ['overflow']), ('partial-repair probe', [['measure', 'x'], 6], ['overflow']), ('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', 'a', 'on', 'x', 'of', 'the', 'a', 'grid'], 16], ['kerning a on x', 'of the a grid']), ('control layout', [['at', 'baseline', 'baseline', 'grid', 'a', 'on', 'baseline', 'of'], 21], ['at baseline baseline', 'grid a on baseline of'])], [('regression: overwide word test', [['is', 'is', 'the', 'serif'], 5], ['is is', 'the', 'serif']), ('regression: overwide word test', [['on', 'baseline'], 8], ['on', 'baseline']), ('partial-repair probe', [['is', 'ink', 'serif', 'kerning', 'x', 'baseline', 'kerning', 'of', 'is'], 7], ['overflow']), ('partial-repair probe', [['at', 'type', 'is', 'baseline', 'ink'], 7], ['overflow']), ('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', [['the', 'ink', 'a'], 19], ['the ink a']), ('control layout', [['a', 'baseline', 'type'], 6], ['overflow'])], [('regression: overwide word test', [['kerning', 'type', 'is', 'is', 'is', 'measure', 'measure', 'type', 'at'], 7], ['kerning', 'type is', 'is is', 'measure', 'measure', 'type at']), ('regression: overwide word test', [['grid', 'serif', 'serif', 'grid', 'x', 'of'], 7], ['grid', 'serif', 'serif', 'grid', 'x of']), ('partial-repair probe', [['measure', 'x', 'serif', 'a', 'a', 'x', 'is', 'of', 'x'], 6], ['overflow']), ('partial-repair probe', [['kerning', 'serif', 'of', 'grid', 'serif', 'on', 'grid', 'x'], 6], ['overflow']), ('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', [['the', 'on', 'at', 'of', 'is', 'measure', 'type'], 10], ['the on', 'at of is', 'measure', 'type']), ('control layout', [['type', 'at', 'ink', 'of', 'measure'], 14], ['type at ink', 'of measure'])]]
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
word exactly the width	`['baseline', 'x']`	`['baseline', 'x']`	Passed
regression: overwide word test	`['grid', 'serif', 'serif', 'grid', 'x of']`	`['grid', 'serif', 'serif', 'grid', 'x of']`	Passed
partial-repair probe	`['overflow']`	`['overflow']`	Passed
partial-repair probe	`['overflow']`	`['overflow']`	Passed
two balanced lines	`['the type grid', 'is on serif']`	`['the type grid', 'is on serif']`	Passed
control layout	`['ink x']`	`['ink x']`	Passed
control layout	`['measure on', 'kerning']`	`['measure on', 'kerning']`	Passed
control layout	`['kerning x is']`	`['kerning x is']`	Passed

SHA-256 / fdffd315f24ebfc02b79472a4d6606c449d5621b868117fd59df7aff1e7c722d

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.467563+00:00.

Case digest / 996d1ad1980aeafae9a14c74414b8fde21da9de56e0e4c314d7b20070ac01c18