Runt last-line prevention: greedy fill boundary · case 01

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    words, width, min_last = x
    lines = []
    cur = ''
    for w in words:
        cand = w if not cur else cur + ' ' + w
        if len(cand) < width or not cur:
            cur = cand
        else:
            lines.append(cur)
            cur = w
    lines.append(cur)
    while len(lines) >= 2 and len(lines[-1]) < min_last:
        prev = lines[-2].split(' ')
        if len(prev) < 2:
            break
        moved = prev[-1] + ' ' + lines[-1]
        if len(moved) > width:
            break
        lines[-2] = ' '.join(prev[:-1])
        lines[-1] = moved
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('regression: greedy fill boundary', [['a', 'the', 'of', 'measure', 'at', 'type', 'kerning', 'the', 'ink'], 15, 7], ['a the of', 'measure at type', 'kerning the ink']), ('regression: greedy fill boundary', [['baseline', 'type', 'is', 'serif', 'on', 'at', 'baseline'], 7, 3], ['baseline', 'type is', 'serif', 'on at', 'baseline']), ('partial-repair probe', [['a', 'is', 'grid', 'at', 'the', 'kerning', 'kerning', 'type', 'measure', 'ink', 'on'], 18, 5], ['a is grid at the', 'kerning kerning', 'type measure', 'ink on']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('control layout', [['a', 'x', 'is'], 15, 7], ['a x is']), ('control layout', [['grid', 'serif', 'at', 'measure'], 15, 3], ['grid serif at', 'measure']), ('control layout', [['serif', 'the', 'is', 'is', 'of', 'grid', 'at', 'is', 'a'], 10, 7], ['serif the', 'is is of', 'grid', 'at is a'])], [('regression: greedy fill boundary', [['is', 'the', 'serif', 'grid', 'serif', 'of', 'serif'], 13, 3], ['is the serif', 'grid serif of', 'serif']), ('regression: greedy fill boundary', [['baseline', 'is', 'grid', 'x', 'x', 'the', 'a', 'is', 'grid', 'at', 'kerning'], 18, 8], ['baseline is grid x', 'x the a is grid', 'at kerning']), ('regression: greedy fill boundary', [['ink', 'the', 'is', 'ink', 'baseline', 'is', 'grid', 'grid', 'x'], 6, 5], ['ink', 'the is', 'ink', 'baseline', 'is', 'grid', 'grid x']), ('regression: greedy fill boundary', [['baseline', 'x', 'at', 'the', 'measure', 'serif', 'ink', 'grid', 'a', 'the', 'on', 'kerning'], 13, 3], ['baseline x at', 'the measure', 'serif ink', 'grid a the on', 'kerning']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['x', 'measure', 'ink', 'measure', 'is'], 14, 4], ['x measure ink', 'measure is']), ('control layout', [['the', 'measure', 'ink', 'the', 'type', 'x', 'is', 'x'], 9, 3], ['the', 'measure', 'ink the', 'type x', 'is x'])], [('regression: greedy fill boundary', [['measure', 'of', 'baseline', 'a', 'on', 'at', 'kerning', 'measure', 'serif', 'grid', 'baseline', 'is'], 13, 8], ['measure of', 'baseline a on', 'at kerning', 'measure serif', 'grid', 'baseline is']), ('regression: greedy fill boundary', [['a', 'baseline', 'the', 'a', 'type', 'kerning', 'is', 'serif', 'a', 'grid', 'the'], 6, 3], ['a', 'baseline', 'the a', 'type', 'kerning', 'is', 'serif', 'a grid', 'the']), ('regression: greedy fill boundary', [['grid', 'measure', 'kerning', 'kerning', 'is', 'the', 'grid', 'is', 'measure', 'is', 'serif'], 14, 5], ['grid measure', 'kerning', 'kerning is the', 'grid is', 'measure is', 'serif']), ('regression: greedy fill boundary', [['baseline', 'of', 'of', 'type', 'serif', 'at', 'measure', 'serif', 'x', 'type', 'ink'], 11, 3], ['baseline of', 'of type', 'serif at', 'measure', 'serif x', 'type ink']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['is', 'of', 'of', 'is', 'type', 'kerning', 'the'], 9, 5], ['is of of', 'is type', 'kerning', 'the']), ('control layout', [['serif', 'grid', 'at', 'ink'], 19, 3], ['serif grid at ink'])], [('regression: greedy fill boundary', [['ink', 'on', 'kerning', 'ink', 'is', 'measure'], 14, 7], ['ink on kerning', 'ink is measure']), ('regression: greedy fill boundary', [['grid', 'ink', 'is', 'a', 'x', 'on', 'serif', 'serif', 'on', 'x', 'x', 'a'], 20, 5], ['grid ink is a x on', 'serif serif on x x a']), ('partial-repair probe', [['kerning', 'on', 'kerning'], 17, 7], ['kerning on', 'kerning']), ('partial-repair probe', [['of', 'on', 'ink', 'kerning', 'serif', 'x', 'grid', 'baseline'], 20, 8], ['of on ink kerning', 'serif x grid', 'baseline']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['kerning', 'type', 'baseline', 'on', 'type', 'a', 'is'], 16, 7], ['kerning type', 'baseline on', 'type a is']), ('control layout', [['serif', 'serif', 'grid', 'measure'], 7, 7], ['serif', 'serif', 'grid', 'measure'])], [('regression: greedy fill boundary', [['grid', 'grid', 'measure', 'on', 'serif', 'serif', 'grid', 'the', 'grid', 'is', 'type'], 12, 8], ['grid grid', 'measure on', 'serif serif', 'grid the', 'grid is type']), ('regression: greedy fill boundary', [['type', 'baseline', 'x', 'grid', 'type', 'grid'], 13, 7], ['type baseline', 'x grid', 'type grid']), ('partial-repair probe', [['grid', 'the', 'ink', 'measure', 'x', 'serif', 'kerning', 'type', 'measure', 'measure', 'on'], 19, 9], ['grid the ink', 'measure x serif', 'kerning type', 'measure measure on']), ('partial-repair probe', [['serif', 'of', 'of', 'serif', 'kerning', 'is', 'grid'], 6, 9], ['serif', 'of of', 'serif', 'kerning', 'is', 'grid']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['the', 'ink', 'kerning', 'of', 'at'], 8, 6], ['the ink', 'kerning', 'of at']), ('control layout', [['baseline', 'x', 'grid'], 7, 3], ['baseline', 'x grid'])]]
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)

