Tag: AdventofCode

Advent of Code 2017 Day 4–#SQLNewBlogger
Another post for me that is simple and hopefully serves as an example for people trying to get blogging as #SQLNewBloggers.

This is day 4 of the Advent of Code 2017. If you want to read about the puzzles, start with Day 1.

This is Day 4, which deals with checking a series of passphrases for duplicates. The idea is that for some input, each of the “words” in the string must be unique. This means that if I have a phrase of “dog cat horse”, it’s valid. If I have “dog cat bird cat”, it’s invalid.

This feels like an easy thing to do in SQL. Let’s begin.

First, I’ll build a table and load some data.
```
CREATE TABLE Day4
(
     passphrase VARCHAR(100)
)
GO
INSERT dbo.Day4
(
     passphrase
)
VALUES
    ('aa bb cc dd ee' )
  , ('aa bb cc dd aa')
  , ('aa bb cc dd aaa')
```
This is the test set. In this set, there are two values that are valid and one that isn’t. I need to figure out which is which.

This seems like a perfect place to use String_Split(). Since this is a small set (512 rows), performance isn’t a big concern. If it were, I’d be moving to use Jeff Moden’s string splitter.

For my tests, I decided to try something quick and dirty. I built a quick inline TVF to return string_split values. This is the code:
```
CREATE FUNCTION dbo.words
     (@input AS VARCHAR(100))
RETURNS TABLE
AS
RETURN ( SELECT value FROM STRING_SPLIT(@input, ' ') AS ss )
```
This made things easier for me to read. I like seeing the code clean, and this way I could easily most to a custom version of Jeff’s code if I wanted.

I quickly tried a short CTE with a CROSS APPLY to get the sets of rows that didn’t have unique passphrases. I thought this was easier since I know these are incorrect. If I look for corrects, it’s a harder issue as I’ll have counts of 1 in both correct and incorrect strings.
```
WITH ctePass
AS
(
SELECT d.passphrase 
        , ss.value, 
        cnt = COUNT(*)
FROM day4 AS d
     CROSS APPLY dbo.words(d.passphrase) AS ss
--WHERE d.passphrase = 'aa bb cc dd ee'
GROUP BY d.passphrase, ss.value 
HAVING COUNT(*) > 1
)
```
I also added a CTE that just gets me the total count.
```
, cteCount
AS
(SELECT total = COUNT(*) FROM day4)
```
Next, I added a CTE that would get my unique passphrases from the first CTE.
```
, cteUnique
AS
(
SELECT ctePass.passphrase
, cnt = COUNT(cnt) 
  FROM ctePass
  GROUP BY ctePass.passphrase
  )
```
Finally, I subtract the invalids from the total to get the vlaids. This gave me the answer that solved the puzzle.
```
SELECT total - COUNT(*) FROM cteUnique, cteCount
GROUP BY cteCount.total
```
Now let’s load the actual data. I cut and pasted data into a file. Let’s load that.
```
TRUNCATE TABLE day4
GO
BULK INSERT dbo.Day4 FROM 'e:\Documents\GitHub\AdventofCode\2017\Day4\Day4_Input.txt'
GO
SELECT 
  *
  FROM dbo.Day4 AS d
```
I can see I have 512 rows in my table, so my result must be between 1 and 512. When I ran this, I got the correct result.

A slight admission here. I misread at first, so I didn’t have the total and just got the 57. When that didn’t work, I re-read things and realized this. I tried to check for the valids, but realized that it was simpler if I just subtracted.

Part II

Part II is tricky, and I made a mistake the first time I tried to solve this. It took a bit, but I eventually figured out the issue.

In this part, we have to avoid anagrams. That means if the phrase as ‘car’ and ‘rac’, it’s invalid. Getting anagrams is tricky, and I looked around to find a post on SO that covers this. I adapted that code from Pawel Dyl to search for anagrams.

