Advent of Code

This guy by the name of Eric Wastl (t) created this neat web site called “Advent of Code“. It’s a… well, let’s let Eric describe it:

Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.

The full explanation is at https://adventofcode.com/2018/about.

These puzzles are nicely arranged in the format of a Christmas tree. Each level in the tree is a different programming challenge, and it has two parts (after completing the first part, the second part is shown to you). So I’ve decided to work through these, and to post a T-SQL solution for each of them.

I performed this challenge in 2015 (see the Advent of Code category), but I’ve either forgotten about it or was too busy to do this in subsequent years. This year, I’m making an effort to do this challenge again. One of my goals is to show how the pieces of code go together, so instead of just showing the final query for each part, I will go through this step-by-step.

Day 1, Part 1

Day 1 starts off with someone messing around with Santa, causing temporal issues, by changing the timeline in the past. You’re the best choice to fix it, and the head temporal elf outfits you with a device to fix the issues in the past. She sends you on your way, forgetting to calibrate the device. The device is showing a set of changes in frequency – in both positive and negative changes. Your task is to determine what the net frequency change is.

The first step is to download your input file. This consists of individual numbers on each line, as shown in this partial screen shot of the file (note: each person gets a different input file, with different results, so I’m only showing partial files and not the results):

The second step is to load this file in to SQL Server. I choose to use the OPENROWSET function:

SELECT  FileData
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData);

Unfortunately, this returns the entire file as one record:

I could go through the effort to set up a format file, but I’m just too lazy for that. So I decided to split this row into individual rows. You can use your string splitter of choice here. My code to split this ended up being (splitting on the CR, or CHAR(13)):

SELECT  ca.Item
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca;

Which returns the input file as:

The next step is to simply add these numbers together. To accomplish this, I convert the data to an integer and sum them up. First, convert to an integer:

Whoops, I’ve got a small issue. Looking at the error message, I can see that there is still a Line Feed (LF – CHAR(10)) in there. I’ll strip that out with the REPLACE function:

SELECT  CONVERT(INTEGER, REPLACE(ca.Item, CHAR(10), '')) AS Offset
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca;

And finally, I add these all up:

SELECT  SUM(CONVERT(INTEGER, REPLACE(ca.Item, CHAR(10), ''))) AS Offset
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca;

Once I enter this, I find out that this is the correct answer, and we have unlocked part 2.

Day 1, Part 2

In part 2, we process the list multiple times. In order to calibrate the device, you need to find the first frequency that repeats.

Since it starts at zero, it is possible that the first repeated frequency is zero. So the first step that I need to do is to start off the list with a zero. Additionally, I want to keep track of the ItemNumber of the list:

SELECT  0 AS ItemNumber, 0 AS Offset 
UNION ALL
SELECT  ca.ItemNumber, 
        CONVERT(INTEGER, REPLACE(ca.Item, CHAR(10), '')) AS Offset
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca;

For the next part, this list will repeat several times before a frequency repeats. I need to multiple this list many times, and keep track of what the resulting frequency is for each row. We multiply the list by creating a set of numbers, cross joining that set to itself a few times, and then assigning a sequential number to these rows, and a sequential row number, in order of the loop and ItemNumber in the loop is also assigned to the final duplicated result set:

WITH Loops1 AS
(
SELECT  LoopNbr
FROM(VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) dt(LoopNbr)
), Loops2 AS
(
SELECT  ROW_NUMBER() OVER (ORDER BY (t1.LoopNbr)) AS LoopNbr
FROMLoops1 t1  -- 10 rows
CROSS JOIN Loops1 t2  -- 100 rows
CROSS JOIN Loops1 t3  -- 1000 rows
), cte1 AS
(
SELECT  1 AS LoopNbr, 0 AS ItemNumber, 0 AS Offset 
UNION ALL
SELECT  Loops2.LoopNbr, 
                ca.ItemNumber, 
                CONVERT(INTEGER, REPLACE(ca.Item, CHAR(10), '')) AS Offset
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca
CROSS JOIN Loops2
)
SELECT  cte1.LoopNbr,
        cte1.ItemNumber, 
        cte1.Offset AS ColumnOffset, 
        SUM(cte1.Offset) OVER (ORDER BY cte1.LoopNbr, cte1.ItemNumber 
                               ROWS BETWEEN UNBOUNDED PRECEDING 
                                        AND CURRENT ROW) AS EffectiveFrequency,
        ROW_NUMBER() OVER (ORDER BY cte1.LoopNbr, cte1.ItemNumber) AS RN
FROMcte1
ORDER BY LoopNbr, ItemNumber;

At this point, we calculate the first and last row for each frequency by grouping the result set by the EffectiveFrequency. To get the first time the frequency repeats, include a predicate where the first and last are not the same row. Finally, the first repeated frequency will be the first row’s EffectiveFrequency when ordered by the max(row number):

WITH Loops1 AS
(
SELECT  LoopNbr
FROM(VALUES (0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) dt(LoopNbr)
), Loops2 AS
(
SELECT  ROW_NUMBER() OVER (ORDER BY (t1.LoopNbr)) AS LoopNbr
FROMLoops1 t1  -- 10 rows
CROSS JOIN Loops1 t2  -- 100 rows
CROSS JOIN Loops1 t3  -- 1000 rows
)
, cte1 AS
(
SELECT  1 AS LoopNbr, 0 AS ItemNumber, 0 AS Offset 
UNION ALL
SELECT  Loops2.LoopNbr, 
                ca.ItemNumber, 
                CONVERT(INTEGER, REPLACE(ca.Item, CHAR(10), '')) AS Offset
FROMOPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day01a.txt', SINGLE_CLOB) dt(FileData)
CROSS APPLY dbo.Split(dt.FileData, CHAR(13)) ca
CROSS JOIN Loops2
), cte2 AS
(
SELECT  cte1.LoopNbr,
cte1.ItemNumber, 
cte1.Offset AS ColumnOffset, 
SUM(cte1.Offset) OVER (ORDER BY cte1.LoopNbr, cte1.ItemNumber 
                                       ROWS BETWEEN UNBOUNDED PRECEDING 
                                                AND CURRENT ROW) AS EffectiveFrequency,
ROW_NUMBER() OVER (ORDER BY cte1.LoopNbr, cte1.ItemNumber) AS RN
FROMcte1
)
SELECT TOP (1) EffectiveFrequency, MIN(RN) AS FirstRN, MAX(RN) AS LastRN
FROMcte2
GROUP BY EffectiveFrequency
HAVING MIN(RN) <> MAX(RN)
ORDER BY LastRN;

Summary

And here we have a T-SQL solution for Day 1 of the Advent of Code challenge. The key tasks that we can learn from today are:

• Loading a file.
• Split a string on a delimiter.
• Including additional rows into a result set (adding the first zero with a UNION ALL).
• Multiplying (duplicating) a result set multiple times.
• Performing a running total calculation.
• Assigning a sequential number to a set of rows in a specific order.
• Use of the GROUP BY and HAVING clauses while performing an aggregation.

The post Advent of Code 2018 – Day 1 (Chronal Calibration) appeared first on Wayne Sheffield.