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

N = 1
observations = []
def solve(x):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] <= 10000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2]], 12], [[10, 'forced'], [13, 'glue'], [9, 'glue'], [9, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 14], [[12, 'glue'], [10, 'forced'], [13, 'penalty'], [4, 'end']]), ('regression: infinite penalty inhibition', [[['b', 5], ['p', 0, 9999, False], ['g', 1], ['g', 1], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2]], 11], [[5, 'penalty'], [7, 'glue'], [11, 'glue'], [6, 'glue'], [12, 'glue']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 6], ['g', 2]], 6], [[2, 'glue'], [7, 'penalty'], [2, 'glue'], [5, 'glue'], [4, 'forced'], [6, 'glue'], [6, 'glue']]), ('control layout', [[['b', 7], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['g', 2]], 15], [[11, 'glue'], [13, 'forced'], [3, 'end']])], [('regression: infinite penalty inhibition', [[['b', 6], ['g', 2], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 4], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 4], ['g', 1]], 16], [[15, 'penalty'], [12, 'glue'], [10, 'glue'], [16, 'glue']]), ('regression: infinite penalty inhibition', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['g', 2], ['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['g', 1], ['b', 2], ['g', 1]], 7], [[7, 'penalty'], [4, 'glue'], [6, 'glue'], [15, 'glue'], [7, 'glue'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 2], ['p', 0, 9999, False], ['g', 2], ['b', 5], ['g', 1], ['g', 1]], 7], [[5, 'glue'], [7, 'penalty'], [6, 'penalty'], [7, 'end']]), ('partial-repair probe', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 9999, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2]], 6], [[8, 'penalty'], [2, 'glue'], [6, 'glue'], [3, 'penalty'], [5, 'penalty'], [2, 'glue'], [6, 'glue']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 2], ['b', 7], ['p', 0, -5000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 2]], 17], [[9, 'glue'], [15, 'forced'], [14, 'glue'], [10, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 5], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['g', 2]], 10], [[4, 'glue'], [5, 'glue'], [7, 'glue'], [4, 'end']])], [('regression: infinite penalty inhibition', [[['b', 4], ['g', 2], ['b', 4], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2]], 18], [[15, 'forced'], [13, 'forced'], [14, 'penalty'], [5, 'end']]), ('regression: infinite penalty inhibition', [[['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 18], [[6, 'glue'], [14, 'glue'], [12, 'end']]), ('regression: infinite penalty inhibition', [[['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 2], ['b', 5], ['p', 0, 9999, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 5], ['g', 2]], 13], [[15, 'penalty'], [6, 'glue'], [9, 'glue'], [7, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 2]], 11], [[10, 'penalty'], [7, 'glue'], [7, 'penalty'], [7, 'glue'], [10, 'forced'], [8, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['g', 1], ['b', 4], ['g', 2], ['b', 3], ['g', 2]], 16], [[12, 'glue'], [14, 'glue'], [16, 'glue']]), ('control layout', [[['b', 3], ['g', 1], ['b', 2], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 2]], 6], [[6, 'glue'], [4, 'glue'], [6, 'glue'], [5, 'end']])], [('regression: infinite penalty inhibition', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1]], 12], [[10, 'glue'], [8, 'penalty'], [6, 'forced']]), ('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2]], 18], [[11, 'penalty'], [12, 'end']]), ('partial-repair probe', [[['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['g', 1], ['b', 2], ['g', 2]], 6], [[7, 'penalty'], [5, 'penalty'], [3, 'penalty'], [7, 'glue'], [3, 'penalty'], [6, 'glue'], [4, 'glue'], [4, 'end']]), ('partial-repair probe', [[['b', 1], ['g', 1], ['b', 2], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 3], ['p', 0, 900, False], ['g', 1], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['p', 0, 9999, False], ['g', 1]], 17], [[7, 'forced'], [11, 'forced'], [10, 'penalty'], [8, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 2]], 18], [[16, 'glue'], [11, 'end']]), ('control layout', [[['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 2]], 6], [[7, 'forced'], [3, 'glue'], [7, 'penalty'], [6, 'penalty']])], [('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 4], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 2]], 8], [[4, 'glue'], [8, 'glue'], [4, 'glue'], [9, 'glue'], [6, 'glue'], [5, 'end']]), ('regression: infinite penalty inhibition', [[['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 2], ['p', 0, 10000, False], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 1]], 9], [[6, 'penalty'], [6, 'glue'], [7, 'glue'], [7, 'penalty'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 14], [[12, 'glue'], [10, 'forced'], [13, 'penalty'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['p', 0, 9999, False], ['g', 2], ['b', 1], ['g', 1], ['b', 4], ['g', 1], ['g', 1]], 6], [[3, 'glue'], [2, 'forced'], [1, 'glue'], [6, 'glue'], [4, 'forced'], [5, 'penalty'], [6, 'glue']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 4], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 3], ['g', 1], ['b', 1], ['g', 1], ['b', 7], ['g', 1], ['g', 1]], 14], [[12, 'glue'], [9, 'glue'], [7, 'forced'], [10, 'glue'], [9, 'end']]), ('control layout', [[['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 1], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1]], 12], [[10, 'glue'], [10, 'glue'], [6, 'glue'], [12, 'glue'], [9, 'forced']])]]
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):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 1000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2]], 12], [[10, 'forced'], [13, 'glue'], [9, 'glue'], [9, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 14], [[12, 'glue'], [10, 'forced'], [13, 'penalty'], [4, 'end']]), ('regression: infinite penalty inhibition', [[['b', 5], ['p', 0, 9999, False], ['g', 1], ['g', 1], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2]], 11], [[5, 'penalty'], [7, 'glue'], [11, 'glue'], [6, 'glue'], [12, 'glue']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 6], ['g', 2]], 6], [[2, 'glue'], [7, 'penalty'], [2, 'glue'], [5, 'glue'], [4, 'forced'], [6, 'glue'], [6, 'glue']]), ('control layout', [[['b', 7], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['g', 2]], 15], [[11, 'glue'], [13, 'forced'], [3, 'end']])], [('regression: infinite penalty inhibition', [[['b', 6], ['g', 2], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 4], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 4], ['g', 1]], 16], [[15, 'penalty'], [12, 'glue'], [10, 'glue'], [16, 'glue']]), ('regression: infinite penalty inhibition', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['g', 2], ['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['g', 1], ['b', 2], ['g', 1]], 7], [[7, 'penalty'], [4, 'glue'], [6, 'glue'], [15, 'glue'], [7, 'glue'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 2], ['p', 0, 9999, False], ['g', 2], ['b', 5], ['g', 1], ['g', 1]], 7], [[5, 'glue'], [7, 'penalty'], [6, 'penalty'], [7, 'end']]), ('partial-repair probe', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 9999, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2]], 6], [[8, 'penalty'], [2, 'glue'], [6, 'glue'], [3, 'penalty'], [5, 'penalty'], [2, 'glue'], [6, 'glue']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 2], ['b', 7], ['p', 0, -5000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 2]], 17], [[9, 'glue'], [15, 'forced'], [14, 'glue'], [10, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 5], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['g', 2]], 10], [[4, 'glue'], [5, 'glue'], [7, 'glue'], [4, 'end']])], [('regression: infinite penalty inhibition', [[['b', 4], ['g', 2], ['b', 4], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2]], 18], [[15, 'forced'], [13, 'forced'], [14, 'penalty'], [5, 'end']]), ('regression: infinite penalty inhibition', [[['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 18], [[6, 'glue'], [14, 'glue'], [12, 'end']]), ('regression: infinite penalty inhibition', [[['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 2], ['b', 5], ['p', 0, 9999, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 5], ['g', 2]], 13], [[15, 'penalty'], [6, 'glue'], [9, 'glue'], [7, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 2]], 11], [[10, 'penalty'], [7, 'glue'], [7, 'penalty'], [7, 'glue'], [10, 'forced'], [8, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['g', 1], ['b', 4], ['g', 2], ['b', 3], ['g', 2]], 16], [[12, 'glue'], [14, 'glue'], [16, 'glue']]), ('control layout', [[['b', 3], ['g', 1], ['b', 2], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 2]], 6], [[6, 'glue'], [4, 'glue'], [6, 'glue'], [5, 'end']])], [('regression: infinite penalty inhibition', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 2], ['g', 2], ['b', 2], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 1]], 12], [[10, 'glue'], [8, 'penalty'], [6, 'forced']]), ('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2]], 18], [[11, 'penalty'], [12, 'end']]), ('partial-repair probe', [[['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['g', 1], ['b', 2], ['g', 2]], 6], [[7, 'penalty'], [5, 'penalty'], [3, 'penalty'], [7, 'glue'], [3, 'penalty'], [6, 'glue'], [4, 'glue'], [4, 'end']]), ('partial-repair probe', [[['b', 1], ['g', 1], ['b', 2], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 3], ['p', 0, 900, False], ['g', 1], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['p', 0, 9999, False], ['g', 1]], 17], [[7, 'forced'], [11, 'forced'], [10, 'penalty'], [8, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 2]], 18], [[16, 'glue'], [11, 'end']]), ('control layout', [[['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 2]], 6], [[7, 'forced'], [3, 'glue'], [7, 'penalty'], [6, 'penalty']])], [('regression: infinite penalty inhibition', [[['b', 4], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 4], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 2]], 8], [[4, 'glue'], [8, 'glue'], [4, 'glue'], [9, 'glue'], [6, 'glue'], [5, 'end']]), ('regression: infinite penalty inhibition', [[['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 2], ['p', 0, 10000, False], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 1]], 9], [[6, 'penalty'], [6, 'glue'], [7, 'glue'], [7, 'penalty'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 14], [[12, 'glue'], [10, 'forced'], [13, 'penalty'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['p', 0, 9999, False], ['g', 2], ['b', 1], ['g', 1], ['b', 4], ['g', 1], ['g', 1]], 6], [[3, 'glue'], [2, 'forced'], [1, 'glue'], [6, 'glue'], [4, 'forced'], [5, 'penalty'], [6, 'glue']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 4], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 3], ['g', 1], ['b', 1], ['g', 1], ['b', 7], ['g', 1], ['g', 1]], 14], [[12, 'glue'], [9, 'glue'], [7, 'forced'], [10, 'glue'], [9, 'end']]), ('control layout', [[['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 1], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1]], 12], [[10, 'glue'], [10, 'glue'], [6, 'glue'], [12, 'glue'], [9, 'forced']])]]
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 break at penalties meant to forbid breaking.