My first task was to put this into a function:
```
CREATE OR ALTER FUNCTION dbo.CheckAnagram
     (@w1 VARCHAR(50)
     , @w2 VARCHAR(50)
)
RETURNS int
AS
begin

declare @r INT;

WITH Src
AS
(
SELECT T.W1 ,
        T.W2
FROM
(
     VALUES
         (@w1, @w2)
) AS T (W1, W2)
) ,
      Numbered
AS
(
SELECT Src.W1 ,
        Src.W2 ,
        Num = ROW_NUMBER() OVER (ORDER BY (SELECT 1))
FROM Src
) ,
      Splitted
AS
(
SELECT Num ,
        Word1 = W1 ,
        Word2 = W2 ,
        L1 = LEFT(W1, 1) ,
        L2 = LEFT(W2, 1) ,
        W1 = SUBSTRING(W1, 2, LEN(W1)) ,
        W2 = SUBSTRING(W2, 2, LEN(W2))
FROM Numbered
UNION ALL
SELECT Num ,
        Word1 ,
        Word2 ,
        L1 = LEFT(W1, 1) ,
        L2 = LEFT(W2, 1) ,
        W1 = SUBSTRING(W1, 2, LEN(W1)) ,
        W2 = SUBSTRING(W2, 2, LEN(W2))
FROM Splitted
WHERE LEN(W1) > 0
       AND LEN(W2) > 0
) ,
      SplitOrdered
AS
(
SELECT Splitted.Num ,
        Splitted.Word1 ,
        Splitted.Word2 ,
        Splitted.L1 ,
        Splitted.L2 ,
        Splitted.W1 ,
        Splitted.W2 ,
        LNum1 = ROW_NUMBER() OVER (PARTITION BY Num ORDER BY L1) ,
        LNum2 = ROW_NUMBER() OVER (PARTITION BY Num ORDER BY L2)
FROM Splitted
)
SELECT @r =  CASE
                   WHEN COUNT(*) = LEN(S1.Word1)
                        AND COUNT(*) = LEN(S1.Word2) THEN
                       1
                   ELSE
                       0
               END
FROM SplitOrdered AS S1
     JOIN
     SplitOrdered AS S2
         ON S1.L1 = S2.L2
            AND S1.Num = S2.Num
            AND S1.LNum1 = S2.LNum2
GROUP BY S1.Num ,
          S1.Word1 ,
          S1.Word2

IF @r IS NULL 
  SET @r = 0
RETURN @r
end
GO
```
Next, I wanted to get a list of items to check. Again, STRING_SPLIT is what I used, but a Jeff’s code works as well. I decided to use another function, which will split the string and then do a cross join to run both combinations of works against each other to check for anagrams.
```
CREATE OR ALTER FUNCTION dbo.SplitandCheck
(@string AS VARCHAR(100))
RETURNS int
AS
BEGIN
DECLARE @r INT = 0;

WITH mycte
AS
(
SELECT checks = CASE WHEN a.value = b.value then 0
ELSE dbo.CheckAnagram(a.value, b.value)
end
FROM STRING_SPLIT(@string, ' ') AS a CROSS JOIN STRING_SPLIT(@string, ' ') AS b
)
SELECT @r = SUM(a.checks)
FROM mycte a
```
This seemed to work, but when I got the final result with this code, it was wrong. Too high.
```
WITH mycte
AS
(
SELECT d.passphrase, IsAnagram = dbo.SplitandCheck(d.passphrase)
FROM dbo.Day4 AS d
)
SELECT mycte.IsAnagram, COUNT(*)
FROM mycte
--  WHERE mycte.IsAnagram = 0
GROUP BY mycte.IsAnagram
```
I had checked for 0s, but also included other results to try and debug my code. As I went through here, I realized that some fo the input data had a string like “oicgs rrol zvnbna rrol”. Clearly “rrol is an anagram of “rrol”. Initially I was knocking those out as a cross join includes those anyway.

