source: //www.adafruit.com/images/145×109/2026-04.jpg
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 18. In this challenge, the fire department has cracked down on how many lights can be in your display. So the million light display that you used previously needs to be modified to have no more than 10,000 lights. You are working with them on a 100×100 grid. And Santa sends you instructions on how best to work with them.
With limiting the number of lights, you are going to need to move to an animated display. You have an input file of the initial state of all of the lights. In this file, a “#” means the light is on, and a “.” means that the light is off. The rules for turning on/off a light are:
- If the light is currently on, it will only stay on if 2 or 3 of it’s neighbors are also on. Otherwise, it is turned off
- If the light is currently off, it will only turn on if exactly 3 of it’s neighbors are on. Otherwise, it stays off.
The status of the lights you are comparing to is the status at the start of the step. All lights are compared based on this initial status.
In this puzzle, a “neighbor” is the eight “cells” that surround a particular cell. If the cell is on the top, bottom, left or right edge, there will be less than eight, and those “missing” neighbors are to be considered to be turned off.
For Part 1, we need to determine just how many lights are on after 100 steps have been performed.
The first step is going to be just like all the other steps with an input file – the input file needs to be loaded in to a temporary table. The file is larger than 8000 characters, so it will use the staged approach to extract the individual rows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE #temp; CREATE TABLE #temp ( ItemNumber INTEGER IDENTITY , Item VARCHAR(8000) ); DECLARE @InputText VARCHAR(MAX); SELECT @InputText = REPLACE(FileText, CHAR(10), '') FROM OPENROWSET(BULK 'D:\AdventOfCode\Day18.txt', SINGLE_CLOB) InputFile(FileText) DECLARE @TempStr VARCHAR(8000), @TempStrLen INTEGER; WHILE LEN(@InputText) > 1-- one because it will have that final CHAR(13) BEGIN -- reverse this string so that you can find the CHAR(13) closest to but prior to the 8000 character of @InputText SELECT @TempStr = REVERSE(SUBSTRING(@InputText, 1, 8000)); -- once you find this, get the rest of the string and reverse it again to be back in the original layout SELECT @TempStr = REVERSE(SUBSTRING(@TempStr, CHARINDEX(CHAR(13), @TempStr), 8000)); -- get the length of this string SET @TempStrLen = LEN(@TempStr); -- insert this string into the temp table. Get the Sue value at the same time. INSERT INTO #temp (Item) SELECT ds.Item FROM Sandbox.dbo.DelimitedSplit8K(@TempStr, CHAR(13)) ds WHERE ds.Item > ''; -- remove @TempStr from @InputText. SET @InputText = SUBSTRING(@InputText, @TempStrLen, 50000); END; |
At this point, we have one hundred rows, and each row has the starting status of it’s one hundred lights. We need to extract the status of the individual lights. To accomplish this, let’s use a virtual tally table to get the character at each position (using the SUBSTRING function), and store the row, position and status in a second temporary table. Here I’m converting the status of “#” or “.” to 1 or 0:
|
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
IF OBJECT_ID('tempdb.dbo.#temp2') IS NOT NULL DROP TABLE #temp2; CREATE TABLE #temp2 ( RowNum TINYINT , Pos TINYINT , Status TINYINT ); 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) INSERT INTO #temp2 SELECT t1.ItemNumber AS RowNum , ca.Pos , CASE ca.Status WHEN '#' THEN 1 WHEN '.' THEN 0 END AS Status FROM #temp t1 CROSS APPLY (SELECT N, SUBSTRING(t1.Item, N, 1) FROM Tally WHERE N <= LEN(t1.Item)) ca(Pos, Status); |
Since we need to get the status of all lights based upon the initial state of the lights at the start of a step, we can use the update statement. However, since we need to perform 100 steps, we will have to perform this update 100 times. This is a combination of set-based and iterative code. I’ll accomplish the iterative part by using a while loop based upon the value of a counter. To determine the new status of an individual light, the query needs to get the status of the lights for the rows prior to and after the current row, and for the light positions prior to and after the current position. Since we are looking for a count of the number of neighbor lights that are on, we can utilize a sub-query to get the neighbors light status (remember that this is now a 1 or 0), and then sum them up. Next the query determines what the new light status should be, and updates the temporary table with this information:
|
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
DECLARE @StepNum INTEGER = 0; WHILE @StepNum < 100 BEGIN WITH cte AS ( SELECT t1.RowNum , t1.Pos , t1.Status , ca.Neighbors FROM #temp2 t1 CROSS APPLY (SELECT SUM(Status) FROM #temp2 t2 WHERE t2.RowNum BETWEEN t1.RowNum - 1 AND t1.RowNum + 1 AND t2.Pos BETWEEN t1.Pos - 1 AND t1.Pos +1) ca(Neighbors) ), cte2 AS ( SELECT * , CASE WHEN Status = 1 AND Neighbors NOT IN (3,4) THEN 0 WHEN Status = 0 AND Neighbors != 3 THEN 0 ELSE 1 END AS NewStatus FROM cte ) UPDATE cte2 SET Status = NewStatus; SET @StepNum += 1; END; SELECT SUM(Status) AS LightsOnQuantity FROM #temp2; |
If the lights current status is on (1), then the sum of all of the cells within the rows and positions will include this cell, therefore the neighbors count is looking for 3 or 4 instead of the specified 2 or 3 in order to compensate for this row (position) being included. If the current light is off, then we just look for whether 3 neighbors are on. And here we have the T-SQL solution for Part 1 of this puzzle.
For Part 2, you notice that the four corner lights are permanently on. What is the number of lights on after 100 steps now?
To solve this, we first need to set the four corner lights to being on initially. After the “Extract individual light status” code block, update those four rows to being on:
|
1 2 3 4 |
UPDATE #temp2 SET Status = 1 WHERE RowNum IN (1,100) AND Pos IN (1,100); |
Next we need to alter the CASE statement in cte2. Replace line 68 and insert a new line 69 in the “Update grid 100 times” code block to these new lines:
|
68 69 |
, CASE WHEN RowNum IN (1, 100) AND Pos IN (1, 100) THEN 1 WHEN Status = 1 AND Neighbors NOT IN (3,4) THEN 0 |
The rest of the code remains the same. And here we have the solution for part 2 of day 18.
At this point, the solution is solved. But is this the most efficient way? That sub-query in the CROSS APPLY part of cte is being run for each row… or it’s being run 10,000 times. Let’s modify this query to use window functions instead – specifically the LAG and LEAD offset functions. In this new code, the LAG and LEAD functions will get the eight neighboring cells. A little bit of logic is needed to determine if this row is an edge, and if so then a 0 is used, otherwise the function is called to get the value from the offset row. The status of these eight neighboring cells are then added together to get the new Neighbors value. cte2 is also modified slightly – the query no longer needs to compensate for the current position being in the group being summed, and the case statement is changed slightly for determining when a status is turned on. The actual update statement is the same. The modified query is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
DECLARE @StepNum INTEGER = 0; WHILE @StepNum < 100 BEGIN WITH cte AS ( SELECT t1.RowNum , t1.Pos , t1.Status , CASE WHEN RowNum = 1 OR Pos = 1 THEN 0 ELSE LAG (t1.Status, 101) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- prior row, prior column CASE WHEN RowNum = 1 THEN 0 ELSE LAG (t1.Status, 100) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- prior row, same column CASE WHEN RowNum = 1 OR Pos = 100 THEN 0 ELSE LAG (t1.Status, 99) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- prior row, next column CASE WHEN Pos = 1 THEN 0 ELSE LAG (t1.Status, 1) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- same row, prior column CASE WHEN Pos = 100 THEN 0 ELSE LEAD(t1.Status, 1) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- same row, next column CASE WHEN RowNum = 100 OR Pos = 1 THEN 0 ELSE LEAD(t1.Status, 99) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- next row, prior column CASE WHEN RowNum = 100 THEN 0 ELSE LEAD(t1.Status, 100) OVER (ORDER BY t1.RowNum, t1.Pos) END + -- next row, same column CASE WHEN RowNum = 100 OR Pos = 100 THEN 0 ELSE LEAD(t1.Status, 101) OVER (ORDER BY t1.RowNum, t1.Pos) END AS Neighbors -- next row, next column FROM #temp2 t1 ), cte2 AS ( SELECT RowNum , Pos , Status , Neighbors , CASE WHEN RowNum IN (1,100) AND Pos IN (1,100) THEN 1 WHEN Status = 1 AND Neighbors IN (2,3) THEN 1 WHEN Status = 0 AND Neighbors = 3 THEN 1 ELSE 0 END AS NewStatus FROM cte ) UPDATE cte2 SET Status = NewStatus; SET @StepNum += 1; END; SELECT SUM(Status) AS LightsOnQuantity FROM #temp2; |
Performance wise, this updated code runs two-thirds faster. That’s a pretty nice improvement.
Come on back tomorrow for a T-SQL Solution for Day 19.
