Advent of Code, Day 6

2016-01-11 Wayne Sheffield No comments

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 6. In this challenge, you’re competing with your neighbors in the annual Christmas house decorating contest. Since you helped Santa fix up his nice list, he’s helping you out. You have a 1000 x 1000 grid that represents lights. Santa has sent you directions on how to light up each light (see the directions here). The directions state whether to turn on, turn off, or toggle the lights in the specified coordinates. These coordinates are specified in starting and ending X/Y pairs, for example, “turn on 0,0 through 5,5”. Your challenge is to determine how many lights are turned on at the end of the lighting instructions.

As before, the first step is to load the instructions into a variable. You should be familiar with this by now…

DECLARE @InputText VARCHAR(MAX);
SELECT  @InputText = REPLACE(FileText, CHAR(10), '')
FROM    OPENROWSET(BULK 'D:\AdventOfCode\Day06.txt', SINGLE_CLOB) UselessAlias(FileText)

DECLARE @TotalLength INTEGER = LEN(@InputText),
        @LengthNoCR  INTEGER = LEN(REPLACE(@InputText, CHAR(13), ''));
DECLARE @TotalRows   INTEGER = @TotalLength - @LengthNoCR;
DECLARE @SizePerRow  INTEGER = @TotalLength / @TotalRows;
DECLARE @CRPosition  INTEGER = CHARINDEX(CHAR(13), @InputText, @TotalLength / 2);

DECLARE @InputText VARCHAR(MAX);

SELECT @InputText = REPLACE(FileText, CHAR(10), '')

FROM OPENROWSET(BULK 'D:\AdventOfCode\Day06.txt', SINGLE_CLOB) UselessAlias(FileText)

DECLARE @TotalLength INTEGER = LEN(@InputText),

@LengthNoCR INTEGER = LEN(REPLACE(@InputText, CHAR(13), ''));

DECLARE @TotalRows INTEGER = @TotalLength - @LengthNoCR;

DECLARE @SizePerRow INTEGER = @TotalLength / @TotalRows;

DECLARE @CRPosition INTEGER = CHARINDEX(CHAR(13), @InputText, @TotalLength / 2);

In the next step, I’ll load this data into a temporary table. In conjunction with this, I will also determine if the lights are being turned on, turned off, or toggled, and what the two sets of coordinates are:

IF OBJECT_ID('tempdb.dbo.#Data') IS NOT NULL DROP TABLE #Data;
CREATE TABLE #Data (
    ItemNumber  INTEGER PRIMARY KEY CLUSTERED,
    Item        VARCHAR(100),
    Toggle      BIT,
    TurnOn      BIT,
    TurnOff     BIT,
    StartX      INTEGER,
    StartY      INTEGER,
    EndX        INTEGER,
    EndY        INTEGER);