As a result, I added this code to my function.
```
IF @r = 0
AND EXISTS(
SELECT COUNT(*)
FROM STRING_SPLIT(@string, ' ') AS ss
GROUP BY ss.value
HAVING COUNT(*) > 1
)
SET @r = 1
```
This will check for duplicate values. If there are dups, then clearly we have an issue already.

This give me a set of items with 1 dup as well as those with anagrams. The 0 result is the count of valid passphrases.
January 18, 2018

tsqlt Tests for Advent of Code 2017 Day 2

This is day 2 of the Advent of Code 2017. If you want to read about the puzzles, start with Day 1. As I worked through the puzzles, I decided that I should be testing using their test sets and solving the issues that way. This lets me use the sample data, but also add in my own sets to cover strange situations.

Here are the tests that I used for each part of day 2.

Part I

This wasn’t a tough puzzle, and the test is fairly simple. I had a function that solves the puzzle with the help of input. My test just sets up the sample input in the table, tab delimited, and then calls the function to calculate the total.

EXEC tsqlt.NewTestClass @ClassName = N'tDay2'
go
CREATE OR ALTER PROCEDURE tDay2.[test day2 sample input]
AS
BEGIN
     ---------------
     -- Assemble
     ---------------
     DECLARE
         @expected INT  18,
         @actual   int;
     
     EXEC tsqlt.faketable @TableName = 'Day2', @SchemaName = 'dbo';
     INSERT dbo.Day2 (DataRow)
      VALUES ('5    1    9    5')
           , ('7    5    3')
           , ('2    4    6    8')

    ---------------
     -- Act
     ---------------
     SELECT  @actual = SUM(b.diff)
      FROM day2 a
      CROSS APPLY dbo.AdventChecksum (a.DataRow) b

    ---------------
     -- Assert    
     ---------------
     EXEC tSQLt.AssertEquals
         @Expected = @expected,
         @Actual = @actual,
         @Message = N'An incorrect calculation occurred.';
END
GO
EXEC tsqlt.run 'tDay2.[test day2 sample input]';

Part II

The test here just calls a different function and has different input.

CREATE OR ALTER PROCEDURE tDay2.[test day2 b sample input]
AS
BEGIN
     ---------------
     -- Assemble
     ---------------
     DECLARE
         @expected INT = 9,
         @actual   int;
     
     EXEC tsqlt.faketable @TableName = 'Day2', @SchemaName = 'dbo';
     INSERT dbo.Day2 (DataRow)
      VALUES ('5    9    2    8')
           , ('9    4    7    3')
           , ('3    8    6    5')

    ---------------
     -- Act
     ---------------
     SELECT  @actual = SUM(b.divmatch)
      FROM day2 a
      CROSS APPLY dbo.AdventChecksum3 (a.DataRow) b

    ---------------
     -- Assert    
     ---------------
     EXEC tSQLt.AssertEquals
         @Expected = @expected,
         @Actual = @actual,
         @Message = N'An incorrect calculation occurred.';
END
GO
EXEC tsqlt.run 'tDay2.[test day2 b sample input]';

GO

January 13, 2018

Advent of Code 2017 Day 1–#SQLNewBlogger
Another post for me that is simple and hopefully serves as an example for people trying to get blogging as #SQLNewBloggers.

I like the Advent of Code. I stumbled on the site a few years ago and enjoyed working through some of the challenges in 2015. I tried solving them with three languages (Python, PoSh, and T-SQL) but only managed to get through about half the items before life got busy. Last year I was worn out and too busy to mess with the code.

This year I was busy in December when the puzzles came out, but decided to work through the puzzles again as a break from work and life, and to keep my mind flexible. I’ll do a series here, hopefully all 25, but here’s my view of Day 1.

Part 1

Each puzzle has two parts, and you need to solve part 1 to get part 2. In this case I need to take a list of input and compare each digit to the next digit and see if they match. If they do, then you add that digit to your sum.

