Advent of Code 2015 - Day 13: Knights of the Dinner Table

Part 1

Description

Solution

The problem is similar to the traveling salesman problem, or the problem in day 9. Only in today's problem, it wraps around. So, I used the similar approach. 

I split the input into for different parts: Name, gain/lose, happiness, and neighbor. Then, I put those into a 8×8 table, associating with each name and happiness point they get when sitting next to others. then, I make a permutations of 8 numbers, according to the seating arrangements possible, and counts the accumulated happiness point. Columns titled left are for points gained with neighbor in the left, and columns titled right are for points gained from neighbor in the right. And then, I just added them up and find the largest number.

Part 2

Description

Solution

For the part 2, I just have to modify my table into 9×9 table and make another permutation (now of 9) and do the rest as in part 1. Or, since it is a round table, I can add one column on the permutation from the first part and put my name there and find the largest sum.