Solves for an advent calendar that maximises the average (euclidean) distance between consecutive entries, assuming they're placed in a 4x6 grid.

solve_advent_calendar_using_tsp.py

import numpy as np
import math
import matplotlib.pyplot as plt
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

vertices = tuple(range(25))
dummy_vertex = 24

def i_from_xy(x, y):
    return y * 6 + x

def xy_from_i(i):
    y = i // 6
    x = i - y * 6
    return x, y

def solve_tsp(cost_matrix):
    n = len(cost_matrix)
    dummy = n - 1  # e.g. 24

    manager = pywrapcp.RoutingIndexManager(n, 1, 0)  # depot = 0
    routing = pywrapcp.RoutingModel(manager)

    def cost_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(cost_matrix[from_node][to_node])

    transit_callback_index = routing.RegisterTransitCallback(cost_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    solution = routing.SolveWithParameters(search_parameters)
    if not solution:
        return None, None

    # Extract tour as a cycle
    index = routing.Start(0)
    tour = []
    while not routing.IsEnd(index):
        node = manager.IndexToNode(index)
        tour.append(node)
        index = solution.Value(routing.NextVar(index))

    # Rotate so that the tour starts at the dummy node
    if dummy in tour:
        k = tour.index(dummy)
        tour = tour[k:] + tour[:k]

    # remove dummy
    return tour[1:]

precision = 1e8

print("building cost matrix for tsp...")

metric = "manhattan"

def compute_metric(x1, y1, x2, y2):
    if metric == "manhattan":
        return abs(x1 - x2) + abs(y1 - y2)
    elif metric == "euclidean":
        return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    elif metric == "square-euclidean":
        return (x1 - x2) ** 2 + (y1 - y2) ** 2
    else:
        raise Exception(f"Unknown metric {metric!r}")

# build a cost matrix
cost_matrix = np.zeros((25, 25), dtype=int)
for i in range(24):
    x1, y1 = xy_from_i(i)
    for j in range(24):
        x2, y2 = xy_from_i(j)
        distance = compute_metric(x1, y1, x2, y2)
        edge_length = round(distance * precision)
        cost_matrix[i, j] = 0 if i == j else edge_length

# invert edge weights and make them all positive
cost_matrix = cost_matrix.max() - cost_matrix
# print(cost_matrix)

print("solving tsp...")
tsp_tour = solve_tsp(cost_matrix)

print("tsp success!")
print(f"{tsp_tour=}")

def tour_to_arrangement(tour):
    arr = []
    for i in tour:
        x, y = xy_from_i(i)
        arr.append([x, y])
    return np.array(arr)

def score_arrangement(arrangement):
    distances = []
    for (x1, y1), (x2, y2) in zip(arrangement, arrangement[1:]):
        distances.append(compute_metric(x1, y1, x2, y2))
    return sum(distances) / len(distances)

def print_arrangement(arrangement):
    calendar = np.zeros((4, 6), dtype=int)
    for i, (x, y) in enumerate(arrangement):
        calendar[y, x] = i + 1
    print(calendar)

def save_arrangement_img(arr, title=None):
    fig, ax = plt.subplots(figsize=(6, 4))  # wider than tall: 6×4

    # 6 columns (0..5) → need grid lines at 0..6
    # 4 rows    (0..3) → need grid lines at 0..4
    ax.set_xlim(0, 6)
    ax.set_ylim(0, 4)
    ax.set_xticks(np.arange(0, 7))
    ax.set_yticks(np.arange(0, 5))
    ax.grid(which='major')

    # origin at top-left: y=0 at top, y=3 at bottom
    ax.invert_yaxis()

    # place day numbers centered in each cell
    for day, (x, y) in enumerate(arr, start=1):
        ax.text(x + 0.5, y + 0.5, str(day),
                ha='center', va='center', fontsize=14)

    # no tick labels
    ax.set_xticklabels([])
    ax.set_yticklabels([])
    ax.set_aspect('equal')

    score = score_arrangement(arr)

    if title is not None:
        title = f"{title} (avg_len={score:.08f})"
    else:
        title = str(score)

    ax.set_title(title)
    plt.tight_layout()
    plt.savefig(f"auto-exports/{title}.png")

arrangement = tour_to_arrangement(tsp_tour)
score = score_arrangement(arrangement)
print(f"cycle_tour_score={score}")

print()
print_arrangement(arrangement)

# save_arrangement_img(arrangement, title=f"best {metric}")