This sounds like a perfect case to use the LEAD/LAG functions in SQL Server, so I did that. Since I get a long list of input, I also decided to use a string splitter. Here’s the first part where I split the string:
```
DECLARE @i VARCHAR(5000);
 --SET @i  = '1122';
 --SET @i  = '951344679963668529';

WITH myTally(n)
 AS
 (SELECT n = ROW_NUMBER() OVER (ORDER BY (SELECT null))
 FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) a(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) b(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) c(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) d(n)
 )
 , cteSplit (i)
 AS
 ( SELECT
 i = SUBSTRING(@i, n, 1)
 FROM myTally
 WHERE n <= LEN(@i)
 )

select i

from cteSplit
```
If you run this, you’ll get your @i string out a character at a time. This get’s me the data in a set of rows, similar to an array.

Now I need to compare each row with the next one, and I’ll use the LEAD function. My data is ordered, so I don’t need an order. That means I’m looking at this:
```
LEAD(i, 1) OVER (ORDER BY (SELECT NULL))
```
I’ll compare that with the current value and if they match, I’ll return the value. If not, I return a zero, adding nothing to the sum.

There is one special case. The list is circular, so if the last digit (when we get there) matches the first digit, I need to include that. I’ll add that as special FIRST_VALUE, LAST_VALUE function match. Here’s my code:
```
WITH myTally(n)
 AS
 (SELECT n = ROW_NUMBER() OVER (ORDER BY (SELECT null))
 FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) a(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) b(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) c(n)
 CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) d(n)
 )
 , cteSplit (i)
 AS
 ( SELECT
 i = SUBSTRING(@i, n, 1)
 FROM myTally
 WHERE n <= LEN(@i)
 )
 , datacte(j)
 AS
 (
 SELECT j = CASE WHEN i = LEAD(i, 1) OVER (ORDER BY (SELECT NULL))
 THEN cteSplit.i
 ELSE 0
 END
 FROM cteSplit
 UNION all
 SELECT TOP 1 j = CASE WHEN FIRST_VALUE(i) OVER (ORDER BY (SELECT NULL)) = LAST_VALUE(i) OVER (ORDER BY (SELECT NULL))
 THEN i
 ELSE 0
 end
 FROM cteSplit
 )
 SELECT SUM(j) FROM datacte
```
When I do this with the input string, I get a result. It happened to be right

Part II

Part II is a variation of Part I. Instead of looking at the next digit, I need to look halfway around the list. The list is an even number, so if it’s 10 digits long, I need to start with char 1 and look at char 6. If they are equal, add to sum. Then look at 2 and 7, and repeat. Since it’s a circular list, when I get to char 5, I look around to char 1. There’s an optimization here, but when I solved this, I decided to take an easy way out.

I first considered adding the first half of the list to the end and only running through the first len(input) characters. Then I thought, I could easily do a LAG. So, I modified my datacte query to do this:
```
, datacte(j, k, i, l, n)
 AS
 (
 SELECT j = CASE WHEN i = LEAD(i, @len) OVER (ORDER BY (SELECT NULL)) AND n <= @len
 THEN cteSplit.i
 ELSE 0
 END
 ,
 k = CASE WHEN i = LAG(i, @len) OVER (ORDER BY (SELECT NULL)) AND n > @len
 THEN cteSplit.i
 ELSE 0
 END

)
```
This quickly counts the matches up to the middle and then counts the next bunch.

There’s a better way, but I’ll leave you to figure that out in the comments.

In any case, I solved both of day 1. Now on to day 2 during the next break.
January 4, 2018

CROSS APPLY v InLine Functions

While working on the Advent of Code problems in SQL, I ran across something interesting. Day 4 involves hashing, which is done with the HASHBYTES function in SQL Server. This is a computation and given the problem, there is no good way to do this without brute force. The problem says

hash a specific string + an integer.
If the leftmost digits are 0 (5 or 6 of them), stop
increment the integer
repeat

Since a hash doesn’t lend itself to a pattern, you can’t start with 100,000 and determine if the integer you need is higher or lower. Instead you need to work through the integers.

