FA-79976 / Typography line breaking / Open access
Widow and orphan page breaking: widow threshold · case 01
Carry-overs one line short of the widow minimum are left in place.
ROOT CAUSE
The widow test compares against widow - 1, so only multi-line shortfalls are cured.
VERIFIED REPAIR
Adjust whenever fewer than the minimum lines would carry over.
Unsuccessful approach: Handling only a shortfall of exactly one line misses larger widow minimums.
Case contract
Input [paragraph line counts, page height, min orphan lines, min widow lines]. Lines flow onto pages. When a paragraph must break on a page that already holds lines, at least min widow lines must carry to the next page (move lines forward) and, if the paragraph starts on this page, at least min orphan lines must stay (else move it all). A paragraph that exactly fits stays. Constraints are waived on an empty page. Return lines per page.
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):
paras, H, orphan, widow = x
pages = []
used = 0
for p in paras:
rem = p
started = True
while rem > 0:
room = H - used
if rem <= room:
used += rem
rem = 0
continue
a = room
if used > 0:
if rem - a < widow - 1:
a = max(rem - widow, 0)
if started and a < orphan:
a = 0
used += a
rem -= a
if a > 0:
started = False
pages.append(used)
used = 0
if used > 0:
pages.append(used)
return pages
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('regression: widow threshold', [[9, 8, 5, 2, 1, 8], 8, 2, 2], [8, 7, 7, 8, 3]), ('regression: widow threshold', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('regression: widow threshold', [[2, 3, 3, 3, 5, 6, 5, 5], 4, 2, 3], [2, 3, 3, 3, 4, 4, 3, 4, 3, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[3, 1, 4], 11, 1, 3], [8]), ('control layout', [[2, 1, 8, 4, 9, 8, 1, 6], 5, 2, 1], [5, 5, 5, 5, 4, 5, 4, 5, 1])], [('regression: widow threshold', [[6, 8, 1, 3, 8, 9], 4, 1, 3], [4, 4, 4, 3, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[6, 6, 4, 1, 5, 3, 3], 12, 1, 2], [12, 11, 5]), ('regression: widow threshold', [[5, 1, 2, 7, 6, 9], 10, 2, 3], [10, 8, 9, 3]), ('partial-repair probe', [[2, 4, 6, 3], 7, 1, 3], [7, 5, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 9, 3, 7, 9, 3, 8], 5, 2, 1], [5, 5, 5, 5, 5, 5, 4, 5, 5, 1]), ('control layout', [[9, 7, 6], 12, 2, 3], [12, 10])], [('regression: widow threshold', [[5, 5, 4, 3], 8, 1, 2], [8, 7, 2]), ('regression: widow threshold', [[6, 5, 2, 6, 6], 10, 2, 2], [9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 1, 5, 6, 7, 7, 5, 1], 10, 2, 3], [8, 9, 10, 10]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[4, 8, 9, 4], 9, 3, 2], [9, 9, 7]), ('control layout', [[4, 5, 1], 4, 3, 1], [4, 4, 2])], [('regression: widow threshold', [[7, 5, 1, 9, 6, 4, 1, 7], 9, 1, 2], [9, 9, 8, 9, 5]), ('regression: widow threshold', [[8, 4, 3, 3, 3, 1, 4], 5, 2, 2], [5, 5, 5, 3, 4, 4]), ('partial-repair probe', [[9, 5, 1, 9, 8, 5], 8, 2, 3], [8, 7, 8, 6, 8]), ('regression: widow threshold', [[7, 7, 4, 4, 2, 3], 4, 1, 3], [4, 4, 4, 3, 4, 3, 2, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 3, 8], 4, 3, 1], [4, 2, 3, 4, 4]), ('control layout', [[1, 8, 1, 2], 4, 2, 1], [4, 4, 4])], [('regression: widow threshold', [[9, 5, 1, 5, 7, 8, 8], 4, 2, 3], [4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[2, 6, 4, 5, 7, 9], 10, 2, 3], [8, 9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 8, 8], 12, 1, 3], [10, 11]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[4, 1, 9, 5], 7, 3, 3], [5, 7, 7]), ('control layout', [[9, 9, 9], 4, 3, 3], [4, 4, 4, 4, 2, 4, 4, 1])]]
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 |
|---|---|---|---|
| single widow pulled back | [6, 1] | [5, 2] | Failed |
| regression: widow threshold | [8, 8, 8, 8, 1] | [8, 7, 7, 8, 3] | Failed |
| regression: widow threshold | [6, 6, 6, 6, 6, 6, 3] | [5, 4, 6, 6, 6, 6, 6] | Failed |
| regression: widow threshold | [2, 3, 3, 3, 4, 4, 3, 4, 4, 2] | [2, 3, 3, 3, 4, 4, 3, 4, 3, 3] | Failed |
| orphan pushed forward | [5, 3] | [5, 3] | Passed |
| long paragraph continuation | [6, 6, 4] | [6, 6, 4] | Passed |
| control layout | [8] | [8] | Passed |
| control layout | [5, 5, 5, 5, 4, 5, 4, 5, 1] | [5, 5, 5, 5, 4, 5, 4, 5, 1] | Passed |
SHA-256 / 11041f68082bb58cffb4ad5747f8c71ed41d4aca1f1a05817ace386c4f15018f
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
paras, H, orphan, widow = x
pages = []
used = 0
for p in paras:
rem = p
started = True
while rem > 0:
room = H - used
if rem <= room:
used += rem
rem = 0
continue
a = room
if used > 0:
if rem - a == widow - 1:
a = max(rem - widow, 0)
if started and a < orphan:
a = 0
used += a
rem -= a
if a > 0:
started = False
pages.append(used)
used = 0
if used > 0:
pages.append(used)
return pages
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('regression: widow threshold', [[9, 8, 5, 2, 1, 8], 8, 2, 2], [8, 7, 7, 8, 3]), ('regression: widow threshold', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('regression: widow threshold', [[2, 3, 3, 3, 5, 6, 5, 5], 4, 2, 3], [2, 3, 3, 3, 4, 4, 3, 4, 3, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[3, 1, 4], 11, 1, 3], [8]), ('control layout', [[2, 1, 8, 4, 9, 8, 1, 6], 5, 2, 1], [5, 5, 5, 5, 4, 5, 4, 5, 1])], [('regression: widow threshold', [[6, 8, 1, 3, 8, 9], 4, 1, 3], [4, 4, 4, 3, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[6, 6, 4, 1, 5, 3, 3], 12, 1, 2], [12, 11, 5]), ('regression: widow threshold', [[5, 1, 2, 7, 6, 9], 10, 2, 3], [10, 8, 9, 3]), ('partial-repair probe', [[2, 4, 6, 3], 7, 1, 3], [7, 5, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 9, 3, 7, 9, 3, 8], 5, 2, 1], [5, 5, 5, 5, 5, 5, 4, 5, 5, 1]), ('control layout', [[9, 7, 6], 12, 2, 3], [12, 10])], [('regression: widow threshold', [[5, 5, 4, 3], 8, 1, 2], [8, 7, 2]), ('regression: widow threshold', [[6, 5, 2, 6, 6], 10, 2, 2], [9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 1, 5, 6, 7, 7, 5, 1], 10, 2, 3], [8, 9, 10, 10]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[4, 8, 9, 4], 9, 3, 2], [9, 9, 7]), ('control layout', [[4, 5, 1], 4, 3, 1], [4, 4, 2])], [('regression: widow threshold', [[7, 5, 1, 9, 6, 4, 1, 7], 9, 1, 2], [9, 9, 8, 9, 5]), ('regression: widow threshold', [[8, 4, 3, 3, 3, 1, 4], 5, 2, 2], [5, 5, 5, 3, 4, 4]), ('partial-repair probe', [[9, 5, 1, 9, 8, 5], 8, 2, 3], [8, 7, 8, 6, 8]), ('regression: widow threshold', [[7, 7, 4, 4, 2, 3], 4, 1, 3], [4, 4, 4, 3, 4, 3, 2, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 3, 8], 4, 3, 1], [4, 2, 3, 4, 4]), ('control layout', [[1, 8, 1, 2], 4, 2, 1], [4, 4, 4])], [('regression: widow threshold', [[9, 5, 1, 5, 7, 8, 8], 4, 2, 3], [4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[2, 6, 4, 5, 7, 9], 10, 2, 3], [8, 9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 8, 8], 12, 1, 3], [10, 11]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[4, 1, 9, 5], 7, 3, 3], [5, 7, 7]), ('control layout', [[9, 9, 9], 4, 3, 3], [4, 4, 4, 4, 2, 4, 4, 1])]]
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 |
|---|---|---|---|
| single widow pulled back | [5, 2] | [5, 2] | Passed |
| regression: widow threshold | [8, 7, 7, 8, 3] | [8, 7, 7, 8, 3] | Passed |
| regression: widow threshold | [5, 6, 6, 6, 6, 6, 4] | [5, 4, 6, 6, 6, 6, 6] | Failed |
| regression: widow threshold | [4, 4, 3, 4, 4, 3, 4, 3, 3] | [2, 3, 3, 3, 4, 4, 3, 4, 3, 3] | Failed |
| orphan pushed forward | [5, 3] | [5, 3] | Passed |
| long paragraph continuation | [6, 6, 4] | [6, 6, 4] | Passed |
| control layout | [8] | [8] | Passed |
| control layout | [5, 5, 5, 5, 4, 5, 4, 5, 1] | [5, 5, 5, 5, 4, 5, 4, 5, 1] | Passed |
SHA-256 / d860536336f7523eb0b149ec785fb64f23e578293620dae2acb608f8dadb97f4
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
paras, H, orphan, widow = x
pages = []
used = 0
for p in paras:
rem = p
started = True
while rem > 0:
room = H - used
if rem <= room:
used += rem
rem = 0
continue
a = room
if used > 0:
if rem - a < widow:
a = max(rem - widow, 0)
if started and a < orphan:
a = 0
used += a
rem -= a
if a > 0:
started = False
pages.append(used)
used = 0
if used > 0:
pages.append(used)
return pages
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('regression: widow threshold', [[9, 8, 5, 2, 1, 8], 8, 2, 2], [8, 7, 7, 8, 3]), ('regression: widow threshold', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('regression: widow threshold', [[2, 3, 3, 3, 5, 6, 5, 5], 4, 2, 3], [2, 3, 3, 3, 4, 4, 3, 4, 3, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[3, 1, 4], 11, 1, 3], [8]), ('control layout', [[2, 1, 8, 4, 9, 8, 1, 6], 5, 2, 1], [5, 5, 5, 5, 4, 5, 4, 5, 1])], [('regression: widow threshold', [[6, 8, 1, 3, 8, 9], 4, 1, 3], [4, 4, 4, 3, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[6, 6, 4, 1, 5, 3, 3], 12, 1, 2], [12, 11, 5]), ('regression: widow threshold', [[5, 1, 2, 7, 6, 9], 10, 2, 3], [10, 8, 9, 3]), ('partial-repair probe', [[2, 4, 6, 3], 7, 1, 3], [7, 5, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 9, 3, 7, 9, 3, 8], 5, 2, 1], [5, 5, 5, 5, 5, 5, 4, 5, 5, 1]), ('control layout', [[9, 7, 6], 12, 2, 3], [12, 10])], [('regression: widow threshold', [[5, 5, 4, 3], 8, 1, 2], [8, 7, 2]), ('regression: widow threshold', [[6, 5, 2, 6, 6], 10, 2, 2], [9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 1, 5, 6, 7, 7, 5, 1], 10, 2, 3], [8, 9, 10, 10]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[4, 8, 9, 4], 9, 3, 2], [9, 9, 7]), ('control layout', [[4, 5, 1], 4, 3, 1], [4, 4, 2])], [('regression: widow threshold', [[7, 5, 1, 9, 6, 4, 1, 7], 9, 1, 2], [9, 9, 8, 9, 5]), ('regression: widow threshold', [[8, 4, 3, 3, 3, 1, 4], 5, 2, 2], [5, 5, 5, 3, 4, 4]), ('partial-repair probe', [[9, 5, 1, 9, 8, 5], 8, 2, 3], [8, 7, 8, 6, 8]), ('regression: widow threshold', [[7, 7, 4, 4, 2, 3], 4, 1, 3], [4, 4, 4, 3, 4, 3, 2, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 3, 8], 4, 3, 1], [4, 2, 3, 4, 4]), ('control layout', [[1, 8, 1, 2], 4, 2, 1], [4, 4, 4])], [('regression: widow threshold', [[9, 5, 1, 5, 7, 8, 8], 4, 2, 3], [4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4]), ('regression: widow threshold', [[2, 6, 4, 5, 7, 9], 10, 2, 3], [8, 9, 10, 6]), ('regression: widow threshold', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('partial-repair probe', [[5, 8, 8], 12, 1, 3], [10, 11]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[4, 1, 9, 5], 7, 3, 3], [5, 7, 7]), ('control layout', [[9, 9, 9], 4, 3, 3], [4, 4, 4, 4, 2, 4, 4, 1])]]
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 |
|---|---|---|---|
| single widow pulled back | [5, 2] | [5, 2] | Passed |
| regression: widow threshold | [8, 7, 7, 8, 3] | [8, 7, 7, 8, 3] | Passed |
| regression: widow threshold | [5, 4, 6, 6, 6, 6, 6] | [5, 4, 6, 6, 6, 6, 6] | Passed |
| regression: widow threshold | [2, 3, 3, 3, 4, 4, 3, 4, 3, 3] | [2, 3, 3, 3, 4, 4, 3, 4, 3, 3] | Passed |
| orphan pushed forward | [5, 3] | [5, 3] | Passed |
| long paragraph continuation | [6, 6, 4] | [6, 6, 4] | Passed |
| control layout | [8] | [8] | Passed |
| control layout | [5, 5, 5, 5, 4, 5, 4, 5, 1] | [5, 5, 5, 5, 4, 5, 4, 5, 1] | Passed |
SHA-256 / d52b0c2c2c0fb56f71af68e4d6b98a790a1fbae440b8a4813fded748f5193da9
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:49.614174+00:00.
Case digest / 7977e3245b344dbc1cfe05677fc5c759379c4f1d3143b1450301b07521c818f8