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:

  1. 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
  2. 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:

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:

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:

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:

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:

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:

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.