I decided to try this with a tally table and hashing with TOP 1. BTW, TOP 1 makes a huge difference.

However, my structure was to query my tally table like this:

SELECT n
, HASHBYTES(‘MD5’, ‘iwrupvqb’ + CONVERT(VARCHAR(15), n))
FROM cteTally

This was in a second CTE, and in the main query I then use a WHERE clause to filter the list down to the entry with leading zeros. When I ran this, I noticed it was rather slow at first, at least, what I considered slow. I checked with a few other people that had solved the problem, and I found their times were faster than mine.

I wasn’t sure the brute force technique would benefit from a TOP clause, but I added a TOP 1 to the outer query. This made the entire process run much quicker, which is interesting. Apparently the filtering is collapsed across the tally table join with the hash computation and as soon as a valid match is found, this ends the calculations. My average went down by a factor of 10.

However, I wondered if moving the calculation to a join, with CROSS APPLY, would be quicker. I couldn’t imagine why, but I decided to try this. I moved the calcuation by changing the HASHBYTES calculation to a SELECT statement in a derived table for the CROSS APPLY and then taking the result of that as part of my column list. This changed my CTE to this:

SELECT n
, hb.hashvalue
FROM cteTally
CROSS APPLY (SELECT HASHBYTES(‘MD5’, ‘iwrupvqb’ + CONVERT(VARCHAR(15), n))) AS hb(hashvalue)

That resulted in a slightly faster query time. When I added a TOP to this, the times improved slightly from using HASHBYTES in the column list with a TOP. Intuitively this doens’t make sense, as it would seem the same number of function calls need to be completed, but the CROSS APPLY handles them a bit more efficiently. I’m sure someone has a much more in-depth understanding of the query optimizer here, and I won’t try to explain things myself. The times are close enough that I suspect some minor optimization from CROSS APPLY.

As a comparison, I also ran a brute force loop, with this code, that calculates the values sequentially until the result is determine. This should be equivalent to the results from TOP 1, and we find that they aren’t. The tally table solution with CROSS APPLY is much quicker.

DECLARE @t BIT = 1;
DECLARE @i INT = 0;
DECLARE @start DATETIME = GETDATE();
WHILE @t = 1
BEGIN
   IF LEFT( CONVERT(VARCHAR(50), HASHBYTES(‘MD5’, ‘iwrupvqb’ + CAST(@i AS VARCHAR(10))), 2), 6) = ‘000000’
     BEGIN
       SELECT @i
       SELECT @t = 0
     end
   SELECT @i = @i + 1
   –IF @i > 10000000
   — SELECT @t = 0
END
SELECT starttime = @start
     , seconds = DATEDIFF(SECOND, @start, GETDATE())
;

Here’s a summary of the code timings (averaged across 5 executions), for the second part of the puzzle, which looks for 6 leading zeros and has a result in the 9million range.

Query	Timings (sec)
Hashbytes in column list, no TOP	185.6
CROSS APPLY, no TOP	182.3
Hasbytes in columns list, TOP	17.8
CROSS APPLY with TOP	16.0
Brute Force, WHILE loop	33.8

Conclusion

The conclusion I’d take here is that CROSS APPLY ought to be a tool you keep in the front of your toolbox and use when you must execute a function for each row of a set of tables. This is one of the T-SQL techniques that I never learned early in my career (it wasn’t available), and I haven’t used much outside of looking for execution plans, but it’s a join capability I will certainly look to use in the future.

However, if you are using UDFs instead of system functions, I’d certainly recommend you read Adam Machanic’s post on Scalar Functions and CROSS APPLY, and perhaps you can change to ITVFs and get some great performance gains.

February 10, 2016

Tag: AdventofCode

Advent of Code 2017 Day 4–#SQLNewBlogger

Part II

tsqlt Tests for Advent of Code 2017 Day 2

Part I

Part II

Advent of Code 2017 Day 1–#SQLNewBlogger

Part 1

Part II

CROSS APPLY v InLine Functions

Conclusion