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

N = 1
observations = []
def solve(x):
    words, width, limit = x
    queue = [list(w) for w in words]
    lines = []
    cur = ''
    streak = 0
    k = 0
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        need = len(token) if cur == '' else len(cur) + 1 + len(token)
        if need <= width:
            cur = token if cur == '' else cur + ' ' + token
            k += 1
            continue
        split = None
        if streak < limit and k < len(queue) - 1:
            for cut in range(1, len(syl)):
                head = ''.join(syl[:cut]) + '-'
                room = len(head) if cur == '' else len(cur) + len(head) + 1
                if room <= width:
                    split = cut
                    break
        if split is not None:
            head = ''.join(syl[:split]) + '-'
            lines.append(head if cur == '' else cur + ' ' + head)
            queue[k] = syl[split:]
            cur = ''
            streak += 1
        elif cur == '':
            lines.append(token)
            k += 1
            streak = 0
        else:
            lines.append(cur)
            cur, streak = '', 0
    if cur:
        lines.append(cur)
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['pa', 'ra', 'graph'], ['a'], ['type'], ['a'], ['com', 'po', 'si', 'tion'], ['kern', 'ing'], ['of']], 14, 3], ['international', 'paragraph a', 'type a compo-', 'sition kerning', 'of']), ('regression: latest boundary preference', [[['set', 'ting'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['type'], ['type'], ['text'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['a'], ['set', 'ting']], 11, 2], ['setting', 'justified', 'breaking', 'type type', 'text break-', 'ing hyphen-', 'ation a', 'setting']), ('regression: latest boundary preference', [[['mar', 'gin'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['col', 'umn'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['set', 'ting'], ['a']], 6, 3], ['margin', 'justi-', 'fied', 'lead-', 'ing', 'column', 'of in-', 'terna-', 'tional', 'hy-', 'phena-', 'tion', 'para-', 'graph', 'lead-', 'ing', 'set-', 'ting a']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['to'], ['break', 'ing'], ['break', 'ing'], ['type'], ['lead', 'ing'], ['break', 'ing'], ['jus', 'ti', 'fied']], 12, 1], ['to breaking', 'breaking', 'type leading', 'breaking', 'justified']), ('control layout', [[['pa', 'ra', 'graph'], ['kern', 'ing'], ['kern', 'ing'], ['set', 'ting'], ['mar', 'gin'], ['set', 'ting']], 9, 2], ['paragraph', 'kerning', 'kerning', 'setting', 'margin', 'setting']), ('control layout', [[['col', 'umn'], ['set', 'ting'], ['break', 'ing'], ['type'], ['text'], ['of'], ['pa', 'ra', 'graph']], 10, 1], ['column', 'setting', 'breaking', 'type text', 'of', 'paragraph'])], [('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['to'], ['kern', 'ing'], ['a'], ['col', 'umn'], ['line'], ['of'], ['of'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing']], 14, 1], ['international', 'to kerning a', 'column line of', 'of of interna-', 'tional kerning']), ('regression: latest boundary preference', [[['a'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['to'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['line'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['hy', 'phen', 'a', 'tion']], 14, 3], ['a internation-', 'al of to mar-', 'gin justified', 'paragraph', 'leading line', 'international', 'a hyphenation']), ('regression: latest boundary preference', [[['jus', 'ti', 'fied'], ['com', 'po', 'si', 'tion'], ['type'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['lead', 'ing'], ['lead', 'ing'], ['hy', 'phen', 'a', 'tion'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph'], ['set', 'ting'], ['lead', 'ing']], 7, 1], ['justi-', 'fied', 'compo-', 'sition', 'type', 'margin', 'inter-', 'national', 'leading', 'leading', 'hyphen-', 'ation', 'compo-', 'sition', 'para-', 'graph', 'setting', 'leading']), ('partial-repair probe', [[['of'], ['lead', 'ing'], ['set', 'ting'], ['kern', 'ing'], ['col', 'umn'], ['line'], ['type'], ['col', 'umn']], 13, 3], ['of leading', 'setting kern-', 'ing column', 'line type', 'column']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['col', 'umn'], ['jus', 'ti', 'fied'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['type']], 9, 2], ['column', 'justified', 'margin', 'justified', 'type']), ('control layout', [[['kern', 'ing'], ['line'], ['kern', 'ing'], ['a'], ['to']], 14, 1], ['kerning line', 'kerning a to'])], [('regression: latest boundary preference', [[['mar', 'gin'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['col', 'umn'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['set', 'ting'], ['a']], 6, 3], ['margin', 'justi-', 'fied', 'lead-', 'ing', 'column', 'of in-', 'terna-', 'tional', 'hy-', 'phena-', 'tion', 'para-', 'graph', 'lead-', 'ing', 'set-', 'ting a']), ('regression: latest boundary preference', [[['set', 'ting'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['type'], ['type'], ['text'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['a'], ['set', 'ting']], 11, 2], ['setting', 'justified', 'breaking', 'type type', 'text break-', 'ing hyphen-', 'ation a', 'setting']), ('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['type'], ['type'], ['lead', 'ing'], ['break', 'ing'], ['mar', 'gin'], ['break', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['set', 'ting']], 9, 1], ['interna-', 'tional', 'hyphena-', 'tion', 'kerning', 'interna-', 'tional', 'type type', 'leading', 'breaking', 'margin', 'breaking', 'interna-', 'tional', 'setting']), ('regression: latest boundary preference', [[['a'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['mar', 'gin'], ['hy', 'phen', 'a', 'tion'], ['mar', 'gin'], ['type'], ['to']], 13, 3], ['a composition', 'leading mar-', 'gin hyphena-', 'tion margin', 'type to']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['type'], ['lead', 'ing'], ['of'], ['jus', 'ti', 'fied'], ['mar', 'gin']], 8, 3], ['type', 'leading', 'of jus-', 'tified', 'margin']), ('control layout', [[['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph']], 13, 2], ['composition', 'international', 'margin hy-', 'phenation', 'paragraph'])], [('regression: latest boundary preference', [[['to'], ['of'], ['type'], ['line'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['line'], ['pa', 'ra', 'graph'], ['jus', 'ti', 'fied'], ['col', 'umn']], 8, 1], ['to of', 'type', 'line', 'justi-', 'fied', 'para-', 'graph', 'line pa-', 'ragraph', 'justi-', 'fied', 'column']), ('regression: latest boundary preference', [[['jus', 'ti', 'fied'], ['type'], ['type'], ['kern', 'ing'], ['lead', 'ing']], 6, 3], ['justi-', 'fied', 'type', 'type', 'kern-', 'ing', 'leading']), ('regression: latest boundary preference', [[['hy', 'phen', 'a', 'tion'], ['a'], ['line'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['text'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['lead', 'ing'], ['type']], 11, 2], ['hyphenation', 'a line mar-', 'gin inter-', 'national', 'text compo-', 'sition', 'leading', 'leading', 'type']), ('regression: latest boundary preference', [[['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['col', 'umn']], 7, 3], ['break-', 'ing hy-', 'phena-', 'tion', 'justi-', 'fied', 'para-', 'graph', 'column']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['col', 'umn'], ['com', 'po', 'si', 'tion'], ['a'], ['col', 'umn'], ['line']], 12, 2], ['column com-', 'position a', 'column line']), ('control layout', [[['line'], ['jus', 'ti', 'fied'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['of'], ['line']], 9, 3], ['line jus-', 'tified', 'margin', 'justified', 'breaking', 'of line'])], [('regression: latest boundary preference', [[['kern', 'ing'], ['pa', 'ra', 'graph'], ['a'], ['pa', 'ra', 'graph'], ['of'], ['pa', 'ra', 'graph'], ['text']], 6, 1], ['kern-', 'ing', 'para-', 'graph', 'a pa-', 'ragraph', 'of pa-', 'ragraph', 'text']), ('regression: latest boundary preference', [[['set', 'ting'], ['line'], ['pa', 'ra', 'graph'], ['of'], ['text'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph']], 10, 1], ['setting', 'line para-', 'graph of', 'text para-', 'graph', 'hyphena-', 'tion', 'leading', 'composi-', 'tion', 'paragraph']), ('regression: latest boundary preference', [[['set', 'ting'], ['hy', 'phen', 'a', 'tion'], ['jus', 'ti', 'fied'], ['of'], ['type'], ['col', 'umn'], ['line'], ['mar', 'gin'], ['to'], ['kern', 'ing']], 9, 3], ['setting', 'hyphena-', 'tion jus-', 'tified of', 'type col-', 'umn line', 'margin to', 'kerning']), ('partial-repair probe', [[['text'], ['kern', 'ing'], ['line'], ['set', 'ting'], ['break', 'ing'], ['to'], ['mar', 'gin'], ['line'], ['col', 'umn'], ['lead', 'ing'], ['com', 'po', 'si', 'tion'], ['type']], 13, 1], ['text kerning', 'line setting', 'breaking to', 'margin line', 'column lead-', 'ing', 'composition', 'type']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['set', 'ting'], ['set', 'ting'], ['a'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['to'], ['col', 'umn'], ['break', 'ing'], ['jus', 'ti', 'fied'], ['type'], ['set', 'ting']], 11, 3], ['setting', 'setting a', 'justified', 'paragraph', 'to column', 'breaking', 'justified', 'type', 'setting']), ('control layout', [[['to'], ['to'], ['com', 'po', 'si', 'tion'], ['line'], ['type'], ['com', 'po', 'si', 'tion'], ['col', 'umn'], ['break', 'ing']], 11, 2], ['to to com-', 'position', 'line type', 'composition', 'column', 'breaking'])]]
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)

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

N = 1
observations = []
def solve(x):
    words, width, limit = x
    queue = [list(w) for w in words]
    lines = []
    cur = ''
    streak = 0
    k = 0
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        need = len(token) if cur == '' else len(cur) + 1 + len(token)
        if need <= width:
            cur = token if cur == '' else cur + ' ' + token
            k += 1
            continue
        split = None
        if streak < limit and k < len(queue) - 1:
            for cut in range(len(syl) - 2, 0, -1):
                head = ''.join(syl[:cut]) + '-'
                room = len(head) if cur == '' else len(cur) + len(head) + 1
                if room <= width:
                    split = cut
                    break
        if split is not None:
            head = ''.join(syl[:split]) + '-'
            lines.append(head if cur == '' else cur + ' ' + head)
            queue[k] = syl[split:]
            cur = ''
            streak += 1
        elif cur == '':
            lines.append(token)
            k += 1
            streak = 0
        else:
            lines.append(cur)
            cur, streak = '', 0
    if cur:
        lines.append(cur)
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['pa', 'ra', 'graph'], ['a'], ['type'], ['a'], ['com', 'po', 'si', 'tion'], ['kern', 'ing'], ['of']], 14, 3], ['international', 'paragraph a', 'type a compo-', 'sition kerning', 'of']), ('regression: latest boundary preference', [[['set', 'ting'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['type'], ['type'], ['text'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['a'], ['set', 'ting']], 11, 2], ['setting', 'justified', 'breaking', 'type type', 'text break-', 'ing hyphen-', 'ation a', 'setting']), ('regression: latest boundary preference', [[['mar', 'gin'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['col', 'umn'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['set', 'ting'], ['a']], 6, 3], ['margin', 'justi-', 'fied', 'lead-', 'ing', 'column', 'of in-', 'terna-', 'tional', 'hy-', 'phena-', 'tion', 'para-', 'graph', 'lead-', 'ing', 'set-', 'ting a']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['to'], ['break', 'ing'], ['break', 'ing'], ['type'], ['lead', 'ing'], ['break', 'ing'], ['jus', 'ti', 'fied']], 12, 1], ['to breaking', 'breaking', 'type leading', 'breaking', 'justified']), ('control layout', [[['pa', 'ra', 'graph'], ['kern', 'ing'], ['kern', 'ing'], ['set', 'ting'], ['mar', 'gin'], ['set', 'ting']], 9, 2], ['paragraph', 'kerning', 'kerning', 'setting', 'margin', 'setting']), ('control layout', [[['col', 'umn'], ['set', 'ting'], ['break', 'ing'], ['type'], ['text'], ['of'], ['pa', 'ra', 'graph']], 10, 1], ['column', 'setting', 'breaking', 'type text', 'of', 'paragraph'])], [('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['to'], ['kern', 'ing'], ['a'], ['col', 'umn'], ['line'], ['of'], ['of'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing']], 14, 1], ['international', 'to kerning a', 'column line of', 'of of interna-', 'tional kerning']), ('regression: latest boundary preference', [[['a'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['to'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['line'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['hy', 'phen', 'a', 'tion']], 14, 3], ['a internation-', 'al of to mar-', 'gin justified', 'paragraph', 'leading line', 'international', 'a hyphenation']), ('regression: latest boundary preference', [[['jus', 'ti', 'fied'], ['com', 'po', 'si', 'tion'], ['type'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['lead', 'ing'], ['lead', 'ing'], ['hy', 'phen', 'a', 'tion'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph'], ['set', 'ting'], ['lead', 'ing']], 7, 1], ['justi-', 'fied', 'compo-', 'sition', 'type', 'margin', 'inter-', 'national', 'leading', 'leading', 'hyphen-', 'ation', 'compo-', 'sition', 'para-', 'graph', 'setting', 'leading']), ('partial-repair probe', [[['of'], ['lead', 'ing'], ['set', 'ting'], ['kern', 'ing'], ['col', 'umn'], ['line'], ['type'], ['col', 'umn']], 13, 3], ['of leading', 'setting kern-', 'ing column', 'line type', 'column']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['col', 'umn'], ['jus', 'ti', 'fied'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['type']], 9, 2], ['column', 'justified', 'margin', 'justified', 'type']), ('control layout', [[['kern', 'ing'], ['line'], ['kern', 'ing'], ['a'], ['to']], 14, 1], ['kerning line', 'kerning a to'])], [('regression: latest boundary preference', [[['mar', 'gin'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['col', 'umn'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['set', 'ting'], ['a']], 6, 3], ['margin', 'justi-', 'fied', 'lead-', 'ing', 'column', 'of in-', 'terna-', 'tional', 'hy-', 'phena-', 'tion', 'para-', 'graph', 'lead-', 'ing', 'set-', 'ting a']), ('regression: latest boundary preference', [[['set', 'ting'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['type'], ['type'], ['text'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['a'], ['set', 'ting']], 11, 2], ['setting', 'justified', 'breaking', 'type type', 'text break-', 'ing hyphen-', 'ation a', 'setting']), ('regression: latest boundary preference', [[['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['type'], ['type'], ['lead', 'ing'], ['break', 'ing'], ['mar', 'gin'], ['break', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['set', 'ting']], 9, 1], ['interna-', 'tional', 'hyphena-', 'tion', 'kerning', 'interna-', 'tional', 'type type', 'leading', 'breaking', 'margin', 'breaking', 'interna-', 'tional', 'setting']), ('regression: latest boundary preference', [[['a'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['mar', 'gin'], ['hy', 'phen', 'a', 'tion'], ['mar', 'gin'], ['type'], ['to']], 13, 3], ['a composition', 'leading mar-', 'gin hyphena-', 'tion margin', 'type to']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['type'], ['lead', 'ing'], ['of'], ['jus', 'ti', 'fied'], ['mar', 'gin']], 8, 3], ['type', 'leading', 'of jus-', 'tified', 'margin']), ('control layout', [[['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph']], 13, 2], ['composition', 'international', 'margin hy-', 'phenation', 'paragraph'])], [('regression: latest boundary preference', [[['to'], ['of'], ['type'], ['line'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['line'], ['pa', 'ra', 'graph'], ['jus', 'ti', 'fied'], ['col', 'umn']], 8, 1], ['to of', 'type', 'line', 'justi-', 'fied', 'para-', 'graph', 'line pa-', 'ragraph', 'justi-', 'fied', 'column']), ('regression: latest boundary preference', [[['jus', 'ti', 'fied'], ['type'], ['type'], ['kern', 'ing'], ['lead', 'ing']], 6, 3], ['justi-', 'fied', 'type', 'type', 'kern-', 'ing', 'leading']), ('regression: latest boundary preference', [[['hy', 'phen', 'a', 'tion'], ['a'], ['line'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['text'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['lead', 'ing'], ['type']], 11, 2], ['hyphenation', 'a line mar-', 'gin inter-', 'national', 'text compo-', 'sition', 'leading', 'leading', 'type']), ('regression: latest boundary preference', [[['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['col', 'umn']], 7, 3], ['break-', 'ing hy-', 'phena-', 'tion', 'justi-', 'fied', 'para-', 'graph', 'column']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['col', 'umn'], ['com', 'po', 'si', 'tion'], ['a'], ['col', 'umn'], ['line']], 12, 2], ['column com-', 'position a', 'column line']), ('control layout', [[['line'], ['jus', 'ti', 'fied'], ['mar', 'gin'], ['jus', 'ti', 'fied'], ['break', 'ing'], ['of'], ['line']], 9, 3], ['line jus-', 'tified', 'margin', 'justified', 'breaking', 'of line'])], [('regression: latest boundary preference', [[['kern', 'ing'], ['pa', 'ra', 'graph'], ['a'], ['pa', 'ra', 'graph'], ['of'], ['pa', 'ra', 'graph'], ['text']], 6, 1], ['kern-', 'ing', 'para-', 'graph', 'a pa-', 'ragraph', 'of pa-', 'ragraph', 'text']), ('regression: latest boundary preference', [[['set', 'ting'], ['line'], ['pa', 'ra', 'graph'], ['of'], ['text'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph']], 10, 1], ['setting', 'line para-', 'graph of', 'text para-', 'graph', 'hyphena-', 'tion', 'leading', 'composi-', 'tion', 'paragraph']), ('regression: latest boundary preference', [[['set', 'ting'], ['hy', 'phen', 'a', 'tion'], ['jus', 'ti', 'fied'], ['of'], ['type'], ['col', 'umn'], ['line'], ['mar', 'gin'], ['to'], ['kern', 'ing']], 9, 3], ['setting', 'hyphena-', 'tion jus-', 'tified of', 'type col-', 'umn line', 'margin to', 'kerning']), ('partial-repair probe', [[['text'], ['kern', 'ing'], ['line'], ['set', 'ting'], ['break', 'ing'], ['to'], ['mar', 'gin'], ['line'], ['col', 'umn'], ['lead', 'ing'], ['com', 'po', 'si', 'tion'], ['type']], 13, 1], ['text kerning', 'line setting', 'breaking to', 'margin line', 'column lead-', 'ing', 'composition', 'type']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['set', 'ting'], ['set', 'ting'], ['a'], ['jus', 'ti', 'fied'], ['pa', 'ra', 'graph'], ['to'], ['col', 'umn'], ['break', 'ing'], ['jus', 'ti', 'fied'], ['type'], ['set', 'ting']], 11, 3], ['setting', 'setting a', 'justified', 'paragraph', 'to column', 'breaking', 'justified', 'type', 'setting']), ('control layout', [[['to'], ['to'], ['com', 'po', 'si', 'tion'], ['line'], ['type'], ['com', 'po', 'si', 'tion'], ['col', 'umn'], ['break', 'ing']], 11, 2], ['to to com-', 'position', 'line type', 'composition', 'column', 'breaking'])]]
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)

prompt:
Words are split at their first syllable, wasting line space.

Input [words as syllable lists, width, limit]. Greedy fill with 1-unit spaces and characters. A word that does not fit may be split at the latest syllable boundary whose head plus "-" fits, only if fewer than limit immediately preceding lines ended in a hyphen and the word is not the paragraph's last word. A line ended without hyphen resets the streak; a word too long for an empty line is set alone. Return the lines.

split: open-access


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

N = 1
observations = []
def solve(x):
    words, width, limit = x
    queue = [list(w) for w in words]
    lines = []
    cur = ''
    streak = 0
    k = 0
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        need = len(token) if cur == '' else len(cur) + 1 + len(token)
        if need < width:
            cur = token if cur == '' else cur + ' ' + token
            k += 1
            continue
        split = None
        if streak < limit and k < len(queue) - 1:
            for cut in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:cut]) + '-'
                room = len(head) if cur == '' else len(cur) + len(head) + 1
                if room <= width:
                    split = cut
                    break
        if split is not None:
            head = ''.join(syl[:split]) + '-'
            lines.append(head if cur == '' else cur + ' ' + head)
            queue[k] = syl[split:]
            cur = ''
            streak += 1
        elif cur == '':
            lines.append(token)
            k += 1
            streak = 0
        else:
            lines.append(cur)
            cur, streak = '', 0
    if cur:
        lines.append(cur)
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: whole-word fit test', [[['lead', 'ing'], ['a'], ['jus', 'ti', 'fied'], ['a'], ['a'], ['pa', 'ra', 'graph'], ['set', 'ting'], ['jus', 'ti', 'fied']], 6, 1], ['lead-', 'ing a', 'justi-', 'fied a', 'a pa-', 'ragraph', 'set-', 'ting', 'justified']), ('regression: whole-word fit test', [[['lead', 'ing'], ['kern', 'ing'], ['com', 'po', 'si', 'tion'], ['text'], ['lead', 'ing'], ['kern', 'ing'], ['hy', 'phen', 'a', 'tion'], ['hy', 'phen', 'a', 'tion'], ['a'], ['text'], ['pa', 'ra', 'graph']], 14, 1], ['leading kern-', 'ing', 'composition', 'text leading', 'kerning hy-', 'phenation', 'hyphenation a', 'text paragraph']), ('partial-repair probe', [[['break', 'ing'], ['kern', 'ing'], ['set', 'ting'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['to'], ['line'], ['jus', 'ti', 'fied']], 12, 1], ['breaking', 'kerning set-', 'ting', 'breaking hy-', 'phenation', 'leading to', 'line', 'justified']), ('regression: whole-word fit test', [[['to'], ['line'], ['com', 'po', 'si', 'tion'], ['mar', 'gin'], ['mar', 'gin'], ['type'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['col', 'umn'], ['line'], ['com', 'po', 'si', 'tion'], ['to']], 14, 1], ['to line compo-', 'sition margin', 'margin type', 'kerning inter-', 'national', 'column line', 'composition to']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['a'], ['hy', 'phen', 'a', 'tion'], ['break', 'ing']], 9, 3], ['interna-', 'tional', 'hyphena-', 'tion a', 'hyphena-', 'tion', 'breaking']), ('control layout', [[['text'], ['line'], ['hy', 'phen', 'a', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['set', 'ting']], 14, 2], ['text line hy-', 'phenation in-', 'ternational', 'composition', 'setting'])], [('regression: whole-word fit test', [[['pa', 'ra', 'graph'], ['of'], ['type'], ['lead', 'ing'], ['col', 'umn'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['kern', 'ing'], ['set', 'ting']], 7, 3], ['para-', 'graph', 'of type', 'leading', 'column', 'para-', 'graph', 'leading', 'kerning', 'setting']), ('regression: whole-word fit test', [[['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['to'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['set', 'ting'], ['col', 'umn']], 13, 3], ['hyphenation', 'leading to', 'international', 'a setting', 'column']), ('partial-repair probe', [[['jus', 'ti', 'fied'], ['text'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['mar', 'gin'], ['of'], ['break', 'ing'], ['line']], 12, 1], ['justified', 'text of in-', 'ternational', 'internation-', 'al margin', 'margin of', 'breaking', 'line']), ('partial-repair probe', [[['lead', 'ing'], ['pa', 'ra', 'graph'], ['to'], ['mar', 'gin'], ['line'], ['jus', 'ti', 'fied']], 14, 3], ['leading para-', 'graph to mar-', 'gin line', 'justified']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['jus', 'ti', 'fied'], ['col', 'umn'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph'], ['to'], ['jus', 'ti', 'fied'], ['mar', 'gin']], 12, 2], ['justified', 'column com-', 'position pa-', 'ragraph to', 'justified', 'margin']), ('control layout', [[['a'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['set', 'ting'], ['pa', 'ra', 'graph']], 11, 1], ['a kerning', 'interna-', 'tional', 'setting', 'paragraph'])], [('regression: whole-word fit test', [[['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['break', 'ing'], ['mar', 'gin'], ['line'], ['set', 'ting'], ['in', 'ter', 'na', 'tion', 'al']], 6, 1], ['compo-', 'sition', 'inter-', 'national', 'margin', 'break-', 'ing', 'margin', 'line', 'set-', 'ting', 'international']), ('regression: whole-word fit test', [[['col', 'umn'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing'], ['type'], ['lead', 'ing'], ['lead', 'ing'], ['text'], ['text'], ['pa', 'ra', 'graph']], 6, 1], ['column', 'inter-', 'national', 'kern-', 'ing', 'type', 'lead-', 'ing', 'lead-', 'ing', 'text', 'text', 'paragraph']), ('regression: whole-word fit test', [[['line'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['pa', 'ra', 'graph'], ['a'], ['a']], 7, 2], ['line', 'inter-', 'nation-', 'al', 'margin', 'para-', 'graph a', 'a']), ('regression: whole-word fit test', [[['break', 'ing'], ['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['break', 'ing'], ['text'], ['set', 'ting'], ['lead', 'ing']], 11, 3], ['breaking', 'composition', 'interna-', 'tional', 'breaking', 'text set-', 'ting', 'leading']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['line'], ['pa', 'ra', 'graph'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing']], 6, 1], ['line', 'para-', 'graph', 'compo-', 'sition', 'hy-', 'phenation', 'para-', 'graph', 'inter-', 'national', 'kerning']), ('control layout', [[['a'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing'], ['col', 'umn'], ['col', 'umn'], ['lead', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['to'], ['break', 'ing'], ['jus', 'ti', 'fied']], 12, 1], ['a margin in-', 'ternational', 'kerning col-', 'umn column', 'leading in-', 'ternational', 'to breaking', 'justified'])], [('regression: whole-word fit test', [[['set', 'ting'], ['of'], ['mar', 'gin'], ['kern', 'ing'], ['set', 'ting'], ['col', 'umn'], ['line'], ['set', 'ting'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin']], 11, 2], ['setting of', 'margin', 'kerning', 'setting', 'column line', 'setting a', 'interna-', 'tional', 'margin']), ('regression: whole-word fit test', [[['type'], ['col', 'umn'], ['lead', 'ing'], ['lead', 'ing'], ['of'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al']], 10, 1], ['type col-', 'umn', 'leading', 'leading of', 'margin', 'international']), ('regression: whole-word fit test', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['type'], ['hy', 'phen', 'a', 'tion'], ['col', 'umn'], ['of'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'type', 'hyphen-', 'ation', 'column', 'of pa-', 'ragraph', 'hyphenation']), ('regression: whole-word fit test', [[['mar', 'gin'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['of'], ['type'], ['col', 'umn'], ['lead', 'ing']], 9, 3], ['margin', 'paragraph', 'leading', 'of type', 'column', 'leading']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['pa', 'ra', 'graph'], ['to'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['to'], ['col', 'umn']], 13, 2], ['paragraph to', 'justified', 'leading to', 'column']), ('control layout', [[['set', 'ting'], ['to'], ['break', 'ing'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['line'], ['jus', 'ti', 'fied'], ['a'], ['break', 'ing'], ['a'], ['line']], 13, 2], ['setting to', 'breaking com-', 'position', 'leading line', 'justified a', 'breaking a', 'line'])], [('regression: whole-word fit test', [[['line'], ['com', 'po', 'si', 'tion'], ['of'], ['to'], ['in', 'ter', 'na', 'tion', 'al'], ['lead', 'ing'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion'], ['set', 'ting']], 10, 3], ['line com-', 'position', 'of to in-', 'ternation-', 'al leading', 'paragraph', 'hyphena-', 'tion', 'setting']), ('regression: whole-word fit test', [[['lead', 'ing'], ['kern', 'ing'], ['hy', 'phen', 'a', 'tion'], ['kern', 'ing'], ['col', 'umn'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['text'], ['of'], ['jus', 'ti', 'fied'], ['type'], ['kern', 'ing']], 12, 1], ['leading', 'kerning hy-', 'phenation', 'kerning col-', 'umn', 'composition', 'leading text', 'of justified', 'type kerning']), ('partial-repair probe', [[['hy', 'phen', 'a', 'tion'], ['type'], ['mar', 'gin'], ['a'], ['jus', 'ti', 'fied'], ['col', 'umn'], ['break', 'ing'], ['com', 'po', 'si', 'tion'], ['line']], 12, 2], ['hyphenation', 'type margin', 'a justified', 'column', 'breaking', 'composition', 'line']), ('partial-repair probe', [[['type'], ['mar', 'gin'], ['of'], ['a'], ['col', 'umn']], 8, 3], ['type', 'margin', 'of a', 'column']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['col', 'umn'], ['kern', 'ing'], ['text'], ['col', 'umn'], ['line'], ['line'], ['a']], 12, 2], ['column kern-', 'ing text', 'column line', 'line a']), ('control layout', [[['of'], ['break', 'ing'], ['type'], ['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['break', 'ing']], 12, 3], ['of breaking', 'type compo-', 'sition in-', 'ternational', 'hyphenation', 'breaking'])]]
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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(x):
    words, width, limit = x
    queue = [list(w) for w in words]
    lines = []
    cur = ''
    streak = 0
    k = 0
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        need = len(token) if cur == '' else len(cur) + 1 + len(token)
        if need <= width + 1:
            cur = token if cur == '' else cur + ' ' + token
            k += 1
            continue
        split = None
        if streak < limit and k < len(queue) - 1:
            for cut in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:cut]) + '-'
                room = len(head) if cur == '' else len(cur) + len(head) + 1
                if room <= width:
                    split = cut
                    break
        if split is not None:
            head = ''.join(syl[:split]) + '-'
            lines.append(head if cur == '' else cur + ' ' + head)
            queue[k] = syl[split:]
            cur = ''
            streak += 1
        elif cur == '':
            lines.append(token)
            k += 1
            streak = 0
        else:
            lines.append(cur)
            cur, streak = '', 0
    if cur:
        lines.append(cur)
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: whole-word fit test', [[['lead', 'ing'], ['a'], ['jus', 'ti', 'fied'], ['a'], ['a'], ['pa', 'ra', 'graph'], ['set', 'ting'], ['jus', 'ti', 'fied']], 6, 1], ['lead-', 'ing a', 'justi-', 'fied a', 'a pa-', 'ragraph', 'set-', 'ting', 'justified']), ('regression: whole-word fit test', [[['lead', 'ing'], ['kern', 'ing'], ['com', 'po', 'si', 'tion'], ['text'], ['lead', 'ing'], ['kern', 'ing'], ['hy', 'phen', 'a', 'tion'], ['hy', 'phen', 'a', 'tion'], ['a'], ['text'], ['pa', 'ra', 'graph']], 14, 1], ['leading kern-', 'ing', 'composition', 'text leading', 'kerning hy-', 'phenation', 'hyphenation a', 'text paragraph']), ('partial-repair probe', [[['break', 'ing'], ['kern', 'ing'], ['set', 'ting'], ['break', 'ing'], ['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['to'], ['line'], ['jus', 'ti', 'fied']], 12, 1], ['breaking', 'kerning set-', 'ting', 'breaking hy-', 'phenation', 'leading to', 'line', 'justified']), ('regression: whole-word fit test', [[['to'], ['line'], ['com', 'po', 'si', 'tion'], ['mar', 'gin'], ['mar', 'gin'], ['type'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['col', 'umn'], ['line'], ['com', 'po', 'si', 'tion'], ['to']], 14, 1], ['to line compo-', 'sition margin', 'margin type', 'kerning inter-', 'national', 'column line', 'composition to']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['a'], ['hy', 'phen', 'a', 'tion'], ['break', 'ing']], 9, 3], ['interna-', 'tional', 'hyphena-', 'tion a', 'hyphena-', 'tion', 'breaking']), ('control layout', [[['text'], ['line'], ['hy', 'phen', 'a', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['set', 'ting']], 14, 2], ['text line hy-', 'phenation in-', 'ternational', 'composition', 'setting'])], [('regression: whole-word fit test', [[['pa', 'ra', 'graph'], ['of'], ['type'], ['lead', 'ing'], ['col', 'umn'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['kern', 'ing'], ['set', 'ting']], 7, 3], ['para-', 'graph', 'of type', 'leading', 'column', 'para-', 'graph', 'leading', 'kerning', 'setting']), ('regression: whole-word fit test', [[['hy', 'phen', 'a', 'tion'], ['lead', 'ing'], ['to'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['set', 'ting'], ['col', 'umn']], 13, 3], ['hyphenation', 'leading to', 'international', 'a setting', 'column']), ('partial-repair probe', [[['jus', 'ti', 'fied'], ['text'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['mar', 'gin'], ['of'], ['break', 'ing'], ['line']], 12, 1], ['justified', 'text of in-', 'ternational', 'internation-', 'al margin', 'margin of', 'breaking', 'line']), ('partial-repair probe', [[['lead', 'ing'], ['pa', 'ra', 'graph'], ['to'], ['mar', 'gin'], ['line'], ['jus', 'ti', 'fied']], 14, 3], ['leading para-', 'graph to mar-', 'gin line', 'justified']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('control layout', [[['jus', 'ti', 'fied'], ['col', 'umn'], ['com', 'po', 'si', 'tion'], ['pa', 'ra', 'graph'], ['to'], ['jus', 'ti', 'fied'], ['mar', 'gin']], 12, 2], ['justified', 'column com-', 'position pa-', 'ragraph to', 'justified', 'margin']), ('control layout', [[['a'], ['kern', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['set', 'ting'], ['pa', 'ra', 'graph']], 11, 1], ['a kerning', 'interna-', 'tional', 'setting', 'paragraph'])], [('regression: whole-word fit test', [[['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['break', 'ing'], ['mar', 'gin'], ['line'], ['set', 'ting'], ['in', 'ter', 'na', 'tion', 'al']], 6, 1], ['compo-', 'sition', 'inter-', 'national', 'margin', 'break-', 'ing', 'margin', 'line', 'set-', 'ting', 'international']), ('regression: whole-word fit test', [[['col', 'umn'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing'], ['type'], ['lead', 'ing'], ['lead', 'ing'], ['text'], ['text'], ['pa', 'ra', 'graph']], 6, 1], ['column', 'inter-', 'national', 'kern-', 'ing', 'type', 'lead-', 'ing', 'lead-', 'ing', 'text', 'text', 'paragraph']), ('regression: whole-word fit test', [[['line'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin'], ['pa', 'ra', 'graph'], ['a'], ['a']], 7, 2], ['line', 'inter-', 'nation-', 'al', 'margin', 'para-', 'graph a', 'a']), ('regression: whole-word fit test', [[['break', 'ing'], ['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['break', 'ing'], ['text'], ['set', 'ting'], ['lead', 'ing']], 11, 3], ['breaking', 'composition', 'interna-', 'tional', 'breaking', 'text set-', 'ting', 'leading']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['line'], ['pa', 'ra', 'graph'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['pa', 'ra', 'graph'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing']], 6, 1], ['line', 'para-', 'graph', 'compo-', 'sition', 'hy-', 'phenation', 'para-', 'graph', 'inter-', 'national', 'kerning']), ('control layout', [[['a'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al'], ['kern', 'ing'], ['col', 'umn'], ['col', 'umn'], ['lead', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['to'], ['break', 'ing'], ['jus', 'ti', 'fied']], 12, 1], ['a margin in-', 'ternational', 'kerning col-', 'umn column', 'leading in-', 'ternational', 'to breaking', 'justified'])], [('regression: whole-word fit test', [[['set', 'ting'], ['of'], ['mar', 'gin'], ['kern', 'ing'], ['set', 'ting'], ['col', 'umn'], ['line'], ['set', 'ting'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['mar', 'gin']], 11, 2], ['setting of', 'margin', 'kerning', 'setting', 'column line', 'setting a', 'interna-', 'tional', 'margin']), ('regression: whole-word fit test', [[['type'], ['col', 'umn'], ['lead', 'ing'], ['lead', 'ing'], ['of'], ['mar', 'gin'], ['in', 'ter', 'na', 'tion', 'al']], 10, 1], ['type col-', 'umn', 'leading', 'leading of', 'margin', 'international']), ('regression: whole-word fit test', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['type'], ['hy', 'phen', 'a', 'tion'], ['col', 'umn'], ['of'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'type', 'hyphen-', 'ation', 'column', 'of pa-', 'ragraph', 'hyphenation']), ('regression: whole-word fit test', [[['mar', 'gin'], ['pa', 'ra', 'graph'], ['lead', 'ing'], ['of'], ['type'], ['col', 'umn'], ['lead', 'ing']], 9, 3], ['margin', 'paragraph', 'leading', 'of type', 'column', 'leading']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['pa', 'ra', 'graph'], ['to'], ['jus', 'ti', 'fied'], ['lead', 'ing'], ['to'], ['col', 'umn']], 13, 2], ['paragraph to', 'justified', 'leading to', 'column']), ('control layout', [[['set', 'ting'], ['to'], ['break', 'ing'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['line'], ['jus', 'ti', 'fied'], ['a'], ['break', 'ing'], ['a'], ['line']], 13, 2], ['setting to', 'breaking com-', 'position', 'leading line', 'justified a', 'breaking a', 'line'])], [('regression: whole-word fit test', [[['line'], ['com', 'po', 'si', 'tion'], ['of'], ['to'], ['in', 'ter', 'na', 'tion', 'al'], ['lead', 'ing'], ['pa', 'ra', 'graph'], ['hy', 'phen', 'a', 'tion'], ['set', 'ting']], 10, 3], ['line com-', 'position', 'of to in-', 'ternation-', 'al leading', 'paragraph', 'hyphena-', 'tion', 'setting']), ('regression: whole-word fit test', [[['lead', 'ing'], ['kern', 'ing'], ['hy', 'phen', 'a', 'tion'], ['kern', 'ing'], ['col', 'umn'], ['com', 'po', 'si', 'tion'], ['lead', 'ing'], ['text'], ['of'], ['jus', 'ti', 'fied'], ['type'], ['kern', 'ing']], 12, 1], ['leading', 'kerning hy-', 'phenation', 'kerning col-', 'umn', 'composition', 'leading text', 'of justified', 'type kerning']), ('partial-repair probe', [[['hy', 'phen', 'a', 'tion'], ['type'], ['mar', 'gin'], ['a'], ['jus', 'ti', 'fied'], ['col', 'umn'], ['break', 'ing'], ['com', 'po', 'si', 'tion'], ['line']], 12, 2], ['hyphenation', 'type margin', 'a justified', 'column', 'breaking', 'composition', 'line']), ('partial-repair probe', [[['type'], ['mar', 'gin'], ['of'], ['a'], ['col', 'umn']], 8, 3], ['type', 'margin', 'of a', 'column']), ('ladder of three hyphenated lines', [[['in', 'ter', 'na', 'tion', 'al'], ['com', 'po', 'si', 'tion'], ['hy', 'phen', 'a', 'tion'], ['text']], 7, 2], ['inter-', 'nation-', 'al', 'compo-', 'sition', 'hyphen-', 'ation', 'text']), ('last word never hyphenated', [[['a'], ['com', 'po', 'si', 'tion']], 8, 2], ['a', 'composition']), ('control layout', [[['col', 'umn'], ['kern', 'ing'], ['text'], ['col', 'umn'], ['line'], ['line'], ['a']], 12, 2], ['column kern-', 'ing text', 'column line', 'line a']), ('control layout', [[['of'], ['break', 'ing'], ['type'], ['com', 'po', 'si', 'tion'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'a', 'tion'], ['break', 'ing']], 12, 3], ['of breaking', 'type compo-', 'sition in-', 'ternational', 'hyphenation', 'breaking'])]]
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)

prompt:
Words that exactly fill the measure are pushed to the next line.

Input [words as syllable lists, width, limit]. Greedy fill with 1-unit spaces and characters. A word that does not fit may be split at the latest syllable boundary whose head plus "-" fits, only if fewer than limit immediately preceding lines ended in a hyphen and the word is not the paragraph's last word. A line ended without hyphen resets the streak; a word too long for an empty line is set alone. Return the lines.

split: open-access


broken_source:
"""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)

source:
"""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)

prompt:
Carry-overs one line short of the widow minimum are left in place.

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.

split: open-access


broken_source:
"""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(room - 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 pull-back amount', [[5, 5, 3], 9, 1, 3], [7, 6]), ('regression: widow pull-back amount', [[1, 5, 6, 1, 2, 4, 2, 6], 7, 2, 3], [6, 7, 6, 5, 3]), ('regression: widow pull-back amount', [[5, 5, 4, 3], 8, 1, 2], [8, 7, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[8, 7, 6, 3, 8], 10, 3, 3], [8, 10, 10, 4]), ('control layout', [[4, 1, 9, 9, 1], 12, 1, 2], [12, 12])], [('regression: widow pull-back amount', [[4, 6, 5, 6, 1, 7, 3, 4], 9, 3, 3], [7, 8, 7, 7, 7]), ('regression: widow pull-back amount', [[3, 2, 1, 1, 5, 5, 6], 5, 2, 3], [5, 4, 5, 5, 4]), ('regression: widow pull-back amount', [[1, 2, 2, 4, 6, 2], 8, 1, 2], [7, 8, 2]), ('regression: widow pull-back amount', [[6, 4, 6, 7, 5, 3], 8, 3, 2], [6, 8, 7, 7, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[1, 3, 9, 4, 3, 6], 10, 3, 1], [10, 10, 6]), ('control layout', [[5, 1, 9, 2, 5, 1, 7, 1], 7, 2, 1], [6, 7, 7, 7, 4])], [('regression: widow pull-back amount', [[9, 7, 3, 7, 4, 4, 7], 10, 1, 3], [10, 10, 10, 8, 3]), ('regression: widow pull-back amount', [[8, 7, 5, 1, 8, 2, 2], 6, 2, 3], [6, 6, 5, 6, 6, 4]), ('regression: widow pull-back amount', [[6, 4, 6, 7, 5, 3], 8, 3, 2], [6, 8, 7, 7, 3]), ('regression: widow pull-back amount', [[2, 3, 3, 3, 5, 6, 5, 5], 4, 2, 3], [2, 3, 3, 3, 4, 4, 3, 4, 3, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[2, 2, 4, 6], 4, 3, 3], [4, 4, 4, 2]), ('control layout', [[6, 9, 1, 3], 8, 1, 2], [8, 8, 3])], [('regression: widow pull-back amount', [[2, 8, 4, 5, 9, 5, 8, 2], 9, 3, 3], [7, 7, 9, 5, 9, 6]), ('regression: widow pull-back amount', [[2, 1, 4, 9, 4, 3], 5, 1, 3], [4, 5, 5, 3, 3, 3]), ('regression: widow pull-back amount', [[4, 6, 5, 8, 9], 5, 2, 2], [4, 5, 4, 5, 5, 5, 4]), ('partial-repair probe', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[4, 9, 6], 5, 3, 1], [4, 5, 4, 5, 1]), ('control layout', [[5, 5, 8, 4, 2], 10, 2, 1], [10, 10, 4])], [('regression: widow pull-back amount', [[4, 6, 5, 6, 1, 7, 3, 4], 9, 3, 3], [7, 8, 7, 7, 7]), ('regression: widow pull-back amount', [[1, 5, 2, 2, 2, 6], 9, 3, 3], [8, 7, 3]), ('regression: widow pull-back amount', [[1, 2, 6, 8, 5, 2], 8, 2, 2], [7, 8, 7, 2]), ('regression: widow pull-back amount', [[8, 7, 6, 5, 6, 5, 5, 3], 11, 1, 2], [11, 11, 11, 10, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[3, 6, 2, 3], 11, 2, 1], [11, 3]), ('control layout', [[2, 2, 9, 7, 5, 4], 6, 2, 1], [6, 6, 6, 6, 5])]]
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)

source:
"""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 + 1, 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 pull-back amount', [[5, 5, 3], 9, 1, 3], [7, 6]), ('regression: widow pull-back amount', [[1, 5, 6, 1, 2, 4, 2, 6], 7, 2, 3], [6, 7, 6, 5, 3]), ('regression: widow pull-back amount', [[5, 5, 4, 3], 8, 1, 2], [8, 7, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[8, 7, 6, 3, 8], 10, 3, 3], [8, 10, 10, 4]), ('control layout', [[4, 1, 9, 9, 1], 12, 1, 2], [12, 12])], [('regression: widow pull-back amount', [[4, 6, 5, 6, 1, 7, 3, 4], 9, 3, 3], [7, 8, 7, 7, 7]), ('regression: widow pull-back amount', [[3, 2, 1, 1, 5, 5, 6], 5, 2, 3], [5, 4, 5, 5, 4]), ('regression: widow pull-back amount', [[1, 2, 2, 4, 6, 2], 8, 1, 2], [7, 8, 2]), ('regression: widow pull-back amount', [[6, 4, 6, 7, 5, 3], 8, 3, 2], [6, 8, 7, 7, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[1, 3, 9, 4, 3, 6], 10, 3, 1], [10, 10, 6]), ('control layout', [[5, 1, 9, 2, 5, 1, 7, 1], 7, 2, 1], [6, 7, 7, 7, 4])], [('regression: widow pull-back amount', [[9, 7, 3, 7, 4, 4, 7], 10, 1, 3], [10, 10, 10, 8, 3]), ('regression: widow pull-back amount', [[8, 7, 5, 1, 8, 2, 2], 6, 2, 3], [6, 6, 5, 6, 6, 4]), ('regression: widow pull-back amount', [[6, 4, 6, 7, 5, 3], 8, 3, 2], [6, 8, 7, 7, 3]), ('regression: widow pull-back amount', [[2, 3, 3, 3, 5, 6, 5, 5], 4, 2, 3], [2, 3, 3, 3, 4, 4, 3, 4, 3, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[2, 2, 4, 6], 4, 3, 3], [4, 4, 4, 2]), ('control layout', [[6, 9, 1, 3], 8, 1, 2], [8, 8, 3])], [('regression: widow pull-back amount', [[2, 8, 4, 5, 9, 5, 8, 2], 9, 3, 3], [7, 7, 9, 5, 9, 6]), ('regression: widow pull-back amount', [[2, 1, 4, 9, 4, 3], 5, 1, 3], [4, 5, 5, 3, 3, 3]), ('regression: widow pull-back amount', [[4, 6, 5, 8, 9], 5, 2, 2], [4, 5, 4, 5, 5, 5, 4]), ('partial-repair probe', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[4, 9, 6], 5, 3, 1], [4, 5, 4, 5, 1]), ('control layout', [[5, 5, 8, 4, 2], 10, 2, 1], [10, 10, 4])], [('regression: widow pull-back amount', [[4, 6, 5, 6, 1, 7, 3, 4], 9, 3, 3], [7, 8, 7, 7, 7]), ('regression: widow pull-back amount', [[1, 5, 2, 2, 2, 6], 9, 3, 3], [8, 7, 3]), ('regression: widow pull-back amount', [[1, 2, 6, 8, 5, 2], 8, 2, 2], [7, 8, 7, 2]), ('regression: widow pull-back amount', [[8, 7, 6, 5, 6, 5, 5, 3], 11, 1, 2], [11, 11, 11, 10, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[3, 6, 2, 3], 11, 2, 1], [11, 3]), ('control layout', [[2, 2, 9, 7, 5, 4], 6, 2, 1], [6, 6, 6, 6, 5])]]
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)

prompt:
The wrong number of lines is moved to the next page to cure a widow.

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.

split: open-access


broken_source:
"""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 = [[('regression: empty page waiver', [[9, 9, 3, 9, 2, 9, 2, 8], 4, 2, 3], [4, 4, 4, 4, 2, 3, 4, 4, 3, 4, 4, 3, 4, 4]), ('regression: empty page waiver', [[4, 5, 5, 1, 6, 1], 4, 3, 2], [4, 4, 4, 3, 4, 3]), ('regression: empty page waiver', [[2, 2, 4, 4, 4, 5, 4, 4], 4, 2, 3], [4, 4, 4, 4, 4, 1, 4, 4]), ('regression: empty page waiver', [[5, 2, 5, 9, 2, 6, 9, 8], 8, 3, 2], [7, 8, 8, 6, 8, 7, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[5, 6, 6], 11, 1, 3], [11, 6]), ('control layout', [[1, 9, 4, 2, 1, 1, 1, 1], 7, 1, 3], [7, 7, 6])], [('regression: empty page waiver', [[9, 9, 9], 4, 3, 3], [4, 4, 4, 4, 2, 4, 4, 1]), ('regression: empty page waiver', [[9, 1, 2, 9, 1, 1, 5], 4, 1, 2], [4, 4, 4, 4, 4, 4, 4]), ('regression: empty page waiver', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('regression: empty page waiver', [[5, 5, 9, 6, 5], 5, 3, 3], [5, 5, 5, 4, 5, 1, 5]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[9, 9, 3, 5, 6, 1], 12, 2, 3], [12, 11, 10]), ('control layout', [[8, 4, 3, 2, 3], 9, 3, 1], [8, 9, 3])], [('regression: empty page waiver', [[9, 8, 5, 2, 1, 8], 8, 2, 2], [8, 7, 7, 8, 3]), ('regression: empty page waiver', [[9, 9, 3, 9, 2, 9, 2, 8], 4, 2, 3], [4, 4, 4, 4, 2, 3, 4, 4, 3, 4, 4, 3, 4, 4]), ('regression: empty page waiver', [[4, 6, 5, 8, 9], 5, 2, 2], [4, 5, 4, 5, 5, 5, 4]), ('regression: empty page waiver', [[9, 5, 1, 9, 8, 5], 8, 2, 3], [8, 7, 8, 6, 8]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[5, 4, 1, 5, 7], 4, 1, 1], [4, 4, 4, 4, 4, 2]), ('control layout', [[5, 6, 1, 3, 1], 12, 3, 1], [12, 4])], [('regression: empty page waiver', [[8, 4, 9, 6, 1], 7, 3, 2], [7, 5, 7, 6, 3]), ('regression: empty page waiver', [[6, 8, 9, 2], 4, 1, 3], [4, 4, 4, 4, 4, 3, 2]), ('regression: empty page waiver', [[5, 2, 5, 9, 2, 6, 9, 8], 8, 3, 2], [7, 8, 8, 6, 8, 7, 2]), ('regression: empty page waiver', [[3, 3, 8, 5, 7, 7], 5, 1, 3], [3, 5, 5, 3, 5, 5, 5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[3, 4, 1], 6, 3, 3], [3, 5]), ('control layout', [[3, 8, 3, 4], 9, 3, 1], [9, 9])], [('regression: empty page waiver', [[6, 7, 1], 5, 1, 3], [5, 5, 4]), ('regression: empty page waiver', [[8, 8, 4, 7, 9, 1, 4], 7, 2, 2], [7, 7, 6, 7, 7, 7]), ('partial-repair probe', [[9, 7, 5, 9, 3, 9, 1, 7], 6, 1, 3], [6, 6, 6, 6, 6, 6, 6, 5, 3]), ('partial-repair probe', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[4, 4, 6, 1], 12, 3, 1], [12, 3]), ('control layout', [[2, 9, 3, 5, 4, 7, 8], 9, 1, 1], [9, 9, 9, 9, 2])]]
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)

source:
"""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 > 1:
                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 = [[('regression: empty page waiver', [[9, 9, 3, 9, 2, 9, 2, 8], 4, 2, 3], [4, 4, 4, 4, 2, 3, 4, 4, 3, 4, 4, 3, 4, 4]), ('regression: empty page waiver', [[4, 5, 5, 1, 6, 1], 4, 3, 2], [4, 4, 4, 3, 4, 3]), ('regression: empty page waiver', [[2, 2, 4, 4, 4, 5, 4, 4], 4, 2, 3], [4, 4, 4, 4, 4, 1, 4, 4]), ('regression: empty page waiver', [[5, 2, 5, 9, 2, 6, 9, 8], 8, 3, 2], [7, 8, 8, 6, 8, 7, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[5, 6, 6], 11, 1, 3], [11, 6]), ('control layout', [[1, 9, 4, 2, 1, 1, 1, 1], 7, 1, 3], [7, 7, 6])], [('regression: empty page waiver', [[9, 9, 9], 4, 3, 3], [4, 4, 4, 4, 2, 4, 4, 1]), ('regression: empty page waiver', [[9, 1, 2, 9, 1, 1, 5], 4, 1, 2], [4, 4, 4, 4, 4, 4, 4]), ('regression: empty page waiver', [[7, 1, 1, 6, 3, 6, 4], 4, 1, 3], [4, 4, 4, 3, 4, 4, 2, 3]), ('regression: empty page waiver', [[5, 5, 9, 6, 5], 5, 3, 3], [5, 5, 5, 4, 5, 1, 5]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[9, 9, 3, 5, 6, 1], 12, 2, 3], [12, 11, 10]), ('control layout', [[8, 4, 3, 2, 3], 9, 3, 1], [8, 9, 3])], [('regression: empty page waiver', [[9, 8, 5, 2, 1, 8], 8, 2, 2], [8, 7, 7, 8, 3]), ('regression: empty page waiver', [[9, 9, 3, 9, 2, 9, 2, 8], 4, 2, 3], [4, 4, 4, 4, 2, 3, 4, 4, 3, 4, 4, 3, 4, 4]), ('regression: empty page waiver', [[4, 6, 5, 8, 9], 5, 2, 2], [4, 5, 4, 5, 5, 5, 4]), ('regression: empty page waiver', [[9, 5, 1, 9, 8, 5], 8, 2, 3], [8, 7, 8, 6, 8]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[5, 4, 1, 5, 7], 4, 1, 1], [4, 4, 4, 4, 4, 2]), ('control layout', [[5, 6, 1, 3, 1], 12, 3, 1], [12, 4])], [('regression: empty page waiver', [[8, 4, 9, 6, 1], 7, 3, 2], [7, 5, 7, 6, 3]), ('regression: empty page waiver', [[6, 8, 9, 2], 4, 1, 3], [4, 4, 4, 4, 4, 3, 2]), ('regression: empty page waiver', [[5, 2, 5, 9, 2, 6, 9, 8], 8, 3, 2], [7, 8, 8, 6, 8, 7, 2]), ('regression: empty page waiver', [[3, 3, 8, 5, 7, 7], 5, 1, 3], [3, 5, 5, 3, 5, 5, 5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[3, 4, 1], 6, 3, 3], [3, 5]), ('control layout', [[3, 8, 3, 4], 9, 3, 1], [9, 9])], [('regression: empty page waiver', [[6, 7, 1], 5, 1, 3], [5, 5, 4]), ('regression: empty page waiver', [[8, 8, 4, 7, 9, 1, 4], 7, 2, 2], [7, 7, 6, 7, 7, 7]), ('partial-repair probe', [[9, 7, 5, 9, 3, 9, 1, 7], 6, 1, 3], [6, 6, 6, 6, 6, 6, 6, 5, 3]), ('partial-repair probe', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[4, 4, 6, 1], 12, 3, 1], [12, 3]), ('control layout', [[2, 9, 3, 5, 4, 7, 8], 9, 1, 1], [9, 9, 9, 9, 2])]]
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)

