Destination dispatch allocation: coincident stop credit · case 01

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

N = 1
observations = []
def solve(x):
    cars = {c['id']: {'ready': c['ready_s'], 'stops': set(c['stops']), 'load': c['load'], 'cap': c['cap']} for c in x['cars']}
    out = []
    for req in x['requests']:
        best = None
        for cid in sorted(cars):
            c = cars[cid]
            if c['load'] + req['n'] > c['cap']:
                continue
            new_stop = 1
            cost = c['ready'] + x['per_stop_s'] * len(c['stops']) + x['stop_penalty_s'] * new_stop
            if best is None or cost < best[0]:
                best = (cost, cid)
        if best is None:
            out.append(None)
            continue
        c = cars[best[1]]
        c['stops'].add(req['dest'])
        c['load'] += req['n']
        out.append(best[1])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 5', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [3, 6, 5], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [2, 3], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 2, 'n': 5}, {'dest': 9, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 1', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [10, 11], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [9], 'load': 11, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [13, 14, 2], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['A', None]), ('sampled regression 4', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 11, 'cap': 13}], 'requests': [{'dest': 7, 'n': 2}, {'dest': 3, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'A', 'B']), ('control 7', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [11, 6], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [7], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 10, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 1}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'C', 'A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 32', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [5, 13], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 14, 'n': 3}, {'dest': 11, 'n': 1}, {'dest': 7, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'A', 'B', 'B']), ('sampled regression 22', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7, 5, 11], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 0, 'stops': [10, 8], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 11, 'n': 5}, {'dest': 13, 'n': 2}, {'dest': 13, 'n': 1}, {'dest': 7, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'A', 'A', 'A', 'C']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('sampled regression 15', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 5, 'stops': [7, 2], 'load': 0, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 3}, {'dest': 13, 'n': 5}, {'dest': 11, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 12, 'n': 3}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'C', 'B', 'C']), ('control 18', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 7, 5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 5}, {'dest': 2, 'n': 1}, {'dest': 6, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 77', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [11, 9, 14], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [6, 3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [5, 13, 12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 5, 'n': 3}, {'dest': 2, 'n': 1}, {'dest': 14, 'n': 3}, {'dest': 5, 'n': 5}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'C', 'A', 'B', 'C']), ('control 53', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 11, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: capacity used up by earlier groups', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 6, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 8, 'n': 3}, {'dest': 9, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'B']), ('sampled regression 23', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [9, 8], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}], 'requests': [{'dest': 8, 'n': 3}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'C', 'B']), ('control 26', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [9], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [11, 14, 4], 'load': 8, 'cap': 13}], 'requests': [{'dest': 13, 'n': 1}, {'dest': 5, 'n': 1}, {'dest': 12, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B']), ('control 29', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 5, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 3, 'n': 5}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 21', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [10, 8, 5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [4], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 13}], 'requests': [{'dest': 8, 'n': 1}, {'dest': 4, 'n': 1}, {'dest': 10, 'n': 5}, {'dest': 11, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'C', 'C']), ('sampled regression 79', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [10, 3], 'load': 8, 'cap': 12}], 'requests': [{'dest': 13, 'n': 3}, {'dest': 6, 'n': 2}, {'dest': 12, 'n': 3}, {'dest': 10, 'n': 1}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 3}, ['B', 'B', 'B', 'C', 'B']), ('boundary: no eligible car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 11, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, [None]), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 34', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [8], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 11, 'n': 3}, {'dest': 5, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 10, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'A', 'B', 'A']), ('sampled regression 37', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [9, 14, 8], 'load': 8, 'cap': 12}], 'requests': [{'dest': 5, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 2, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'B', 'A']), ('control 40', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [10, 5, 7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 5}, {'dest': 5, 'n': 5}, {'dest': 7, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'B', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 42', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3, 8, 13], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [6], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 10, 'n': 3}, {'dest': 12, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'A', 'A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 45', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 5}, {'dest': 9, 'n': 5}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'B', 'A', 'A']), ('control 48', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 13], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [10, 12], 'load': 11, 'cap': 12}], 'requests': [{'dest': 6, 'n': 2}, {'dest': 14, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', None]), ('control 51', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [12, 8], 'load': 0, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10], 'load': 0, 'cap': 13}], 'requests': [{'dest': 14, 'n': 1}, {'dest': 13, 'n': 2}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A'])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

SHA-256 / b1d4517de90e5bc3527fb4b55d42ea722b5242c1fb912ccf4efc387fd5abd645

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

N = 1
observations = []
def solve(x):
    cars = {c['id']: {'ready': c['ready_s'], 'stops': set(c['stops']), 'load': c['load'], 'cap': c['cap']} for c in x['cars']}
    out = []
    for req in x['requests']:
        best = None
        for cid in sorted(cars):
            c = cars[cid]
            if c['load'] + req['n'] > c['cap']:
                continue
            new_stop = 0 if req['dest'] in c['stops'] or not c['stops'] else 1
            cost = c['ready'] + x['per_stop_s'] * len(c['stops']) + x['stop_penalty_s'] * new_stop
            if best is None or cost < best[0]:
                best = (cost, cid)
        if best is None:
            out.append(None)
            continue
        c = cars[best[1]]
        c['stops'].add(req['dest'])
        c['load'] += req['n']
        out.append(best[1])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 5', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [3, 6, 5], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [2, 3], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 2, 'n': 5}, {'dest': 9, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 1', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [10, 11], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [9], 'load': 11, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [13, 14, 2], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['A', None]), ('sampled regression 4', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 11, 'cap': 13}], 'requests': [{'dest': 7, 'n': 2}, {'dest': 3, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'A', 'B']), ('control 7', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [11, 6], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [7], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 10, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 1}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'C', 'A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 32', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [5, 13], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 14, 'n': 3}, {'dest': 11, 'n': 1}, {'dest': 7, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'A', 'B', 'B']), ('sampled regression 22', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7, 5, 11], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 0, 'stops': [10, 8], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 11, 'n': 5}, {'dest': 13, 'n': 2}, {'dest': 13, 'n': 1}, {'dest': 7, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'A', 'A', 'A', 'C']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('sampled regression 15', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 5, 'stops': [7, 2], 'load': 0, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 3}, {'dest': 13, 'n': 5}, {'dest': 11, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 12, 'n': 3}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'C', 'B', 'C']), ('control 18', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 7, 5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 5}, {'dest': 2, 'n': 1}, {'dest': 6, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 77', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [11, 9, 14], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [6, 3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [5, 13, 12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 5, 'n': 3}, {'dest': 2, 'n': 1}, {'dest': 14, 'n': 3}, {'dest': 5, 'n': 5}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'C', 'A', 'B', 'C']), ('control 53', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 11, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: capacity used up by earlier groups', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 6, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 8, 'n': 3}, {'dest': 9, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'B']), ('sampled regression 23', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [9, 8], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}], 'requests': [{'dest': 8, 'n': 3}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'C', 'B']), ('control 26', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [9], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [11, 14, 4], 'load': 8, 'cap': 13}], 'requests': [{'dest': 13, 'n': 1}, {'dest': 5, 'n': 1}, {'dest': 12, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B']), ('control 29', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 5, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 3, 'n': 5}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 21', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [10, 8, 5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [4], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 13}], 'requests': [{'dest': 8, 'n': 1}, {'dest': 4, 'n': 1}, {'dest': 10, 'n': 5}, {'dest': 11, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'C', 'C']), ('sampled regression 79', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [10, 3], 'load': 8, 'cap': 12}], 'requests': [{'dest': 13, 'n': 3}, {'dest': 6, 'n': 2}, {'dest': 12, 'n': 3}, {'dest': 10, 'n': 1}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 3}, ['B', 'B', 'B', 'C', 'B']), ('boundary: no eligible car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 11, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, [None]), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 34', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [8], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 11, 'n': 3}, {'dest': 5, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 10, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'A', 'B', 'A']), ('sampled regression 37', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [9, 14, 8], 'load': 8, 'cap': 12}], 'requests': [{'dest': 5, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 2, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'B', 'A']), ('control 40', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [10, 5, 7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 5}, {'dest': 5, 'n': 5}, {'dest': 7, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'B', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 42', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3, 8, 13], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [6], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 10, 'n': 3}, {'dest': 12, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'A', 'A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 45', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 5}, {'dest': 9, 'n': 5}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'B', 'A', 'A']), ('control 48', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 13], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [10, 12], 'load': 11, 'cap': 12}], 'requests': [{'dest': 6, 'n': 2}, {'dest': 14, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', None]), ('control 51', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [12, 8], 'load': 0, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10], 'load': 0, 'cap': 13}], 'requests': [{'dest': 14, 'n': 1}, {'dest': 13, 'n': 2}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A'])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

SHA-256 / 9c9c3f7551ad77efd3d29d78d8cd823508d1b09f23ac05610d7a1799d35c2c7d

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

N = 1
observations = []
def solve(x):
    cars = {c['id']: {'ready': c['ready_s'], 'stops': set(c['stops']), 'load': c['load'], 'cap': c['cap']} for c in x['cars']}
    out = []
    for req in x['requests']:
        best = None
        for cid in sorted(cars):
            c = cars[cid]
            if c['load'] + req['n'] > c['cap']:
                continue
            new_stop = 0 if req['dest'] in c['stops'] else 1
            cost = c['ready'] + x['per_stop_s'] * len(c['stops']) + x['stop_penalty_s'] * new_stop
            if best is None or cost < best[0]:
                best = (cost, cid)
        if best is None:
            out.append(None)
            continue
        c = cars[best[1]]
        c['stops'].add(req['dest'])
        c['load'] += req['n']
        out.append(best[1])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 5', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [3, 6, 5], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [2, 3], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 2, 'n': 5}, {'dest': 9, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 1', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [10, 11], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [9], 'load': 11, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [13, 14, 2], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['A', None]), ('sampled regression 4', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 11, 'cap': 13}], 'requests': [{'dest': 7, 'n': 2}, {'dest': 3, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 3, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'B', 'A', 'B']), ('control 7', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [11, 6], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 20, 'stops': [7], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 10, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 1}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'C', 'A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 32', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [5, 13], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 14, 'n': 3}, {'dest': 11, 'n': 1}, {'dest': 7, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'A', 'B', 'B']), ('sampled regression 22', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7, 5, 11], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 0, 'stops': [10, 8], 'load': 0, 'cap': 13}], 'requests': [{'dest': 12, 'n': 2}, {'dest': 11, 'n': 5}, {'dest': 13, 'n': 2}, {'dest': 13, 'n': 1}, {'dest': 7, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'A', 'A', 'A', 'C']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('sampled regression 15', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 5, 'stops': [7, 2], 'load': 0, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 0, 'cap': 12}], 'requests': [{'dest': 2, 'n': 3}, {'dest': 13, 'n': 5}, {'dest': 11, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 12, 'n': 3}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'C', 'B', 'C']), ('control 18', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 7, 5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 5}, {'dest': 2, 'n': 1}, {'dest': 6, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 77', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [11, 9, 14], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [6, 3], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 0, 'stops': [5, 13, 12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 5, 'n': 3}, {'dest': 2, 'n': 1}, {'dest': 14, 'n': 3}, {'dest': 5, 'n': 5}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['C', 'C', 'A', 'B', 'C']), ('control 53', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}, {'dest': 11, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'B']), ('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('boundary: capacity used up by earlier groups', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 6, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 8, 'n': 3}, {'dest': 9, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'B']), ('sampled regression 23', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [9, 8], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [], 'load': 0, 'cap': 13}], 'requests': [{'dest': 8, 'n': 3}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'C', 'B']), ('control 26', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [9], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [11, 14, 4], 'load': 8, 'cap': 13}], 'requests': [{'dest': 13, 'n': 1}, {'dest': 5, 'n': 1}, {'dest': 12, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 7, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B']), ('control 29', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 5, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [2], 'load': 4, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 3, 'n': 5}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'A'])], [('regression: second group sees the first allocation', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 2, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}, {'dest': 6, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A']), ('sampled regression 21', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [10, 8, 5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [4], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [], 'load': 4, 'cap': 13}], 'requests': [{'dest': 8, 'n': 1}, {'dest': 4, 'n': 1}, {'dest': 10, 'n': 5}, {'dest': 11, 'n': 3}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'C', 'C']), ('sampled regression 79', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 10, 'stops': [10, 3], 'load': 8, 'cap': 12}], 'requests': [{'dest': 13, 'n': 3}, {'dest': 6, 'n': 2}, {'dest': 12, 'n': 3}, {'dest': 10, 'n': 1}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 15, 'per_stop_s': 3}, ['B', 'B', 'B', 'C', 'B']), ('boundary: no eligible car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 11, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, [None]), ('boundary: group exactly fills the car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 10, 'cap': 12}, {'id': 'B', 'ready_s': 30, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 34', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [8], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 1}, {'dest': 11, 'n': 3}, {'dest': 5, 'n': 1}, {'dest': 9, 'n': 1}, {'dest': 10, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', 'B', 'A', 'B', 'A']), ('sampled regression 37', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [9, 14, 8], 'load': 8, 'cap': 12}], 'requests': [{'dest': 5, 'n': 1}, {'dest': 8, 'n': 1}, {'dest': 2, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'B', 'A']), ('control 40', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 4, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [10, 5, 7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 5, 'n': 5}, {'dest': 5, 'n': 5}, {'dest': 7, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'B', 'A'])], [('regression: coincident destination beats an idle car', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [7], 'load': 0, 'cap': 12}], 'requests': [{'dest': 7, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B']), ('sampled regression 42', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3, 8, 13], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [6], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [12], 'load': 8, 'cap': 13}], 'requests': [{'dest': 10, 'n': 3}, {'dest': 12, 'n': 3}, {'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['C', 'A', 'A']), ('control 12', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [6, 3], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10, 8], 'load': 11, 'cap': 13}], 'requests': [{'dest': 10, 'n': 1}, {'dest': 2, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['A', 'A']), ('boundary: empty car earns no discount', {'cars': [{'id': 'A', 'ready_s': 4, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [9], 'load': 0, 'cap': 12}], 'requests': [{'dest': 3, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('boundary: equal cost cars', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 4, 'n': 1}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A']), ('control 45', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [5], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [], 'load': 0, 'cap': 12}], 'requests': [{'dest': 6, 'n': 5}, {'dest': 9, 'n': 5}, {'dest': 13, 'n': 1}, {'dest': 9, 'n': 2}, {'dest': 8, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 3}, ['B', 'A', 'B', 'A', 'A']), ('control 48', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [2, 13], 'load': 11, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [10, 12], 'load': 11, 'cap': 12}], 'requests': [{'dest': 6, 'n': 2}, {'dest': 14, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['B', None]), ('control 51', {'cars': [{'id': 'A', 'ready_s': 5, 'stops': [3], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 10, 'stops': [12, 8], 'load': 0, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [10], 'load': 0, 'cap': 13}], 'requests': [{'dest': 14, 'n': 1}, {'dest': 13, 'n': 2}, {'dest': 5, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A'])]]
for label, args, expected in fixtures[N-1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

SHA-256 / c9ac3d71b1f2aace1d64d3de21120d50556ac80abd60c4e6579a066c2d3a7227