WITH cte1 AS
(
    -- split the strings on the CR (CHAR(13))
    -- split the first half (going to the CR after the midpoint)
    SELECT  *
    FROM    Sandbox.dbo.DelimitedSplit8K(SUBSTRING(@InputText, 1, @CRPosition), CHAR(13))
    WHERE   Item <> ''
    UNION ALL
    -- split the remainder of the string.
    -- Add 10k to the item number so that we keep them in order
    SELECT  ItemNumber + 10000, Item
    FROM    Sandbox.dbo.DelimitedSplit8K(SUBSTRING(@InputText, @CRPosition+1, 8000), CHAR(13))
    WHERE   Item <> ''
)
, cte2 AS
(
    -- Reorder using the ROW_NUMBER function
    SELECT  ROW_NUMBER() OVER (ORDER BY cte1.ItemNumber) AS ItemNumber
    ,       cte1.Item
    -- returns a positive number if the search expression is found, 0 if not.
    -- for bit columns, a non-zero number will be treated as a '1'
    ,       CHARINDEX('toggle', cte1.Item) AS Toggle
    ,       CHARINDEX('turn on', cte1.Item) AS TurnOn
    ,       CHARINDEX('turn off', cte1.Item) AS TurnOff
    ,       ca4.StartRange
    ,       ca4.EndRange
    -- unremark this to see what the values are being returned as
    --, ca1.StartRangeStart, ca2.StartRangeEnd, ca3.EndRangeStart
    FROM    cte1
            -- find where any number starts in the string
            CROSS APPLY (SELECT PATINDEX('%[0-9]%', cte1.Item)) ca1(StartRangeStart)
            -- now find where a space is after the number
            CROSS APPLY (SELECT CHARINDEX(' ', cte1.Item, ca1.StartRangeStart)) ca2(StartRangeEnd)
            -- find where any number starts in the remainder of the string
            CROSS APPLY (SELECT PATINDEX('%[0-9]%', SUBSTRING(cte1.Item, ca2.StartRangeEnd+1, 8000))) ca3(EndRangeStart)
            -- get the starting and ending range (ending range is the rest of the string)
            CROSS APPLY (SELECT SUBSTRING(cte1.Item, ca1.StartRangeStart, ca2.StartRangeEnd - ca1.StartRangeStart + 1),
                                SUBSTRING(cte1.Item, ca3.EndRangeStart + ca2.StartRangeEnd, 8000) ) ca4(StartRange, EndRange)
)
-- split the ranges into their two parts
-- these cross applys here are going to make 4 rows for each row. So, pivot them all back into one row, with values for the Starting / Ending X/Y positions.
INSERT INTO #Data (ItemNumber, Item, Toggle, TurnOn, TurnOff, StartX, StartY, EndX, EndY)
SELECT  cte2.ItemNumber
,       MAX(cte2.Item) AS Item
,       MAX(cte2.Toggle) AS Toggle
,       MAX(cte2.TurnOn) AS TurnOn
,       MAX(cte2.TurnOff) AS TurnOff
,       MAX(CASE WHEN dsStart.ItemNumber = 1 THEN CONVERT(INTEGER, dsStart.Item) ELSE NULL END) AS StartX
,       MAX(CASE WHEN dsStart.ItemNumber = 2 THEN CONVERT(INTEGER, dsStart.Item) ELSE NULL END) AS StartY
,       MAX(CASE WHEN dsEnd.ItemNumber   = 1 THEN CONVERT(INTEGER, dsEnd.Item)   ELSE NULL END) AS EndX
,       MAX(CASE WHEN dsEnd.ItemNumber   = 2 THEN CONVERT(INTEGER, dsEnd.Item)   ELSE NULL END) AS EndY
FROM    cte2
CROSS APPLY Sandbox.dbo.DelimitedSplit8K(cte2.StartRange, ',') dsStart
CROSS APPLY Sandbox.dbo.DelimitedSplit8K(cte2.EndRange, ',')   dsEnd
GROUP BY cte2.ItemNumber
ORDER BY cte2.ItemNumber;

IF OBJECT_ID('tempdb.dbo.#Data') IS NOT NULL DROP TABLE #Data;

CREATE TABLE #Data (

ItemNumber INTEGER PRIMARY KEY CLUSTERED,

Item VARCHAR(100),

Toggle BIT,

TurnOn BIT,

TurnOff BIT,

StartX INTEGER,

StartY INTEGER,

EndX INTEGER,

EndY INTEGER);

WITH cte1 AS

(

-- split the strings on the CR (CHAR(13))

-- split the first half (going to the CR after the midpoint)

SELECT *

FROM Sandbox.dbo.DelimitedSplit8K(SUBSTRING(@InputText, 1, @CRPosition), CHAR(13))

WHERE Item <> ''

UNION ALL

-- split the remainder of the string.

-- Add 10k to the item number so that we keep them in order

SELECT ItemNumber + 10000, Item

FROM Sandbox.dbo.DelimitedSplit8K(SUBSTRING(@InputText, @CRPosition+1, 8000), CHAR(13))

WHERE Item <> ''

)

, cte2 AS