prompt:
Pages that start mid-paragraph are left short or stall the flow.

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.

split: open-access


broken_source:
"""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 started and a < orphan:
                    a = 0
                if rem - a < widow:
                    a = max(rem - widow, 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 = [[('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('regression: widow before orphan ordering', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('regression: widow before orphan ordering', [[9, 7, 4, 1, 2], 10, 2, 3], [9, 7, 7]), ('regression: widow before orphan ordering', [[5, 2, 7, 5, 9], 6, 3, 3], [5, 6, 3, 5, 6, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[7, 1, 3, 8, 6, 3], 12, 3, 2], [11, 12, 5]), ('control layout', [[4, 1, 5], 9, 3, 1], [9, 1])], [('regression: widow before orphan ordering', [[1, 2, 8, 5, 8, 6, 7, 9], 7, 3, 3], [7, 4, 5, 7, 7, 7, 7, 2]), ('regression: widow before orphan ordering', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('regression: widow before orphan ordering', [[3, 4, 1], 6, 3, 3], [3, 5]), ('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[6, 3, 5, 3, 1, 6, 5, 7], 10, 2, 3], [9, 9, 8, 10]), ('control layout', [[2, 5, 2], 11, 3, 1], [9])], [('regression: widow before orphan ordering', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('regression: widow before orphan ordering', [[3, 4, 1], 6, 3, 3], [3, 5]), ('regression: widow before orphan ordering', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('regression: widow before orphan ordering', [[2, 8, 4, 5, 9, 5, 8, 2], 9, 3, 3], [7, 7, 9, 5, 9, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[7, 4, 1, 1, 2, 6], 6, 3, 2], [6, 6, 6, 3]), ('control layout', [[7, 8, 5, 1], 10, 1, 3], [10, 10, 1])], [('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('regression: widow before orphan ordering', [[7, 6, 7, 4], 8, 2, 3], [7, 8, 5, 4]), ('regression: widow before orphan ordering', [[8, 4, 3, 3, 3, 1, 4], 5, 2, 2], [5, 5, 5, 3, 4, 4]), ('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[3, 3, 8, 5, 7, 7], 5, 1, 3], [3, 5, 5, 3, 5, 5, 5, 2]), ('control layout', [[6, 9, 7, 1, 7, 9, 8], 4, 3, 2], [4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1])], [('regression: widow before orphan ordering', [[9, 7, 4, 1, 2], 10, 2, 3], [9, 7, 7]), ('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('regression: widow before orphan ordering', [[5, 5, 9, 6, 5], 5, 3, 3], [5, 5, 5, 4, 5, 1, 5]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[2, 9, 5, 6, 7, 3, 5, 6], 9, 1, 2], [9, 9, 9, 8, 8]), ('control layout', [[2, 6, 6, 3, 7, 5], 11, 2, 1], [11, 11, 7])]]
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)

source:
"""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 room < 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 = [[('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('regression: widow before orphan ordering', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('regression: widow before orphan ordering', [[9, 7, 4, 1, 2], 10, 2, 3], [9, 7, 7]), ('regression: widow before orphan ordering', [[5, 2, 7, 5, 9], 6, 3, 3], [5, 6, 3, 5, 6, 3]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[7, 1, 3, 8, 6, 3], 12, 3, 2], [11, 12, 5]), ('control layout', [[4, 1, 5], 9, 3, 1], [9, 1])], [('regression: widow before orphan ordering', [[1, 2, 8, 5, 8, 6, 7, 9], 7, 3, 3], [7, 4, 5, 7, 7, 7, 7, 2]), ('regression: widow before orphan ordering', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('regression: widow before orphan ordering', [[3, 4, 1], 6, 3, 3], [3, 5]), ('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[6, 3, 5, 3, 1, 6, 5, 7], 10, 2, 3], [9, 9, 8, 10]), ('control layout', [[2, 5, 2], 11, 3, 1], [9])], [('regression: widow before orphan ordering', [[7, 9, 3, 9, 7, 5], 5, 3, 3], [5, 5, 5, 4, 5, 4, 5, 2, 5]), ('regression: widow before orphan ordering', [[3, 4, 1], 6, 3, 3], [3, 5]), ('regression: widow before orphan ordering', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('regression: widow before orphan ordering', [[2, 8, 4, 5, 9, 5, 8, 2], 9, 3, 3], [7, 7, 9, 5, 9, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[7, 4, 1, 1, 2, 6], 6, 3, 2], [6, 6, 6, 3]), ('control layout', [[7, 8, 5, 1], 10, 1, 3], [10, 10, 1])], [('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('regression: widow before orphan ordering', [[7, 6, 7, 4], 8, 2, 3], [7, 8, 5, 4]), ('regression: widow before orphan ordering', [[8, 4, 3, 3, 3, 1, 4], 5, 2, 2], [5, 5, 5, 3, 4, 4]), ('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[3, 3, 8, 5, 7, 7], 5, 1, 3], [3, 5, 5, 3, 5, 5, 5, 2]), ('control layout', [[6, 9, 7, 1, 7, 9, 8], 4, 3, 2], [4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1])], [('regression: widow before orphan ordering', [[9, 7, 4, 1, 2], 10, 2, 3], [9, 7, 7]), ('regression: widow before orphan ordering', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('regression: widow before orphan ordering', [[2, 2, 1, 1, 4, 8], 4, 2, 3], [4, 2, 4, 4, 4]), ('regression: widow before orphan ordering', [[5, 5, 9, 6, 5], 5, 3, 3], [5, 5, 5, 4, 5, 1, 5]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[2, 9, 5, 6, 7, 3, 5, 6], 9, 1, 2], [9, 9, 9, 8, 8]), ('control layout', [[2, 6, 6, 3, 7, 5], 11, 2, 1], [11, 11, 7])]]
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)

