broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['ok', 0, 'decent']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [62, 0, 4, 76, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [91, 0, 10, 106, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [80, 0, 11, 90, 100], ['underfull', 10000, 'very_loose']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('control layout', [69, 10, 7, 69, 100], ['ok', 0, 'decent']), ('control layout', [74, 6, 6, 67, 100], ['overfull', 1000000, 'tight'])], [('regression: rigid line with slack', [94, 0, 10, 118, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [72, 0, 3, 87, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [114, 0, 6, 129, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [69, 2, 11, 55, 150], ['overfull', 1000000, 'tight']), ('control layout', [62, 4, 4, 58, 200], ['ok', 100, 'tight'])], [('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [62, 0, 4, 76, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [79, 0, 11, 96, 1000], ['underfull', 10000, 'very_loose']), ('full shrink is still acceptable', [100, 10, 5, 95, 200], ['ok', 100, 'tight']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('control layout', [118, 6, 5, 121, 100], ['ok', 13, 'decent']), ('control layout', [105, 4, 1, 111, 100], ['underfull', 338, 'very_loose'])], [('regression: rigid line with slack', [114, 0, 6, 129, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [83, 0, 3, 97, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [116, 0, 11, 126, 100], ['underfull', 10000, 'very_loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [85, 4, 0, 98, 150], ['underfull', 3433, 'very_loose']), ('control layout', [62, 6, 1, 51, 100], ['overfull', 1000000, 'tight'])], [('regression: rigid line with slack', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [91, 0, 10, 106, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [75, 0, 11, 88, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('control layout', [79, 6, 10, 67, 1000], ['overfull', 1000000, 'tight']), ('control layout', [74, 16, 0, 61, 200], ['overfull', 1000000, 'tight'])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [62, 0, 4, 76, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [91, 0, 10, 106, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [80, 0, 11, 90, 100], ['underfull', 10000, 'very_loose']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('control layout', [69, 10, 7, 69, 100], ['ok', 0, 'decent']), ('control layout', [74, 6, 6, 67, 100], ['overfull', 1000000, 'tight'])], [('regression: rigid line with slack', [94, 0, 10, 118, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [72, 0, 3, 87, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [114, 0, 6, 129, 200], ['underfull', 10000, 'very_loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [69, 2, 11, 55, 150], ['overfull', 1000000, 'tight']), ('control layout', [62, 4, 4, 58, 200], ['ok', 100, 'tight'])], [('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [62, 0, 4, 76, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [79, 0, 11, 96, 1000], ['underfull', 10000, 'very_loose']), ('full shrink is still acceptable', [100, 10, 5, 95, 200], ['ok', 100, 'tight']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('control layout', [118, 6, 5, 121, 100], ['ok', 13, 'decent']), ('control layout', [105, 4, 1, 111, 100], ['underfull', 338, 'very_loose'])], [('regression: rigid line with slack', [114, 0, 6, 129, 200], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [83, 0, 3, 97, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [116, 0, 11, 126, 100], ['underfull', 10000, 'very_loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [85, 4, 0, 98, 150], ['underfull', 3433, 'very_loose']), ('control layout', [62, 6, 1, 51, 100], ['overfull', 1000000, 'tight'])], [('regression: rigid line with slack', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [91, 0, 10, 106, 500], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [75, 0, 11, 88, 100], ['underfull', 10000, 'very_loose']), ('regression: rigid line with slack', [100, 0, 9, 105, 100], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('control layout', [79, 6, 10, 67, 1000], ['overfull', 1000000, 'tight']), ('control layout', [74, 16, 0, 61, 200], ['overfull', 1000000, 'tight'])]]
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 line with slack but no stretchable glue is accepted as perfect.

Input [natural, stretch, shrink, width, tolerance] (ints). shortfall=width-natural. Positive shortfall with zero stretch is underfull 10000 very_loose; shrinking past total shrink is overfull 1000000 tight. r=shortfall/stretch (or /shrink when negative); badness=min(10000, floor(100*|r|^3+1/2)); fitness tight r<-1/2, decent r<=1/2, loose r<=1, else very_loose; status ok iff badness<=tolerance. Return [status, badness, fitness].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'very_loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r < Fraction(1, 2):
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [120, 12, 3, 126, 1000], ['ok', 13, 'decent']), ('partial-repair probe', [94, 20, 0, 108, 100], ['ok', 34, 'loose']), ('partial-repair probe', [67, 6, 10, 71, 100], ['ok', 30, 'loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [63, 8, 8, 61, 200], ['ok', 2, 'decent']), ('control layout', [64, 4, 11, 65, 500], ['ok', 2, 'decent'])], [('regression: decent fitness upper bound', [101, 10, 11, 106, 150], ['ok', 13, 'decent']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('partial-repair probe', [80, 20, 1, 99, 150], ['ok', 86, 'loose']), ('partial-repair probe', [117, 10, 10, 127, 150], ['ok', 100, 'loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [92, 3, 7, 100, 500], ['underfull', 1896, 'very_loose']), ('control layout', [86, 3, 10, 109, 100], ['underfull', 10000, 'very_loose'])], [('regression: decent fitness upper bound', [60, 2, 9, 61, 1000], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [105, 12, 8, 111, 100], ['ok', 13, 'decent']), ('partial-repair probe', [61, 12, 9, 70, 100], ['ok', 42, 'loose']), ('partial-repair probe', [82, 20, 4, 95, 500], ['ok', 27, 'loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('control layout', [98, 2, 2, 102, 100], ['underfull', 800, 'very_loose']), ('control layout', [73, 3, 0, 67, 200], ['overfull', 1000000, 'tight'])], [('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [120, 12, 3, 126, 1000], ['ok', 13, 'decent']), ('partial-repair probe', [112, 8, 6, 120, 500], ['ok', 100, 'loose']), ('partial-repair probe', [71, 10, 5, 77, 200], ['ok', 22, 'loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('control layout', [65, 10, 12, 82, 150], ['underfull', 491, 'very_loose'])], [('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [105, 12, 8, 111, 100], ['ok', 13, 'decent']), ('partial-repair probe', [114, 8, 8, 119, 150], ['ok', 24, 'loose']), ('partial-repair probe', [82, 20, 4, 95, 500], ['ok', 27, 'loose']), ('badness cap at 10000', [100, 2, 0, 150, 200], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [104, 8, 7, 113, 500], ['ok', 142, 'very_loose']), ('control layout', [90, 12, 4, 95, 150], ['ok', 7, 'decent'])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    natural, stretch, shrink, width, tolerance = x
    shortfall = width - natural
    if shortfall > 0:
        if stretch == 0:
            return ['underfull', 10000, 'very_loose']
        r = Fraction(shortfall, stretch)
    elif shortfall < 0:
        if -shortfall > shrink:
            return ['overfull', 1000000, 'tight']
        r = Fraction(shortfall, shrink)
    else:
        r = Fraction(0)
    badness = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
    if r < Fraction(-1, 2):
        fitness = 'tight'
    elif r <= 1:
        fitness = 'decent'
    elif r <= 1:
        fitness = 'loose'
    else:
        fitness = 'very_loose'
    status = 'ok' if badness <= tolerance else 'underfull'
    return [status, badness, fitness]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [120, 12, 3, 126, 1000], ['ok', 13, 'decent']), ('partial-repair probe', [94, 20, 0, 108, 100], ['ok', 34, 'loose']), ('partial-repair probe', [67, 6, 10, 71, 100], ['ok', 30, 'loose']), ('rigid line with slack', [100, 0, 5, 110, 200], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [63, 8, 8, 61, 200], ['ok', 2, 'decent']), ('control layout', [64, 4, 11, 65, 500], ['ok', 2, 'decent'])], [('regression: decent fitness upper bound', [101, 10, 11, 106, 150], ['ok', 13, 'decent']), ('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('partial-repair probe', [80, 20, 1, 99, 150], ['ok', 86, 'loose']), ('partial-repair probe', [117, 10, 10, 127, 150], ['ok', 100, 'loose']), ('exact natural width', [100, 10, 5, 100, 200], ['ok', 0, 'decent']), ('one unit past total shrink', [100, 10, 5, 94, 200], ['overfull', 1000000, 'tight']), ('control layout', [92, 3, 7, 100, 500], ['underfull', 1896, 'very_loose']), ('control layout', [86, 3, 10, 109, 100], ['underfull', 10000, 'very_loose'])], [('regression: decent fitness upper bound', [60, 2, 9, 61, 1000], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [105, 12, 8, 111, 100], ['ok', 13, 'decent']), ('partial-repair probe', [61, 12, 9, 70, 100], ['ok', 42, 'loose']), ('partial-repair probe', [82, 20, 4, 95, 500], ['ok', 27, 'loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('control layout', [98, 2, 2, 102, 100], ['underfull', 800, 'very_loose']), ('control layout', [73, 3, 0, 67, 200], ['overfull', 1000000, 'tight'])], [('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [120, 12, 3, 126, 1000], ['ok', 13, 'decent']), ('partial-repair probe', [112, 8, 6, 120, 500], ['ok', 100, 'loose']), ('partial-repair probe', [71, 10, 5, 77, 200], ['ok', 22, 'loose']), ('negative half ratio is decent', [100, 10, 6, 97, 200], ['ok', 13, 'decent']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [90, 0, 6, 102, 1000], ['underfull', 10000, 'very_loose']), ('control layout', [65, 10, 12, 82, 150], ['underfull', 491, 'very_loose'])], [('half stretch ratio rounds 12.5 up', [100, 10, 5, 105, 200], ['ok', 13, 'decent']), ('regression: decent fitness upper bound', [105, 12, 8, 111, 100], ['ok', 13, 'decent']), ('partial-repair probe', [114, 8, 8, 119, 150], ['ok', 24, 'loose']), ('partial-repair probe', [82, 20, 4, 95, 500], ['ok', 27, 'loose']), ('badness cap at 10000', [100, 2, 0, 150, 200], ['underfull', 10000, 'very_loose']), ('very loose over tolerance', [100, 4, 0, 110, 200], ['underfull', 1563, 'very_loose']), ('control layout', [104, 8, 7, 113, 500], ['ok', 142, 'very_loose']), ('control layout', [90, 12, 4, 95, 150], ['ok', 7, 'decent'])]]
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:
Lines stretched by exactly half their stretch are classed loose.

Input [natural, stretch, shrink, width, tolerance] (ints). shortfall=width-natural. Positive shortfall with zero stretch is underfull 10000 very_loose; shrinking past total shrink is overfull 1000000 tight. r=shortfall/stretch (or /shrink when negative); badness=min(10000, floor(100*|r|^3+1/2)); fitness tight r<-1/2, decent r<=1/2, loose r<=1, else very_loose; status ok iff badness<=tolerance. Return [status, badness, fitness].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n - 1 and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: last-line exemption', [[1, 3, 6, 5, 7], [3, 1, 2], 21, 1], [197, [4, 5]]), ('regression: last-line exemption', [[7, 2, 1, 4, 1, 6, 1], [3, 1, 0], 12, 1], [3, [2, 5, 7]]), ('regression: last-line exemption', [[7, 2, 7, 1, 5, 1, 5, 3], [2, 2, 1], 15, 50], [753500, [2, 5, 8]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[3, 6, 2, 3, 1], [2, 1, 0], 23, 10], [100, [5]]), ('control layout', [[5, 5, 3, 6], [1, 1, 1], 22, 1], [1, [4]])], [('regression: last-line exemption', [[4, 5, 7, 1], [3, 2, 1], 15, 10], [127204, [2, 4]]), ('regression: last-line exemption', [[6, 5, 1], [2, 2, 1], 12, 10], [12200, [2, 3]]), ('partial-repair probe', [[1, 2, 6], [3, 3, 2], 13, 10], [529, [3]]), ('regression: last-line exemption', [[6, 6, 5, 3, 2, 4, 1, 5], [1, 1, 2], 14, 50], [28969, [2, 6, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[1, 3, 2, 5, 1, 5, 1], [1, 3, 2], 23, 10], [100, [7]]), ('control layout', [[2, 3, 2], [1, 3, 2], 9, 10], [100, [3]])], [('regression: last-line exemption', [[6, 5, 1], [2, 2, 1], 12, 10], [12200, [2, 3]]), ('regression: last-line exemption', [[3, 3, 2, 3, 4, 7], [2, 3, 1], 12, 50], [27500, [3, 5, 6]]), ('partial-repair probe', [[2, 7, 6, 1, 7, 4, 6, 2], [2, 3, 0], 17, 10], ['infeasible']), ('partial-repair probe', [[2, 5, 3, 6, 5], [2, 1, 1], 12, 50], [45000, [3, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 7, 7, 2], [1, 3, 1], 21, 10], [100, [4]]), ('control layout', [[2, 3, 2], [1, 3, 2], 9, 10], [100, [3]])], [('regression: last-line exemption', [[6, 7, 6, 7, 4], [3, 2, 2], 22, 10], [2804, [3, 5]]), ('regression: last-line exemption', [[2, 7, 2, 6, 7], [2, 1, 1], 16, 10], [629, [3, 5]]), ('partial-repair probe', [[5, 7, 4, 4], [3, 2, 1], 13, 10], ['infeasible']), ('regression: last-line exemption', [[4, 3, 3, 4, 2], [1, 3, 0], 17, 1], [2, [4, 5]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 5, 3], [1, 1, 2], 14, 1], [1, [3]]), ('control layout', [[3, 6, 2, 3, 1], [2, 1, 0], 23, 10], [100, [5]])], [('regression: last-line exemption', [[6, 1, 7, 7, 2, 1, 5, 5], [2, 2, 1], 17, 10], [3333, [3, 6, 8]]), ('regression: last-line exemption', [[5, 3, 1, 4, 2, 7, 3, 6], [2, 2, 1], 15, 50], [28969, [3, 6, 8]]), ('regression: last-line exemption', [[2, 2, 7, 7], [3, 3, 0], 19, 1], [26, [3, 4]]), ('regression: last-line exemption', [[5, 7, 5, 6, 5, 6, 4], [1, 2, 1], 17, 1], [20403, [3, 6, 7]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[5, 2, 1, 7], [1, 2, 0], 19, 1], [1, [4]]), ('control layout', [[4, 2, 3], [1, 3, 0], 12, 50], [2500, [3]])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: last-line exemption', [[1, 3, 6, 5, 7], [3, 1, 2], 21, 1], [197, [4, 5]]), ('regression: last-line exemption', [[7, 2, 1, 4, 1, 6, 1], [3, 1, 0], 12, 1], [3, [2, 5, 7]]), ('regression: last-line exemption', [[7, 2, 7, 1, 5, 1, 5, 3], [2, 2, 1], 15, 50], [753500, [2, 5, 8]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[3, 6, 2, 3, 1], [2, 1, 0], 23, 10], [100, [5]]), ('control layout', [[5, 5, 3, 6], [1, 1, 1], 22, 1], [1, [4]])], [('regression: last-line exemption', [[4, 5, 7, 1], [3, 2, 1], 15, 10], [127204, [2, 4]]), ('regression: last-line exemption', [[6, 5, 1], [2, 2, 1], 12, 10], [12200, [2, 3]]), ('partial-repair probe', [[1, 2, 6], [3, 3, 2], 13, 10], [529, [3]]), ('regression: last-line exemption', [[6, 6, 5, 3, 2, 4, 1, 5], [1, 1, 2], 14, 50], [28969, [2, 6, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[1, 3, 2, 5, 1, 5, 1], [1, 3, 2], 23, 10], [100, [7]]), ('control layout', [[2, 3, 2], [1, 3, 2], 9, 10], [100, [3]])], [('regression: last-line exemption', [[6, 5, 1], [2, 2, 1], 12, 10], [12200, [2, 3]]), ('regression: last-line exemption', [[3, 3, 2, 3, 4, 7], [2, 3, 1], 12, 50], [27500, [3, 5, 6]]), ('partial-repair probe', [[2, 7, 6, 1, 7, 4, 6, 2], [2, 3, 0], 17, 10], ['infeasible']), ('partial-repair probe', [[2, 5, 3, 6, 5], [2, 1, 1], 12, 50], [45000, [3, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 7, 7, 2], [1, 3, 1], 21, 10], [100, [4]]), ('control layout', [[2, 3, 2], [1, 3, 2], 9, 10], [100, [3]])], [('regression: last-line exemption', [[6, 7, 6, 7, 4], [3, 2, 2], 22, 10], [2804, [3, 5]]), ('regression: last-line exemption', [[2, 7, 2, 6, 7], [2, 1, 1], 16, 10], [629, [3, 5]]), ('partial-repair probe', [[5, 7, 4, 4], [3, 2, 1], 13, 10], ['infeasible']), ('regression: last-line exemption', [[4, 3, 3, 4, 2], [1, 3, 0], 17, 1], [2, [4, 5]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 5, 3], [1, 1, 2], 14, 1], [1, [3]]), ('control layout', [[3, 6, 2, 3, 1], [2, 1, 0], 23, 10], [100, [5]])], [('regression: last-line exemption', [[6, 1, 7, 7, 2, 1, 5, 5], [2, 2, 1], 17, 10], [3333, [3, 6, 8]]), ('regression: last-line exemption', [[5, 3, 1, 4, 2, 7, 3, 6], [2, 2, 1], 15, 50], [28969, [3, 6, 8]]), ('regression: last-line exemption', [[2, 2, 7, 7], [3, 3, 0], 19, 1], [26, [3, 4]]), ('regression: last-line exemption', [[5, 7, 5, 6, 5, 6, 4], [1, 2, 1], 17, 1], [20403, [3, 6, 7]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[5, 2, 1, 7], [1, 2, 0], 19, 1], [1, [4]]), ('control layout', [[4, 2, 3], [1, 3, 0], 12, 50], [2500, [3]])]]
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 paragraph ending is rated like a justified line and good breaks become infeasible.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + lp + b ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: demerit squaring', [[1, 5, 5], [1, 3, 2], 14, 10], [100, [3]]), ('regression: demerit squaring', [[4, 2, 4, 4, 5, 1, 1], [2, 3, 0], 14, 50], [7500, [3, 6, 7]]), ('regression: demerit squaring', [[2, 5, 1, 1, 6, 7], [1, 2, 2], 15, 10], [629, [4, 6]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[6, 1, 7, 2, 3, 2, 3, 3], [3, 3, 0], 9, 1], ['infeasible']), ('control layout', [[6, 6, 6, 1, 4, 3, 1, 7], [3, 1, 1], 10, 1], ['infeasible'])], [('regression: demerit squaring', [[4, 6, 5, 1, 1, 1, 5, 2], [1, 1, 2], 18, 10], [200, [4, 8]]), ('regression: demerit squaring', [[1, 4, 6, 3, 3, 2, 3, 4], [3, 2, 0], 20, 50], [13464, [3, 7, 8]]), ('partial-repair probe', [[4, 5, 4, 4], [1, 3, 2], 23, 1], [1, [4]]), ('regression: demerit squaring', [[2, 2, 5, 3, 6, 2, 5, 3], [2, 1, 2], 17, 50], [7500, [4, 7, 8]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 6, 5, 7, 3, 6], [3, 3, 1], 13, 10], ['infeasible']), ('control layout', [[2, 6, 7, 3, 1, 5, 5, 1], [1, 1, 1], 9, 1], ['infeasible'])], [('regression: demerit squaring', [[1, 5, 5], [1, 3, 2], 14, 10], [100, [3]]), ('regression: demerit squaring', [[5, 6, 4, 5, 5, 2], [1, 2, 2], 11, 10], [1158, [2, 4, 6]]), ('regression: demerit squaring', [[4, 1, 4], [3, 2, 1], 24, 50], [2500, [3]]), ('regression: demerit squaring', [[6, 3, 4, 2, 2], [3, 3, 2], 11, 1], [1158, [2, 4, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[3, 2, 6, 5, 1], [1, 1, 0], 9, 50], ['infeasible']), ('control layout', [[6, 4, 6, 5, 2, 3], [3, 1, 0], 9, 50], ['infeasible'])], [('regression: demerit squaring', [[2, 5, 1, 1, 6, 7], [1, 2, 2], 15, 10], [629, [4, 6]]), ('regression: demerit squaring', [[1, 7, 7, 2, 4, 1, 3, 4], [1, 1, 2], 13, 50], [27500, [3, 7, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('regression: demerit squaring', [[3, 2, 5, 2], [2, 1, 2], 20, 50], [2500, [4]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[6, 3, 6, 5, 7], [3, 1, 2], 9, 1], ['infeasible']), ('control layout', [[3, 2, 4, 1, 4, 4, 1, 7], [3, 1, 0], 9, 10], ['infeasible'])], [('regression: demerit squaring', [[7, 1, 4, 7, 1, 4], [3, 3, 0], 24, 1], [10202, [3, 6]]), ('regression: demerit squaring', [[3, 5, 7, 2, 2, 1], [2, 3, 1], 11, 1], [27, [2, 4, 6]]), ('regression: demerit squaring', [[1, 2, 4, 4, 5], [2, 2, 1], 21, 1], [962, [4, 5]]), ('regression: demerit squaring', [[1, 3, 1, 2, 2], [3, 2, 1], 10, 10], [629, [3, 5]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[2, 7, 6, 1, 7, 4, 6, 2], [2, 3, 0], 17, 10], ['infeasible']), ('control layout', [[4, 3, 7, 7, 7], [1, 1, 1], 11, 10], ['infeasible'])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) * 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: demerit squaring', [[1, 5, 5], [1, 3, 2], 14, 10], [100, [3]]), ('regression: demerit squaring', [[4, 2, 4, 4, 5, 1, 1], [2, 3, 0], 14, 50], [7500, [3, 6, 7]]), ('regression: demerit squaring', [[2, 5, 1, 1, 6, 7], [1, 2, 2], 15, 10], [629, [4, 6]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[6, 1, 7, 2, 3, 2, 3, 3], [3, 3, 0], 9, 1], ['infeasible']), ('control layout', [[6, 6, 6, 1, 4, 3, 1, 7], [3, 1, 1], 10, 1], ['infeasible'])], [('regression: demerit squaring', [[4, 6, 5, 1, 1, 1, 5, 2], [1, 1, 2], 18, 10], [200, [4, 8]]), ('regression: demerit squaring', [[1, 4, 6, 3, 3, 2, 3, 4], [3, 2, 0], 20, 50], [13464, [3, 7, 8]]), ('partial-repair probe', [[4, 5, 4, 4], [1, 3, 2], 23, 1], [1, [4]]), ('regression: demerit squaring', [[2, 2, 5, 3, 6, 2, 5, 3], [2, 1, 2], 17, 50], [7500, [4, 7, 8]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 6, 5, 7, 3, 6], [3, 3, 1], 13, 10], ['infeasible']), ('control layout', [[2, 6, 7, 3, 1, 5, 5, 1], [1, 1, 1], 9, 1], ['infeasible'])], [('regression: demerit squaring', [[1, 5, 5], [1, 3, 2], 14, 10], [100, [3]]), ('regression: demerit squaring', [[5, 6, 4, 5, 5, 2], [1, 2, 2], 11, 10], [1158, [2, 4, 6]]), ('regression: demerit squaring', [[4, 1, 4], [3, 2, 1], 24, 50], [2500, [3]]), ('regression: demerit squaring', [[6, 3, 4, 2, 2], [3, 3, 2], 11, 1], [1158, [2, 4, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[3, 2, 6, 5, 1], [1, 1, 0], 9, 50], ['infeasible']), ('control layout', [[6, 4, 6, 5, 2, 3], [3, 1, 0], 9, 50], ['infeasible'])], [('regression: demerit squaring', [[2, 5, 1, 1, 6, 7], [1, 2, 2], 15, 10], [629, [4, 6]]), ('regression: demerit squaring', [[1, 7, 7, 2, 4, 1, 3, 4], [1, 1, 2], 13, 50], [27500, [3, 7, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('regression: demerit squaring', [[3, 2, 5, 2], [2, 1, 2], 20, 50], [2500, [4]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[6, 3, 6, 5, 7], [3, 1, 2], 9, 1], ['infeasible']), ('control layout', [[3, 2, 4, 1, 4, 4, 1, 7], [3, 1, 0], 9, 10], ['infeasible'])], [('regression: demerit squaring', [[7, 1, 4, 7, 1, 4], [3, 3, 0], 24, 1], [10202, [3, 6]]), ('regression: demerit squaring', [[3, 5, 7, 2, 2, 1], [2, 3, 1], 11, 1], [27, [2, 4, 6]]), ('regression: demerit squaring', [[1, 2, 4, 4, 5], [2, 2, 1], 21, 1], [962, [4, 5]]), ('regression: demerit squaring', [[1, 3, 1, 2, 2], [3, 2, 1], 10, 10], [629, [3, 5]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[2, 7, 6, 1, 7, 4, 6, 2], [2, 3, 0], 17, 10], ['infeasible']), ('control layout', [[4, 3, 7, 7, 7], [1, 1, 1], 11, 10], ['infeasible'])]]
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:
Break choices favour many mediocre lines over fewer good ones.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) >= 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: adjacent fitness penalty', [[3, 6, 2, 2, 3, 1, 6], [3, 2, 1], 14, 1], [10211, [2, 5, 7]]), ('partial-repair probe', [[6, 6, 7, 3, 4, 4], [1, 1, 2], 15, 1], [647611, [2, 5, 6]]), ('partial-repair probe', [[1, 3, 7], [3, 2, 2], 11, 1], [647602, [2, 3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 5, 6], [1, 1, 1], 10, 10], [200, [2, 3]]), ('control layout', [[4, 5, 6, 3, 3, 6, 2, 5], [3, 3, 0], 24, 50], [8969, [3, 7, 8]])], [('regression: adjacent fitness penalty', [[1, 7, 7, 2, 4, 1, 3, 4], [1, 1, 2], 13, 50], [27500, [3, 7, 8]]), ('regression: adjacent fitness penalty', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[7, 5, 2, 3, 3], [3, 1, 0], 17, 10], [662200, [2, 5]]), ('regression: adjacent fitness penalty', [[4, 7, 6, 7, 2, 7, 6, 4], [1, 1, 1], 22, 10], [139304, [3, 7, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[3, 3, 5], [3, 1, 2], 21, 10], [100, [3]]), ('control layout', [[5, 5, 3, 6], [1, 1, 1], 22, 1], [1, [4]])], [('regression: adjacent fitness penalty', [[3, 6, 2, 2, 3, 1, 6], [3, 2, 1], 14, 1], [10211, [2, 5, 7]]), ('regression: adjacent fitness penalty', [[4, 2, 7, 3, 4], [2, 1, 1], 15, 50], [25000, [3, 5]]), ('partial-repair probe', [[5, 1, 6, 4, 7, 7, 1, 4], [1, 1, 1], 14, 1], [647603, [3, 5, 8]]), ('regression: adjacent fitness penalty', [[5, 7, 4, 7, 6, 4, 4, 1], [2, 1, 1], 24, 10], [674300, [3, 7, 8]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[1, 2, 5], [3, 3, 2], 13, 1], [9, [3]]), ('control layout', [[2, 3, 2, 2, 2, 4, 2, 7], [3, 3, 1], 9, 10], ['infeasible'])], [('regression: adjacent fitness penalty', [[2, 7, 2, 3, 3, 4], [3, 2, 0], 21, 50], [25000, [3, 6]]), ('regression: adjacent fitness penalty', [[7, 4, 3, 3, 6, 3, 7], [1, 1, 1], 13, 10], [12729, [2, 5, 7]]), ('partial-repair probe', [[2, 1, 4, 6, 1, 5], [3, 1, 1], 16, 50], [179044, [3, 6]]), ('partial-repair probe', [[5, 1, 5, 4], [2, 2, 1], 12, 1], [647602, [2, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[4, 5, 4, 4], [1, 3, 2], 23, 1], [1, [4]]), ('control layout', [[7, 2, 2, 5, 7, 5], [3, 1, 0], 24, 10], ['infeasible'])], [('regression: adjacent fitness penalty', [[4, 4, 5, 4, 5], [1, 1, 1], 11, 10], [671300, [2, 4, 5]]), ('regression: adjacent fitness penalty', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[4, 1, 2, 3, 1, 7, 5, 1], [3, 2, 2], 11, 1], [235844, [2, 4, 6, 8]]), ('partial-repair probe', [[7, 6, 6, 6, 5, 5, 2, 4], [2, 2, 0], 15, 1], [121119, [2, 4, 6, 8]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[7, 4, 6, 5, 6, 4], [2, 2, 2], 23, 50], [6469, [3, 6]]), ('control layout', [[6, 1, 2], [2, 2, 2], 14, 10], [100, [3]])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if fit - pfit > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: adjacent fitness penalty', [[3, 6, 2, 2, 3, 1, 6], [3, 2, 1], 14, 1], [10211, [2, 5, 7]]), ('partial-repair probe', [[6, 6, 7, 3, 4, 4], [1, 1, 2], 15, 1], [647611, [2, 5, 6]]), ('partial-repair probe', [[1, 3, 7], [3, 2, 2], 11, 1], [647602, [2, 3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 5, 6], [1, 1, 1], 10, 10], [200, [2, 3]]), ('control layout', [[4, 5, 6, 3, 3, 6, 2, 5], [3, 3, 0], 24, 50], [8969, [3, 7, 8]])], [('regression: adjacent fitness penalty', [[1, 7, 7, 2, 4, 1, 3, 4], [1, 1, 2], 13, 50], [27500, [3, 7, 8]]), ('regression: adjacent fitness penalty', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[7, 5, 2, 3, 3], [3, 1, 0], 17, 10], [662200, [2, 5]]), ('regression: adjacent fitness penalty', [[4, 7, 6, 7, 2, 7, 6, 4], [1, 1, 1], 22, 10], [139304, [3, 7, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[3, 3, 5], [3, 1, 2], 21, 10], [100, [3]]), ('control layout', [[5, 5, 3, 6], [1, 1, 1], 22, 1], [1, [4]])], [('regression: adjacent fitness penalty', [[3, 6, 2, 2, 3, 1, 6], [3, 2, 1], 14, 1], [10211, [2, 5, 7]]), ('regression: adjacent fitness penalty', [[4, 2, 7, 3, 4], [2, 1, 1], 15, 50], [25000, [3, 5]]), ('partial-repair probe', [[5, 1, 6, 4, 7, 7, 1, 4], [1, 1, 1], 14, 1], [647603, [3, 5, 8]]), ('regression: adjacent fitness penalty', [[5, 7, 4, 7, 6, 4, 4, 1], [2, 1, 1], 24, 10], [674300, [3, 7, 8]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[1, 2, 5], [3, 3, 2], 13, 1], [9, [3]]), ('control layout', [[2, 3, 2, 2, 2, 4, 2, 7], [3, 3, 1], 9, 10], ['infeasible'])], [('regression: adjacent fitness penalty', [[2, 7, 2, 3, 3, 4], [3, 2, 0], 21, 50], [25000, [3, 6]]), ('regression: adjacent fitness penalty', [[7, 4, 3, 3, 6, 3, 7], [1, 1, 1], 13, 10], [12729, [2, 5, 7]]), ('partial-repair probe', [[2, 1, 4, 6, 1, 5], [3, 1, 1], 16, 50], [179044, [3, 6]]), ('partial-repair probe', [[5, 1, 5, 4], [2, 2, 1], 12, 1], [647602, [2, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[4, 5, 4, 4], [1, 3, 2], 23, 1], [1, [4]]), ('control layout', [[7, 2, 2, 5, 7, 5], [3, 1, 0], 24, 10], ['infeasible'])], [('regression: adjacent fitness penalty', [[4, 4, 5, 4, 5], [1, 1, 1], 11, 10], [671300, [2, 4, 5]]), ('regression: adjacent fitness penalty', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[4, 1, 2, 3, 1, 7, 5, 1], [3, 2, 2], 11, 1], [235844, [2, 4, 6, 8]]), ('partial-repair probe', [[7, 6, 6, 6, 5, 5, 2, 4], [2, 2, 0], 15, 1], [121119, [2, 4, 6, 8]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[7, 4, 6, 5, 6, 4], [2, 2, 2], 23, 50], [6469, [3, 6]]), ('control layout', [[6, 1, 2], [2, 2, 2], 14, 10], [100, [3]])]]
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:
Neighbouring lines one class apart are penalised as visually incompatible.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * (j - i)
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: interword gap count', [[4, 1, 7, 4, 5, 5, 4], [3, 3, 1], 23, 50], [8900, [4, 7]]), ('regression: interword gap count', [[2, 1, 3, 5, 5], [3, 1, 0], 20, 50], [5000, [4, 5]]), ('regression: interword gap count', [[1, 3, 1, 2, 2], [3, 2, 1], 10, 10], [629, [3, 5]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[7, 6, 5, 6, 3, 1, 3], [1, 3, 2], 9, 10], ['infeasible']), ('control layout', [[7, 7, 3, 4, 5, 3, 6], [2, 1, 1], 9, 10], ['infeasible'])], [('regression: interword gap count', [[1, 7, 5, 5, 2], [2, 2, 0], 17, 10], [200, [3, 5]]), ('regression: interword gap count', [[4, 3, 1, 4, 3, 5], [2, 1, 2], 24, 10], [244, [5, 6]]), ('regression: interword gap count', [[2, 4, 1, 6, 1, 2, 3, 1], [2, 1, 0], 10, 50], [753000, [2, 4, 7, 8]]), ('regression: interword gap count', [[2, 5, 3, 6, 5], [2, 1, 1], 12, 50], [45000, [3, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[6, 5, 3, 7, 5, 2], [3, 3, 0], 11, 10], ['infeasible']), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]])], [('regression: interword gap count', [[6, 5, 7, 7, 4, 7], [3, 1, 1], 23, 50], [7938, [3, 6]]), ('regression: interword gap count', [[2, 5, 7, 6, 7, 6, 6], [1, 3, 0], 15, 10], ['infeasible']), ('regression: interword gap count', [[3, 5, 7, 2, 2, 1], [2, 3, 1], 11, 1], [27, [2, 4, 6]]), ('regression: interword gap count', [[2, 5, 4, 7, 4, 1, 3], [1, 2, 1], 18, 10], [12200, [4, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[5, 4, 4], [2, 1, 2], 20, 50], [2500, [3]]), ('control layout', [[2, 7, 6, 5, 5], [3, 3, 1], 12, 50], ['infeasible'])], [('regression: interword gap count', [[1, 7, 4, 1, 6, 5, 2, 4], [2, 3, 0], 23, 50], [5981, [4, 8]]), ('regression: interword gap count', [[4, 1, 4, 3, 5, 3, 6], [3, 3, 0], 23, 1], [5, [4, 7]]), ('regression: interword gap count', [[5, 4, 5, 2], [3, 2, 0], 16, 10], [662200, [2, 4]]), ('regression: interword gap count', [[5, 2, 3, 6, 7], [2, 2, 1], 24, 1], [26, [4, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[6, 7, 3, 4, 3, 5], [3, 1, 1], 9, 10], ['infeasible']), ('control layout', [[7, 1, 2], [1, 1, 0], 22, 50], [2500, [3]])], [('regression: interword gap count', [[2, 5, 4, 7, 4, 1, 3], [1, 2, 1], 18, 10], [12200, [4, 7]]), ('regression: interword gap count', [[7, 3, 1, 4, 5, 7, 2, 1], [1, 1, 2], 12, 50], [27500, [2, 5, 8]]), ('regression: interword gap count', [[7, 1, 4, 6, 6, 2, 3], [3, 2, 1], 12, 50], [32938, [2, 4, 6, 7]]), ('regression: interword gap count', [[7, 3, 7, 4, 7, 3, 1, 5], [3, 1, 2], 19, 10], [12344, [3, 6, 8]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('control layout', [[4, 1, 1], [1, 3, 2], 15, 50], [2500, [3]])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps + (1 if j < n else 0)
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('regression: interword gap count', [[4, 1, 7, 4, 5, 5, 4], [3, 3, 1], 23, 50], [8900, [4, 7]]), ('regression: interword gap count', [[2, 1, 3, 5, 5], [3, 1, 0], 20, 50], [5000, [4, 5]]), ('regression: interword gap count', [[1, 3, 1, 2, 2], [3, 2, 1], 10, 10], [629, [3, 5]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[7, 6, 5, 6, 3, 1, 3], [1, 3, 2], 9, 10], ['infeasible']), ('control layout', [[7, 7, 3, 4, 5, 3, 6], [2, 1, 1], 9, 10], ['infeasible'])], [('regression: interword gap count', [[1, 7, 5, 5, 2], [2, 2, 0], 17, 10], [200, [3, 5]]), ('regression: interword gap count', [[4, 3, 1, 4, 3, 5], [2, 1, 2], 24, 10], [244, [5, 6]]), ('regression: interword gap count', [[2, 4, 1, 6, 1, 2, 3, 1], [2, 1, 0], 10, 50], [753000, [2, 4, 7, 8]]), ('regression: interword gap count', [[2, 5, 3, 6, 5], [2, 1, 1], 12, 50], [45000, [3, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[6, 5, 3, 7, 5, 2], [3, 3, 0], 11, 10], ['infeasible']), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]])], [('regression: interword gap count', [[6, 5, 7, 7, 4, 7], [3, 1, 1], 23, 50], [7938, [3, 6]]), ('regression: interword gap count', [[2, 5, 7, 6, 7, 6, 6], [1, 3, 0], 15, 10], ['infeasible']), ('regression: interword gap count', [[3, 5, 7, 2, 2, 1], [2, 3, 1], 11, 1], [27, [2, 4, 6]]), ('regression: interword gap count', [[2, 5, 4, 7, 4, 1, 3], [1, 2, 1], 18, 10], [12200, [4, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[5, 4, 4], [2, 1, 2], 20, 50], [2500, [3]]), ('control layout', [[2, 7, 6, 5, 5], [3, 3, 1], 12, 50], ['infeasible'])], [('regression: interword gap count', [[1, 7, 4, 1, 6, 5, 2, 4], [2, 3, 0], 23, 50], [5981, [4, 8]]), ('regression: interword gap count', [[4, 1, 4, 3, 5, 3, 6], [3, 3, 0], 23, 1], [5, [4, 7]]), ('regression: interword gap count', [[5, 4, 5, 2], [3, 2, 0], 16, 10], [662200, [2, 4]]), ('regression: interword gap count', [[5, 2, 3, 6, 7], [2, 2, 1], 24, 1], [26, [4, 5]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[6, 7, 3, 4, 3, 5], [3, 1, 1], 9, 10], ['infeasible']), ('control layout', [[7, 1, 2], [1, 1, 0], 22, 50], [2500, [3]])], [('regression: interword gap count', [[2, 5, 4, 7, 4, 1, 3], [1, 2, 1], 18, 10], [12200, [4, 7]]), ('regression: interword gap count', [[7, 3, 1, 4, 5, 7, 2, 1], [1, 1, 2], 12, 50], [27500, [2, 5, 8]]), ('regression: interword gap count', [[7, 1, 4, 6, 6, 2, 3], [3, 2, 1], 12, 50], [32938, [2, 4, 6, 7]]), ('regression: interword gap count', [[7, 3, 7, 4, 7, 3, 1, 5], [3, 1, 2], 19, 10], [12344, [3, 6, 8]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('control layout', [[4, 1, 1], [1, 3, 2], 15, 50], [2500, [3]])]]
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:
Every line measures one space too wide and breaks too early.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 10000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: badness tolerance', [[2, 7, 3, 5, 2, 5, 6], [2, 1, 0], 21, 50], ['infeasible']), ('regression: badness tolerance', [[5, 5, 6, 1], [3, 3, 0], 20, 50], ['infeasible']), ('partial-repair probe', [[7, 4, 5, 1, 7, 3], [2, 2, 0], 17, 1], [647603, [2, 5, 6]]), ('partial-repair probe', [[7, 5, 2, 3, 3], [3, 1, 0], 17, 10], [662200, [2, 5]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 3, 3], [3, 1, 2], 12, 10], [529, [3]]), ('control layout', [[2, 1, 7, 7], [2, 3, 0], 13, 10], ['infeasible'])], [('regression: badness tolerance', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('regression: badness tolerance', [[1, 4, 7, 1, 7, 3, 2, 4], [2, 1, 0], 14, 10], ['infeasible']), ('partial-repair probe', [[7, 4, 7, 6], [2, 3, 1], 19, 10], [662200, [2, 4]]), ('partial-repair probe', [[4, 4, 6], [2, 2, 0], 14, 10], [662200, [2, 3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[2, 4, 4, 7, 4, 2, 5], [1, 3, 2], 16, 50], [8900, [4, 7]]), ('control layout', [[1, 2, 5, 4, 1, 6], [2, 1, 2], 18, 50], [5000, [4, 6]])], [('regression: badness tolerance', [[5, 4, 1, 2, 6, 1, 5], [3, 1, 1], 11, 50], ['infeasible']), ('regression: badness tolerance', [[6, 7, 6, 5], [3, 3, 0], 24, 50], ['infeasible']), ('partial-repair probe', [[6, 1, 2, 5, 6, 1, 3, 4], [3, 2, 0], 22, 10], [313316, [3, 6, 8]]), ('partial-repair probe', [[1, 3, 3], [3, 3, 0], 12, 50], [271669, [2, 3]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[7, 6, 4, 1, 7, 1, 6], [1, 3, 2], 16, 1], [963, [2, 6, 7]]), ('control layout', [[7, 7, 7, 6], [2, 3, 1], 24, 10], [629, [3, 4]])], [('regression: badness tolerance', [[6, 7, 6, 5], [3, 3, 0], 24, 50], ['infeasible']), ('regression: badness tolerance', [[1, 2, 6, 2, 4, 4, 7, 1], [1, 2, 0], 9, 10], ['infeasible']), ('partial-repair probe', [[4, 5, 7, 1], [3, 2, 1], 15, 10], [127204, [2, 4]]), ('partial-repair probe', [[7, 4, 7, 6], [2, 3, 1], 19, 10], [662200, [2, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[7, 7, 7, 1, 2], [3, 3, 2], 20, 10], [12200, [2, 5]]), ('control layout', [[7, 7, 4, 3, 1], [2, 2, 1], 21, 10], [629, [3, 5]])], [('regression: badness tolerance', [[4, 5, 3, 6, 2, 7], [1, 1, 0], 13, 1], ['infeasible']), ('regression: badness tolerance', [[3, 7, 1, 2, 7, 1], [2, 2, 0], 13, 10], ['infeasible']), ('partial-repair probe', [[5, 2, 6, 2, 2, 5, 5], [3, 1, 1], 12, 10], [1330400, [2, 4, 6, 7]]), ('partial-repair probe', [[5, 3, 5, 4, 7], [3, 1, 2], 13, 50], [750500, [2, 4, 5]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[5, 7, 2], [2, 1, 2], 24, 50], [2500, [3]]), ('control layout', [[1, 1, 5, 3], [3, 2, 0], 14, 50], [5204, [3, 4]])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 100:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 1): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: badness tolerance', [[2, 7, 3, 5, 2, 5, 6], [2, 1, 0], 21, 50], ['infeasible']), ('regression: badness tolerance', [[5, 5, 6, 1], [3, 3, 0], 20, 50], ['infeasible']), ('partial-repair probe', [[7, 4, 5, 1, 7, 3], [2, 2, 0], 17, 1], [647603, [2, 5, 6]]), ('partial-repair probe', [[7, 5, 2, 3, 3], [3, 1, 0], 17, 10], [662200, [2, 5]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 3, 3], [3, 1, 2], 12, 10], [529, [3]]), ('control layout', [[2, 1, 7, 7], [2, 3, 0], 13, 10], ['infeasible'])], [('regression: badness tolerance', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('regression: badness tolerance', [[1, 4, 7, 1, 7, 3, 2, 4], [2, 1, 0], 14, 10], ['infeasible']), ('partial-repair probe', [[7, 4, 7, 6], [2, 3, 1], 19, 10], [662200, [2, 4]]), ('partial-repair probe', [[4, 4, 6], [2, 2, 0], 14, 10], [662200, [2, 3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[2, 4, 4, 7, 4, 2, 5], [1, 3, 2], 16, 50], [8900, [4, 7]]), ('control layout', [[1, 2, 5, 4, 1, 6], [2, 1, 2], 18, 50], [5000, [4, 6]])], [('regression: badness tolerance', [[5, 4, 1, 2, 6, 1, 5], [3, 1, 1], 11, 50], ['infeasible']), ('regression: badness tolerance', [[6, 7, 6, 5], [3, 3, 0], 24, 50], ['infeasible']), ('partial-repair probe', [[6, 1, 2, 5, 6, 1, 3, 4], [3, 2, 0], 22, 10], [313316, [3, 6, 8]]), ('partial-repair probe', [[1, 3, 3], [3, 3, 0], 12, 50], [271669, [2, 3]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('control layout', [[7, 6, 4, 1, 7, 1, 6], [1, 3, 2], 16, 1], [963, [2, 6, 7]]), ('control layout', [[7, 7, 7, 6], [2, 3, 1], 24, 10], [629, [3, 4]])], [('regression: badness tolerance', [[6, 7, 6, 5], [3, 3, 0], 24, 50], ['infeasible']), ('regression: badness tolerance', [[1, 2, 6, 2, 4, 4, 7, 1], [1, 2, 0], 9, 10], ['infeasible']), ('partial-repair probe', [[4, 5, 7, 1], [3, 2, 1], 15, 10], [127204, [2, 4]]), ('partial-repair probe', [[7, 4, 7, 6], [2, 3, 1], 19, 10], [662200, [2, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[7, 7, 7, 1, 2], [3, 3, 2], 20, 10], [12200, [2, 5]]), ('control layout', [[7, 7, 4, 3, 1], [2, 2, 1], 21, 10], [629, [3, 5]])], [('regression: badness tolerance', [[4, 5, 3, 6, 2, 7], [1, 1, 0], 13, 1], ['infeasible']), ('regression: badness tolerance', [[3, 7, 1, 2, 7, 1], [2, 2, 0], 13, 10], ['infeasible']), ('partial-repair probe', [[5, 2, 6, 2, 2, 5, 5], [3, 1, 1], 12, 10], [1330400, [2, 4, 6, 7]]), ('partial-repair probe', [[5, 3, 5, 4, 7], [3, 1, 2], 13, 50], [750500, [2, 4, 5]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[5, 7, 2], [2, 1, 2], 24, 50], [2500, [3]]), ('control layout', [[1, 1, 5, 3], [3, 2, 0], 14, 50], [5204, [3, 4]])]]
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:
Very loose lines are chosen that should have been rejected as infeasible.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 0): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: initial fitness class', [[7, 6, 7, 4, 4, 2], [2, 1, 2], 16, 10], [17904, [2, 5, 6]]), ('regression: initial fitness class', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[2, 5, 1], [1, 1, 2], 12, 1], [1, [3]]), ('partial-repair probe', [[2, 3, 3], [1, 3, 1], 12, 10], [100, [3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 7, 7, 7, 3, 6, 6], [3, 2, 1], 15, 10], ['infeasible']), ('control layout', [[4, 3, 7, 7, 7], [1, 1, 1], 11, 10], ['infeasible'])], [('regression: initial fitness class', [[4, 1, 1, 6, 4], [3, 1, 0], 24, 10], [12200, [4, 5]]), ('regression: initial fitness class', [[3, 3, 4, 3, 2], [3, 3, 0], 12, 50], [31400, [2, 4, 5]]), ('partial-repair probe', [[1, 6, 7, 3, 5, 6, 7], [2, 1, 1], 18, 50], [7500, [3, 6, 7]]), ('partial-repair probe', [[2, 5, 1], [1, 1, 2], 12, 1], [1, [3]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[1, 4, 7, 1, 7, 3, 2, 4], [2, 1, 0], 14, 10], ['infeasible']), ('control layout', [[4, 6, 6, 4, 1, 5, 4], [2, 1, 0], 17, 50], ['infeasible'])], [('regression: initial fitness class', [[1, 5, 4, 4], [1, 2, 0], 15, 10], [2804, [3, 4]]), ('regression: initial fitness class', [[1, 3, 1, 3, 5, 5, 3, 3], [3, 2, 0], 23, 10], [24300, [4, 7, 8]]), ('partial-repair probe', [[6, 2, 2, 4], [3, 2, 2], 20, 10], [529, [4]]), ('partial-repair probe', [[6, 3, 6, 2, 1, 4, 3], [2, 2, 1], 20, 10], [244, [3, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[6, 1, 6, 5, 5, 2, 6], [2, 2, 0], 16, 1], ['infeasible']), ('control layout', [[1, 7, 7, 7, 5, 1, 2, 4], [1, 2, 0], 14, 1], ['infeasible'])], [('regression: initial fitness class', [[3, 3, 4, 4], [3, 3, 2], 12, 10], [12200, [2, 4]]), ('regression: initial fitness class', [[2, 7, 5, 2, 5], [3, 2, 0], 14, 10], [671300, [2, 4, 5]]), ('partial-repair probe', [[5, 3, 3, 2, 5], [1, 3, 2], 22, 10], [100, [5]]), ('partial-repair probe', [[4, 1, 6, 6, 3, 1, 1, 3], [3, 2, 0], 18, 10], [773, [3, 6, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('control layout', [[2, 6, 7, 3, 1, 5, 5, 1], [1, 1, 1], 9, 1], ['infeasible'])], [('regression: initial fitness class', [[2, 6, 2, 3, 4, 3, 5], [1, 1, 0], 14, 10], [24300, [3, 6, 7]]), ('regression: initial fitness class', [[3, 6, 1, 7, 2], [1, 1, 0], 22, 10], [1700, [4, 5]]), ('partial-repair probe', [[1, 3, 7], [3, 2, 2], 11, 1], [647602, [2, 3]]), ('partial-repair probe', [[3, 7, 7, 6, 1, 6, 1], [2, 1, 2], 20, 1], [10, [3, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 6, 3, 3, 7, 7], [3, 3, 1], 12, 1], ['infeasible']), ('control layout', [[3, 7, 1, 4, 7, 4], [3, 2, 0], 11, 10], ['infeasible'])]]
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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    words, glue, width, lp = x
    sp, st, sh = glue
    n = len(words)
    def rate(i, j):
        gaps = j - i - 1
        nat = sum(words[i:j]) + sp * gaps
        short = width - nat
        if j == n and short >= 0:
            return 0, 1
        if short > 0:
            if st * gaps == 0:
                return None
            r = Fraction(short, st * gaps)
        elif short < 0:
            if -short > sh * gaps:
                return None
            r = Fraction(short, sh * gaps)
        else:
            r = Fraction(0)
        b = min(10000, math.floor(100 * abs(r) ** 3 + Fraction(1, 2)))
        if b > 1000:
            return None
        fit = 0 if r < Fraction(-1, 2) else 1 if r <= Fraction(1, 2) else 2 if r <= 1 else 3
        return b, fit
    best = {(0, 3): (0, [])}
    for j in range(1, n + 1):
        for i in range(j):
            rated = rate(i, j)
            if rated is None:
                continue
            b, fit = rated
            for (pos, pfit), (dem, brk) in sorted(best.items()):
                if pos != i:
                    continue
                d = dem + (lp + b) ** 2
                if abs(fit - pfit) > 1:
                    d += 3000
                key = (j, fit)
                if key not in best or d < best[key][0]:
                    best[key] = (d, brk + [j])
    finals = [v for (pos, f), v in best.items() if pos == n]
    if not finals:
        return ['infeasible']
    d, brk = min(finals)
    return [d, brk]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: initial fitness class', [[7, 6, 7, 4, 4, 2], [2, 1, 2], 16, 10], [17904, [2, 5, 6]]), ('regression: initial fitness class', [[4, 2, 3, 4], [2, 1, 0], 15, 10], [12200, [3, 4]]), ('partial-repair probe', [[2, 5, 1], [1, 1, 2], 12, 1], [1, [3]]), ('partial-repair probe', [[2, 3, 3], [1, 3, 1], 12, 10], [100, [3]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('control layout', [[4, 7, 7, 7, 3, 6, 6], [3, 2, 1], 15, 10], ['infeasible']), ('control layout', [[4, 3, 7, 7, 7], [1, 1, 1], 11, 10], ['infeasible'])], [('regression: initial fitness class', [[4, 1, 1, 6, 4], [3, 1, 0], 24, 10], [12200, [4, 5]]), ('regression: initial fitness class', [[3, 3, 4, 3, 2], [3, 3, 0], 12, 50], [31400, [2, 4, 5]]), ('partial-repair probe', [[1, 6, 7, 3, 5, 6, 7], [2, 1, 1], 18, 50], [7500, [3, 6, 7]]), ('partial-repair probe', [[2, 5, 1], [1, 1, 2], 12, 1], [1, [3]]), ('tight then loose lines', [[3, 3, 3, 3, 3, 3, 3], [2, 2, 1], 11, 1], [20403, [3, 6, 7]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[1, 4, 7, 1, 7, 3, 2, 4], [2, 1, 0], 14, 10], ['infeasible']), ('control layout', [[4, 6, 6, 4, 1, 5, 4], [2, 1, 0], 17, 50], ['infeasible'])], [('regression: initial fitness class', [[1, 5, 4, 4], [1, 2, 0], 15, 10], [2804, [3, 4]]), ('regression: initial fitness class', [[1, 3, 1, 3, 5, 5, 3, 3], [3, 2, 0], 23, 10], [24300, [4, 7, 8]]), ('partial-repair probe', [[6, 2, 2, 4], [3, 2, 2], 20, 10], [529, [4]]), ('partial-repair probe', [[6, 3, 6, 2, 1, 4, 3], [2, 2, 1], 20, 10], [244, [3, 7]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('control layout', [[6, 1, 6, 5, 5, 2, 6], [2, 2, 0], 16, 1], ['infeasible']), ('control layout', [[1, 7, 7, 7, 5, 1, 2, 4], [1, 2, 0], 14, 1], ['infeasible'])], [('regression: initial fitness class', [[3, 3, 4, 4], [3, 3, 2], 12, 10], [12200, [2, 4]]), ('regression: initial fitness class', [[2, 7, 5, 2, 5], [3, 2, 0], 14, 10], [671300, [2, 4, 5]]), ('partial-repair probe', [[5, 3, 3, 2, 5], [1, 3, 2], 22, 10], [100, [5]]), ('partial-repair probe', [[4, 1, 6, 6, 3, 1, 1, 3], [3, 2, 0], 18, 10], [773, [3, 6, 8]]), ('single word paragraph', [[7], [2, 2, 1], 10, 10], [100, [1]]), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[7, 4, 7, 2, 4, 2, 1], [2, 1, 0], 17, 10], ['infeasible']), ('control layout', [[2, 6, 7, 3, 1, 5, 5, 1], [1, 1, 1], 9, 1], ['infeasible'])], [('regression: initial fitness class', [[2, 6, 2, 3, 4, 3, 5], [1, 1, 0], 14, 10], [24300, [3, 6, 7]]), ('regression: initial fitness class', [[3, 6, 1, 7, 2], [1, 1, 0], 22, 10], [1700, [4, 5]]), ('partial-repair probe', [[1, 3, 7], [3, 2, 2], 11, 1], [647602, [2, 3]]), ('partial-repair probe', [[3, 7, 7, 6, 1, 6, 1], [2, 1, 2], 20, 1], [10, [3, 7]]), ('last line overfull', [[5, 5, 5], [1, 1, 0], 9, 10], ['infeasible']), ('two-line paragraph with loose first line', [[4, 5, 3, 6], [2, 2, 1], 14, 10], [12200, [3, 4]]), ('control layout', [[2, 6, 3, 3, 7, 7], [3, 3, 1], 12, 1], ['infeasible']), ('control layout', [[3, 7, 1, 4, 7, 4], [3, 2, 0], 11, 10], ['infeasible'])]]
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 first line pays adjacency demerits it should not.

Input [word widths, [space, stretch, shrink] per gap, line width, line penalty]. A line i..j has gaps=j-i-1. The last line has zero badness when not overfull. Other lines use ratio shortfall/(stretch*gaps) or /(shrink*gaps); zero stretch with slack or compression past shrink is infeasible; badness=min(10000, floor(100|r|^3+1/2)) and must be <=1000. Fitness 0 tight (r<-1/2), 1 decent (r<=1/2), 2 loose (r<=1), 3 very loose; last line decent. Demerits (lp+b)^2 plus 3000 when adjacent fitness classes differ by more than 1, starting from decent. Return [min total demerits, break list] (ties: first found) or ["infeasible"].

split: open-access