SHA-256 / 9196d3b1e3cb286327b2e37788c9664e18bada74fc78d96a5add8e96a99c352c

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    words, width, min_last = x
    lines = []
    cur = ''
    for w in words:
        cand = w if not cur else cur + ' ' + w
        if len(cand) <= width + 1 or not cur:
            cur = cand
        else:
            lines.append(cur)
            cur = w
    lines.append(cur)
    while len(lines) >= 2 and len(lines[-1]) < min_last:
        prev = lines[-2].split(' ')
        if len(prev) < 2:
            break
        moved = prev[-1] + ' ' + lines[-1]
        if len(moved) > width:
            break
        lines[-2] = ' '.join(prev[:-1])
        lines[-1] = moved
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('regression: greedy fill boundary', [['a', 'the', 'of', 'measure', 'at', 'type', 'kerning', 'the', 'ink'], 15, 7], ['a the of', 'measure at type', 'kerning the ink']), ('regression: greedy fill boundary', [['baseline', 'type', 'is', 'serif', 'on', 'at', 'baseline'], 7, 3], ['baseline', 'type is', 'serif', 'on at', 'baseline']), ('partial-repair probe', [['a', 'is', 'grid', 'at', 'the', 'kerning', 'kerning', 'type', 'measure', 'ink', 'on'], 18, 5], ['a is grid at the', 'kerning kerning', 'type measure', 'ink on']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('control layout', [['a', 'x', 'is'], 15, 7], ['a x is']), ('control layout', [['grid', 'serif', 'at', 'measure'], 15, 3], ['grid serif at', 'measure']), ('control layout', [['serif', 'the', 'is', 'is', 'of', 'grid', 'at', 'is', 'a'], 10, 7], ['serif the', 'is is of', 'grid', 'at is a'])], [('regression: greedy fill boundary', [['is', 'the', 'serif', 'grid', 'serif', 'of', 'serif'], 13, 3], ['is the serif', 'grid serif of', 'serif']), ('regression: greedy fill boundary', [['baseline', 'is', 'grid', 'x', 'x', 'the', 'a', 'is', 'grid', 'at', 'kerning'], 18, 8], ['baseline is grid x', 'x the a is grid', 'at kerning']), ('regression: greedy fill boundary', [['ink', 'the', 'is', 'ink', 'baseline', 'is', 'grid', 'grid', 'x'], 6, 5], ['ink', 'the is', 'ink', 'baseline', 'is', 'grid', 'grid x']), ('regression: greedy fill boundary', [['baseline', 'x', 'at', 'the', 'measure', 'serif', 'ink', 'grid', 'a', 'the', 'on', 'kerning'], 13, 3], ['baseline x at', 'the measure', 'serif ink', 'grid a the on', 'kerning']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['x', 'measure', 'ink', 'measure', 'is'], 14, 4], ['x measure ink', 'measure is']), ('control layout', [['the', 'measure', 'ink', 'the', 'type', 'x', 'is', 'x'], 9, 3], ['the', 'measure', 'ink the', 'type x', 'is x'])], [('regression: greedy fill boundary', [['measure', 'of', 'baseline', 'a', 'on', 'at', 'kerning', 'measure', 'serif', 'grid', 'baseline', 'is'], 13, 8], ['measure of', 'baseline a on', 'at kerning', 'measure serif', 'grid', 'baseline is']), ('regression: greedy fill boundary', [['a', 'baseline', 'the', 'a', 'type', 'kerning', 'is', 'serif', 'a', 'grid', 'the'], 6, 3], ['a', 'baseline', 'the a', 'type', 'kerning', 'is', 'serif', 'a grid', 'the']), ('regression: greedy fill boundary', [['grid', 'measure', 'kerning', 'kerning', 'is', 'the', 'grid', 'is', 'measure', 'is', 'serif'], 14, 5], ['grid measure', 'kerning', 'kerning is the', 'grid is', 'measure is', 'serif']), ('regression: greedy fill boundary', [['baseline', 'of', 'of', 'type', 'serif', 'at', 'measure', 'serif', 'x', 'type', 'ink'], 11, 3], ['baseline of', 'of type', 'serif at', 'measure', 'serif x', 'type ink']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['is', 'of', 'of', 'is', 'type', 'kerning', 'the'], 9, 5], ['is of of', 'is type', 'kerning', 'the']), ('control layout', [['serif', 'grid', 'at', 'ink'], 19, 3], ['serif grid at ink'])], [('regression: greedy fill boundary', [['ink', 'on', 'kerning', 'ink', 'is', 'measure'], 14, 7], ['ink on kerning', 'ink is measure']), ('regression: greedy fill boundary', [['grid', 'ink', 'is', 'a', 'x', 'on', 'serif', 'serif', 'on', 'x', 'x', 'a'], 20, 5], ['grid ink is a x on', 'serif serif on x x a']), ('partial-repair probe', [['kerning', 'on', 'kerning'], 17, 7], ['kerning on', 'kerning']), ('partial-repair probe', [['of', 'on', 'ink', 'kerning', 'serif', 'x', 'grid', 'baseline'], 20, 8], ['of on ink kerning', 'serif x grid', 'baseline']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['kerning', 'type', 'baseline', 'on', 'type', 'a', 'is'], 16, 7], ['kerning type', 'baseline on', 'type a is']), ('control layout', [['serif', 'serif', 'grid', 'measure'], 7, 7], ['serif', 'serif', 'grid', 'measure'])], [('regression: greedy fill boundary', [['grid', 'grid', 'measure', 'on', 'serif', 'serif', 'grid', 'the', 'grid', 'is', 'type'], 12, 8], ['grid grid', 'measure on', 'serif serif', 'grid the', 'grid is type']), ('regression: greedy fill boundary', [['type', 'baseline', 'x', 'grid', 'type', 'grid'], 13, 7], ['type baseline', 'x grid', 'type grid']), ('partial-repair probe', [['grid', 'the', 'ink', 'measure', 'x', 'serif', 'kerning', 'type', 'measure', 'measure', 'on'], 19, 9], ['grid the ink', 'measure x serif', 'kerning type', 'measure measure on']), ('partial-repair probe', [['serif', 'of', 'of', 'serif', 'kerning', 'is', 'grid'], 6, 9], ['serif', 'of of', 'serif', 'kerning', 'is', 'grid']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['the', 'ink', 'kerning', 'of', 'at'], 8, 6], ['the ink', 'kerning', 'of at']), ('control layout', [['baseline', 'x', 'grid'], 7, 3], ['baseline', 'x grid'])]]
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)

