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

N = 1
observations = []
def solve(x):
    words, width, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not any(ch.isupper() for ch in token))
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: capitalisation test', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['of'], ['Ber', 'lin'], ['a']], 15, 3, 5, 1, 3, False], ['hyphenated e-', 'Booking inter-', 'national the of', 'Berlin a']), ('regression: capitalisation test', [[['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing']], 12, 3, 5, 1, 2, False], ['important of', 'only typo-', 'graphy e-', 'Booking']), ('partial-repair probe', [[['on', 'ly'], ['a'], ['set'], ['on', 'ly'], ['on', 'ly'], ['a'], ['rag', 'ged'], ['Mc', 'Don', 'ald'], ['the'], ['Ber', 'lin']], 13, 1, 7, 2, 3, False], ['only a set', 'only only a', 'ragged', 'McDonald the', 'Berlin']), ('partial-repair probe', [[['set'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['of'], ['set'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al']], 8, 1, 7, 2, 2, False], ['set', 'McDonald', 'interna-', 'tional', 'set of', 'set', 'McDonald', 'only', 'ragged', 'interna-', 'tional']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Ber', 'lin'], ['a'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['of'], ['a'], ['a']], 16, 5, 7, 1, 2, False], ['Berlin a hyphen-', 'ated ragged', 'international', 'ragged of a a']), ('control layout', [[['e', 'Book', 'ing'], ['of'], ['a'], ['e', 'Book', 'ing'], ['a'], ['of'], ['the'], ['set']], 11, 3, 7, 2, 2, False], ['eBooking of', 'a eBooking', 'a of the', 'set'])], [('regression: capitalisation test', [[['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['hy', 'phen', 'at', 'ed']], 13, 3, 7, 3, 3, False], ['Berlin eBook-', 'ing ragged', 'hyphenated']), ('regression: capitalisation test', [[['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 13, 4, 5, 3, 3, False], ['McDonald', 'eBooking', 'Berlin eBook-', 'ing']), ('partial-repair probe', [[['the'], ['Mc', 'Don', 'ald'], ['of'], ['of'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['set'], ['Mc', 'Don', 'ald']], 8, 2, 6, 2, 2, False], ['the', 'McDonald', 'of of', 'hyphen-', 'ated ty-', 'pography', 'set', 'McDonald']), ('partial-repair probe', [[['of'], ['set'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 9, 5, 4, 3, 3, False], ['of set a', 'of', 'McDonald', 'only', 'typogra-', 'phy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald']], 13, 5, 7, 1, 2, True], ['only hyphen-', 'ated eBooking', 'McDonald']), ('control layout', [[['set'], ['Ber', 'lin'], ['on', 'ly'], ['e', 'Book', 'ing'], ['the'], ['the'], ['a'], ['Mc', 'Don', 'ald'], ['of']], 16, 4, 7, 2, 2, True], ['set Berlin only', 'eBooking the the', 'a McDonald of'])], [('regression: capitalisation test', [[['on', 'ly'], ['a'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 14, 1, 7, 3, 3, False], ['only a eBook-', 'ing hyphenated', 'ragged Berlin', 'McDonald']), ('regression: capitalisation test', [[['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al']], 12, 2, 4, 1, 3, False], ['typography', 'eBooking e-', 'Booking im-', 'portant im-', 'portant in-', 'ternational']), ('partial-repair probe', [[['the'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['a'], ['Ber', 'lin'], ['a'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 11, 5, 5, 2, 2, False], ['the', 'McDonald', 'Berlin a', 'Berlin a a', 'interna-', 'tional', 'hyphenated', 'typography']), ('partial-repair probe', [[['Mc', 'Don', 'ald'], ['of'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['set']], 10, 1, 6, 1, 2, False], ['McDonald', 'of', 'McDonald', 'typography', 'set']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['rag', 'ged'], ['e', 'Book', 'ing']], 14, 5, 6, 2, 3, True], ['ragged typo-', 'graphy Berlin', 'eBooking rag-', 'ged ragged', 'eBooking']), ('control layout', [[['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['set'], ['e', 'Book', 'ing']], 12, 5, 4, 2, 2, True], ['important', 'typography', 'hyphenated', 'important', 'Berlin im-', 'portant set', 'eBooking'])], [('regression: capitalisation test', [[['set'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['of'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['set']], 14, 1, 5, 2, 3, False], ['set typography', 'hyphenated im-', 'portant of', 'Berlin eBook-', 'ing set']), ('regression: capitalisation test', [[['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al']], 12, 1, 4, 1, 2, False], ['eBooking hy-', 'phenated e-', 'Booking', 'McDonald', 'Berlin in-', 'ternational', 'set McDonald', 'internation-', 'al']), ('partial-repair probe', [[['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Mc', 'Don', 'ald'], ['a'], ['of'], ['on', 'ly']], 12, 2, 7, 2, 3, False], ['Berlin typo-', 'graphy typo-', 'graphy', 'McDonald a', 'of only']), ('partial-repair probe', [[['of'], ['set'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 9, 5, 4, 3, 3, False], ['of set a', 'of', 'McDonald', 'only', 'typogra-', 'phy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['set'], ['of'], ['on', 'ly'], ['e', 'Book', 'ing']], 11, 5, 5, 3, 3, False], ['interna-', 'tional set', 'of only', 'eBooking']), ('control layout', [[['Ber', 'lin'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['set'], ['a'], ['of'], ['rag', 'ged']], 10, 2, 7, 1, 2, True], ['Berlin e-', 'Booking', 'Berlin im-', 'portant', 'typography', 'set a of', 'ragged'])], [('regression: capitalisation test', [[['on', 'ly'], ['e', 'Book', 'ing'], ['a'], ['im', 'por', 'tant'], ['a'], ['the'], ['Ber', 'lin']], 12, 3, 7, 2, 3, False], ['only eBook-', 'ing a impor-', 'tant a the', 'Berlin']), ('regression: capitalisation test', [[['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['hy', 'phen', 'at', 'ed'], ['of'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 14, 4, 6, 3, 3, False], ['ragged inter-', 'national set', 'hyphenated of', 'Berlin eBook-', 'ing']), ('partial-repair probe', [[['Mc', 'Don', 'ald'], ['set'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['hy', 'phen', 'at', 'ed'], ['a'], ['a'], ['the'], ['Mc', 'Don', 'ald']], 11, 3, 4, 2, 3, False], ['McDonald', 'set only', 'hyphenated', 'hyphenated', 'a a the', 'McDonald']), ('partial-repair probe', [[['a'], ['im', 'por', 'tant'], ['the'], ['of'], ['Mc', 'Don', 'ald'], ['the'], ['in', 'ter', 'na', 'tion', 'al']], 11, 3, 4, 1, 3, False], ['a important', 'the of', 'McDonald', 'the inter-', 'national']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['set'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['set']], 16, 5, 4, 2, 2, True], ['set important', 'important inter-', 'national McDon-', 'ald set']), ('control layout', [[['set'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['on', 'ly']], 12, 3, 6, 2, 3, True], ['set interna-', 'tional rag-', 'ged only'])]]
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, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not token.istitle())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: capitalisation test', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['of'], ['Ber', 'lin'], ['a']], 15, 3, 5, 1, 3, False], ['hyphenated e-', 'Booking inter-', 'national the of', 'Berlin a']), ('regression: capitalisation test', [[['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing']], 12, 3, 5, 1, 2, False], ['important of', 'only typo-', 'graphy e-', 'Booking']), ('partial-repair probe', [[['on', 'ly'], ['a'], ['set'], ['on', 'ly'], ['on', 'ly'], ['a'], ['rag', 'ged'], ['Mc', 'Don', 'ald'], ['the'], ['Ber', 'lin']], 13, 1, 7, 2, 3, False], ['only a set', 'only only a', 'ragged', 'McDonald the', 'Berlin']), ('partial-repair probe', [[['set'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['of'], ['set'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al']], 8, 1, 7, 2, 2, False], ['set', 'McDonald', 'interna-', 'tional', 'set of', 'set', 'McDonald', 'only', 'ragged', 'interna-', 'tional']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Ber', 'lin'], ['a'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['of'], ['a'], ['a']], 16, 5, 7, 1, 2, False], ['Berlin a hyphen-', 'ated ragged', 'international', 'ragged of a a']), ('control layout', [[['e', 'Book', 'ing'], ['of'], ['a'], ['e', 'Book', 'ing'], ['a'], ['of'], ['the'], ['set']], 11, 3, 7, 2, 2, False], ['eBooking of', 'a eBooking', 'a of the', 'set'])], [('regression: capitalisation test', [[['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['hy', 'phen', 'at', 'ed']], 13, 3, 7, 3, 3, False], ['Berlin eBook-', 'ing ragged', 'hyphenated']), ('regression: capitalisation test', [[['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 13, 4, 5, 3, 3, False], ['McDonald', 'eBooking', 'Berlin eBook-', 'ing']), ('partial-repair probe', [[['the'], ['Mc', 'Don', 'ald'], ['of'], ['of'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['set'], ['Mc', 'Don', 'ald']], 8, 2, 6, 2, 2, False], ['the', 'McDonald', 'of of', 'hyphen-', 'ated ty-', 'pography', 'set', 'McDonald']), ('partial-repair probe', [[['of'], ['set'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 9, 5, 4, 3, 3, False], ['of set a', 'of', 'McDonald', 'only', 'typogra-', 'phy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald']], 13, 5, 7, 1, 2, True], ['only hyphen-', 'ated eBooking', 'McDonald']), ('control layout', [[['set'], ['Ber', 'lin'], ['on', 'ly'], ['e', 'Book', 'ing'], ['the'], ['the'], ['a'], ['Mc', 'Don', 'ald'], ['of']], 16, 4, 7, 2, 2, True], ['set Berlin only', 'eBooking the the', 'a McDonald of'])], [('regression: capitalisation test', [[['on', 'ly'], ['a'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 14, 1, 7, 3, 3, False], ['only a eBook-', 'ing hyphenated', 'ragged Berlin', 'McDonald']), ('regression: capitalisation test', [[['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al']], 12, 2, 4, 1, 3, False], ['typography', 'eBooking e-', 'Booking im-', 'portant im-', 'portant in-', 'ternational']), ('partial-repair probe', [[['the'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['a'], ['Ber', 'lin'], ['a'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 11, 5, 5, 2, 2, False], ['the', 'McDonald', 'Berlin a', 'Berlin a a', 'interna-', 'tional', 'hyphenated', 'typography']), ('partial-repair probe', [[['Mc', 'Don', 'ald'], ['of'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['set']], 10, 1, 6, 1, 2, False], ['McDonald', 'of', 'McDonald', 'typography', 'set']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['rag', 'ged'], ['e', 'Book', 'ing']], 14, 5, 6, 2, 3, True], ['ragged typo-', 'graphy Berlin', 'eBooking rag-', 'ged ragged', 'eBooking']), ('control layout', [[['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['set'], ['e', 'Book', 'ing']], 12, 5, 4, 2, 2, True], ['important', 'typography', 'hyphenated', 'important', 'Berlin im-', 'portant set', 'eBooking'])], [('regression: capitalisation test', [[['set'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['of'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['set']], 14, 1, 5, 2, 3, False], ['set typography', 'hyphenated im-', 'portant of', 'Berlin eBook-', 'ing set']), ('regression: capitalisation test', [[['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al']], 12, 1, 4, 1, 2, False], ['eBooking hy-', 'phenated e-', 'Booking', 'McDonald', 'Berlin in-', 'ternational', 'set McDonald', 'internation-', 'al']), ('partial-repair probe', [[['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Mc', 'Don', 'ald'], ['a'], ['of'], ['on', 'ly']], 12, 2, 7, 2, 3, False], ['Berlin typo-', 'graphy typo-', 'graphy', 'McDonald a', 'of only']), ('partial-repair probe', [[['of'], ['set'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 9, 5, 4, 3, 3, False], ['of set a', 'of', 'McDonald', 'only', 'typogra-', 'phy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['set'], ['of'], ['on', 'ly'], ['e', 'Book', 'ing']], 11, 5, 5, 3, 3, False], ['interna-', 'tional set', 'of only', 'eBooking']), ('control layout', [[['Ber', 'lin'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['set'], ['a'], ['of'], ['rag', 'ged']], 10, 2, 7, 1, 2, True], ['Berlin e-', 'Booking', 'Berlin im-', 'portant', 'typography', 'set a of', 'ragged'])], [('regression: capitalisation test', [[['on', 'ly'], ['e', 'Book', 'ing'], ['a'], ['im', 'por', 'tant'], ['a'], ['the'], ['Ber', 'lin']], 12, 3, 7, 2, 3, False], ['only eBook-', 'ing a impor-', 'tant a the', 'Berlin']), ('regression: capitalisation test', [[['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['set'], ['hy', 'phen', 'at', 'ed'], ['of'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 14, 4, 6, 3, 3, False], ['ragged inter-', 'national set', 'hyphenated of', 'Berlin eBook-', 'ing']), ('partial-repair probe', [[['Mc', 'Don', 'ald'], ['set'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['hy', 'phen', 'at', 'ed'], ['a'], ['a'], ['the'], ['Mc', 'Don', 'ald']], 11, 3, 4, 2, 3, False], ['McDonald', 'set only', 'hyphenated', 'hyphenated', 'a a the', 'McDonald']), ('partial-repair probe', [[['a'], ['im', 'por', 'tant'], ['the'], ['of'], ['Mc', 'Don', 'ald'], ['the'], ['in', 'ter', 'na', 'tion', 'al']], 11, 3, 4, 1, 3, False], ['a important', 'the of', 'McDonald', 'the inter-', 'national']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['set'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['set']], 16, 5, 4, 2, 2, True], ['set important', 'important inter-', 'national McDon-', 'ald set']), ('control layout', [[['set'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['on', 'ly']], 12, 3, 6, 2, 3, True], ['set interna-', 'tional rag-', 'ged only'])]]
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 with internal capitals are protected, or proper names are hyphenated.

Input [words as syllables, width, zone, min word length, min chars before, min chars after, hyphenate capitals]. Greedy fill. A word that does not fit may be hyphenated only if the slack left on the line (width minus current text minus the separating space) is at least the zone, the word has at least min-word characters, and (capitals allowed or its first letter is not uppercase). Pick the latest syllable boundary with head >= min before and tail >= min after chars whose head plus "-" fits. Return lines.

split: open-access


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

N = 1
observations = []
def solve(x):
    words, width, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(syl) >= min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: minimum word length unit', [[['of'], ['of'], ['hy', 'phen', 'at', 'ed'], ['set'], ['rag', 'ged'], ['the'], ['Mc', 'Don', 'ald']], 9, 3, 4, 2, 3, True], ['of of hy-', 'phenated', 'set rag-', 'ged the', 'McDonald']), ('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['of'], ['im', 'por', 'tant'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 14, 5, 7, 1, 3, False], ['eBooking in-', 'ternational', 'eBooking', 'McDonald', 'ragged of', 'important set', 'international']), ('regression: minimum word length unit', [[['the'], ['the'], ['on', 'ly'], ['rag', 'ged']], 10, 5, 6, 3, 2, False], ['the the', 'only rag-', 'ged']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['the'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['the'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 2, 6, 1, 2, False], ['important', 'the the', 'typogra-', 'phy', 'Berlin', 'the rag-', 'ged the', 'Berlin', 'McDonald']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['set'], ['ty', 'po', 'gra', 'phy']], 14, 3, 4, 2, 2, False], ['only typogra-', 'phy important', 'important set', 'typography']), ('control layout', [[['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['set'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['on', 'ly'], ['on', 'ly']], 9, 4, 4, 2, 2, False], ['only ty-', 'pography', 'only set', 'important', 'McDonald', 'only only', 'only'])], [('regression: minimum word length unit', [[['a'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['Ber', 'lin'], ['rag', 'ged'], ['im', 'por', 'tant'], ['e', 'Book', 'ing']], 16, 5, 6, 1, 3, True], ['a Berlin inter-', 'national Berlin', 'ragged important', 'eBooking']), ('regression: minimum word length unit', [[['hy', 'phen', 'at', 'ed'], ['set'], ['set'], ['ty', 'po', 'gra', 'phy'], ['a'], ['rag', 'ged']], 13, 3, 5, 2, 2, False], ['hyphenated', 'set set typo-', 'graphy a rag-', 'ged']), ('regression: minimum word length unit', [[['set'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['on', 'ly']], 12, 3, 6, 2, 3, True], ['set interna-', 'tional rag-', 'ged only']), ('regression: minimum word length unit', [[['of'], ['on', 'ly'], ['rag', 'ged'], ['of'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 2, 6, 2, 2, True], ['of only', 'ragged', 'of Ber-', 'lin hy-', 'phenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['a'], ['Ber', 'lin'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['im', 'por', 'tant'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing'], ['on', 'ly']], 15, 4, 5, 1, 3, True], ['a Berlin a in-', 'ternational of', 'important a', 'international', 'eBooking only']), ('control layout', [[['the'], ['rag', 'ged'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['on', 'ly']], 12, 2, 6, 1, 2, True], ['the ragged', 'ragged the', 'Berlin only'])], [('regression: minimum word length unit', [[['of'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['rag', 'ged'], ['a'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald'], ['set'], ['e', 'Book', 'ing']], 15, 3, 5, 2, 3, True], ['of hyphenated', 'typography Ber-', 'lin ragged a', 'McDonald McDon-', 'ald set eBook-', 'ing']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['Ber', 'lin']], 13, 4, 5, 3, 2, True], ['important the', 'important', 'Berlin typo-', 'graphy only', 'Berlin']), ('regression: minimum word length unit', [[['of'], ['of'], ['set'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged']], 9, 1, 6, 3, 2, True], ['of of set', 'typogra-', 'phy rag-', 'ged']), ('regression: minimum word length unit', [[['on', 'ly'], ['rag', 'ged'], ['the'], ['on', 'ly']], 9, 2, 6, 3, 3, False], ['only rag-', 'ged the', 'only']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Ber', 'lin'], ['the'], ['a'], ['of'], ['rag', 'ged'], ['Ber', 'lin'], ['set'], ['set']], 14, 3, 4, 2, 2, False], ['Berlin the a', 'of ragged', 'Berlin set set']), ('control layout', [[['on', 'ly'], ['Ber', 'lin'], ['of'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy']], 13, 2, 5, 3, 3, True], ['only Berlin', 'of hyphenated', 'important', 'important', 'important', 'McDonald', 'typography'])], [('regression: minimum word length unit', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: minimum word length unit', [[['ty', 'po', 'gra', 'phy'], ['a'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['ty', 'po', 'gra', 'phy'], ['in', 'ter', 'na', 'tion', 'al']], 14, 3, 6, 3, 2, True], ['typography a', 'typography', 'ragged inter-', 'national typo-', 'graphy inter-', 'national']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['the'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['the'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 2, 6, 1, 2, False], ['important', 'the the', 'typogra-', 'phy', 'Berlin', 'the rag-', 'ged the', 'Berlin', 'McDonald']), ('regression: minimum word length unit', [[['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['rag', 'ged'], ['e', 'Book', 'ing']], 14, 5, 6, 2, 3, True], ['ragged typo-', 'graphy Berlin', 'eBooking rag-', 'ged ragged', 'eBooking']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['Ber', 'lin'], ['Ber', 'lin'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 1, 5, 3, 3, False], ['Berlin', 'Berlin', 'Berlin', 'McDonald']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['of'], ['e', 'Book', 'ing'], ['on', 'ly'], ['rag', 'ged'], ['Ber', 'lin']], 14, 3, 6, 3, 2, True], ['hyphenated of', 'eBooking only', 'ragged Berlin'])], [('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald']], 15, 5, 7, 3, 2, True], ['eBooking McDon-', 'ald interna-', 'tional McDonald', 'McDonald']), ('regression: minimum word length unit', [[['hy', 'phen', 'at', 'ed'], ['the'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['of'], ['rag', 'ged'], ['of'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 5, 6, 2, 2, False], ['hyphen-', 'ated the', 'ragged', 'typogra-', 'phy', 'Berlin', 'of rag-', 'ged of', 'hyphen-', 'ated', 'ragged']), ('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['on', 'ly'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing']], 14, 3, 6, 1, 2, True], ['eBooking only', 'Berlin inter-', 'national Ber-', 'lin hyphenated', 'eBooking']), ('regression: minimum word length unit', [[['of'], ['on', 'ly'], ['rag', 'ged'], ['of'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 2, 6, 2, 2, True], ['of only', 'ragged', 'of Ber-', 'lin hy-', 'phenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['the'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed']], 16, 5, 7, 2, 3, True], ['the McDonald', 'international', 'hyphenated']), ('control layout', [[['set'], ['Ber', 'lin'], ['set'], ['a']], 14, 5, 5, 2, 2, True], ['set Berlin set', 'a'])]]
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, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) > min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: minimum word length unit', [[['of'], ['of'], ['hy', 'phen', 'at', 'ed'], ['set'], ['rag', 'ged'], ['the'], ['Mc', 'Don', 'ald']], 9, 3, 4, 2, 3, True], ['of of hy-', 'phenated', 'set rag-', 'ged the', 'McDonald']), ('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['of'], ['im', 'por', 'tant'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 14, 5, 7, 1, 3, False], ['eBooking in-', 'ternational', 'eBooking', 'McDonald', 'ragged of', 'important set', 'international']), ('regression: minimum word length unit', [[['the'], ['the'], ['on', 'ly'], ['rag', 'ged']], 10, 5, 6, 3, 2, False], ['the the', 'only rag-', 'ged']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['the'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['the'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 2, 6, 1, 2, False], ['important', 'the the', 'typogra-', 'phy', 'Berlin', 'the rag-', 'ged the', 'Berlin', 'McDonald']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['set'], ['ty', 'po', 'gra', 'phy']], 14, 3, 4, 2, 2, False], ['only typogra-', 'phy important', 'important set', 'typography']), ('control layout', [[['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['set'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['on', 'ly'], ['on', 'ly']], 9, 4, 4, 2, 2, False], ['only ty-', 'pography', 'only set', 'important', 'McDonald', 'only only', 'only'])], [('regression: minimum word length unit', [[['a'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['Ber', 'lin'], ['rag', 'ged'], ['im', 'por', 'tant'], ['e', 'Book', 'ing']], 16, 5, 6, 1, 3, True], ['a Berlin inter-', 'national Berlin', 'ragged important', 'eBooking']), ('regression: minimum word length unit', [[['hy', 'phen', 'at', 'ed'], ['set'], ['set'], ['ty', 'po', 'gra', 'phy'], ['a'], ['rag', 'ged']], 13, 3, 5, 2, 2, False], ['hyphenated', 'set set typo-', 'graphy a rag-', 'ged']), ('regression: minimum word length unit', [[['set'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged'], ['on', 'ly']], 12, 3, 6, 2, 3, True], ['set interna-', 'tional rag-', 'ged only']), ('regression: minimum word length unit', [[['of'], ['on', 'ly'], ['rag', 'ged'], ['of'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 2, 6, 2, 2, True], ['of only', 'ragged', 'of Ber-', 'lin hy-', 'phenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['a'], ['Ber', 'lin'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['im', 'por', 'tant'], ['a'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing'], ['on', 'ly']], 15, 4, 5, 1, 3, True], ['a Berlin a in-', 'ternational of', 'important a', 'international', 'eBooking only']), ('control layout', [[['the'], ['rag', 'ged'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['on', 'ly']], 12, 2, 6, 1, 2, True], ['the ragged', 'ragged the', 'Berlin only'])], [('regression: minimum word length unit', [[['of'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['rag', 'ged'], ['a'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald'], ['set'], ['e', 'Book', 'ing']], 15, 3, 5, 2, 3, True], ['of hyphenated', 'typography Ber-', 'lin ragged a', 'McDonald McDon-', 'ald set eBook-', 'ing']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['Ber', 'lin']], 13, 4, 5, 3, 2, True], ['important the', 'important', 'Berlin typo-', 'graphy only', 'Berlin']), ('regression: minimum word length unit', [[['of'], ['of'], ['set'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged']], 9, 1, 6, 3, 2, True], ['of of set', 'typogra-', 'phy rag-', 'ged']), ('regression: minimum word length unit', [[['on', 'ly'], ['rag', 'ged'], ['the'], ['on', 'ly']], 9, 2, 6, 3, 3, False], ['only rag-', 'ged the', 'only']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Ber', 'lin'], ['the'], ['a'], ['of'], ['rag', 'ged'], ['Ber', 'lin'], ['set'], ['set']], 14, 3, 4, 2, 2, False], ['Berlin the a', 'of ragged', 'Berlin set set']), ('control layout', [[['on', 'ly'], ['Ber', 'lin'], ['of'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy']], 13, 2, 5, 3, 3, True], ['only Berlin', 'of hyphenated', 'important', 'important', 'important', 'McDonald', 'typography'])], [('regression: minimum word length unit', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: minimum word length unit', [[['ty', 'po', 'gra', 'phy'], ['a'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['ty', 'po', 'gra', 'phy'], ['in', 'ter', 'na', 'tion', 'al']], 14, 3, 6, 3, 2, True], ['typography a', 'typography', 'ragged inter-', 'national typo-', 'graphy inter-', 'national']), ('regression: minimum word length unit', [[['im', 'por', 'tant'], ['the'], ['the'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['the'], ['rag', 'ged'], ['the'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 2, 6, 1, 2, False], ['important', 'the the', 'typogra-', 'phy', 'Berlin', 'the rag-', 'ged the', 'Berlin', 'McDonald']), ('regression: minimum word length unit', [[['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['rag', 'ged'], ['e', 'Book', 'ing']], 14, 5, 6, 2, 3, True], ['ragged typo-', 'graphy Berlin', 'eBooking rag-', 'ged ragged', 'eBooking']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['Ber', 'lin'], ['Ber', 'lin'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 9, 1, 5, 3, 3, False], ['Berlin', 'Berlin', 'Berlin', 'McDonald']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['of'], ['e', 'Book', 'ing'], ['on', 'ly'], ['rag', 'ged'], ['Ber', 'lin']], 14, 3, 6, 3, 2, True], ['hyphenated of', 'eBooking only', 'ragged Berlin'])], [('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald']], 15, 5, 7, 3, 2, True], ['eBooking McDon-', 'ald interna-', 'tional McDonald', 'McDonald']), ('regression: minimum word length unit', [[['hy', 'phen', 'at', 'ed'], ['the'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['of'], ['rag', 'ged'], ['of'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 5, 6, 2, 2, False], ['hyphen-', 'ated the', 'ragged', 'typogra-', 'phy', 'Berlin', 'of rag-', 'ged of', 'hyphen-', 'ated', 'ragged']), ('regression: minimum word length unit', [[['e', 'Book', 'ing'], ['on', 'ly'], ['Ber', 'lin'], ['in', 'ter', 'na', 'tion', 'al'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing']], 14, 3, 6, 1, 2, True], ['eBooking only', 'Berlin inter-', 'national Ber-', 'lin hyphenated', 'eBooking']), ('regression: minimum word length unit', [[['of'], ['on', 'ly'], ['rag', 'ged'], ['of'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 8, 2, 6, 2, 2, True], ['of only', 'ragged', 'of Ber-', 'lin hy-', 'phenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['the'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed']], 16, 5, 7, 2, 3, True], ['the McDonald', 'international', 'hyphenated']), ('control layout', [[['set'], ['Ber', 'lin'], ['set'], ['a']], 14, 5, 5, 2, 2, True], ['set Berlin set', 'a'])]]
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:
Long words with few syllables are never hyphenated.

Input [words as syllables, width, zone, min word length, min chars before, min chars after, hyphenate capitals]. Greedy fill. A word that does not fit may be hyphenated only if the slack left on the line (width minus current text minus the separating space) is at least the zone, the word has at least min-word characters, and (capitals allowed or its first letter is not uppercase). Pick the latest syllable boundary with head >= min before and tail >= min after chars whose head plus "-" fits. Return lines.

split: open-access


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

N = 1
observations = []
def solve(x):
    words, width, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_after or len(tail) < min_before:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: before/after minimums', [[['Mc', 'Don', 'ald'], ['rag', 'ged'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['a'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 11, 3, 6, 1, 2, False], ['McDonald', 'ragged e-', 'Booking ty-', 'pography', 'Berlin ty-', 'pography a', 'ragged ty-', 'pography']), ('regression: before/after minimums', [[['of'], ['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['the'], ['hy', 'phen', 'at', 'ed'], ['a']], 12, 4, 7, 3, 2, True], ['of important', 'of only', 'hyphenated', 'the hyphen-', 'ated a']), ('partial-repair probe', [[['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['rag', 'ged'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed']], 12, 5, 4, 3, 3, False], ['interna-', 'tional', 'McDonald a', 'eBooking', 'typography', 'ragged rag-', 'ged only', 'hyphenated']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['a'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald']], 13, 2, 5, 1, 3, True], ['McDonald im-', 'portant typo-', 'graphy a e-', 'Booking im-', 'portant Mc-', 'Donald inter-', 'national Mc-', 'Donald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['a'], ['im', 'por', 'tant'], ['on', 'ly'], ['rag', 'ged'], ['the'], ['set']], 15, 5, 5, 2, 3, True], ['eBooking typo-', 'graphy a impor-', 'tant only rag-', 'ged the set']), ('control layout', [[['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['Ber', 'lin'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 14, 2, 4, 2, 2, False], ['McDonald typo-', 'graphy Berlin', 'only hyphenat-', 'ed Berlin', 'Berlin Berlin', 'eBooking'])], [('regression: before/after minimums', [[['im', 'por', 'tant'], ['im', 'por', 'tant'], ['a'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['set'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['of'], ['rag', 'ged']], 13, 1, 4, 2, 3, False], ['important im-', 'portant a ty-', 'pography ty-', 'pography set', 'ragged typo-', 'graphy of', 'ragged']), ('regression: before/after minimums', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['the'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant']], 9, 1, 4, 1, 3, True], ['eBooking', 'McDonald', 'Berlin', 'hyphen-', 'ated the', 'typogra-', 'phy im-', 'portant']), ('partial-repair probe', [[['a'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['a'], ['im', 'por', 'tant']], 14, 5, 7, 2, 2, False], ['a Berlin im-', 'portant typo-', 'graphy eBook-', 'ing Berlin a', 'important']), ('partial-repair probe', [[['im', 'por', 'tant'], ['on', 'ly'], ['rag', 'ged'], ['set'], ['the']], 9, 4, 4, 3, 2, False], ['important', 'only rag-', 'ged set', 'the']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['a'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['set']], 14, 3, 4, 3, 2, True], ['a only typo-', 'graphy set']), ('control layout', [[['a'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['set'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['a']], 14, 2, 5, 2, 2, True], ['a McDonald', 'eBooking set', 'typography', 'ragged a'])], [('regression: before/after minimums', [[['rag', 'ged'], ['the'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['set'], ['of'], ['the'], ['im', 'por', 'tant']], 12, 5, 7, 2, 3, True], ['ragged the', 'hyphenated', 'Berlin', 'eBooking set', 'of the im-', 'portant']), ('regression: before/after minimums', [[['a'], ['of'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 13, 3, 4, 3, 2, False], ['a of typogra-', 'phy only', 'hyphenated', 'typography']), ('regression: before/after minimums', [[['the'], ['set'], ['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald']], 12, 4, 7, 2, 3, False], ['the set hy-', 'phenated', 'McDonald']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['the'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['set'], ['rag', 'ged'], ['set'], ['Mc', 'Don', 'ald'], ['rag', 'ged']], 8, 5, 4, 1, 2, True], ['the', 'typogra-', 'phy', 'typogra-', 'phy set', 'ragged', 'set', 'McDonald', 'ragged']), ('control layout', [[['set'], ['the'], ['the'], ['set'], ['e', 'Book', 'ing'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al']], 13, 1, 5, 3, 3, True], ['set the the', 'set eBooking', 'only interna-', 'tional'])], [('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['set'], ['Mc', 'Don', 'ald'], ['the'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['im', 'por', 'tant']], 11, 2, 5, 2, 3, True], ['McDonald', 'important', 'McDonald', 'set McDon-', 'ald the hy-', 'phenated', 'eBooking', 'important']), ('regression: before/after minimums', [[['rag', 'ged'], ['e', 'Book', 'ing'], ['of'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant'], ['of'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 13, 5, 6, 1, 2, True], ['ragged eBook-', 'ing of typo-', 'graphy impor-', 'tant of e-', 'Booking rag-', 'ged Berlin', 'McDonald']), ('regression: before/after minimums', [[['the'], ['set'], ['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald']], 12, 4, 7, 2, 3, False], ['the set hy-', 'phenated', 'McDonald']), ('partial-repair probe', [[['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['rag', 'ged'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed']], 12, 5, 4, 3, 3, False], ['interna-', 'tional', 'McDonald a', 'eBooking', 'typography', 'ragged rag-', 'ged only', 'hyphenated']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['rag', 'ged'], ['rag', 'ged'], ['set'], ['im', 'por', 'tant'], ['set'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['hy', 'phen', 'at', 'ed']], 16, 4, 5, 3, 3, True], ['ragged ragged', 'set important', 'set eBooking', 'McDonald hyphen-', 'ated']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald'], ['of'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 12, 4, 6, 2, 2, False], ['hyphenated', 'McDonald of', 'set interna-', 'tional'])], [('regression: before/after minimums', [[['Ber', 'lin'], ['the'], ['hy', 'phen', 'at', 'ed'], ['the'], ['Mc', 'Don', 'ald'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 8, 1, 7, 2, 3, False], ['Berlin', 'the hy-', 'phenated', 'the', 'McDonald', 'set in-', 'terna-', 'tional']), ('regression: before/after minimums', [[['the'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['the'], ['the'], ['set']], 8, 3, 5, 3, 2, False], ['the', 'hyphen-', 'ated', 'ragged', 'the the', 'set']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: before/after minimums', [[['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['e', 'Book', 'ing'], ['rag', 'ged']], 15, 1, 4, 1, 2, True], ['important e-', 'Booking eBook-', 'ing ragged']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald']], 10, 5, 6, 3, 3, True], ['McDonald', 'important', 'Berlin', 'McDonald', 'ragged', 'McDonald', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['the'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 11, 3, 4, 2, 3, True], ['eBooking', 'McDonald', 'eBooking', 'the only', 'typography'])]]
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, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) <= min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 2
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: before/after minimums', [[['Mc', 'Don', 'ald'], ['rag', 'ged'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['a'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 11, 3, 6, 1, 2, False], ['McDonald', 'ragged e-', 'Booking ty-', 'pography', 'Berlin ty-', 'pography a', 'ragged ty-', 'pography']), ('regression: before/after minimums', [[['of'], ['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['the'], ['hy', 'phen', 'at', 'ed'], ['a']], 12, 4, 7, 3, 2, True], ['of important', 'of only', 'hyphenated', 'the hyphen-', 'ated a']), ('partial-repair probe', [[['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['rag', 'ged'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed']], 12, 5, 4, 3, 3, False], ['interna-', 'tional', 'McDonald a', 'eBooking', 'typography', 'ragged rag-', 'ged only', 'hyphenated']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['a'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald']], 13, 2, 5, 1, 3, True], ['McDonald im-', 'portant typo-', 'graphy a e-', 'Booking im-', 'portant Mc-', 'Donald inter-', 'national Mc-', 'Donald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['a'], ['im', 'por', 'tant'], ['on', 'ly'], ['rag', 'ged'], ['the'], ['set']], 15, 5, 5, 2, 3, True], ['eBooking typo-', 'graphy a impor-', 'tant only rag-', 'ged the set']), ('control layout', [[['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['Ber', 'lin'], ['Ber', 'lin'], ['e', 'Book', 'ing']], 14, 2, 4, 2, 2, False], ['McDonald typo-', 'graphy Berlin', 'only hyphenat-', 'ed Berlin', 'Berlin Berlin', 'eBooking'])], [('regression: before/after minimums', [[['im', 'por', 'tant'], ['im', 'por', 'tant'], ['a'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['set'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['of'], ['rag', 'ged']], 13, 1, 4, 2, 3, False], ['important im-', 'portant a ty-', 'pography ty-', 'pography set', 'ragged typo-', 'graphy of', 'ragged']), ('regression: before/after minimums', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['hy', 'phen', 'at', 'ed'], ['the'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant']], 9, 1, 4, 1, 3, True], ['eBooking', 'McDonald', 'Berlin', 'hyphen-', 'ated the', 'typogra-', 'phy im-', 'portant']), ('partial-repair probe', [[['a'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['a'], ['im', 'por', 'tant']], 14, 5, 7, 2, 2, False], ['a Berlin im-', 'portant typo-', 'graphy eBook-', 'ing Berlin a', 'important']), ('partial-repair probe', [[['im', 'por', 'tant'], ['on', 'ly'], ['rag', 'ged'], ['set'], ['the']], 9, 4, 4, 3, 2, False], ['important', 'only rag-', 'ged set', 'the']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['a'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['set']], 14, 3, 4, 3, 2, True], ['a only typo-', 'graphy set']), ('control layout', [[['a'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['set'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['a']], 14, 2, 5, 2, 2, True], ['a McDonald', 'eBooking set', 'typography', 'ragged a'])], [('regression: before/after minimums', [[['rag', 'ged'], ['the'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['set'], ['of'], ['the'], ['im', 'por', 'tant']], 12, 5, 7, 2, 3, True], ['ragged the', 'hyphenated', 'Berlin', 'eBooking set', 'of the im-', 'portant']), ('regression: before/after minimums', [[['a'], ['of'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 13, 3, 4, 3, 2, False], ['a of typogra-', 'phy only', 'hyphenated', 'typography']), ('regression: before/after minimums', [[['the'], ['set'], ['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald']], 12, 4, 7, 2, 3, False], ['the set hy-', 'phenated', 'McDonald']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['the'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['set'], ['rag', 'ged'], ['set'], ['Mc', 'Don', 'ald'], ['rag', 'ged']], 8, 5, 4, 1, 2, True], ['the', 'typogra-', 'phy', 'typogra-', 'phy set', 'ragged', 'set', 'McDonald', 'ragged']), ('control layout', [[['set'], ['the'], ['the'], ['set'], ['e', 'Book', 'ing'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al']], 13, 1, 5, 3, 3, True], ['set the the', 'set eBooking', 'only interna-', 'tional'])], [('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['set'], ['Mc', 'Don', 'ald'], ['the'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['im', 'por', 'tant']], 11, 2, 5, 2, 3, True], ['McDonald', 'important', 'McDonald', 'set McDon-', 'ald the hy-', 'phenated', 'eBooking', 'important']), ('regression: before/after minimums', [[['rag', 'ged'], ['e', 'Book', 'ing'], ['of'], ['ty', 'po', 'gra', 'phy'], ['im', 'por', 'tant'], ['of'], ['e', 'Book', 'ing'], ['rag', 'ged'], ['Ber', 'lin'], ['Mc', 'Don', 'ald']], 13, 5, 6, 1, 2, True], ['ragged eBook-', 'ing of typo-', 'graphy impor-', 'tant of e-', 'Booking rag-', 'ged Berlin', 'McDonald']), ('regression: before/after minimums', [[['the'], ['set'], ['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald']], 12, 4, 7, 2, 3, False], ['the set hy-', 'phenated', 'McDonald']), ('partial-repair probe', [[['in', 'ter', 'na', 'tion', 'al'], ['Mc', 'Don', 'ald'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['rag', 'ged'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed']], 12, 5, 4, 3, 3, False], ['interna-', 'tional', 'McDonald a', 'eBooking', 'typography', 'ragged rag-', 'ged only', 'hyphenated']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['rag', 'ged'], ['rag', 'ged'], ['set'], ['im', 'por', 'tant'], ['set'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['hy', 'phen', 'at', 'ed']], 16, 4, 5, 3, 3, True], ['ragged ragged', 'set important', 'set eBooking', 'McDonald hyphen-', 'ated']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['Mc', 'Don', 'ald'], ['of'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 12, 4, 6, 2, 2, False], ['hyphenated', 'McDonald of', 'set interna-', 'tional'])], [('regression: before/after minimums', [[['Ber', 'lin'], ['the'], ['hy', 'phen', 'at', 'ed'], ['the'], ['Mc', 'Don', 'ald'], ['set'], ['in', 'ter', 'na', 'tion', 'al']], 8, 1, 7, 2, 3, False], ['Berlin', 'the hy-', 'phenated', 'the', 'McDonald', 'set in-', 'terna-', 'tional']), ('regression: before/after minimums', [[['the'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged'], ['the'], ['the'], ['set']], 8, 3, 5, 3, 2, False], ['the', 'hyphen-', 'ated', 'ragged', 'the the', 'set']), ('regression: before/after minimums', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: before/after minimums', [[['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['e', 'Book', 'ing'], ['rag', 'ged']], 15, 1, 4, 1, 2, True], ['important e-', 'Booking eBook-', 'ing ragged']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['Mc', 'Don', 'ald'], ['im', 'por', 'tant'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['Mc', 'Don', 'ald'], ['Mc', 'Don', 'ald']], 10, 5, 6, 3, 3, True], ['McDonald', 'important', 'Berlin', 'McDonald', 'ragged', 'McDonald', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['the'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 11, 3, 4, 2, 3, True], ['eBooking', 'McDonald', 'eBooking', 'the only', 'typography'])]]
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:
Hyphens leave too-short heads or tails.

Input [words as syllables, width, zone, min word length, min chars before, min chars after, hyphenate capitals]. Greedy fill. A word that does not fit may be hyphenated only if the slack left on the line (width minus current text minus the separating space) is at least the zone, the word has at least min-word characters, and (capitals allowed or its first letter is not uppercase). Pick the latest syllable boundary with head >= min before and tail >= min after chars whose head plus "-" fits. Return lines.

split: open-access


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

N = 1
observations = []
def solve(x):
    words, width, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) if not cur else len(cur) + len(head) + 1
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: hyphenated head fit', [[['in', 'ter', 'na', 'tion', 'al'], ['a'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['set']], 11, 3, 7, 3, 2, True], ['interna-', 'tional a', 'Berlin', 'McDonald', 'eBooking', 'set']), ('regression: hyphenated head fit', [[['e', 'Book', 'ing'], ['a'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['on', 'ly'], ['on', 'ly'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 9, 3, 6, 2, 3, False], ['eBooking', 'a hyphen-', 'ated ty-', 'pography', 'hyphen-', 'ated only', 'only', 'eBooking', 'hyphen-', 'ated ty-', 'pography']), ('regression: hyphenated head fit', [[['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant']], 15, 2, 6, 1, 3, True], ['important im-', 'portant impor-', 'tant important']), ('regression: hyphenated head fit', [[['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 14, 2, 7, 3, 3, False], ['only interna-', 'tional inter-', 'national of', 'international', 'hyphenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['the'], ['rag', 'ged'], ['set'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['rag', 'ged']], 10, 3, 5, 3, 2, True], ['the ragged', 'set Berlin', 'McDonald', 'ragged']), ('control layout', [[['Ber', 'lin'], ['Ber', 'lin'], ['the'], ['Mc', 'Don', 'ald']], 14, 5, 4, 3, 3, True], ['Berlin Berlin', 'the McDonald'])], [('regression: hyphenated head fit', [[['e', 'Book', 'ing'], ['on', 'ly'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al']], 15, 2, 6, 1, 2, True], ['eBooking only', 'important im-', 'portant hyphen-', 'ated important', 'eBooking impor-', 'tant interna-', 'tional']), ('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['a']], 15, 4, 7, 1, 2, True], ['McDonald inter-', 'national the', 'important im-', 'portant a']), ('regression: hyphenated head fit', [[['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['a']], 15, 1, 4, 1, 3, True], ['important e-', 'Booking McDon-', 'ald a']), ('regression: hyphenated head fit', [[['set'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['a'], ['e', 'Book', 'ing'], ['im', 'por', 'tant']], 9, 1, 7, 1, 2, True], ['set Mc-', 'Donald', 'typogra-', 'phy typo-', 'graphy', 'Berlin a', 'eBooking', 'important']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['hy', 'phen', 'at', 'ed'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['im', 'por', 'tant'], ['the'], ['Ber', 'lin'], ['set'], ['a']], 13, 2, 6, 3, 2, False], ['hyphenated', 'hyphenated', 'international', 'a important', 'the Berlin', 'set a']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['hy', 'phen', 'at', 'ed'], ['set'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['set'], ['Ber', 'lin']], 12, 4, 4, 3, 3, False], ['hyphenated', 'eBooking', 'important', 'McDonald', 'hyphenated', 'set only', 'typography', 'set Berlin'])], [('regression: hyphenated head fit', [[['Ber', 'lin'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['rag', 'ged'], ['hy', 'phen', 'at', 'ed'], ['set'], ['Ber', 'lin'], ['the']], 11, 3, 5, 2, 2, True], ['Berlin rag-', 'ged typo-', 'graphy only', 'ragged hy-', 'phenated', 'set Berlin', 'the']), ('regression: hyphenated head fit', [[['set'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['the'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['a'], ['in', 'ter', 'na', 'tion', 'al']], 15, 1, 6, 2, 2, False], ['set eBooking', 'Berlin the ty-', 'pography hy-', 'phenated a in-', 'ternational']), ('regression: hyphenated head fit', [[['a'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['a'], ['im', 'por', 'tant']], 14, 5, 7, 2, 2, False], ['a Berlin im-', 'portant typo-', 'graphy eBook-', 'ing Berlin a', 'important']), ('regression: hyphenated head fit', [[['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['the'], ['e', 'Book', 'ing'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['of'], ['the']], 9, 4, 7, 3, 3, True], ['Berlin', 'McDonald', 'the', 'eBooking', 'a eBook-', 'ing typo-', 'graphy of', 'the']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['the'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 11, 3, 4, 2, 3, True], ['eBooking', 'McDonald', 'eBooking', 'the only', 'typography']), ('control layout', [[['Mc', 'Don', 'ald'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['the'], ['of']], 16, 3, 4, 2, 2, False], ['McDonald only', 'hyphenated', 'Berlin the of'])], [('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: hyphenated head fit', [[['of'], ['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['the'], ['hy', 'phen', 'at', 'ed'], ['a']], 12, 4, 7, 3, 2, True], ['of important', 'of only', 'hyphenated', 'the hyphen-', 'ated a']), ('regression: hyphenated head fit', [[['Ber', 'lin'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin']], 11, 4, 5, 1, 3, True], ['Berlin only', 'interna-', 'tional a', 'only typo-', 'graphy ty-', 'pography', 'Berlin']), ('regression: hyphenated head fit', [[['a'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['a']], 8, 2, 7, 2, 3, False], ['a hy-', 'phenated', 'eBooking', 'interna-', 'tional', 'the', 'Berlin', 'eBooking', 'hyphen-', 'ated a']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Mc', 'Don', 'ald'], ['a'], ['Mc', 'Don', 'ald'], ['of']], 9, 3, 6, 3, 2, True], ['McDonald', 'a McDon-', 'ald of']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['on', 'ly'], ['a'], ['Mc', 'Don', 'ald']], 10, 1, 6, 2, 3, False], ['interna-', 'tional', 'only a', 'McDonald'])], [('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['im', 'por', 'tant'], ['hy', 'phen', 'at', 'ed'], ['set']], 12, 2, 4, 2, 2, False], ['McDonald a', 'of McDonald', 'ragged in-', 'ternational', 'important', 'hyphenated', 'set']), ('regression: hyphenated head fit', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged']], 10, 3, 5, 3, 3, True], ['hyphenated', 'eBooking', 'interna-', 'tional', 'ragged']), ('regression: hyphenated head fit', [[['on', 'ly'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['the'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['in', 'ter', 'na', 'tion', 'al']], 15, 4, 5, 1, 2, True], ['only important', 'McDonald the', 'Berlin typogra-', 'phy interna-', 'tional']), ('regression: hyphenated head fit', [[['hy', 'phen', 'at', 'ed'], ['the'], ['Ber', 'lin'], ['of'], ['im', 'por', 'tant'], ['of'], ['a'], ['set']], 8, 1, 5, 1, 2, True], ['hyphen-', 'ated the', 'Berlin', 'of im-', 'portant', 'of a set']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['set'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing']], 13, 5, 7, 1, 2, True], ['set typogra-', 'phy Berlin', 'McDonald only', 'international', 'eBooking']), ('control layout', [[['set'], ['Ber', 'lin'], ['set'], ['a']], 14, 5, 5, 2, 2, True], ['set Berlin set', 'a'])]]
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, zone, min_word, min_before, min_after, caps = x
    lines = []
    cur = ''
    k = 0
    queue = [list(w) for w in words]
    while k < len(queue):
        syl = queue[k]
        token = ''.join(syl)
        cand = token if not cur else cur + ' ' + token
        if len(cand) <= width:
            cur = cand
            k += 1
            continue
        slack = width - len(cur) - (1 if cur else 0)
        eligible = slack >= zone and len(token) >= min_word and (caps or not token[0].isupper())
        cut = None
        if eligible:
            for c in range(len(syl) - 1, 0, -1):
                head = ''.join(syl[:c])
                tail = ''.join(syl[c:])
                if len(head) < min_before or len(tail) < min_after:
                    continue
                fit = len(head) + 1 if not cur else len(cur) + len(head) + 1
                if fit <= width:
                    cut = c
                    break
        if cut is not None:
            head = ''.join(syl[:cut]) + '-'
            lines.append(head if not cur else cur + ' ' + head)
            queue[k] = syl[cut:]
            cur = ''
        elif cur:
            lines.append(cur)
            cur = ''
        else:
            cur = token
            k += 1
    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: hyphenated head fit', [[['in', 'ter', 'na', 'tion', 'al'], ['a'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['set']], 11, 3, 7, 3, 2, True], ['interna-', 'tional a', 'Berlin', 'McDonald', 'eBooking', 'set']), ('regression: hyphenated head fit', [[['e', 'Book', 'ing'], ['a'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['on', 'ly'], ['on', 'ly'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['ty', 'po', 'gra', 'phy']], 9, 3, 6, 2, 3, False], ['eBooking', 'a hyphen-', 'ated ty-', 'pography', 'hyphen-', 'ated only', 'only', 'eBooking', 'hyphen-', 'ated ty-', 'pography']), ('regression: hyphenated head fit', [[['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['im', 'por', 'tant']], 15, 2, 6, 1, 3, True], ['important im-', 'portant impor-', 'tant important']), ('regression: hyphenated head fit', [[['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['in', 'ter', 'na', 'tion', 'al'], ['of'], ['in', 'ter', 'na', 'tion', 'al'], ['hy', 'phen', 'at', 'ed'], ['rag', 'ged']], 14, 2, 7, 3, 3, False], ['only interna-', 'tional inter-', 'national of', 'international', 'hyphenated', 'ragged']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['the'], ['rag', 'ged'], ['set'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['rag', 'ged']], 10, 3, 5, 3, 2, True], ['the ragged', 'set Berlin', 'McDonald', 'ragged']), ('control layout', [[['Ber', 'lin'], ['Ber', 'lin'], ['the'], ['Mc', 'Don', 'ald']], 14, 5, 4, 3, 3, True], ['Berlin Berlin', 'the McDonald'])], [('regression: hyphenated head fit', [[['e', 'Book', 'ing'], ['on', 'ly'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['hy', 'phen', 'at', 'ed'], ['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['in', 'ter', 'na', 'tion', 'al']], 15, 2, 6, 1, 2, True], ['eBooking only', 'important im-', 'portant hyphen-', 'ated important', 'eBooking impor-', 'tant interna-', 'tional']), ('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['im', 'por', 'tant'], ['im', 'por', 'tant'], ['a']], 15, 4, 7, 1, 2, True], ['McDonald inter-', 'national the', 'important im-', 'portant a']), ('regression: hyphenated head fit', [[['im', 'por', 'tant'], ['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['a']], 15, 1, 4, 1, 3, True], ['important e-', 'Booking McDon-', 'ald a']), ('regression: hyphenated head fit', [[['set'], ['Mc', 'Don', 'ald'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['a'], ['e', 'Book', 'ing'], ['im', 'por', 'tant']], 9, 1, 7, 1, 2, True], ['set Mc-', 'Donald', 'typogra-', 'phy typo-', 'graphy', 'Berlin a', 'eBooking', 'important']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['hy', 'phen', 'at', 'ed'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['im', 'por', 'tant'], ['the'], ['Ber', 'lin'], ['set'], ['a']], 13, 2, 6, 3, 2, False], ['hyphenated', 'hyphenated', 'international', 'a important', 'the Berlin', 'set a']), ('control layout', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['hy', 'phen', 'at', 'ed'], ['set'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['set'], ['Ber', 'lin']], 12, 4, 4, 3, 3, False], ['hyphenated', 'eBooking', 'important', 'McDonald', 'hyphenated', 'set only', 'typography', 'set Berlin'])], [('regression: hyphenated head fit', [[['Ber', 'lin'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy'], ['on', 'ly'], ['rag', 'ged'], ['hy', 'phen', 'at', 'ed'], ['set'], ['Ber', 'lin'], ['the']], 11, 3, 5, 2, 2, True], ['Berlin rag-', 'ged typo-', 'graphy only', 'ragged hy-', 'phenated', 'set Berlin', 'the']), ('regression: hyphenated head fit', [[['set'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['the'], ['ty', 'po', 'gra', 'phy'], ['hy', 'phen', 'at', 'ed'], ['a'], ['in', 'ter', 'na', 'tion', 'al']], 15, 1, 6, 2, 2, False], ['set eBooking', 'Berlin the ty-', 'pography hy-', 'phenated a in-', 'ternational']), ('regression: hyphenated head fit', [[['a'], ['Ber', 'lin'], ['im', 'por', 'tant'], ['ty', 'po', 'gra', 'phy'], ['e', 'Book', 'ing'], ['Ber', 'lin'], ['a'], ['im', 'por', 'tant']], 14, 5, 7, 2, 2, False], ['a Berlin im-', 'portant typo-', 'graphy eBook-', 'ing Berlin a', 'important']), ('regression: hyphenated head fit', [[['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['the'], ['e', 'Book', 'ing'], ['a'], ['e', 'Book', 'ing'], ['ty', 'po', 'gra', 'phy'], ['of'], ['the']], 9, 4, 7, 3, 3, True], ['Berlin', 'McDonald', 'the', 'eBooking', 'a eBook-', 'ing typo-', 'graphy of', 'the']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('control layout', [[['e', 'Book', 'ing'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['the'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy']], 11, 3, 4, 2, 3, True], ['eBooking', 'McDonald', 'eBooking', 'the only', 'typography']), ('control layout', [[['Mc', 'Don', 'ald'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['Ber', 'lin'], ['the'], ['of']], 16, 3, 4, 2, 2, False], ['McDonald only', 'hyphenated', 'Berlin the of'])], [('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['e', 'Book', 'ing'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['rag', 'ged'], ['ty', 'po', 'gra', 'phy']], 9, 4, 6, 2, 3, False], ['McDonald', 'Berlin', 'McDonald', 'eBooking', 'only ty-', 'pography', 'typogra-', 'phy rag-', 'ged typo-', 'graphy']), ('regression: hyphenated head fit', [[['of'], ['im', 'por', 'tant'], ['of'], ['on', 'ly'], ['hy', 'phen', 'at', 'ed'], ['the'], ['hy', 'phen', 'at', 'ed'], ['a']], 12, 4, 7, 3, 2, True], ['of important', 'of only', 'hyphenated', 'the hyphen-', 'ated a']), ('regression: hyphenated head fit', [[['Ber', 'lin'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['a'], ['on', 'ly'], ['ty', 'po', 'gra', 'phy'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin']], 11, 4, 5, 1, 3, True], ['Berlin only', 'interna-', 'tional a', 'only typo-', 'graphy ty-', 'pography', 'Berlin']), ('regression: hyphenated head fit', [[['a'], ['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['the'], ['Ber', 'lin'], ['e', 'Book', 'ing'], ['hy', 'phen', 'at', 'ed'], ['a']], 8, 2, 7, 2, 3, False], ['a hy-', 'phenated', 'eBooking', 'interna-', 'tional', 'the', 'Berlin', 'eBooking', 'hyphen-', 'ated a']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['Mc', 'Don', 'ald'], ['a'], ['Mc', 'Don', 'ald'], ['of']], 9, 3, 6, 3, 2, True], ['McDonald', 'a McDon-', 'ald of']), ('control layout', [[['in', 'ter', 'na', 'tion', 'al'], ['on', 'ly'], ['a'], ['Mc', 'Don', 'ald']], 10, 1, 6, 2, 3, False], ['interna-', 'tional', 'only a', 'McDonald'])], [('regression: hyphenated head fit', [[['Mc', 'Don', 'ald'], ['a'], ['of'], ['Mc', 'Don', 'ald'], ['rag', 'ged'], ['in', 'ter', 'na', 'tion', 'al'], ['im', 'por', 'tant'], ['hy', 'phen', 'at', 'ed'], ['set']], 12, 2, 4, 2, 2, False], ['McDonald a', 'of McDonald', 'ragged in-', 'ternational', 'important', 'hyphenated', 'set']), ('regression: hyphenated head fit', [[['hy', 'phen', 'at', 'ed'], ['e', 'Book', 'ing'], ['in', 'ter', 'na', 'tion', 'al'], ['rag', 'ged']], 10, 3, 5, 3, 3, True], ['hyphenated', 'eBooking', 'interna-', 'tional', 'ragged']), ('regression: hyphenated head fit', [[['on', 'ly'], ['im', 'por', 'tant'], ['Mc', 'Don', 'ald'], ['the'], ['Ber', 'lin'], ['ty', 'po', 'gra', 'phy'], ['in', 'ter', 'na', 'tion', 'al']], 15, 4, 5, 1, 2, True], ['only important', 'McDonald the', 'Berlin typogra-', 'phy interna-', 'tional']), ('regression: hyphenated head fit', [[['hy', 'phen', 'at', 'ed'], ['the'], ['Ber', 'lin'], ['of'], ['im', 'por', 'tant'], ['of'], ['a'], ['set']], 8, 1, 5, 1, 2, True], ['hyphen-', 'ated the', 'Berlin', 'of im-', 'portant', 'of a set']), ('capitalised word protected', [[['the'], ['Mc', 'Don', 'ald']], 10, 2, 4, 2, 2, False], ['the', 'McDonald']), ('zone exactly met', [[['the'], ['ty', 'po', 'gra', 'phy']], 10, 6, 4, 2, 2, False], ['the typo-', 'graphy']), ('control layout', [[['set'], ['ty', 'po', 'gra', 'phy'], ['Ber', 'lin'], ['Mc', 'Don', 'ald'], ['on', 'ly'], ['in', 'ter', 'na', 'tion', 'al'], ['e', 'Book', 'ing']], 13, 5, 7, 1, 2, True], ['set typogra-', 'phy Berlin', 'McDonald only', 'international', 'eBooking']), ('control layout', [[['set'], ['Ber', 'lin'], ['set'], ['a']], 14, 5, 5, 2, 2, True], ['set Berlin set', 'a'])]]
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:
Hyphenated lines overrun the measure.

Input [words as syllables, width, zone, min word length, min chars before, min chars after, hyphenate capitals]. Greedy fill. A word that does not fit may be hyphenated only if the slack left on the line (width minus current text minus the separating space) is at least the zone, the word has at least min-word characters, and (capitals allowed or its first letter is not uppercase). Pick the latest syllable boundary with head >= min before and tail >= min after chars whose head plus "-" fits. Return lines.

split: open-access