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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE #temp; CREATE TABLE #temp ( Person VARCHAR(20), H_Units INTEGER, SitsNextTo VARCHAR(20) ); CREATE INDEX IX_1 ON #temp (Person, SitsNextTo, H_Units); INSERT INTO #temp (Person, H_Units, SitsNextTo) SELECT LEFT(Item, CHARINDEX(' ', Item)-1) AS Person , CASE WHEN CHARINDEX('gain', Item) > 0 THEN 1 ELSE -1 END * CONVERT(INTEGER, SUBSTRING(Item, caNum.Pos, caNum2.Pos - caNum.Pos)) AS H_Units , REPLACE(SUBSTRING(Item, CHARINDEX(' to ', Item) + 4, 8000), '.', '') AS SitsNextTo FROM OPENROWSET(BULK 'D:\AdventOfCode\Day13.txt', SINGLE_CLOB) InputFile(FileText) CROSS APPLY Sandbox.dbo.DelimitedSplit8K(REPLACE(InputFile.FileText, CHAR(10), ''), CHAR(13)) CROSS APPLY (VALUES (PATINDEX('%[0-9]%', Item))) caNum(Pos) CROSS APPLY (VALUES (CHARINDEX(' ', Item, caNum.Pos))) caNum2(Pos) WHERE Item > ''; |
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:
|
19 20 21 22 23 |
IF OBJECT_ID('tempdb.dbo.#temp2') IS NOT NULL DROP TABLE #temp2; CREATE TABLE #temp2 (Person VARCHAR(20) PRIMARY KEY CLUSTERED); INSERT INTO #temp2 SELECT DISTINCT Person FROM #temp; |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
WITH cteAllPossibleSeatingCombos AS ( -- join the nums cte together 8 times, but ensure that each one does not have a value that any of the other joins are already using SELECT t1.Person AS Person1 , t2.Person AS Person2 , t3.Person AS Person3 , t4.Person AS Person4 , t5.Person AS Person5 , t6.Person AS Person6 , t7.Person AS Person7 , t8.Person AS Person8 -- assign a row number to be the table seating arrangement , ROW_NUMBER() OVER (ORDER BY t1.Person, t2.Person, t3.Person, t4.Person, t5.Person, t6.Person, t7.Person, t8.Person) AS RN FROM #temp2 t1 JOIN #temp2 t2 ON t1.Person <> t2.Person JOIN #temp2 t3 ON t1.Person <> t3.Person AND t2.Person <> t3.Person JOIN #temp2 t4 ON t1.Person <> t4.Person AND t2.Person <> t4.Person AND t3.Person <> t4.Person JOIN #temp2 t5 ON t1.Person <> t5.Person AND t2.Person <> t5.Person AND t3.Person <> t5.Person AND t4.Person <> t5.Person JOIN #temp2 t6 ON t1.Person <> t6.Person AND t2.Person <> t6.Person AND t3.Person <> t6.Person AND t4.Person <> t6.Person AND t5.Person <> t6.Person JOIN #temp2 t7 ON t1.Person <> t7.Person AND t2.Person <> t7.Person AND t3.Person <> t7.Person AND t4.Person <> t7.Person AND t5.Person <> t7.Person AND t6.Person <> t7.Person JOIN #temp2 t8 ON t1.Person <> t8.Person AND t2.Person <> t8.Person AND t3.Person <> t8.Person AND t4.Person <> t8.Person AND t5.Person <> t8.Person AND t6.Person <> t8.Person AND t7.Person <> t8.Person ), cte2SeatingCombosPivoted AS ( -- put each number into a separate row to make the subsequent join easier SELECT ca.RN, ca.SeatingPos, ca.PersonAtSeat, ca.PersonAtLeft, ca.PersonAtRight FROM cteAllPossibleSeatingCombos CROSS APPLY (VALUES (RN, 1, Person1, Person8, Person2), (RN, 2, Person2, Person1, Person3), (RN, 3, Person3, Person2, Person4), (RN, 4, Person4, Person3, Person5), (RN, 5, Person5, Person4, Person6), (RN, 6, Person6, Person5, Person7), (RN, 7, Person7, Person6, Person8), (RN, 8, Person8, Person7, Person1) ) ca(RN, SeatingPos, PersonAtSeat, PersonAtLeft, PersonAtRight) ), cte3SeatingCombosWithUnits AS ( SELECT RN , t1.H_Units + t2.H_Units AS TotalUnits FROM cte2SeatingCombosPivoted c JOIN #temp t1 ON t1.Person = c.PersonAtSeat AND t1.SitsNextTo = c.PersonAtLeft JOIN #temp t2 ON t2.Person = c.PersonAtSeat AND t2.SitsNextTo = c.PersonAtRight ), cte4SeatingTotals AS ( SELECT RN, SUM(TotalUnits) AS TableTotalUnits FROM cte3SeatingCombosWithUnits GROUP BY RN ) SELECT MAX(TableTotalUnits) AS HighestHappinessUnits FROM cte4SeatingTotals; |
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):
|
1 2 3 4 5 6 7 8 |
INSERT INTO #temp (Person, H_Units, SitsNextTo) SELECT dt.Person, 0, t2.Person FROM (VALUES ('Me')) dt(Person), #temp2 t2 UNION ALL SELECT t2.Person, 0, dt.Person FROM (VALUES ('Me')) dt(Person), #temp2 t2 INSERT INTO #temp2 (Person) VALUES ('Me'); |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
, t9.Person AS Person9 -- added for part 2 , ROW_NUMBER() OVER (ORDER BY t1.Person, t2.Person, t3.Person, t4.Person, t5.Person, t6.Person, t7.Person, t8.Person, t9.Person) AS RN JOIN #temp2 t9 ON t1.Person <> t9.Person AND t2.Person <> t9.Person AND t3.Person <> t9.Person AND t4.Person <> t9.Person AND t5.Person <> t9.Person AND t6.Person <> t9.Person AND t7.Person <> t9.Person AND t8.Person <> t9.Person CROSS APPLY (VALUES (RN, 1, Person1, Person9, Person2), (RN, 2, Person2, Person1, Person3), (RN, 3, Person3, Person2, Person4), (RN, 4, Person4, Person3, Person5), (RN, 5, Person5, Person4, Person6), (RN, 6, Person6, Person5, Person7), (RN, 7, Person7, Person6, Person8), (RN, 8, Person8, Person7, Person9), (RN, 9, Person9, Person8, Person1) ) ca(RN, SeatingPos, PersonAtSeat, PersonAtLeft, PersonAtRight) |
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.
