In my previous post, I introduced you to the Advent of Code programming challenge, and explained how I’m going through the days, solving both parts of each puzzle. Continuing on, today we have day 13. In this challenge, it’s time for the family dinner, and you’re in charge of the seating arrangements. There is one oval shaped table, and you have a list of how happy a particular person is to be seated next to every other person in the family (a quantified ranking happiness unit, which can be positive or negative). Your task is to come up with the seating arrangement that produces the highest overall happiness unit. The input for this task is here, and the answer to be supplied is the total of all of the happiness units for this optimal seating arrangement.

Each line in the input file is in the format “Alice would lose 57 happiness units by sitting next to Bob.” The “lose” will be either “lose” or “gain”. So the first step is to load the file in, and to split out the two names and the number of happiness units that will be had. I’m going to load the list into a temporary table:

This code starts off by loading the file (using the OPENROWSET function) and splitting it into individual lines. For each line, the second CROSS APPLY gets the position where any number starts at using the PATINDEX function, and the third CROSS APPLY gets the first space after this number using the CHARINDEX function. In the column list, the CHARINDEX function is used to find the first space. Everything prior to that is the persons name (PersonA). It then looks to see if the word “gain” is in the string. If so it uses the value 1; if not, it uses the value -1. This value is multiplied by the number that is extracted by the SUBSTRING function using the values from the two CROSS APPLY operations. Finally, we get the person that PersonA is sitting next to by looking for the string ” to “. Everything after this is the person that PersonA is sitting next to. However, each line also end with a period, so this is also removed.

If we think back to Day 9, Santa had to create an optimal traveling route between cities. To solve that, we had to get every possible route, and then compare the distance between the cities to get the shortest travel route. Today’s puzzle is pretty much the same thing, with one difference. The difference is that the distance between the two cities is the same whether we are going from CityA to CityB, or CityB to CityA. In this case, each person has a different happiness unit for sitting next to another person. So, Alice may lose 57 happiness units when sitting next to Bob (because he talks soooooo much), but Bob may gain 83 happiness units when sitting next to Alice (because she listens so well). Therefore, both of these need to be considered.

Just like in Day 9, we need to generate every possible combination of seating arrangements. In Day 9, I used numbers to represent the cities, but then I had to join back to this information to get the city name. Today, we’ll use the names of the people, so let’s start off by getting every distinct name from the list and inserting that into another temporary table:

This next step does all of the work. The first cte starts off by getting all possible seating arrangements by joining this table to itself eight times (once for each person). In the second cte, this data is pivoted so that each arrangement has a seating position number and person in that position. Concurrently with this step, it determines who this person is sitting next to, on both the left and right sides. The third cte joins back to the table with the happiness units to get the units on both the left, right and total for that person. The fourth cte sums up the total happiness units for each sitting arrangement, and finally the seating arrangement with the highest happiness unit is returned.

And there we have our optimal seating arrangement.

For part 2 of this puzzle, you realize that you forgot to seat yourself. After realizing this, and considering that you are such a neutral person, you decide that the happiness unit for everyone involved with you is zero. So, the first step is to add you to this mix (this should be performed between the first two blocks of code above):

Next, the code needs to be modified slightly to handle the additional person. In the “Get the seating arrangement with the highest total happiness units”, insert line 1 below after the Person8 line (insert it as line 12); replace the ROW_NUMBER() calculation (lines 13-15) with lines 2-4 below, insert lines 5-8 below after the join to t8 (starting at line 33). All three of these are in the cteAllPossibleSeatingCombos cte. Lastly, replace the CROSS APPLY in the cte2SeatingCombosPivoted (lines 38-46) with the one starting at line 9 below.

This concludes day 13, which means that we are over 50% through the Advent of Code challenges. Come back tomorrow to see my solution for Day 14.