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 14. In this challenge, Santa is evaluating his reindeer, so he’s sending them through Reindeer Olympics. The reindeer can all fly at high speeds… but that comes at a cost where they need to rest also. In Part 1 of this challenge, Santa wants to find out which of the reindeer is the fastest. The supplied list tells the speed and length of time that each reindeer can fly at, and how long it must rest after that burst. So Santa sends the reindeer to a race, and he wants to know the distance the fastest reindeer traveled in 2503 seconds. Yeah, that’s a weird number all right. Santa’s elves have determined that this is the minimum time in order to get accurate results.
In the following code, the first cte imports the test data and uses the PATINDEX, CHARINDEX and SUBSTRING functions to find key parts of the string, and then extract the data for the reindeer. The second cte uses this data to calculate how far each reindeer travels during the time, and then the query just returns the longest distance.
|
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 |
WITH cte AS ( SELECT LEFT(Item, CHARINDEX(' ', Item)-1) AS Reindeer , CONVERT(NUMERIC(5,1), SUBSTRING(Item, caRate.Pos, caRate2.kmPos-caRate.Pos-1)) AS Speed , CONVERT(NUMERIC(5,1), SUBSTRING(Item, caRate2.kmPos + 8, caRate2.SecondPos - caRate2.kmPos - 8)) AS Duration , CONVERT(NUMERIC(5,1), REPLACE(SUBSTRING(Item, caRate2.RestPos + 9, 8000), ' seconds.', '')) AS Rest FROM OPENROWSET(BULK 'D:\AdventOfCode\Day14.txt', SINGLE_CLOB) InputFile(FileText) CROSS APPLY Sandbox.dbo.DelimitedSplit8K(REPLACE(InputFile.FileText, CHAR(10), ''), CHAR(13)) ds CROSS APPLY (VALUES (PATINDEX('%[0-9]%', Item))) caRate(Pos) CROSS APPLY (VALUES (CHARINDEX(' ', Item, caRate.Pos), CHARINDEX('km', Item), CHARINDEX('seconds', Item), CHARINDEX('rest', Item)) ) caRate2(Pos, kmPos, SecondPos, RestPos) ), cte2 AS ( SELECT (FLOOR(ca2.Cycles)*Speed*Duration) + (CASE WHEN ca3.TimeLeft > cte.Duration THEN cte.Duration ELSE ca3.TimeLeft END * cte.Speed) AS Distance FROM cte CROSS APPLY (VALUES (2503)) ca1(TimeLimit) CROSS APPLY (VALUES (ca1.TimeLimit/(cte.Duration+cte.Rest))) ca2(Cycles) CROSS APPLY (VALUES (ca1.TimeLimit - (FLOOR(ca2.Cycles) * (cte.Duration+cte.Rest)))) ca3(TimeLeft) ) SELECT MAX(Distance) DistanceTraveled FROM cte2; |
The hardest part of this code is the formula that determines the distance that the reindeer travels. Starting off in the CROSS APPLY lines, I first introduce the time interval so that it can then be referenced in multiple locations later. I could have used the hard coded value in all of those locations, but I’m expecting that the part 2 will do something involving changing the time, and I’m taking steps now to make it easier later. The second CROSS APPLY calculates the number of cycles where that reindeer can move. The cycle is the time limit divided by the sum of the active moving and resting times. The third cte calculates how much time is left where the reindeer can travel after the last cycle. The code utilizes all of this information to calculate the distance that the reindeer traveled. It starts off with the number of cycles times the speed and duration. It then checks to see if the time left is longer that the duration the reindeer can fly before needing to rest, and determines whether it needs to use the active duration time or the time left. Once this has been determined, it is multiplied by the speed, and this result is added to the prior calculation for the total distance that the reindeer traveled during this time frame.
For part 2, Santa realizes that this scoring isn’t that good of a true indicator, so he decides to go to a point system. At each second of the race, the reindeer in the lead gets a point, and if multiple reindeer are tied then they both get a point. At the end of the race, the reindeer in the lead in the winner. For this, we need to return the number of points that the winning reindeer received.
For this solution, the code starts off with a dynamic tally table. The tally table is restricted to 2503 rows – one for each second. The code next (in cte) extracts the data from the input file just as in part 1. In cte2, the distance that each reindeer has traveled so far is calculated for each second. This is different from above by cross-joining to the tally table, and using this number to calculate the distance for that second. In cte3, the code calculates the reindeer in the lead at that second. Since multiple reindeer can be tied, the RANK function is used so that those ties will both be marked as being at #1 for that second. The partition by clause is used to recalculate the winner for each second, and by ordering by the distance descending, the reindeer(s) that has traveled the furthest are ranked with a value of 1. The next cte (cte4) gets the distinct list of reindeers that are ranked 1 for any time slot, and the query finally counts for each reindeer the number of times that it was leading during the race. By ordering this in descending order, and getting just the top row, we have returned the number of points that the winning reindeer has.
|
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 |
WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT TOP (2503) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) ,cte AS ( SELECT LEFT(Item, CHARINDEX(' ', Item)-1) AS Reindeer , CONVERT(NUMERIC(5,1), SUBSTRING(Item, caRate.Pos, caRate2.kmPos-caRate.Pos-1)) AS Speed , CONVERT(NUMERIC(5,1), SUBSTRING(Item, caRate2.kmPos + 8, caRate2.SecondPos - caRate2.kmPos - 8)) AS Duration , CONVERT(NUMERIC(5,1), REPLACE(SUBSTRING(Item, caRate2.RestPos + 9, 8000), ' seconds.', '')) AS Rest FROM OPENROWSET(BULK 'D:\AdventOfCode\Day14.txt', SINGLE_CLOB) InputFile(FileText) CROSS APPLY Sandbox.dbo.DelimitedSplit8K(REPLACE(InputFile.FileText, CHAR(10), ''), CHAR(13)) ds CROSS APPLY (VALUES (PATINDEX('%[0-9]%', Item))) caRate(Pos) CROSS APPLY (VALUES (CHARINDEX(' ', Item, caRate.Pos), CHARINDEX('km', Item), CHARINDEX('seconds', Item), CHARINDEX('rest', Item)) ) caRate2(Pos, kmPos, SecondPos, RestPos) ), cte2 AS ( SELECT * , (FLOOR(ca2.Cycles)*Speed*Duration) + (CASE WHEN ca3.TimeLeft > cte.Duration THEN cte.Duration ELSE ca3.TimeLeft END * cte.Speed) AS Distance FROM cte CROSS JOIN Tally CROSS APPLY (VALUES (Tally.N/(cte.Duration+cte.Rest))) ca2(Cycles) CROSS APPLY (VALUES (Tally.N - (FLOOR(ca2.Cycles) * (cte.Duration+cte.Rest)))) ca3(TimeLeft) ), cte3 AS ( SELECT * , RANK() OVER (PARTITION BY N ORDER BY Distance DESC) AS LeaderThisN FROM cte2 ), cte4 AS ( SELECT DISTINCT N, LeaderThisN FROM cte3 ) SELECT TOP (1) Reindeer, COUNT(*) AS Quantity FROM cte3 WHERE LeaderThisN = 1 GROUP BY Reindeer ORDER BY Quantity DESC; |
This completes day 14. Come back tomorrow to see how day 15 is solved in T-SQL!