(

-- Reorder using the ROW_NUMBER function

SELECT ROW_NUMBER() OVER (ORDER BY cte1.ItemNumber) AS ItemNumber

, cte1.Item

-- returns a positive number if the search expression is found, 0 if not.

-- for bit columns, a non-zero number will be treated as a '1'

, CHARINDEX('toggle', cte1.Item) AS Toggle

, CHARINDEX('turn on', cte1.Item) AS TurnOn

, CHARINDEX('turn off', cte1.Item) AS TurnOff

, ca4.StartRange

, ca4.EndRange

-- unremark this to see what the values are being returned as

--, ca1.StartRangeStart, ca2.StartRangeEnd, ca3.EndRangeStart

FROM cte1

-- find where any number starts in the string

CROSS APPLY (SELECT PATINDEX('%[0-9]%', cte1.Item)) ca1(StartRangeStart)

-- now find where a space is after the number

CROSS APPLY (SELECT CHARINDEX(' ', cte1.Item, ca1.StartRangeStart)) ca2(StartRangeEnd)

-- find where any number starts in the remainder of the string

CROSS APPLY (SELECT PATINDEX('%[0-9]%', SUBSTRING(cte1.Item, ca2.StartRangeEnd+1, 8000))) ca3(EndRangeStart)

-- get the starting and ending range (ending range is the rest of the string)

CROSS APPLY (SELECT SUBSTRING(cte1.Item, ca1.StartRangeStart, ca2.StartRangeEnd - ca1.StartRangeStart + 1),

SUBSTRING(cte1.Item, ca3.EndRangeStart + ca2.StartRangeEnd, 8000) ) ca4(StartRange, EndRange)

)

-- split the ranges into their two parts

-- these cross applys here are going to make 4 rows for each row. So, pivot them all back into one row, with values for the Starting / Ending X/Y positions.

INSERT INTO #Data (ItemNumber, Item, Toggle, TurnOn, TurnOff, StartX, StartY, EndX, EndY)

SELECT cte2.ItemNumber

, MAX(cte2.Item) AS Item

, MAX(cte2.Toggle) AS Toggle

, MAX(cte2.TurnOn) AS TurnOn

, MAX(cte2.TurnOff) AS TurnOff

, MAX(CASE WHEN dsStart.ItemNumber = 1 THEN CONVERT(INTEGER, dsStart.Item) ELSE NULL END) AS StartX

, MAX(CASE WHEN dsStart.ItemNumber = 2 THEN CONVERT(INTEGER, dsStart.Item) ELSE NULL END) AS StartY

, MAX(CASE WHEN dsEnd.ItemNumber = 1 THEN CONVERT(INTEGER, dsEnd.Item) ELSE NULL END) AS EndX

, MAX(CASE WHEN dsEnd.ItemNumber = 2 THEN CONVERT(INTEGER, dsEnd.Item) ELSE NULL END) AS EndY

FROM cte2

CROSS APPLY Sandbox.dbo.DelimitedSplit8K(cte2.StartRange, ',') dsStart

CROSS APPLY Sandbox.dbo.DelimitedSplit8K(cte2.EndRange, ',') dsEnd

GROUP BY cte2.ItemNumber

ORDER BY cte2.ItemNumber;

One thing that I want to point out here is that the “Toggle”, “TurnOn” and “TurnOff” columns are of the BIT data type. These are being set by a neat little feature: if the value being passed into this data is a zero, then the bit will be off / false / 0. If the value is not zero, then the bit value with be on / true / 1. Any non-zero value (even a negative number) will set a bit to true. What I am doing is using the CHARINDEX function to return whether the specified text is found in the search string. If it is found, then it will return the starting position of the specified text; if it is not found then it will return 0. So this will very nicely set the BIT column for me.

At this point, we have all of the instructions loaded into a table. Now we need to process them. There are two ways to represent this grid – either a table with 1001 columns (1 for the row number), and 1000 rows. Or a table with 3 columns (X position, Y position, and a column to store the current setting of the light), and a million rows. I’m going to go with the million-row version:

IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE dbo.#temp;
CREATE TABLE dbo.#temp 
(
    X           INTEGER
,   Y           INTEGER
,   IsLightOn   TINYINT
,   Brightness  INTEGER
,   PRIMARY KEY CLUSTERED (X, Y)
);

-- populate it with a 1000x1000 grid
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),
     Thousands(N)AS (SELECT 1 FROM Tens t1, Hundreds 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 Thousands)
INSERT INTO #temp (X, Y, IsLightOn, Brightness)
SELECT  t1.N AS X, t2.N AS Y, CONVERT(BIT, 0) AS IsLightOn, 0 AS Brightness
FROM    Tally t1 CROSS JOIN Tally t2;

IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE dbo.#temp;

CREATE TABLE dbo.#temp

(

X INTEGER

, Y INTEGER

, IsLightOn TINYINT

, Brightness INTEGER

, PRIMARY KEY CLUSTERED (X, Y)

);

-- populate it with a 1000x1000 grid

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),

Thousands(N)AS (SELECT 1 FROM Tens t1, Hundreds 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 Thousands)

INSERT INTO #temp (X, Y, IsLightOn, Brightness)

SELECT t1.N AS X, t2.N AS Y, CONVERT(BIT, 0) AS IsLightOn, 0 AS Brightness

FROM Tally t1 CROSS JOIN Tally t2;

Notice that the “Tally” cte was modified to use the “Thousands” cte, so that only a thousand rows are generated.

Looking through the instructions, you notice that each step needs to be performed in order, and lights at a specific point can be flipped multiple times. This means that we need to utilize a looping mechanism. And in SQL Server, a looping mechanism means just one thing… I need to use my ugly foe, a cursor, so that all of the updates for the first instruction are performed before starting the next one. So this next bit of code will create the SQL statement to be run for each statement, and it will use a cursor to present this to be run instruction by instruction. By creating the SQL statement, this also means that I’ll be running some dynamic SQL. The where clause controls what X/Y ranges are updated.

DECLARE @SQLCMD     VARCHAR(MAX),
        @Message    VARCHAR(MAX);
-- cursor to run the individual commands in order
DECLARE cCommands CURSOR FAST_FORWARD READ_ONLY FOR 
SELECT  'UPDATE #temp SET IsLightOn = ' + 
        CASE WHEN TurnOn = 1 THEN '1' 
             WHEN TurnOff = 1 THEN '0'
             WHEN Toggle = 1 THEN 'CASE WHEN IsLightOn = 0 THEN 1 ELSE 0 END'
        END + ' WHERE X BETWEEN ' + CONVERT(VARCHAR(15), StartX) + ' AND ' + CONVERT(VARCHAR(15), EndX) + 
              ' AND   Y BETWEEN ' + CONVERT(VARCHAR(15), StartY) + ' AND ' + CONVERT(VARCHAR(15), EndY) + ';'
FROM    #Data
ORDER BY ItemNumber;
OPEN cCommands;
FETCH NEXT FROM cCommands INTO @SQLCMD;

WHILE @@FETCH_STATUS = 0
BEGIN
    SET @Message = @SQLCMD + ' (%i rows affected)';
    EXECUTE (@SQLCMD);
    RAISERROR(@Message, 10, 1, @@ROWCOUNT) WITH NOWAIT;
    FETCH NEXT FROM cCommands INTO @SQLCMD;
END
CLOSE cCommands;
DEALLOCATE cCommands;

DECLARE @SQLCMD VARCHAR(MAX),

@Message VARCHAR(MAX);

-- cursor to run the individual commands in order

DECLARE cCommands CURSOR FAST_FORWARD READ_ONLY FOR

SELECT 'UPDATE #temp SET IsLightOn = ' +

CASE WHEN TurnOn = 1 THEN '1'

WHEN TurnOff = 1 THEN '0'

WHEN Toggle = 1 THEN 'CASE WHEN IsLightOn = 0 THEN 1 ELSE 0 END'

