broken_source:
"""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: 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']), ('regression: 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 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']), ('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: 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']), ('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 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']), ('control 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'B'])], [('regression: 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']), ('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]), ('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']), ('control 11', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [13], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [6, 4], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 10, 'stops': [2, 14], 'load': 0, 'cap': 13}], 'requests': [{'dest': 5, 'n': 3}, {'dest': 9, 'n': 2}, {'dest': 8, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['C', 'C', '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']), ('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']), ('control 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: 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']), ('regression: 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 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 20', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [7], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [3, 6, 4], 'load': 8, 'cap': 12}], 'requests': [{'dest': 4, 'n': 5}, {'dest': 4, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 3}, [None, 'B']), ('boundary: 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']), ('control 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']), ('sampled regression 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: 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']), ('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]), ('sampled regression 61', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [13, 9], 'load': 0, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [11], 'load': 4, 'cap': 13}], 'requests': [{'dest': 7, 'n': 1}, {'dest': 11, 'n': 1}, {'dest': 12, 'n': 3}, {'dest': 3, 'n': 5}, {'dest': 2, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A', 'B', 'B']), ('control 33', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7, 10], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [11], 'load': 11, 'cap': 12}], 'requests': [{'dest': 11, 'n': 3}, {'dest': 14, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', None]), ('regression: 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']), ('control 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: 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']), ('regression: 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 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']), ('control 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']), ('boundary: 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 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']), ('sampled regression 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]), ('sampled regression 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)

source:
"""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 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: 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']), ('regression: 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 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']), ('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: 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']), ('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 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']), ('control 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'B'])], [('regression: 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']), ('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]), ('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']), ('control 11', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [13], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [6, 4], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 10, 'stops': [2, 14], 'load': 0, 'cap': 13}], 'requests': [{'dest': 5, 'n': 3}, {'dest': 9, 'n': 2}, {'dest': 8, 'n': 5}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['C', 'C', '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']), ('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']), ('control 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: 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']), ('regression: 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 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 20', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [7], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 0, 'stops': [3, 6, 4], 'load': 8, 'cap': 12}], 'requests': [{'dest': 4, 'n': 5}, {'dest': 4, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 3}, [None, 'B']), ('boundary: 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']), ('control 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']), ('sampled regression 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: 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']), ('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]), ('sampled regression 61', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [], 'load': 8, 'cap': 13}, {'id': 'B', 'ready_s': 0, 'stops': [13, 9], 'load': 0, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [11], 'load': 4, 'cap': 13}], 'requests': [{'dest': 7, 'n': 1}, {'dest': 11, 'n': 1}, {'dest': 12, 'n': 3}, {'dest': 3, 'n': 5}, {'dest': 2, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', 'A', 'A', 'B', 'B']), ('control 33', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [7, 10], 'load': 8, 'cap': 12}, {'id': 'B', 'ready_s': 20, 'stops': [11], 'load': 11, 'cap': 12}], 'requests': [{'dest': 11, 'n': 3}, {'dest': 14, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 5}, ['A', None]), ('regression: 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']), ('control 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: 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']), ('regression: 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 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']), ('control 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']), ('boundary: 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 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']), ('sampled regression 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]), ('sampled regression 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)

prompt:
A group that exactly fills the car is sent elsewhere, or an overfull car is chosen.

Requests (destination, group size) are allocated one by one. A car is eligible if load + group size <= capacity. Cost = ready time + per_stop_s * existing stops + stop_penalty_s if the destination is not already a stop. The lowest cost wins, ties to the lowest car id. The chosen car adds the destination to its stops and the group to its load. None if no car is eligible.

split: open-access


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

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

prompt:
Passengers for the same floor are spread over several cars.

Requests (destination, group size) are allocated one by one. A car is eligible if load + group size <= capacity. Cost = ready time + per_stop_s * existing stops + stop_penalty_s if the destination is not already a stop. The lowest cost wins, ties to the lowest car id. The chosen car adds the destination to its stops and the group to its load. None if no car is eligible.

split: open-access


broken_source:
"""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: 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']), ('sampled regression 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']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'B']), ('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: 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']), ('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]), ('control 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']), ('sampled regression 13', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 11, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [6], 'load': 0, 'cap': 12}], 'requests': [{'dest': 9, 'n': 3}, {'dest': 14, 'n': 5}, {'dest': 14, 'n': 1}, {'dest': 3, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B'])], [('regression: 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']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', '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']), ('sampled regression 27', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 6, 13], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [6, 14, 5], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 12, 'n': 3}, {'dest': 2, 'n': 2}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['C', 'B', 'C', 'B']), ('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 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']), ('sampled regression 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: 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']), ('sampled regression 13', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 11, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [6], 'load': 0, 'cap': 12}], 'requests': [{'dest': 9, 'n': 3}, {'dest': 14, 'n': 5}, {'dest': 14, 'n': 1}, {'dest': 3, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B']), ('sampled regression 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 58', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 2, 9], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5, 13], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [5, 11], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 3}, {'dest': 13, 'n': 2}, {'dest': 4, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'C']), ('boundary: 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 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']), ('sampled regression 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: 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']), ('sampled regression 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']), ('sampled regression 59', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [6], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [8, 13, 14], 'load': 4, 'cap': 13}], 'requests': [{'dest': 7, 'n': 1}, {'dest': 4, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['B', 'A']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', '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]), ('sampled regression 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']), ('control 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: 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']), ('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']), ('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']), ('sampled regression 27', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 6, 13], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [6, 14, 5], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 12, 'n': 3}, {'dest': 2, 'n': 2}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['C', 'B', 'C', 'B']), ('boundary: 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 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]), ('sampled regression 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)

source:
"""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] or (cost == best[0] and c['load'] < cars[best[1]]['load']):
                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: 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']), ('sampled regression 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']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', 'B']), ('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: 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']), ('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]), ('control 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']), ('sampled regression 13', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 11, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [6], 'load': 0, 'cap': 12}], 'requests': [{'dest': 9, 'n': 3}, {'dest': 14, 'n': 5}, {'dest': 14, 'n': 1}, {'dest': 3, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B'])], [('regression: 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']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', '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']), ('sampled regression 27', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 6, 13], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [6, 14, 5], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 12, 'n': 3}, {'dest': 2, 'n': 2}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['C', 'B', 'C', 'B']), ('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 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']), ('sampled regression 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: 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']), ('sampled regression 13', {'cars': [{'id': 'A', 'ready_s': 0, 'stops': [3], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [2, 11, 7], 'load': 8, 'cap': 13}, {'id': 'C', 'ready_s': 20, 'stops': [6], 'load': 0, 'cap': 12}], 'requests': [{'dest': 9, 'n': 3}, {'dest': 14, 'n': 5}, {'dest': 14, 'n': 1}, {'dest': 3, 'n': 1}, {'dest': 9, 'n': 5}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['A', 'A', 'A', 'A', 'B']), ('sampled regression 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 58', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 2, 9], 'load': 0, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5, 13], 'load': 4, 'cap': 13}, {'id': 'C', 'ready_s': 5, 'stops': [5, 11], 'load': 0, 'cap': 12}], 'requests': [{'dest': 10, 'n': 3}, {'dest': 13, 'n': 2}, {'dest': 4, 'n': 2}], 'stop_penalty_s': 10, 'per_stop_s': 3}, ['B', 'B', 'C']), ('boundary: 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 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']), ('sampled regression 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: 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']), ('sampled regression 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']), ('sampled regression 59', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [6], 'load': 11, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [8, 13, 14], 'load': 4, 'cap': 13}], 'requests': [{'dest': 7, 'n': 1}, {'dest': 4, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['B', 'A']), ('sampled regression 10', {'cars': [{'id': 'A', 'ready_s': 10, 'stops': [], 'load': 4, 'cap': 12}, {'id': 'B', 'ready_s': 5, 'stops': [5], 'load': 0, 'cap': 12}], 'requests': [{'dest': 12, 'n': 1}, {'dest': 8, 'n': 3}], 'stop_penalty_s': 15, 'per_stop_s': 5}, ['A', '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]), ('sampled regression 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']), ('control 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: 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']), ('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']), ('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']), ('sampled regression 27', {'cars': [{'id': 'A', 'ready_s': 20, 'stops': [12, 6, 13], 'load': 0, 'cap': 13}, {'id': 'B', 'ready_s': 10, 'stops': [6, 14, 5], 'load': 8, 'cap': 12}, {'id': 'C', 'ready_s': 20, 'stops': [], 'load': 4, 'cap': 12}], 'requests': [{'dest': 12, 'n': 3}, {'dest': 2, 'n': 2}, {'dest': 8, 'n': 5}, {'dest': 11, 'n': 1}], 'stop_penalty_s': 8, 'per_stop_s': 5}, ['C', 'B', 'C', 'B']), ('boundary: 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 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]), ('sampled regression 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)

prompt:
Equal-cost allocations go to the highest car id.

Requests (destination, group size) are allocated one by one. A car is eligible if load + group size <= capacity. Cost = ready time + per_stop_s * existing stops + stop_penalty_s if the destination is not already a stop. The lowest cost wins, ties to the lowest car id. The chosen car adds the destination to its stops and the group to its load. None if no car is eligible.

split: open-access