Author: way0utwest

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.