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