prompt:
Curing a widow can create an orphan that is left on the page.

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.

split: open-access


broken_source:
"""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 = [[('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('regression: exact fit acceptance', [[7, 6, 7, 1], 4, 3, 1], [4, 3, 4, 2, 4, 4]), ('regression: exact fit acceptance', [[6, 3, 5, 3, 1, 6, 5, 7], 10, 2, 3], [9, 9, 8, 10]), ('regression: exact fit acceptance', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 3, 4, 2], 11, 1, 2], [11, 4]), ('control layout', [[9, 6, 2, 9, 7], 12, 3, 2], [12, 12, 9])], [('regression: exact fit acceptance', [[2, 8, 2, 7], 12, 1, 1], [12, 7]), ('regression: exact fit acceptance', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('partial-repair probe', [[6, 7, 1, 1], 12, 3, 2], [11, 4]), ('regression: exact fit acceptance', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[5, 1, 2, 7, 6], 9, 1, 2], [9, 9, 3]), ('control layout', [[9, 7, 4], 11, 2, 1], [11, 9])], [('regression: exact fit acceptance', [[6, 9, 1, 5, 1, 8], 11, 2, 1], [11, 11, 8]), ('regression: exact fit acceptance', [[6, 6, 2, 6, 9, 7, 2, 8], 7, 1, 1], [7, 7, 7, 7, 7, 7, 4]), ('partial-repair probe', [[8, 8, 2, 6, 7, 7, 9], 7, 3, 3], [7, 6, 5, 6, 7, 7, 7, 2]), ('partial-repair probe', [[1, 9, 7, 4, 6, 9], 5, 2, 1], [5, 5, 5, 5, 5, 5, 5, 1]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[5, 9, 5, 1], 12, 1, 1], [12, 8]), ('control layout', [[5, 2, 2, 6, 3, 3, 3, 3], 10, 2, 3], [9, 9, 9])], [('regression: exact fit acceptance', [[8, 1, 5, 2, 5, 5], 8, 1, 3], [8, 8, 7, 3]), ('regression: exact fit acceptance', [[4, 5, 5, 3, 2, 6], 9, 2, 2], [9, 8, 8]), ('partial-repair probe', [[3, 7, 3, 2], 6, 1, 2], [6, 5, 4]), ('regression: exact fit acceptance', [[7, 4, 1, 1, 2, 6], 6, 3, 2], [6, 6, 6, 3]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[2, 5, 2], 11, 3, 1], [9]), ('control layout', [[3, 5, 4, 4, 2, 7], 10, 1, 1], [10, 10, 5])], [('regression: exact fit acceptance', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('regression: exact fit acceptance', [[9, 3, 5, 4], 6, 3, 3], [6, 6, 5, 4]), ('regression: exact fit acceptance', [[6, 4, 9, 9, 4], 5, 2, 3], [5, 5, 5, 4, 5, 4, 4]), ('partial-repair probe', [[6, 8, 9, 3, 2, 5, 9, 6], 4, 1, 3], [4, 4, 4, 4, 4, 3, 3, 4, 4, 4, 4, 4, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[7, 4, 6, 6], 4, 3, 1], [4, 3, 4, 4, 2, 4, 2]), ('control layout', [[8, 7, 8], 8, 1, 3], [8, 8, 7])]]
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)

source:
"""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 + 1:
                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 = [[('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('regression: exact fit acceptance', [[7, 6, 7, 1], 4, 3, 1], [4, 3, 4, 2, 4, 4]), ('regression: exact fit acceptance', [[6, 3, 5, 3, 1, 6, 5, 7], 10, 2, 3], [9, 9, 8, 10]), ('regression: exact fit acceptance', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[6, 3, 4, 2], 11, 1, 2], [11, 4]), ('control layout', [[9, 6, 2, 9, 7], 12, 3, 2], [12, 12, 9])], [('regression: exact fit acceptance', [[2, 8, 2, 7], 12, 1, 1], [12, 7]), ('regression: exact fit acceptance', [[3, 5, 5, 1, 7, 7, 3, 1], 4, 3, 3], [3, 4, 1, 4, 2, 4, 3, 4, 3, 4]), ('partial-repair probe', [[6, 7, 1, 1], 12, 3, 2], [11, 4]), ('regression: exact fit acceptance', [[2, 2, 5, 5, 7, 6, 4, 2], 8, 2, 3], [6, 8, 7, 6, 6]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('orphan pushed forward', [[5, 3], 6, 2, 2], [5, 3]), ('control layout', [[5, 1, 2, 7, 6], 9, 1, 2], [9, 9, 3]), ('control layout', [[9, 7, 4], 11, 2, 1], [11, 9])], [('regression: exact fit acceptance', [[6, 9, 1, 5, 1, 8], 11, 2, 1], [11, 11, 8]), ('regression: exact fit acceptance', [[6, 6, 2, 6, 9, 7, 2, 8], 7, 1, 1], [7, 7, 7, 7, 7, 7, 4]), ('partial-repair probe', [[8, 8, 2, 6, 7, 7, 9], 7, 3, 3], [7, 6, 5, 6, 7, 7, 7, 2]), ('partial-repair probe', [[1, 9, 7, 4, 6, 9], 5, 2, 1], [5, 5, 5, 5, 5, 5, 5, 1]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('control layout', [[5, 9, 5, 1], 12, 1, 1], [12, 8]), ('control layout', [[5, 2, 2, 6, 3, 3, 3, 3], 10, 2, 3], [9, 9, 9])], [('regression: exact fit acceptance', [[8, 1, 5, 2, 5, 5], 8, 1, 3], [8, 8, 7, 3]), ('regression: exact fit acceptance', [[4, 5, 5, 3, 2, 6], 9, 2, 2], [9, 8, 8]), ('partial-repair probe', [[3, 7, 3, 2], 6, 1, 2], [6, 5, 4]), ('regression: exact fit acceptance', [[7, 4, 1, 1, 2, 6], 6, 3, 2], [6, 6, 6, 3]), ('paragraph exactly fills page', [[2, 4, 3], 6, 2, 2], [6, 3]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('control layout', [[2, 5, 2], 11, 3, 1], [9]), ('control layout', [[3, 5, 4, 4, 2, 7], 10, 1, 1], [10, 10, 5])], [('regression: exact fit acceptance', [[1, 7, 1, 3, 3, 9, 6, 9], 6, 1, 3], [5, 4, 6, 6, 6, 6, 6]), ('regression: exact fit acceptance', [[9, 3, 5, 4], 6, 3, 3], [6, 6, 5, 4]), ('regression: exact fit acceptance', [[6, 4, 9, 9, 4], 5, 2, 3], [5, 5, 5, 4, 5, 4, 4]), ('partial-repair probe', [[6, 8, 9, 3, 2, 5, 9, 6], 4, 1, 3], [4, 4, 4, 4, 4, 3, 3, 4, 4, 4, 4, 4, 2]), ('long paragraph continuation', [[2, 14], 6, 2, 2], [6, 6, 4]), ('single widow pulled back', [[3, 4], 6, 2, 2], [5, 2]), ('control layout', [[7, 4, 6, 6], 4, 3, 1], [4, 3, 4, 4, 2, 4, 2]), ('control layout', [[8, 7, 8], 8, 1, 3], [8, 8, 7])]]
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)

prompt:
A paragraph that exactly fills the page is split needlessly.

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.

split: open-access