In January 2016, I stumbled across a little coding challenge called Advent Of Code.
Like a virtual advent calendar, you get to “unwrap” a new coding challenge each day in December until Christmas. Each challenge also has 2 parts, where the second part builds on the first. When I stumbled across the AoC, Advent was over, but the coding challenges remained. So over the next few weeks I got
stuck into sharpening my skills and solving the puzzles. The challenges are language agnostic, so I chose to solve them using T-SQL. I found that some challenges were very well suited to being solved in this way, and some were extremely tedious. But I thoroughly enjoyed completing my advent calendar.
Last year, I was ready for the challenge, and at the start of the month, I was incredibly motivated to take it quite seriously. I even managed to get into the top 100 (fastest correct answers) on day 6
T-SQL. Even managed a top 100 today 😊pic.twitter.com/xFg1heXwUS
— James McGillivray (@JamesMcG_MSBI) December 6, 2016
Unfortunately, December 2016 turned out to be a pretty rough one in my personal life, so I didn’t complete the challenge. I would like to go back at some point and do that. But that’s another story.
Anyway, today was the start of Advent of Code 2017. Thanks to Eric Wastl (@ericwastl) for the idea and the effort that goes into making it a fun way to refine your skills or learn new ones. I’m going to attempt to complete it using T-SQL again, and I thought I’d post my solutions and the thinking behind my solutions each day. There are often many ways to solve these problems, and I’m sure that my solution will often be clumsy and cumbersome, but it’s a fun challenge and I will solve it the first way I can think of.
The Challenge: Part 1
Today, we were given a sequence of digits, and asked to calculate the sum of characters where a character matches the character immediately following it. In addition, the string is “circular”, so the first character actually follows the last character.
My Solution (download)
My initial thought when I read the problem was to loop through the string and compare digits, but since I’m going to be coding in T-SQL, I think it’s appropriate to try and use set-based logic wherever I can. Thankfully, using set-based logic and some nifty SQL window functions actually makes this problem quite easy to solve.
Oftentimes when you need a “loop” type solution in SQL, the answer lies in a Cursor While Loop Tally Table.
/* In reality, I have a tally table which lives in a Utilities database. But for a quick reference, you can easily create a tally table with the code snippet below. */ declare @tallytable table (Number int) insert into @tallytable select top 100000 row_number() over (order by a.table_name) from INFORMATION_SCHEMA.COLUMNS as a cross join INFORMATION_SCHEMA.COLUMNS as b
I then used the tally table and the substring function to split the string into a table of individual characters.
declare @text nvarchar(max) = ''
select Number as RowID,
substring(@text,Number,1) as Item
from @tallytable
where Number <= len(@text)
Right, time for the windowing function (he says with a smile). For each row in my table, I want to get the value of the row preceding it (to compare the characters). Before I knew about windowing functions, I would have done a self-join, with an ON clause of a.RowID = b.RowID – 1, or something similar. But actually, the LAG function does exactly what we’re looking for. The first parameter is the column which we want the previous value of (in this case, Item). The second parameter (offset) is how many rows back in the set we’d like to go (in this case, 1). The final parameter is just the value to default the column to, if there isn’t a row with the offset specified. In our scenario, only the first row will not have a related row, so I am going to set the default parameter to the value of the last character in my string (which was 8). As with all windowing functions, the OVER clause specifies that we are using the entire set as our window, and, because the LAG function is order specific, an ORDER BY clause must be present.
select RowID,
Item,
LAG(Item,1,8) over (order by RowID) as NextRow
from SplitList
Once I have a table with a row for each character, and the next character in a column on the same row, calculating the total is pretty simple.
select sum(case when Item = NextRow then Item else 0 end) as TotalMatching1 from NextCharacter
This worked first time, and I was pretty happy with it. It also unlocked the second part of the puzzle, in which, instead of offsetting the character by one, I needed to go exactly halfway around the string and add up the characters that then matched.
I required 2 minor changes to my code to make this work. Firstly, I had to take the first half of the string, and add it to the end of my current string to mimic the “round string” idea. In the first part, I only had one row worry about, so I solved it with the default parameter of the LAG function.
select * from SplitList union select RowID + len(@text), Item from SplitList where RowID <= (len(@text) / 2)
Secondly, I had to change the offset value in the lag function. This was really easy.
select RowID,
Item,
LAG(Item, <span style="color: #ff0000;" data-mce-style="color: #ff0000;">len(@text)</span> / 2,null) over (order by RowID) as LoopRound
from LoopRound
Everything else was exactly the same, and I was awarded my stars for completing the challenges.
Looking forward to tomorrow’s challenge. I may even get up early and try answer it as it’s released
One comment