SHA-256 / aff963c53d8616d77c88ec4f1cc1505a494d01fe9574142dd5b8e7fcbc8bb279

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    words, width, min_last = x
    lines = []
    cur = ''
    for w in words:
        cand = w if not cur else cur + ' ' + w
        if len(cand) <= width or not cur:
            cur = cand
        else:
            lines.append(cur)
            cur = w
    lines.append(cur)
    while len(lines) >= 2 and len(lines[-1]) < min_last:
        prev = lines[-2].split(' ')
        if len(prev) < 2:
            break
        moved = prev[-1] + ' ' + lines[-1]
        if len(moved) > width:
            break
        lines[-2] = ' '.join(prev[:-1])
        lines[-1] = moved
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('regression: greedy fill boundary', [['a', 'the', 'of', 'measure', 'at', 'type', 'kerning', 'the', 'ink'], 15, 7], ['a the of', 'measure at type', 'kerning the ink']), ('regression: greedy fill boundary', [['baseline', 'type', 'is', 'serif', 'on', 'at', 'baseline'], 7, 3], ['baseline', 'type is', 'serif', 'on at', 'baseline']), ('partial-repair probe', [['a', 'is', 'grid', 'at', 'the', 'kerning', 'kerning', 'type', 'measure', 'ink', 'on'], 18, 5], ['a is grid at the', 'kerning kerning', 'type measure', 'ink on']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('control layout', [['a', 'x', 'is'], 15, 7], ['a x is']), ('control layout', [['grid', 'serif', 'at', 'measure'], 15, 3], ['grid serif at', 'measure']), ('control layout', [['serif', 'the', 'is', 'is', 'of', 'grid', 'at', 'is', 'a'], 10, 7], ['serif the', 'is is of', 'grid', 'at is a'])], [('regression: greedy fill boundary', [['is', 'the', 'serif', 'grid', 'serif', 'of', 'serif'], 13, 3], ['is the serif', 'grid serif of', 'serif']), ('regression: greedy fill boundary', [['baseline', 'is', 'grid', 'x', 'x', 'the', 'a', 'is', 'grid', 'at', 'kerning'], 18, 8], ['baseline is grid x', 'x the a is grid', 'at kerning']), ('regression: greedy fill boundary', [['ink', 'the', 'is', 'ink', 'baseline', 'is', 'grid', 'grid', 'x'], 6, 5], ['ink', 'the is', 'ink', 'baseline', 'is', 'grid', 'grid x']), ('regression: greedy fill boundary', [['baseline', 'x', 'at', 'the', 'measure', 'serif', 'ink', 'grid', 'a', 'the', 'on', 'kerning'], 13, 3], ['baseline x at', 'the measure', 'serif ink', 'grid a the on', 'kerning']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['x', 'measure', 'ink', 'measure', 'is'], 14, 4], ['x measure ink', 'measure is']), ('control layout', [['the', 'measure', 'ink', 'the', 'type', 'x', 'is', 'x'], 9, 3], ['the', 'measure', 'ink the', 'type x', 'is x'])], [('regression: greedy fill boundary', [['measure', 'of', 'baseline', 'a', 'on', 'at', 'kerning', 'measure', 'serif', 'grid', 'baseline', 'is'], 13, 8], ['measure of', 'baseline a on', 'at kerning', 'measure serif', 'grid', 'baseline is']), ('regression: greedy fill boundary', [['a', 'baseline', 'the', 'a', 'type', 'kerning', 'is', 'serif', 'a', 'grid', 'the'], 6, 3], ['a', 'baseline', 'the a', 'type', 'kerning', 'is', 'serif', 'a grid', 'the']), ('regression: greedy fill boundary', [['grid', 'measure', 'kerning', 'kerning', 'is', 'the', 'grid', 'is', 'measure', 'is', 'serif'], 14, 5], ['grid measure', 'kerning', 'kerning is the', 'grid is', 'measure is', 'serif']), ('regression: greedy fill boundary', [['baseline', 'of', 'of', 'type', 'serif', 'at', 'measure', 'serif', 'x', 'type', 'ink'], 11, 3], ['baseline of', 'of type', 'serif at', 'measure', 'serif x', 'type ink']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['is', 'of', 'of', 'is', 'type', 'kerning', 'the'], 9, 5], ['is of of', 'is type', 'kerning', 'the']), ('control layout', [['serif', 'grid', 'at', 'ink'], 19, 3], ['serif grid at ink'])], [('regression: greedy fill boundary', [['ink', 'on', 'kerning', 'ink', 'is', 'measure'], 14, 7], ['ink on kerning', 'ink is measure']), ('regression: greedy fill boundary', [['grid', 'ink', 'is', 'a', 'x', 'on', 'serif', 'serif', 'on', 'x', 'x', 'a'], 20, 5], ['grid ink is a x on', 'serif serif on x x a']), ('partial-repair probe', [['kerning', 'on', 'kerning'], 17, 7], ['kerning on', 'kerning']), ('partial-repair probe', [['of', 'on', 'ink', 'kerning', 'serif', 'x', 'grid', 'baseline'], 20, 8], ['of on ink kerning', 'serif x grid', 'baseline']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['kerning', 'type', 'baseline', 'on', 'type', 'a', 'is'], 16, 7], ['kerning type', 'baseline on', 'type a is']), ('control layout', [['serif', 'serif', 'grid', 'measure'], 7, 7], ['serif', 'serif', 'grid', 'measure'])], [('regression: greedy fill boundary', [['grid', 'grid', 'measure', 'on', 'serif', 'serif', 'grid', 'the', 'grid', 'is', 'type'], 12, 8], ['grid grid', 'measure on', 'serif serif', 'grid the', 'grid is type']), ('regression: greedy fill boundary', [['type', 'baseline', 'x', 'grid', 'type', 'grid'], 13, 7], ['type baseline', 'x grid', 'type grid']), ('partial-repair probe', [['grid', 'the', 'ink', 'measure', 'x', 'serif', 'kerning', 'type', 'measure', 'measure', 'on'], 19, 9], ['grid the ink', 'measure x serif', 'kerning type', 'measure measure on']), ('partial-repair probe', [['serif', 'of', 'of', 'serif', 'kerning', 'is', 'grid'], 6, 9], ['serif', 'of of', 'serif', 'kerning', 'is', 'grid']), ('one-word runt pulled down', [['the', 'type', 'grid', 'is', 'a'], 12, 5], ['the type', 'grid is a']), ('runt limited by width', [['kerning', 'baseline', 'x'], 10, 4], ['kerning', 'baseline x']), ('control layout', [['the', 'ink', 'kerning', 'of', 'at'], 8, 6], ['the ink', 'kerning', 'of at']), ('control layout', [['baseline', 'x', 'grid'], 7, 3], ['baseline', 'x grid'])]]
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)

SHA-256 / 34175ea798b548e397ec893135915337064d0de10ac82ad341a12be8454fca21