Advent of Code 2015 Day 13

— Day 13: Knights of the Dinner Table —

You have to decide how to seat people for Christmas dinner.

What is the total change in happiness for the optimal seating arrangement of the actual guest list?

import numpy as np
import pandas as pd
from python_tsp.exact import solve_tsp_dynamic_programming

with open('data-2015-13.txt', 'r') as f:
    inp = f.read().splitlines()

This feels to me like a TSP with two weights per link/edge/seating combo.

seat_list = [x.split(' ') for x in inp]

seat_info = [[x[0], x[-1][:-1], x[2], x[3]] for x in seat_list]

names = list(set([x[0] for x in seat_info]))
names.sort()

df = pd.DataFrame(0, 
                  index=pd.Index(names, name='Seats'),
                  columns=pd.Index(names, name='Seats'))

# allocate our arrangement
for s in seat_info:
    if s[2] == 'gain':
        df.loc[s[0],s[1]] = -1 * int(s[3])
    else: 
        df.loc[s[0],s[1]] = int(s[3])


# but we need to make this symmetrical
# not needed for the optimisation, but for the proper input

df2 = df.transpose()

df3 = (df + df2).to_numpy()

df3

array([[   0,  -42,    9,   46,  140,    6,    6, -131],
       [ -42,    0,  160,   33,  -87, -132,   -5,    9],
       [   9,  160,    0,  116, -195,  -98,   -1,  -43],
       [  46,   33,  116,    0,  -33,   88,  -94,   39],
       [ 140,  -87, -195,  -33,    0, -118,   37,   13],
       [   6, -132,  -98,   88, -118,    0,   -9,  165],
       [   6,   -5,   -1,  -94,   37,   -9,    0,   -8],
       [-131,    9,  -43,   39,   13,  165,   -8,    0]])

Now for the solver. Actually - go back and make gain negative, because we want to maximise happiness which is minimise in this array.

permutation, distance = solve_tsp_dynamic_programming(df3)
permutation
distance


for e, p in enumerate(permutation[:-1]):
    df3[permutation[e]][permutation[e+1]]
   
# 733 

— Part Two —

Actually, you need to seat yourself too.

What is the total change in happiness for the optimal seating arrangement that actually includes yourself?

df4 = np.c_[df3, np.zeros(8)]

df4 = np.r_[df4, [np.zeros(9)]]

permutation, distance = solve_tsp_dynamic_programming(df4)
permutation
distance

# 725

np.float64(-725.0)