lars
e7bb0b9c69
The fixed +1/-4 offsets in get_courses only produced a collision-free rotation for certain group counts; for n=9 (three groups per course) the pairwise gaps collapsed and 9 pairs of groups met twice. Replace it with a resolvable transversal design (_rotation_hosts): slots form a k x 3 grid, each course is a parallel class partitioning all groups into transversal tables of three, guaranteeing every pair meets at most once for any n >= 9. n=3/6 are combinatorially impossible and fall back to a degenerate same-row rotation that still satisfies the structural invariants. Add a regression test asserting no pair meets more than once.
168 lines
6.7 KiB
Python
168 lines
6.7 KiB
Python
"""Tests for the dinner-rotation topology and the route-cost / optimization logic.
|
|
|
|
These cover the two areas most prone to subtle bugs: the ``get_courses`` rotation
|
|
(who hosts whom) and ``fast_total_time`` / ``simulated_annealing`` (the route cost
|
|
and its optimization).
|
|
"""
|
|
|
|
import itertools
|
|
from collections import Counter
|
|
|
|
import numpy as np
|
|
import pytest
|
|
|
|
from tatami.tatami_masterplan import (
|
|
fast_total_time,
|
|
get_courses,
|
|
simulated_annealing,
|
|
)
|
|
|
|
# Group counts must be multiples of 3 (one slot per course); test a range of sizes.
|
|
GROUP_COUNTS = [3, 6, 9, 12, 15]
|
|
|
|
|
|
def asymmetric_matrix(n: int, seed: int = 0) -> np.ndarray:
|
|
"""Random asymmetric (n+1)x(n+1) cost matrix, last index = after party."""
|
|
rng = np.random.default_rng(seed)
|
|
matrix = rng.integers(60, 1200, size=(n + 1, n + 1)).astype(float)
|
|
np.fill_diagonal(matrix, 0)
|
|
return matrix
|
|
|
|
|
|
class TestGetCourses:
|
|
@pytest.mark.parametrize("n", GROUP_COUNTS)
|
|
def test_group_is_its_own_first_host(self, n):
|
|
# A group always hosts the course it cooks, so it appears in its own host list.
|
|
for i in range(n):
|
|
assert i in get_courses(i, n)
|
|
|
|
@pytest.mark.parametrize("n", GROUP_COUNTS)
|
|
def test_each_group_visits_three_distinct_courses(self, n):
|
|
for i in range(n):
|
|
hosts = get_courses(i, n)
|
|
assert len(hosts) == 3
|
|
assert len(set(hosts)) == 3, "a group must visit three distinct hosts"
|
|
# The three hosts must cook three different courses (course == index % 3).
|
|
assert {h % 3 for h in hosts} == {0, 1, 2}
|
|
|
|
@pytest.mark.parametrize("n", GROUP_COUNTS)
|
|
def test_hosts_returned_in_starter_main_dessert_order(self, n):
|
|
# get_courses sorts by index % 3 -> starter(0), main(1), dessert(2).
|
|
for i in range(n):
|
|
a, b, c = get_courses(i, n)
|
|
assert (a % 3, b % 3, c % 3) == (0, 1, 2)
|
|
|
|
@pytest.mark.parametrize("n", GROUP_COUNTS)
|
|
def test_every_host_receives_exactly_three_groups(self, n):
|
|
# The defining invariant of a running dinner: every hosting location serves
|
|
# exactly three groups (itself + two guests) for its course.
|
|
received = Counter()
|
|
for i in range(n):
|
|
for host in get_courses(i, n):
|
|
received[host] += 1
|
|
assert set(received.values()) == {3}
|
|
assert len(received) == n
|
|
|
|
@pytest.mark.parametrize("n", GROUP_COUNTS)
|
|
def test_guests_at_each_host_cook_distinct_courses(self, n):
|
|
# Invert the relation: the (exactly three) groups that show up at host h for
|
|
# its course must each be responsible for a different course in the rotation.
|
|
hosts_of = {i: set(get_courses(i, n)) for i in range(n)}
|
|
for host in range(n):
|
|
guests = [g for g in range(n) if host in hosts_of[g]]
|
|
assert len(guests) == 3
|
|
assert {g % 3 for g in guests} == {0, 1, 2}
|
|
|
|
@pytest.mark.parametrize("n", [n for n in GROUP_COUNTS if n >= 9])
|
|
def test_no_two_groups_meet_more_than_once(self, n):
|
|
# The whole point of the Latin-square rotation: for n >= 9 (>= 3 groups per
|
|
# course) every pair of groups shares a table at most once across the evening.
|
|
# (n = 3 and 6 are combinatorially impossible and deliberately excluded.)
|
|
hosts_of = {i: set(get_courses(i, n)) for i in range(n)}
|
|
meetings = Counter()
|
|
for host in range(n):
|
|
guests = sorted(g for g in range(n) if host in hosts_of[g])
|
|
for a, b in itertools.combinations(guests, 2):
|
|
meetings[(a, b)] += 1
|
|
repeats = {pair: c for pair, c in meetings.items() if c > 1}
|
|
assert repeats == {}, f"pairs meeting more than once: {repeats}"
|
|
|
|
|
|
class TestFastTotalTime:
|
|
def test_matches_hand_computed_value_n3(self):
|
|
# For n=3 every slot resolves to hosts (0, 1, 2), so the cost is
|
|
# 3 * (D[s0][s1] + D[s1][s2] + D[s2][afterparty]).
|
|
matrix = np.array(
|
|
[
|
|
[0, 10, 20, 30],
|
|
[40, 0, 50, 60],
|
|
[70, 80, 0, 90],
|
|
[1, 2, 3, 0], # after-party row (unused as origin)
|
|
],
|
|
dtype=float,
|
|
)
|
|
solution = [0, 1, 2]
|
|
expected = 3 * (matrix[0][1] + matrix[1][2] + matrix[2][3])
|
|
assert fast_total_time(matrix, solution) == pytest.approx(expected)
|
|
|
|
def test_cost_depends_on_permutation(self):
|
|
# The whole point of the optimizer: different slot->group assignments must
|
|
# generally produce different costs on an asymmetric matrix.
|
|
matrix = asymmetric_matrix(6, seed=2)
|
|
costs = {
|
|
fast_total_time(matrix, list(p))
|
|
for p in itertools.islice(itertools.permutations(range(6)), 50)
|
|
}
|
|
assert len(costs) > 1
|
|
|
|
def test_returns_float(self):
|
|
matrix = asymmetric_matrix(6, seed=2)
|
|
assert isinstance(fast_total_time(matrix, list(range(6))), float)
|
|
|
|
|
|
class TestSimulatedAnnealing:
|
|
@pytest.mark.parametrize("seed", [0, 1, 2, 3, 4])
|
|
def test_never_returns_worse_than_optimum(self, seed):
|
|
# Sanity floor: the cost can never be below the true (brute-force) optimum.
|
|
n = 6
|
|
matrix = asymmetric_matrix(n, seed=seed)
|
|
optimum = min(
|
|
fast_total_time(matrix, list(p)) for p in itertools.permutations(range(n))
|
|
)
|
|
result = simulated_annealing(matrix, list(range(n)), 1000, 0.99, 5000)
|
|
assert fast_total_time(matrix, result) >= optimum
|
|
|
|
@pytest.mark.parametrize("seed", [0, 1, 2, 3, 4])
|
|
def test_beats_random_baseline(self, seed):
|
|
# SA should reliably do better than the average random ordering.
|
|
n = 9
|
|
matrix = asymmetric_matrix(n, seed=seed)
|
|
random_costs = []
|
|
for _ in range(500):
|
|
perm = list(range(n))
|
|
np.random.shuffle(perm)
|
|
random_costs.append(fast_total_time(matrix, perm))
|
|
result = simulated_annealing(matrix, list(range(n)), 1000, 0.99, 5000)
|
|
assert fast_total_time(matrix, result) < np.mean(random_costs)
|
|
|
|
def test_returns_valid_permutation(self):
|
|
n = 9
|
|
matrix = asymmetric_matrix(n, seed=3)
|
|
result = simulated_annealing(matrix, list(range(n)), 1000, 0.99, 1000)
|
|
assert sorted(result) == list(range(n))
|
|
|
|
def test_handles_single_slot(self):
|
|
matrix = asymmetric_matrix(1, seed=0)
|
|
assert simulated_annealing(matrix, [0], 1000, 0.99, 100) == [0]
|
|
|
|
def test_handles_empty(self):
|
|
matrix = np.zeros((1, 1))
|
|
assert simulated_annealing(matrix, [], 1000, 0.99, 100) == []
|
|
|
|
def test_does_not_mutate_input_indices(self):
|
|
n = 6
|
|
matrix = asymmetric_matrix(n, seed=1)
|
|
indices = list(range(n))
|
|
simulated_annealing(matrix, indices, 1000, 0.99, 100)
|
|
assert indices == list(range(n))
|