ledger
f864998aba
Q105 pointed beam/CHECK at pytest; pytest is not installed on this interpreter, so the gate exited 2 and ran zero cells. run_lane_tests.py collects TestCase classes (TestLoader) and bare module-level def test_*() (FunctionTestCase) itself, treats an unimportable module and a printed FAIL transcript as faults, and exits 0/1/2. Four test files that imported pytest now use beam_assert.raises/fail and unittest.mock; no cell dropped. Measured: unittest discover 353 tests; runner 570 (353 + 217 bare); bash wizard-work/beam/CHECK rc 0; test_run_lane_tests.py 10 cells OK; 7-mutant battery in scratch copies all as expected (HEAD CHECK rc 2, broken bare rc 1, pytest import rc 1, failing TestCase rc 1, script FAIL rc 1, empty lane rc 2, control rc 0). Record: WORK-QUEUE.md Q128; report wizard-outputs/volt/2026-10-30-q128.md
116 lines
3.9 KiB
Python
116 lines
3.9 KiB
Python
"""Q111: cells for weighted_interval_scheduling's zero-length and reversed input.
|
|
|
|
The module's own docstring defines overlap as intersection with POSITIVE
|
|
length, so a zero-length interval (start == end) is compatible with every
|
|
interval and with every other zero-length interval. Before this file the
|
|
module's only check was a `__main__` self-test whose generator emitted
|
|
`length = randint(1, 4)`, so no cell could construct the failing case and
|
|
`beam/CHECK` (which, when this file was written, ran pytest over `test_*.py`;
|
|
it now runs `run_lane_tests.py`, which needs no third-party package) never
|
|
imported the module at all.
|
|
|
|
The enumerator below is written here rather than imported from the module's
|
|
`brute_force`, so the differential compares the DP against independent code.
|
|
"""
|
|
|
|
import random
|
|
|
|
from beam_assert import raises
|
|
|
|
from weighted_interval_scheduling import weighted_interval_scheduling as wis
|
|
|
|
|
|
def _overlap(a, b):
|
|
"""Positive-length intersection, exactly the rule in the module docstring."""
|
|
return min(a[1], b[1]) - max(a[0], b[0]) > 0
|
|
|
|
|
|
def _enumerate(intervals):
|
|
"""Exhaustive optimum over all subsets; independent of the module's DP."""
|
|
n = len(intervals)
|
|
best = 0
|
|
for mask in range(1 << n):
|
|
chosen = [intervals[k] for k in range(n) if mask >> k & 1]
|
|
blocked = False
|
|
for i in range(len(chosen)):
|
|
for j in range(i + 1, len(chosen)):
|
|
if _overlap(chosen[i], chosen[j]):
|
|
blocked = True
|
|
break
|
|
if blocked:
|
|
break
|
|
if not blocked:
|
|
best = max(best, sum(w for _, _, w in chosen))
|
|
return best
|
|
|
|
|
|
# --- the filed repro and its immediate neighbours -------------------------
|
|
|
|
|
|
def test_zero_length_inside_positive_interval_is_compatible():
|
|
# Q111's minimal repro: the point interval at t=1 does not block [0,3].
|
|
assert wis([(1, 1, 5), (0, 3, 1)]) == 6
|
|
|
|
|
|
def test_zero_length_only():
|
|
assert wis([(2, 2, 7)]) == 7
|
|
assert wis([(2, 2, 7), (5, 5, 3)]) == 10
|
|
assert wis([(2, 2, 7), (2, 2, 3)]) == 10 # same point: still no overlap
|
|
|
|
|
|
def test_negative_weight_zero_length_is_dropped():
|
|
assert wis([(2, 2, -7), (0, 9, 4)]) == 4
|
|
assert wis([(2, 2, -7)]) == 0
|
|
assert wis([(2, 2, -7), (4, 4, -3), (0, 0, 1)]) == 1
|
|
|
|
|
|
def test_zero_length_points_add_to_a_packed_schedule():
|
|
# two touching positive intervals [0,2] and [2,4] can both be taken;
|
|
# points sitting inside them are free on top of that.
|
|
assert wis([(0, 2, 3), (2, 4, 5), (1, 1, 2), (2, 2, 4), (3, 3, 1)]) == 15
|
|
|
|
|
|
def test_reversed_interval_is_rejected():
|
|
with raises(ValueError):
|
|
wis([(3, 1, 5)])
|
|
with raises(ValueError):
|
|
wis([(0, 2, 1), (5, 4, 9)])
|
|
|
|
|
|
# --- the positive-length behaviour this file must not disturb -------------
|
|
|
|
|
|
def test_documented_example_and_boundaries():
|
|
assert wis([]) == 0
|
|
assert wis([(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4)]) == 14
|
|
assert wis([(0, 1, 5), (1, 2, 3)]) == 8 # touching endpoints coexist
|
|
assert wis([(0, 10, 100), (2, 8, 90)]) == 100 # nested: pick one
|
|
assert wis([(0, 2, -5), (3, 4, -1)]) == 0 # all negative: take nothing
|
|
|
|
|
|
# --- differential against the independent enumerator ----------------------
|
|
|
|
|
|
def _random_intervals(rng, allow_zero_length):
|
|
n = rng.randint(0, 7)
|
|
out = []
|
|
for _ in range(n):
|
|
s = rng.randint(0, 6)
|
|
length = rng.randint(0 if allow_zero_length else 1, 4)
|
|
out.append((s, s + length, rng.randint(-5, 9)))
|
|
return out
|
|
|
|
|
|
def test_differential_positive_length_only():
|
|
rng = random.Random(7)
|
|
for _ in range(400):
|
|
ivs = _random_intervals(rng, allow_zero_length=False)
|
|
assert wis(ivs) == _enumerate(ivs), ivs
|
|
|
|
|
|
def test_differential_with_zero_length_intervals():
|
|
rng = random.Random(11)
|
|
for _ in range(400):
|
|
ivs = _random_intervals(rng, allow_zero_length=True)
|
|
assert wis(ivs) == _enumerate(ivs), ivs
|