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 4. Since you can only see this if you are up to this level in the challenge, let me explain it to you. In part one of this puzzle, we are to take a given seed, and prefix that to a number to find the lowest number that will generate a MD5 hash that starts with five zeros.
There are three steps to this process:
- Generate a series of numbers. (does this sounds like a really good use for the virtual tally table to you?)
- Generate a MD5 hash with the seed and this number.
- Get the lowest number that generates a MD5 hash that starts with five zeros.
This time, I’ll show the code, and then explain it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
-- Part 1: get the lowest number that when prefixed by the specified input, returns a MD5 hash that starts with 5 zeros. -- use a dynamic tally table for the generation of numbers 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 ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) SELECT TOP (1) N, ca.HashResult FROM Tally -- use the HASHBYTES function to generate the hash CROSS APPLY (SELECT HASHBYTES('MD5', 'iwrupvqb' + CONVERT(VARCHAR(15), N))) AS ca(HashResult) -- the result is hexadecimal (0x...). Need to convert it using style 2, then examine the left 5 characters WHERE LEFT(CONVERT(VARCHAR(50), ca.HashResult, 2), 5) = REPLICATE('0', 5) -- and order it so that we get the lowest number ORDER BY N; |
As it was suggested earlier, I will indeed use a virtual tally table to generate the series of numbers. Next, the SELECT statement does a TOP 1 in conjunction with ORDER BY and WHERE clauses to get the first matching value. The HASHBYTES function specifies to generate a MD5 hash from the seed and the current number (this is performed in the CROSS APPLY since I need to use it in two places – once to display the hash, and the second in the where clause. Performing this in the CROSS APPLY allows me to introduce a computed column for use anywhere in the query after it has been introduced). Finally, in the WHERE clause, this is converted to a character field using the CONVERT function with a style of 2 (since a varbinary starts with 0x, we need to get rid of that). Additionally, if we try to just convert it without a style option, it will try to convert the varbinary to the textual equivalent – not the hash. So, style 2 is used to convert it into the hash without the leading 0x. And there we have our simple query to get the lowest number matching the seed value.
For part 2, we just need to change this to get the first number that generates a seed with six leading zeros. For the first attempt, the obvious change is to just change the LEFT function to get the first six characters, and to compare it to six zeros. However, when you run this, you don’t get a result… the smallest number is higher than the capacity of this virtual tally table. So, we change the virtual tally table to generate a billion rows instead (CROSS JOIN to the Hundreds CTE four times), and now we get the number that we need.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
-- Part 2: get the lowest number that when prefixed by the specified input, returns a MD5 hash that starts with 6 zeros. 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), Billions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3, Hundreds t4), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Billions) SELECT TOP (1) N, ca.HashResult FROM Tally -- use the HASHBYTES function to generate the hash CROSS APPLY (SELECT HASHBYTES('MD5', 'iwrupvqb' + CONVERT(VARCHAR(15), N))) AS ca(HashResult) -- the result is hexadecimal (0x...). Need to convert it using style 2, then examine the left 5 characters WHERE LEFT(CONVERT(VARCHAR(50), ca.HashResult, 2), 6) = REPLICATE('0', 6) -- and order it so that we get the lowest number ORDER BY N; |
And there we go… two scripts (with very minor changes between them) to get the lowest number that generates a MD5 hash with either five or six leading zeros. They used a virtual tally table, the HASHBYTES function, and the CONVERT function with style 2.