END + ' WHERE X BETWEEN ' + CONVERT(VARCHAR(15), StartX) + ' AND ' + CONVERT(VARCHAR(15), EndX) +

' AND Y BETWEEN ' + CONVERT(VARCHAR(15), StartY) + ' AND ' + CONVERT(VARCHAR(15), EndY) + ';'

FROM #Data

ORDER BY ItemNumber;

OPEN cCommands;

FETCH NEXT FROM cCommands INTO @SQLCMD;

WHILE @@FETCH_STATUS = 0

BEGIN

SET @Message = @SQLCMD + ' (%i rows affected)';

EXECUTE (@SQLCMD);

RAISERROR(@Message, 10, 1, @@ROWCOUNT) WITH NOWAIT;

FETCH NEXT FROM cCommands INTO @SQLCMD;

END

CLOSE cCommands;

DEALLOCATE cCommands;

And since the requirement is to count how many lights are on:

SELECT  SUM(IsLightOn) AS LightsOn
FROM    #temp;

1 2	SELECT SUM(IsLightOn) AS LightsOn FROM #temp;

Another way that this could have been handled is to count the number of rows where IsLightOn = 1.

Part two: after you have got this up and running, you realize that it doesn’t really look that great. How are you going to win the contest with this? So you go back and look over the instructions, and you realize that you interpreted the instructions wrong. What you’re supposed to be doing is adjusting the brightness level of the lights in that grid. A turn on command means to increase the brightness level by one level. A turn off command means to decrease it by one brightness level (but it can’t go below 0 – off is off, and it won’t go any darker than that!). And a toggle command means to increase the brightness level by two levels. And now you need to know what the final brightness level is of all of the lights. Fortunately, this means that only minor changes are necessary.

Add the following line to be inserted between lines 6 and 7 of the “Create Grid” block of code so that the brightness level can be kept track of:

,   Brightness  INTEGER

7	, Brightness INTEGER

Replace lines 17 and 18 in the “Create Grid” block of code with the following so that the brightness level is initially set to zero:

INSERT INTO #temp (X, Y, IsLightOn, Brightness)
SELECT  t1.N AS X, t2.N AS Y, CONVERT(BIT, 0) AS IsLightOn, 0 AS Brightness

INSERT INTO #temp (X, Y, IsLightOn, Brightness)

SELECT t1.N AS X, t2.N AS Y, CONVERT(BIT, 0) AS IsLightOn, 0 AS Brightness

Insert the following code between lines 8 and 9 of the “Update Grid” code to control the modification of the brightness level:

        END + 
        -- Part 2 - change brightness
        ', Brightness = ' + 
        CASE WHEN TurnOn = 1 THEN ' Brightness + 1'
             WHEN TurnOff = 1 THEN 'CASE WHEN Brightness > 0 THEN Brightness - 1 ELSE 0 END'
             WHEN Toggle = 1 THEN ' Brightness + 2'

END +

-- Part 2 - change brightness

', Brightness = ' +

CASE WHEN TurnOn = 1 THEN ' Brightness + 1'

WHEN TurnOff = 1 THEN 'CASE WHEN Brightness > 0 THEN Brightness - 1 ELSE 0 END'

WHEN Toggle = 1 THEN ' Brightness + 2'

And finally, replace the “Return results” code block with the following code so that you can see what the final results are:

SELECT  SUM(IsLightOn) AS LightsOn, 
        SUM(Brightness) AS Brightness
FROM    #temp;

SELECT SUM(IsLightOn) AS LightsOn,

SUM(Brightness) AS Brightness

FROM #temp;

Advent of Code, SQL none

Wayne Sheffield

Recent Posts

Top Posts

Archives

Categories

Blogroll

Advent of Code, Day 6

Like this:

Related

Leave a Reply to let me know how you liked this postCancel reply

Wayne Sheffield

Recent Posts

Top Posts

Archives

Categories

Tags

Blogroll

Advent of Code, Day 6

Share this:

Like this:

Related

Leave a Reply to let me know how you liked this postCancel reply