{"abstract":"Balanced widths come out one column too wide.","category":"Typography line breaking","checks":8,"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.","contract_signature":"x","evaluation_group":"w2-typography-line-breaking-balanced-headline","failed_approach":"Stopping when bounds differ by two is also premature.","family":"w2-typography-line-breaking-balanced-headline-search-termination","id":"FA-80306","implementations":{"attempt":{"sha256":"278f1204774fe6cf7bb733aa5d5f33782fa00c5efea26a19e8d63c7faf6b9b95","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    words, width = x\n    def lines_for(w):\n        count, cur = 0, -1\n        for t in words:\n            if len(t) > w:\n                return None\n            if cur == -1:\n                cur = len(t)\n                count = 1\n            elif cur + 1 + len(t) <= w:\n                cur += 1 + len(t)\n            else:\n                count += 1\n                cur = len(t)\n        return count\n    target = lines_for(width)\n    if target is None:\n        return ['overflow']\n    lo = max(len(t) for t in words)\n    hi = width\n    while lo + 2 < hi:\n        mid = (lo + hi) // 2\n        c = lines_for(mid)\n        if c is not None and c <= target:\n            hi = mid\n        else:\n            lo = mid + 1\n    out, cur = [], ''\n    for t in words:\n        cand = t if not cur else cur + ' ' + t\n        if len(cand) <= lo:\n            cur = cand\n        else:\n            out.append(cur)\n            cur = t\n    out.append(cur)\n    return out\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[('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'])]]\nfor label, args, expected in fixtures[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"e8601b13465c9aa9a01aff437afd59ed7ec0826afc428b6aaa5a8ce58851fe98","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    words, width = x\n    def lines_for(w):\n        count, cur = 0, -1\n        for t in words:\n            if len(t) > w:\n                return None\n            if cur == -1:\n                cur = len(t)\n                count = 1\n            elif cur + 1 + len(t) <= w:\n                cur += 1 + len(t)\n            else:\n                count += 1\n                cur = len(t)\n        return count\n    target = lines_for(width)\n    if target is None:\n        return ['overflow']\n    lo = max(len(t) for t in words)\n    hi = width\n    while lo + 1 < hi:\n        mid = (lo + hi) // 2\n        c = lines_for(mid)\n        if c is not None and c <= target:\n            hi = mid\n        else:\n            lo = mid + 1\n    out, cur = [], ''\n    for t in words:\n        cand = t if not cur else cur + ' ' + t\n        if len(cand) <= lo:\n            cur = cand\n        else:\n            out.append(cur)\n            cur = t\n    out.append(cur)\n    return out\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[('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'])]]\nfor label, args, expected in fixtures[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-typography-line-breaking-balanced-headline-search-termination","generated_at":"2026-09-29T14:49:52.803753+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Line breaking decides where paragraphs wrap on screen and in print; a wrong decision point shifts every following line.","root_cause":"The binary search stops when the bounds are adjacent, before testing the lower one.","sha256":"5197e3e2b64ba9d60fe8fa2da481e5e8dfb78c1ee3c38d89a456e9f5ad68f47a","title":"Balanced headline wrapping: search termination · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":42.405,"exit_code":1,"observations":[{"actual":["the type","grid is on","serif"],"check":"two balanced lines","expected":["the type grid","is on serif"],"passed":false},{"actual":["type on the","is ink of","grid"],"check":"regression: search termination","expected":["type on the is","ink of grid"],"passed":false},{"actual":["the at grid baseline","serif"],"check":"regression: search termination","expected":["the at grid baseline serif"],"passed":false},{"actual":["at","x","ink","at","the","is"],"check":"regression: search termination","expected":["at x","ink","at","the","is"],"passed":false},{"actual":["baseline","x"],"check":"word exactly the width","expected":["baseline","x"],"passed":true},{"actual":["at serif at measure","measure grid"],"check":"control layout","expected":["at serif at measure","measure grid"],"passed":true},{"actual":["at is the ink","x measure","grid at grid"],"check":"control layout","expected":["at is the ink","x measure","grid at grid"],"passed":true},{"actual":["kerning","x ink","the on","grid x","grid"],"check":"control layout","expected":["kerning","x ink","the on","grid x","grid"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two balanced lines\", \"actual\": [\"the type\", \"grid is on\", \"serif\"], \"expected\": [\"the type grid\", \"is on serif\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"type on the\", \"is ink of\", \"grid\"], \"expected\": [\"type on the is\", \"ink of grid\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"the at grid baseline\", \"serif\"], \"expected\": [\"the at grid baseline serif\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"at\", \"x\", \"ink\", \"at\", \"the\", \"is\"], \"expected\": [\"at x\", \"ink\", \"at\", \"the\", \"is\"], \"passed\": false}, {\"check\": \"word exactly the width\", \"actual\": [\"baseline\", \"x\"], \"expected\": [\"baseline\", \"x\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"at serif at measure\", \"measure grid\"], \"expected\": [\"at serif at measure\", \"measure grid\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"at is the ink\", \"x measure\", \"grid at grid\"], \"expected\": [\"at is the ink\", \"x measure\", \"grid at grid\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"kerning\", \"x ink\", \"the on\", \"grid x\", \"grid\"], \"expected\": [\"kerning\", \"x ink\", \"the on\", \"grid x\", \"grid\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.043,"exit_code":1,"observations":[{"actual":["the type","grid is on","serif"],"check":"two balanced lines","expected":["the type grid","is on serif"],"passed":false},{"actual":["type on the","is ink of","grid"],"check":"regression: search termination","expected":["type on the is","ink of grid"],"passed":false},{"actual":["the at grid baseline","serif"],"check":"regression: search termination","expected":["the at grid baseline serif"],"passed":false},{"actual":["at","x","ink","at","the","is"],"check":"regression: search termination","expected":["at x","ink","at","the","is"],"passed":false},{"actual":["baseline","x"],"check":"word exactly the width","expected":["baseline","x"],"passed":true},{"actual":["at serif at measure","measure grid"],"check":"control layout","expected":["at serif at measure","measure grid"],"passed":true},{"actual":["at is the ink","x measure","grid at grid"],"check":"control layout","expected":["at is the ink","x measure","grid at grid"],"passed":true},{"actual":["kerning","x ink","the on","grid x","grid"],"check":"control layout","expected":["kerning","x ink","the on","grid x","grid"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"two balanced lines\", \"actual\": [\"the type\", \"grid is on\", \"serif\"], \"expected\": [\"the type grid\", \"is on serif\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"type on the\", \"is ink of\", \"grid\"], \"expected\": [\"type on the is\", \"ink of grid\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"the at grid baseline\", \"serif\"], \"expected\": [\"the at grid baseline serif\"], \"passed\": false}, {\"check\": \"regression: search termination\", \"actual\": [\"at\", \"x\", \"ink\", \"at\", \"the\", \"is\"], \"expected\": [\"at x\", \"ink\", \"at\", \"the\", \"is\"], \"passed\": false}, {\"check\": \"word exactly the width\", \"actual\": [\"baseline\", \"x\"], \"expected\": [\"baseline\", \"x\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"at serif at measure\", \"measure grid\"], \"expected\": [\"at serif at measure\", \"measure grid\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"at is the ink\", \"x measure\", \"grid at grid\"], \"expected\": [\"at is the ink\", \"x measure\", \"grid at grid\"], \"passed\": true}, {\"check\": \"control layout\", \"actual\": [\"kerning\", \"x ink\", \"the on\", \"grid x\", \"grid\"], \"expected\": [\"kerning\", \"x ink\", \"the on\", \"grid x\", \"grid\"], \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}