FA-67361 / Elevator dispatch scheduling / Open access
Destination dispatch allocation: capacity boundary · case 01
A group that exactly fills the car is sent elsewhere, or an overfull car is chosen.
ROOT CAUSE
The capacity test rejects a group that would exactly fill the car.
VERIFIED REPAIR
Reject only when load plus group size exceeds capacity.
Unsuccessful approach: Testing the group size alone ignores the passengers already allocated.
Case contract
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.
Why this case matters
Lift group controllers make these decisions many times per minute; a wrong answer strands passengers, wastes trips or overrides a safety rule.
1 / The failure
Exit 1"""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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: group exactly fills the car | ['B'] | ['A'] | Failed |
| regression: capacity used up by earlier groups | ['A', 'B', 'A'] | ['A', 'A', 'B'] | Failed |
| sampled regression 4 | ['B', 'C', 'B', 'B'] | ['C', 'B', 'A', 'B'] | Failed |
| boundary: no eligible car | [None] | [None] | Passed |
| boundary: coincident destination beats an idle car | ['B'] | ['B'] | Passed |
| control 1 | ['A', None] | ['A', None] | Passed |
| sampled regression 7 | ['A', 'C', 'A', 'C'] | ['A', 'C', 'A', 'A'] | Failed |
| control 10 | ['A', 'B'] | ['A', 'B'] | Passed |
SHA-256 / 64744158167b7e8910cbbad7f63c7c7d5a8b1522212235e05f5e887c2889fa31
2 / The unsuccessful fix
Exit 1"""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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: group exactly fills the car | ['A'] | ['A'] | Passed |
| regression: capacity used up by earlier groups | ['A', 'A', 'A'] | ['A', 'A', 'B'] | Failed |
| sampled regression 4 | ['C', 'B', 'A', 'B'] | ['C', 'B', 'A', 'B'] | Passed |
| boundary: no eligible car | ['A'] | [None] | Failed |
| boundary: coincident destination beats an idle car | ['B'] | ['B'] | Passed |
| control 1 | ['A', 'A'] | ['A', None] | Failed |
| sampled regression 7 | ['A', 'C', 'A', 'A'] | ['A', 'C', 'A', 'A'] | Passed |
| control 10 | ['A', 'B'] | ['A', 'B'] | Passed |
SHA-256 / de9867a9d3056c59ecb0e836fb01c8b791ab94abeb8558f4427ab9d57c68dd86
3 / The verified repair
Exit 0"""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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: group exactly fills the car | ['A'] | ['A'] | Passed |
| regression: capacity used up by earlier groups | ['A', 'A', 'B'] | ['A', 'A', 'B'] | Passed |
| sampled regression 4 | ['C', 'B', 'A', 'B'] | ['C', 'B', 'A', 'B'] | Passed |
| boundary: no eligible car | [None] | [None] | Passed |
| boundary: coincident destination beats an idle car | ['B'] | ['B'] | Passed |
| control 1 | ['A', None] | ['A', None] | Passed |
| sampled regression 7 | ['A', 'C', 'A', 'A'] | ['A', 'C', 'A', 'A'] | Passed |
| control 10 | ['A', 'B'] | ['A', 'B'] | Passed |
SHA-256 / d3a4c24c2d568e6b0077183cd7337b01d04bbdfbb8f42a6b3649b44459efec47
Verification & scope
Stipulated toy lift-control contract for a bounded teaching model; it makes no claim of conformance to any lift code or vendor dispatcher and omits real safety cases. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:47:52.044590+00:00.
Case digest / 4cf0f58814fdbad46e044140d6a23dfff9df4527df31e2bf1dab306e5dc72f5f