Input [items, width]; items are ["b",w], ["g",w] or ["p",w,cost,flag]. Legal breaks: glue immediately after a box; penalty with cost < 10000 (width counted only if broken there); cost <= -10000 forces a break. Discardable glue/penalties at a line start are dropped. First-fit: when the running width exceeds the measure, break at the last legal breakpoint. Return [[line width, break kind]] with kinds glue/penalty/forced/end.

split: open-access


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

N = 1
observations = []
def solve(x):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] < -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('regression: forced break threshold', [[['b', 2], ['g', 2], ['b', 2], ['g', 2], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 1], ['b', 5], ['p', 0, 900, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 1], ['g', 1]], 17], [[10, 'glue'], [11, 'glue'], [15, 'forced'], [6, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['p', 0, -5000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['g', 1]], 11], [[7, 'glue'], [8, 'penalty'], [4, 'glue'], [10, 'glue'], [9, 'end']]), ('regression: forced break threshold', [[['b', 3], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['p', 0, -5000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['p', 0, 9999, False], ['g', 1], ['b', 2], ['g', 2]], 18], [[12, 'forced'], [12, 'glue'], [11, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['p', 0, 9999, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1]], 8], [[2, 'glue'], [6, 'glue'], [4, 'penalty'], [5, 'penalty'], [5, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 8], [[3, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'end']])], [('regression: forced break threshold', [[['b', 1], ['p', 0, -5000, False], ['g', 2], ['b', 6], ['g', 2], ['b', 7], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 10], [[9, 'glue'], [9, 'forced'], [5, 'penalty'], [7, 'glue'], [5, 'glue'], [6, 'glue'], [4, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1]], 11], [[11, 'glue'], [2, 'forced'], [10, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['p', 0, -5000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['g', 1]], 11], [[7, 'glue'], [8, 'penalty'], [4, 'glue'], [10, 'glue'], [9, 'end']]), ('partial-repair probe', [[['b', 4], ['g', 2], ['b', 3], ['g', 2], ['b', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -5000, False], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['g', 2], ['b', 5], ['g', 2]], 15], [[12, 'glue'], [14, 'penalty'], [10, 'glue'], [7, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 18], [[6, 'glue'], [14, 'glue'], [12, 'end']]), ('control layout', [[['b', 7], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1]], 16], [[17, 'penalty'], [5, 'end']])], [('regression: forced break threshold', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 16], [[13, 'glue'], [15, 'glue'], [12, 'forced'], [6, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 7], ['g', 2]], 18], [[12, 'forced'], [17, 'end']]), ('partial-repair probe', [[['b', 1], ['p', 0, -5000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 1], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 2], ['g', 1]], 6], [[1, 'penalty'], [7, 'glue'], [1, 'glue'], [7, 'penalty'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['g', 1], ['b', 5], ['g', 1], ['b', 4], ['g', 2], ['b', 3], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['p', 0, -5000, False], ['g', 2], ['b', 7], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 2]], 6], [[5, 'glue'], [5, 'glue'], [4, 'glue'], [3, 'glue'], [6, 'glue'], [6, 'glue'], [2, 'penalty'], [7, 'glue'], [7, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['b', 4], ['g', 2], ['b', 7], ['g', 2], ['b', 2], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['g', 1]], 15], [[16, 'penalty'], [10, 'glue'], [14, 'glue'], [4, 'end']]), ('control layout', [[['b', 3], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 2]], 14], [[12, 'penalty'], [6, 'glue'], [9, 'glue'], [8, 'end']])], [('regression: forced break threshold', [[['b', 7], ['p', 0, -10000, False], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 2], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 2]], 16], [[7, 'forced'], [15, 'glue'], [10, 'end']]), ('regression: forced break threshold', [[['b', 6], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 7], ['p', 0, 9999, False], ['g', 2]], 7], [[6, 'glue'], [7, 'forced'], [3, 'glue'], [7, 'penalty']]), ('regression: forced break threshold', [[['b', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 4], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 2], ['b', 1], ['g', 1], ['b', 4], ['p', 0, 9999, False], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2]], 7], [[7, 'glue'], [4, 'glue'], [6, 'glue'], [1, 'forced'], [7, 'glue'], [4, 'penalty'], [6, 'penalty'], [5, 'end']]), ('partial-repair probe', [[['b', 2], ['p', 0, -5000, False], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 5], ['g', 2]], 7], [[7, 'penalty'], [5, 'glue'], [7, 'penalty'], [7, 'glue'], [4, 'glue'], [7, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 1], ['b', 3], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 2], ['g', 2]], 12], [[12, 'glue'], [9, 'glue'], [12, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 2], ['b', 5], ['g', 2], ['b', 5], ['g', 1], ['b', 3], ['p', 0, 900, False], ['g', 2], ['b', 2], ['g', 2], ['b', 5], ['g', 2]], 8], [[6, 'glue'], [8, 'glue'], [5, 'glue'], [5, 'glue'], [7, 'glue'], [7, 'end']])], [('regression: forced break threshold', [[['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 1]], 15], [[15, 'glue'], [5, 'forced'], [8, 'glue'], [13, 'glue'], [4, 'end']]), ('regression: forced break threshold', [[['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'penalty'], [8, 'glue'], [8, 'glue'], [7, 'penalty'], [9, 'penalty'], [6, 'forced'], [2, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 0, -5000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 1]], 12], [[9, 'forced'], [7, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 6], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 2]], 6], [[2, 'glue'], [6, 'glue'], [4, 'glue'], [6, 'glue'], [5, 'penalty'], [4, 'penalty'], [6, 'glue'], [5, 'glue'], [6, 'penalty']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 1], ['g', 1]], 16], [[13, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 2]], 18], [[16, 'penalty'], [14, 'glue'], [17, 'end']])]]
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):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -1000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('regression: forced break threshold', [[['b', 2], ['g', 2], ['b', 2], ['g', 2], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 1], ['b', 5], ['p', 0, 900, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 1], ['g', 1]], 17], [[10, 'glue'], [11, 'glue'], [15, 'forced'], [6, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['p', 0, -5000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['g', 1]], 11], [[7, 'glue'], [8, 'penalty'], [4, 'glue'], [10, 'glue'], [9, 'end']]), ('regression: forced break threshold', [[['b', 3], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['p', 0, -5000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['p', 0, 9999, False], ['g', 1], ['b', 2], ['g', 2]], 18], [[12, 'forced'], [12, 'glue'], [11, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['p', 0, 9999, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1]], 8], [[2, 'glue'], [6, 'glue'], [4, 'penalty'], [5, 'penalty'], [5, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 8], [[3, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'end']])], [('regression: forced break threshold', [[['b', 1], ['p', 0, -5000, False], ['g', 2], ['b', 6], ['g', 2], ['b', 7], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1]], 10], [[9, 'glue'], [9, 'forced'], [5, 'penalty'], [7, 'glue'], [5, 'glue'], [6, 'glue'], [4, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1]], 11], [[11, 'glue'], [2, 'forced'], [10, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['p', 0, -5000, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 3], ['g', 1]], 11], [[7, 'glue'], [8, 'penalty'], [4, 'glue'], [10, 'glue'], [9, 'end']]), ('partial-repair probe', [[['b', 4], ['g', 2], ['b', 3], ['g', 2], ['b', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -5000, False], ['g', 1], ['b', 2], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['g', 2], ['b', 5], ['g', 2]], 15], [[12, 'glue'], [14, 'penalty'], [10, 'glue'], [7, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 6], ['g', 2], ['b', 7], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 18], [[6, 'glue'], [14, 'glue'], [12, 'end']]), ('control layout', [[['b', 7], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1]], 16], [[17, 'penalty'], [5, 'end']])], [('regression: forced break threshold', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 16], [[13, 'glue'], [15, 'glue'], [12, 'forced'], [6, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 7], ['g', 2]], 18], [[12, 'forced'], [17, 'end']]), ('partial-repair probe', [[['b', 1], ['p', 0, -5000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 1], ['g', 2], ['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 2], ['g', 1]], 6], [[1, 'penalty'], [7, 'glue'], [1, 'glue'], [7, 'penalty'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['g', 1], ['b', 5], ['g', 1], ['b', 4], ['g', 2], ['b', 3], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['p', 0, -5000, False], ['g', 2], ['b', 7], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 2]], 6], [[5, 'glue'], [5, 'glue'], [4, 'glue'], [3, 'glue'], [6, 'glue'], [6, 'glue'], [2, 'penalty'], [7, 'glue'], [7, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['b', 4], ['g', 2], ['b', 7], ['g', 2], ['b', 2], ['g', 2], ['b', 1], ['g', 1], ['b', 3], ['g', 1]], 15], [[16, 'penalty'], [10, 'glue'], [14, 'glue'], [4, 'end']]), ('control layout', [[['b', 3], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 2]], 14], [[12, 'penalty'], [6, 'glue'], [9, 'glue'], [8, 'end']])], [('regression: forced break threshold', [[['b', 7], ['p', 0, -10000, False], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 2], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 2]], 16], [[7, 'forced'], [15, 'glue'], [10, 'end']]), ('regression: forced break threshold', [[['b', 6], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 7], ['p', 0, 9999, False], ['g', 2]], 7], [[6, 'glue'], [7, 'forced'], [3, 'glue'], [7, 'penalty']]), ('regression: forced break threshold', [[['b', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 4], ['g', 1], ['b', 6], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['g', 2], ['b', 1], ['g', 1], ['b', 4], ['p', 0, 9999, False], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 2]], 7], [[7, 'glue'], [4, 'glue'], [6, 'glue'], [1, 'forced'], [7, 'glue'], [4, 'penalty'], [6, 'penalty'], [5, 'end']]), ('partial-repair probe', [[['b', 2], ['p', 0, -5000, False], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 5], ['g', 2]], 7], [[7, 'penalty'], [5, 'glue'], [7, 'penalty'], [7, 'glue'], [4, 'glue'], [7, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 1], ['b', 3], ['g', 1], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 2], ['g', 2]], 12], [[12, 'glue'], [9, 'glue'], [12, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 2], ['b', 5], ['g', 2], ['b', 5], ['g', 1], ['b', 3], ['p', 0, 900, False], ['g', 2], ['b', 2], ['g', 2], ['b', 5], ['g', 2]], 8], [[6, 'glue'], [8, 'glue'], [5, 'glue'], [5, 'glue'], [7, 'glue'], [7, 'end']])], [('regression: forced break threshold', [[['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 1], ['b', 3], ['g', 1]], 15], [[15, 'glue'], [5, 'forced'], [8, 'glue'], [13, 'glue'], [4, 'end']]), ('regression: forced break threshold', [[['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'penalty'], [8, 'glue'], [8, 'glue'], [7, 'penalty'], [9, 'penalty'], [6, 'forced'], [2, 'end']]), ('regression: forced break threshold', [[['b', 6], ['p', 0, -5000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 1]], 12], [[9, 'forced'], [7, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 6], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 0, -5000, False], ['g', 2]], 6], [[2, 'glue'], [6, 'glue'], [4, 'glue'], [6, 'glue'], [5, 'penalty'], [4, 'penalty'], [6, 'glue'], [5, 'glue'], [6, 'penalty']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 1], ['g', 1]], 16], [[13, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 2]], 18], [[16, 'penalty'], [14, 'glue'], [17, 'end']])]]
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:
Explicit forced breaks are ignored.

Input [items, width]; items are ["b",w], ["g",w] or ["p",w,cost,flag]. Legal breaks: glue immediately after a box; penalty with cost < 10000 (width counted only if broken there); cost <= -10000 forces a break. Discardable glue/penalties at a line start are dropped. First-fit: when the running width exceeds the measure, break at the last legal breakpoint. Return [[line width, break kind]] with kinds glue/penalty/forced/end.

split: open-access


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

N = 1
observations = []
def solve(x):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total, 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2]], 18], [[12, 'glue'], [18, 'penalty']]), ('regression: penalty width accounting', [[['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['g', 2], ['b', 5], ['g', 2]], 11], [[12, 'penalty'], [1, 'forced'], [9, 'penalty'], [6, 'glue'], [5, 'glue'], [7, 'end']]), ('regression: penalty width accounting', [[['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 7], ['p', 0, -5000, False], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1]], 7], [[5, 'penalty'], [7, 'glue'], [3, 'glue'], [7, 'penalty'], [3, 'forced'], [6, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 2], ['b', 2], ['g', 2], ['b', 7], ['g', 1], ['b', 3], ['p', 0, 10000, False], ['g', 1]], 11], [[7, 'forced'], [5, 'glue'], [7, 'glue'], [4, 'end']]), ('control layout', [[['b', 7], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['g', 1], ['b', 2], ['g', 1]], 15], [[15, 'glue'], [15, 'glue'], [15, 'glue']])], [('regression: penalty width accounting', [[['b', 1], ['g', 2], ['b', 4], ['g', 1], ['b', 5], ['p', 0, -5000, False], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 4], ['p', 0, 9999, False], ['g', 1], ['g', 1]], 7], [[7, 'glue'], [5, 'penalty'], [6, 'penalty'], [6, 'end']]), ('regression: penalty width accounting', [[['b', 5], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 9], [[9, 'penalty'], [5, 'forced'], [8, 'glue'], [8, 'glue']]), ('regression: penalty width accounting', [[['b', 7], ['g', 2], ['b', 4], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 6], ['g', 1]], 17], [[18, 'penalty'], [15, 'forced'], [7, 'end']]), ('regression: penalty width accounting', [[['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1]], 7], [[4, 'glue'], [8, 'penalty'], [6, 'glue'], [7, 'glue']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, -10000, False], ['g', 2]], 15], [[12, 'glue'], [13, 'glue'], [6, 'forced']]), ('control layout', [[['b', 1], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 2]], 11], [[6, 'glue'], [7, 'glue'], [9, 'glue'], [6, 'forced']])], [('regression: penalty width accounting', [[['b', 2], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 6], [[2, 'glue'], [6, 'glue'], [7, 'penalty'], [4, 'penalty'], [8, 'penalty'], [2, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 1]], 12], [[12, 'penalty'], [12, 'glue'], [8, 'end']]), ('regression: penalty width accounting', [[['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'penalty'], [8, 'glue'], [8, 'glue'], [7, 'penalty'], [9, 'penalty'], [6, 'forced'], [2, 'end']]), ('partial-repair probe', [[['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 2], ['b', 5], ['g', 2]], 18], [[2, 'forced'], [16, 'forced'], [11, 'forced'], [18, 'glue']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 8], [[3, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'end']]), ('control layout', [[['b', 1], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 1]], 13], [[10, 'forced'], [11, 'penalty'], [13, 'glue'], [7, 'glue'], [6, 'end']])], [('regression: penalty width accounting', [[['b', 2], ['g', 1], ['b', 4], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 2], ['b', 6], ['g', 1]], 16], [[11, 'penalty'], [14, 'glue'], [16, 'end']]), ('regression: penalty width accounting', [[['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['g', 1], ['b', 6], ['g', 1], ['b', 7], ['g', 2]], 10], [[6, 'glue'], [4, 'glue'], [7, 'penalty'], [8, 'penalty'], [8, 'penalty'], [7, 'glue'], [6, 'glue'], [9, 'end']]), ('regression: penalty width accounting', [[['b', 1], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1]], 7], [[1, 'glue'], [7, 'glue'], [6, 'penalty'], [3, 'penalty'], [8, 'penalty'], [5, 'end']]), ('partial-repair probe', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 16], [[13, 'glue'], [15, 'glue'], [12, 'forced'], [6, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 2], ['g', 1]], 7], [[6, 'forced'], [1, 'forced'], [6, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 6], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1]], 14], [[12, 'glue'], [10, 'end']])], [('regression: penalty width accounting', [[['b', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['g', 2]], 9], [[10, 'penalty'], [9, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 6], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 6], ['p', 0, 9999, False], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1]], 11], [[7, 'penalty'], [10, 'penalty'], [6, 'glue'], [9, 'glue'], [8, 'penalty'], [6, 'penalty'], [6, 'end']]), ('partial-repair probe', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['g', 1]], 16], [[14, 'forced'], [15, 'glue']]), ('regression: penalty width accounting', [[['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1]], 15], [[9, 'penalty'], [7, 'forced'], [1, 'forced'], [5, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 5], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 7], ['p', 0, 900, False], ['g', 1], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['b', 6], ['g', 1], ['b', 4], ['g', 2]], 14], [[12, 'glue'], [14, 'glue'], [14, 'glue'], [6, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['g', 1], ['b', 2], ['g', 2], ['b', 6], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 3], ['g', 1]], 16], [[16, 'glue'], [11, 'end']])]]
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):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] != 'b':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total + it[1], 'penalty')
                    total += it[1]
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2]], 18], [[12, 'glue'], [18, 'penalty']]), ('regression: penalty width accounting', [[['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['g', 2], ['b', 5], ['g', 2]], 11], [[12, 'penalty'], [1, 'forced'], [9, 'penalty'], [6, 'glue'], [5, 'glue'], [7, 'end']]), ('regression: penalty width accounting', [[['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 7], ['p', 0, -5000, False], ['g', 2], ['b', 3], ['p', 0, -10000, False], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1]], 7], [[5, 'penalty'], [7, 'glue'], [3, 'glue'], [7, 'penalty'], [3, 'forced'], [6, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['g', 2], ['b', 2], ['g', 2], ['b', 7], ['g', 1], ['b', 3], ['p', 0, 10000, False], ['g', 1]], 11], [[7, 'forced'], [5, 'glue'], [7, 'glue'], [4, 'end']]), ('control layout', [[['b', 7], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['g', 1], ['b', 2], ['g', 1]], 15], [[15, 'glue'], [15, 'glue'], [15, 'glue']])], [('regression: penalty width accounting', [[['b', 1], ['g', 2], ['b', 4], ['g', 1], ['b', 5], ['p', 0, -5000, False], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 4], ['p', 0, 9999, False], ['g', 1], ['g', 1]], 7], [[7, 'glue'], [5, 'penalty'], [6, 'penalty'], [6, 'end']]), ('regression: penalty width accounting', [[['b', 5], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 9], [[9, 'penalty'], [5, 'forced'], [8, 'glue'], [8, 'glue']]), ('regression: penalty width accounting', [[['b', 7], ['g', 2], ['b', 4], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['b', 6], ['g', 1]], 17], [[18, 'penalty'], [15, 'forced'], [7, 'end']]), ('regression: penalty width accounting', [[['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['p', 0, 10000, False], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 1]], 7], [[4, 'glue'], [8, 'penalty'], [6, 'glue'], [7, 'glue']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['b', 2], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['p', 0, -10000, False], ['g', 2]], 15], [[12, 'glue'], [13, 'glue'], [6, 'forced']]), ('control layout', [[['b', 1], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 2]], 11], [[6, 'glue'], [7, 'glue'], [9, 'glue'], [6, 'forced']])], [('regression: penalty width accounting', [[['b', 2], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 6], [[2, 'glue'], [6, 'glue'], [7, 'penalty'], [4, 'penalty'], [8, 'penalty'], [2, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 1]], 12], [[12, 'penalty'], [12, 'glue'], [8, 'end']]), ('regression: penalty width accounting', [[['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['g', 2], ['b', 5], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'penalty'], [8, 'glue'], [8, 'glue'], [7, 'penalty'], [9, 'penalty'], [6, 'forced'], [2, 'end']]), ('partial-repair probe', [[['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 5], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 2], ['b', 5], ['g', 2]], 18], [[2, 'forced'], [16, 'forced'], [11, 'forced'], [18, 'glue']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 8], [[3, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'end']]), ('control layout', [[['b', 1], ['g', 2], ['b', 7], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -5000, False], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 1]], 13], [[10, 'forced'], [11, 'penalty'], [13, 'glue'], [7, 'glue'], [6, 'end']])], [('regression: penalty width accounting', [[['b', 2], ['g', 1], ['b', 4], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 6], ['g', 1], ['b', 7], ['g', 2], ['b', 6], ['g', 1]], 16], [[11, 'penalty'], [14, 'glue'], [16, 'end']]), ('regression: penalty width accounting', [[['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 4], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 0, 9999, False], ['g', 2], ['b', 7], ['g', 1], ['b', 6], ['g', 1], ['b', 7], ['g', 2]], 10], [[6, 'glue'], [4, 'glue'], [7, 'penalty'], [8, 'penalty'], [8, 'penalty'], [7, 'glue'], [6, 'glue'], [9, 'end']]), ('regression: penalty width accounting', [[['b', 1], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1]], 7], [[1, 'glue'], [7, 'glue'], [6, 'penalty'], [3, 'penalty'], [8, 'penalty'], [5, 'end']]), ('partial-repair probe', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2]], 16], [[13, 'glue'], [15, 'glue'], [12, 'forced'], [6, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('control layout', [[['b', 6], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['g', 1], ['g', 1], ['b', 2], ['g', 1]], 7], [[6, 'forced'], [1, 'forced'], [6, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 6], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1]], 14], [[12, 'glue'], [10, 'end']])], [('regression: penalty width accounting', [[['b', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 1], ['p', 0, 10000, False], ['g', 2]], 9], [[10, 'penalty'], [9, 'end']]), ('regression: penalty width accounting', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 6], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 6], ['p', 0, 9999, False], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1]], 11], [[7, 'penalty'], [10, 'penalty'], [6, 'glue'], [9, 'glue'], [8, 'penalty'], [6, 'penalty'], [6, 'end']]), ('partial-repair probe', [[['b', 6], ['p', 1, 50, True], ['g', 2], ['b', 6], ['p', 0, -10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['g', 1]], 16], [[14, 'forced'], [15, 'glue']]), ('regression: penalty width accounting', [[['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1]], 15], [[9, 'penalty'], [7, 'forced'], [1, 'forced'], [5, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 5], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 7], ['p', 0, 900, False], ['g', 1], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['b', 6], ['g', 1], ['b', 4], ['g', 2]], 14], [[12, 'glue'], [14, 'glue'], [14, 'glue'], [6, 'end']]), ('control layout', [[['b', 2], ['g', 1], ['g', 1], ['b', 2], ['g', 2], ['b', 6], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 3], ['g', 1]], 16], [[16, 'glue'], [11, 'end']])]]
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 are reported one hyphen narrower.

Input [items, width]; items are ["b",w], ["g",w] or ["p",w,cost,flag]. Legal breaks: glue immediately after a box; penalty with cost < 10000 (width counted only if broken there); cost <= -10000 forces a break. Discardable glue/penalties at a line start are dropped. First-fit: when the running width exceeds the measure, break at the last legal breakpoint. Return [[line width, break kind]] with kinds glue/penalty/forced/end.

split: open-access


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

N = 1
observations = []
def solve(x):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] == 'g':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: discardable items at line start', [[['b', 7], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 1], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 6], [[7, 'glue'], [7, 'forced'], [5, 'glue'], [2, 'glue'], [7, 'glue'], [7, 'glue'], [8, 'penalty'], [6, 'glue'], [3, 'glue'], [5, 'end']]), ('regression: discardable items at line start', [[['b', 7], ['g', 2], ['b', 7], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1]], 10], [[7, 'glue'], [7, 'glue'], [13, 'penalty']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 6], [[2, 'glue'], [6, 'glue'], [7, 'penalty'], [4, 'penalty'], [8, 'penalty'], [2, 'end']]), ('partial-repair probe', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 5], ['g', 1], ['b', 2], ['p', 0, 900, False], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 1]], 6], [[6, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'glue'], [2, 'penalty'], [6, 'glue'], [6, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 1], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['g', 2]], 15], [[14, 'glue'], [7, 'glue'], [9, 'glue'], [8, 'end']]), ('control layout', [[['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 7], ['g', 2]], 7], [[7, 'glue'], [7, 'glue'], [7, 'glue']])], [('regression: discardable items at line start', [[['b', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 2], ['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 1]], 6], [[1, 'glue'], [7, 'glue'], [3, 'glue'], [7, 'glue'], [2, 'forced'], [8, 'penalty'], [6, 'glue'], [6, 'end']]), ('regression: discardable items at line start', [[['b', 4], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 1]], 18], [[9, 'forced'], [13, 'penalty'], [14, 'glue'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['g', 1]], 13], [[13, 'glue'], [6, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 0, -10000, False], ['g', 2], ['b', 7], ['p', 1, 50, True], ['g', 1], ['g', 1]], 17], [[9, 'forced'], [9, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['b', 2], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2]], 16], [[13, 'glue'], [14, 'glue'], [7, 'end']]), ('control layout', [[['b', 6], ['g', 1], ['b', 7], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 2]], 6], [[6, 'glue'], [7, 'glue'], [6, 'glue'], [3, 'glue'], [5, 'end']])], [('regression: discardable items at line start', [[['b', 7], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, 900, False], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1]], 9], [[10, 'penalty'], [3, 'glue'], [7, 'forced'], [6, 'penalty'], [7, 'glue'], [4, 'end']]), ('regression: discardable items at line start', [[['b', 1], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 7], ['g', 1], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 2]], 12], [[5, 'glue'], [7, 'glue'], [7, 'glue'], [10, 'forced'], [5, 'end']]), ('partial-repair probe', [[['b', 4], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2]], 16], [[10, 'forced'], [8, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 6], [[7, 'glue'], [3, 'glue'], [3, 'glue'], [8, 'penalty'], [7, 'glue'], [5, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 1], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['b', 4], ['g', 2]], 15], [[15, 'end']]), ('control layout', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1]], 17], [[13, 'glue'], [14, 'glue'], [5, 'end']])], [('regression: discardable items at line start', [[['b', 4], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 7], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1], ['b', 5], ['g', 1]], 6], [[4, 'glue'], [5, 'glue'], [12, 'penalty'], [7, 'glue'], [1, 'glue'], [8, 'penalty'], [4, 'glue'], [6, 'end']]), ('regression: discardable items at line start', [[['b', 3], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'glue'], [4, 'forced'], [6, 'glue'], [6, 'glue'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['b', 2], ['g', 2], ['b', 7], ['g', 1], ['g', 1]], 17], [[13, 'glue'], [17, 'glue']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 4], ['p', 0, 900, False], ['g', 2], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['g', 1]], 8], [[7, 'penalty'], [6, 'glue'], [8, 'glue'], [8, 'glue'], [8, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 5], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 2]], 15], [[14, 'glue'], [5, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1]], 15], [[15, 'end']])], [('regression: discardable items at line start', [[['b', 4], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1]], 14], [[11, 'glue'], [6, 'forced'], [14, 'end']]), ('regression: discardable items at line start', [[['b', 7], ['g', 2], ['b', 7], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1]], 10], [[7, 'glue'], [7, 'glue'], [13, 'penalty']]), ('partial-repair probe', [[['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 6], ['p', 0, 9999, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1]], 6], [[1, 'forced'], [7, 'penalty'], [6, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 1], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2]], 12], [[13, 'penalty'], [10, 'glue'], [12, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 6], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1]], 14], [[12, 'glue'], [10, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 7], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['g', 2], ['b', 4], ['g', 2], ['b', 2], ['g', 1], ['b', 4], ['g', 1]], 10], [[4, 'glue'], [7, 'glue'], [7, 'glue'], [6, 'glue'], [8, 'glue'], [5, 'end']])]]
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):
    items, width = x
    lines = []
    start = 0
    n = len(items)
    while start < n:
        while start < n and items[start][0] == 'p':
            start += 1
        if start >= n:
            break
        total = 0
        last = None
        result = None
        i = start
        while i < n:
            it = items[i]
            if it[0] == 'p':
                if it[2] <= -10000:
                    result = (i, total + it[1], 'forced')
                    break
                if it[2] < 10000:
                    last = (i, total + it[1], 'penalty')
            elif it[0] == 'g':
                if items[i - 1][0] == 'b':
                    last = (i, total, 'glue')
                total += it[1]
            else:
                total += it[1]
            if total > width and last is not None:
                result = last
                break
            i += 1
        if result is None:
            lines.append([total, 'end'])
            break
        lines.append([result[1], result[2]])
        start = result[0] + 1
    return lines
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: discardable items at line start', [[['b', 7], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 1], ['b', 2], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 1], ['g', 1]], 6], [[7, 'glue'], [7, 'forced'], [5, 'glue'], [2, 'glue'], [7, 'glue'], [7, 'glue'], [8, 'penalty'], [6, 'glue'], [3, 'glue'], [5, 'end']]), ('regression: discardable items at line start', [[['b', 7], ['g', 2], ['b', 7], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1]], 10], [[7, 'glue'], [7, 'glue'], [13, 'penalty']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 6], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 1]], 6], [[2, 'glue'], [6, 'glue'], [7, 'penalty'], [4, 'penalty'], [8, 'penalty'], [2, 'end']]), ('partial-repair probe', [[['b', 6], ['g', 1], ['b', 6], ['g', 2], ['b', 2], ['g', 1], ['b', 3], ['g', 1], ['b', 5], ['g', 1], ['b', 2], ['p', 0, 900, False], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['g', 2], ['b', 1], ['p', 0, 10000, False], ['g', 1]], 6], [[6, 'glue'], [6, 'glue'], [6, 'glue'], [5, 'glue'], [2, 'penalty'], [6, 'glue'], [6, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 1], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 2], ['b', 7], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['g', 1], ['b', 3], ['g', 2], ['b', 6], ['g', 2]], 15], [[14, 'glue'], [7, 'glue'], [9, 'glue'], [8, 'end']]), ('control layout', [[['b', 2], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 4], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 2], ['g', 2], ['b', 7], ['g', 2]], 7], [[7, 'glue'], [7, 'glue'], [7, 'glue']])], [('regression: discardable items at line start', [[['b', 1], ['g', 1], ['b', 7], ['g', 2], ['b', 3], ['g', 1], ['b', 7], ['g', 2], ['b', 2], ['p', 0, -10000, False], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 2], ['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 6], ['g', 2], ['b', 5], ['p', 0, 10000, False], ['g', 1]], 6], [[1, 'glue'], [7, 'glue'], [3, 'glue'], [7, 'glue'], [2, 'forced'], [8, 'penalty'], [6, 'glue'], [6, 'end']]), ('regression: discardable items at line start', [[['b', 4], ['g', 1], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 2], ['b', 7], ['g', 1], ['b', 4], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 1]], 18], [[9, 'forced'], [13, 'penalty'], [14, 'glue'], [4, 'end']]), ('partial-repair probe', [[['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 0, 9999, False], ['g', 2], ['b', 4], ['g', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 3], ['g', 1]], 13], [[13, 'glue'], [6, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 0, -10000, False], ['g', 2], ['b', 7], ['p', 1, 50, True], ['g', 1], ['g', 1]], 17], [[9, 'forced'], [9, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 3], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['b', 2], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2]], 16], [[13, 'glue'], [14, 'glue'], [7, 'end']]), ('control layout', [[['b', 6], ['g', 1], ['b', 7], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['g', 1], ['b', 3], ['g', 2]], 6], [[6, 'glue'], [7, 'glue'], [6, 'glue'], [3, 'glue'], [5, 'end']])], [('regression: discardable items at line start', [[['b', 7], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 1], ['p', 1, 50, True], ['g', 2], ['b', 1], ['p', 0, 900, False], ['g', 1], ['b', 1], ['g', 1], ['g', 1], ['b', 7], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1]], 9], [[10, 'penalty'], [3, 'glue'], [7, 'forced'], [6, 'penalty'], [7, 'glue'], [4, 'end']]), ('regression: discardable items at line start', [[['b', 1], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['g', 2], ['b', 7], ['g', 1], ['b', 7], ['g', 2], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 2]], 12], [[5, 'glue'], [7, 'glue'], [7, 'glue'], [10, 'forced'], [5, 'end']]), ('partial-repair probe', [[['b', 4], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['g', 1], ['b', 1], ['p', 0, -10000, False], ['g', 1], ['g', 1], ['b', 6], ['p', 1, 50, True], ['g', 2]], 16], [[10, 'forced'], [8, 'end']]), ('partial-repair probe', [[['b', 7], ['g', 2], ['b', 3], ['g', 2], ['b', 3], ['g', 1], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 3], ['g', 2]], 6], [[7, 'glue'], [3, 'glue'], [3, 'glue'], [8, 'penalty'], [7, 'glue'], [5, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 1], ['p', 0, 10000, False], ['g', 1], ['b', 3], ['g', 1], ['b', 2], ['g', 1], ['b', 4], ['g', 2]], 15], [[15, 'end']]), ('control layout', [[['b', 7], ['p', 1, 50, True], ['g', 1], ['b', 5], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 2], ['b', 5], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 4], ['p', 0, 10000, False], ['g', 1]], 17], [[13, 'glue'], [14, 'glue'], [5, 'end']])], [('regression: discardable items at line start', [[['b', 4], ['g', 1], ['g', 1], ['b', 5], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 2], ['b', 3], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 7], ['g', 1], ['g', 1], ['b', 1], ['g', 2], ['b', 7], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 1], ['b', 5], ['g', 1]], 6], [[4, 'glue'], [5, 'glue'], [12, 'penalty'], [7, 'glue'], [1, 'glue'], [8, 'penalty'], [4, 'glue'], [6, 'end']]), ('regression: discardable items at line start', [[['b', 3], ['g', 2], ['b', 4], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 1], ['g', 2], ['b', 3], ['g', 2], ['b', 6], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1]], 8], [[3, 'glue'], [4, 'forced'], [6, 'glue'], [6, 'glue'], [3, 'end']]), ('partial-repair probe', [[['b', 5], ['p', 1, 50, True], ['g', 2], ['b', 3], ['g', 1], ['b', 2], ['g', 2], ['b', 5], ['g', 1], ['b', 2], ['g', 2], ['b', 7], ['g', 1], ['g', 1]], 17], [[13, 'glue'], [17, 'glue']]), ('partial-repair probe', [[['b', 2], ['g', 1], ['b', 4], ['p', 0, 900, False], ['g', 2], ['b', 6], ['g', 2], ['b', 1], ['g', 1], ['b', 6], ['g', 2], ['b', 3], ['p', 0, 10000, False], ['g', 1], ['b', 4], ['g', 1], ['g', 1], ['b', 7], ['g', 1]], 8], [[7, 'penalty'], [6, 'glue'], [8, 'glue'], [8, 'glue'], [8, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('forced break', [[['b', 2], ['g', 1], ['b', 2], ['p', 0, -10000, False], ['b', 3]], 20], [[5, 'forced'], [3, 'end']]), ('control layout', [[['b', 5], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 2]], 15], [[14, 'glue'], [5, 'end']]), ('control layout', [[['b', 1], ['p', 1, 50, True], ['g', 1], ['b', 3], ['p', 1, 50, True], ['g', 1], ['b', 4], ['g', 2], ['b', 2], ['p', 1, 50, True], ['g', 1]], 15], [[15, 'end']])], [('regression: discardable items at line start', [[['b', 4], ['g', 1], ['g', 1], ['b', 5], ['g', 1], ['b', 3], ['g', 2], ['b', 1], ['p', 0, -10000, False], ['p', 1, 50, True], ['g', 1], ['b', 5], ['p', 1, 50, True], ['g', 1], ['b', 7], ['p', 1, 50, True], ['g', 1]], 14], [[11, 'glue'], [6, 'forced'], [14, 'end']]), ('regression: discardable items at line start', [[['b', 7], ['g', 2], ['b', 7], ['g', 1], ['b', 5], ['p', 0, 10000, False], ['g', 1], ['b', 6], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1]], 10], [[7, 'glue'], [7, 'glue'], [13, 'penalty']]), ('partial-repair probe', [[['b', 1], ['p', 0, -10000, False], ['g', 1], ['b', 6], ['p', 0, 9999, False], ['p', 1, 50, True], ['g', 1], ['b', 2], ['p', 1, 50, True], ['g', 2], ['b', 1], ['g', 1]], 6], [[1, 'forced'], [7, 'penalty'], [6, 'end']]), ('partial-repair probe', [[['b', 2], ['g', 2], ['b', 6], ['p', 0, 10000, False], ['g', 1], ['b', 1], ['p', 1, 50, True], ['p', 1, 50, True], ['g', 1], ['b', 4], ['p', 1, 50, True], ['g', 1], ['b', 3], ['g', 1], ['b', 1], ['g', 1], ['b', 4], ['p', 0, 10000, False], ['g', 1], ['b', 5], ['g', 2]], 12], [[13, 'penalty'], [10, 'glue'], [12, 'end']]), ('inhibited penalty', [[['b', 5], ['p', 0, 10000, False], ['b', 4], ['g', 1], ['b', 3]], 7], [[9, 'glue'], [3, 'end']]), ('hyphen penalty taken', [[['b', 5], ['p', 1, 50, True], ['b', 4], ['g', 1], ['b', 3]], 7], [[6, 'penalty'], [4, 'glue'], [3, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 6], ['g', 1], ['b', 6], ['g', 1], ['b', 2], ['p', 0, 10000, False], ['g', 1]], 14], [[12, 'glue'], [10, 'end']]), ('control layout', [[['b', 4], ['g', 2], ['b', 7], ['g', 1], ['b', 3], ['g', 2], ['b', 2], ['g', 2], ['b', 6], ['g', 2], ['b', 4], ['g', 2], ['b', 2], ['g', 1], ['b', 4], ['g', 1]], 10], [[4, 'glue'], [7, 'glue'], [7, 'glue'], [6, 'glue'], [8, 'glue'], [5, 'end']])]]
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:
Penalties left at the start of a line produce empty breaks.

Input [items, width]; items are ["b",w], ["g",w] or ["p",w,cost,flag]. Legal breaks: glue immediately after a box; penalty with cost < 10000 (width counted only if broken there); cost <= -10000 forces a break. Discardable glue/penalties at a line start are dropped. First-fit: when the running width exceeds the measure, break at the last legal breakpoint. Return [[line width, break kind]] with kinds glue/penalty/forced/end.

split: open-access