Advent of Code, Day 7

2016-01-12 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 7. In this challenge, Santa brought little Bobby Tables a bunch of wire and bitwise logic gates. Unfortunately, Bobby needs some help in getting this all assembled. The assembly instructions (here) tell you how to hook the wires up the the gates. A signal is provided to each wire by a gate, another wire, or a specific value. Each wire can only get a signal from one source, but it can provide its signal to multiple destinations. All of the instructions are 16-bit, in the range 0-65535. The instructions are in the form:

123 -> x
456 -> y
x AND y -> d
x OR y -> e
x LSHIFT 2 -> f
y RSHIFT 2 -> g
NOT x -> h
NOT y -> i

In this example, signal 123 is provided to wire x. Signal 456 is provided to wire y. A bitwise AND is performed on x and y, and the results are sent to wire d. A bitwise OR is performed on X and Y, and the results are sent to wire e. The value of wire x is bit-shifted to the left by 2 and sent to wire f. The value of wire y is bit-shifted to the right by 2 and sent to wire g. A bitwise NOT is performed on x and sent to wire h. Finally, a bitwise NOT is performed on x and sent to wire i. The final results of these will be:

d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456

In SQL Server, all of these bitwise operations can be performed, some more easily than others. The directly supported bitwise operators in SQL Server are:

Operator
& (Bitwise AND)
&= (Bitwise AND EQUALS)
| (Bitwise OR)
|= (Bitwise OR EQUALS)
^ (Bitwise Exclusive OR)
^= (Bitwise Exclusive OR EQUALS)
~ (Bitwise NOT)

Did you notices that the left-shift and right-shift bitwise operations are missing? In searching for these, I found this excellent post from Adam Machanic where he shows how to perform them (please read this for an explanation of what they are and how they work), but in a nutshell the left-shift can be performed by multiplying the value by the POWER(2, x) function, where x is the number of digits to shift. The right-shift can be performed by dividing the value by POWER(2, x). For more in Adam’s series on bitmask operations, see the bitmask category on his blog.

Now, to explain the NOT operator. What is does is reverse every bit of the value. In SQL Server, all of the numeric data types are signed, so that they can also represent a negative number. However, notice above that this was specified to be an unsigned value (values 0-65535). Thus, the bitwise NOT doesn’t work the way that we would expect it to – it makes the result be a negative number. So, what we need to do is to subtract the value from 65535.

For the above operations, let’s look at how we would perform these in SQL Server:

DECLARE @x INTEGER = 123;
DECLARE @y INTEGER = 456;
DECLARE @d INTEGER = @x & @y;
DECLARE @e INTEGER = @x | @y;
DECLARE @f INTEGER = @x * POWER(2, 2);
DECLARE @g INTEGER = @y / POWER(2, 2);
DECLARE @h INTEGER = 65535-@x;
DECLARE @i INTEGER = 65535-@y;

SELECT 'Actual Values', @d [@d], @e [@e], @f [@f], @g [@g], @h [@h], @i [@i], @x [@x], @y [@y] UNION ALL
SELECT 'Expected Values', 72, 507, 492, 114, 65412, 65079, 123, 456;

DECLARE @x INTEGER = 123;

DECLARE @y INTEGER = 456;

DECLARE @d INTEGER = @x & @y;

DECLARE @e INTEGER = @x | @y;

DECLARE @f INTEGER = @x * POWER(2, 2);

DECLARE @g INTEGER = @y / POWER(2, 2);

DECLARE @h INTEGER = 65535-@x;

DECLARE @i INTEGER = 65535-@y;

SELECT 'Actual Values', @d [@d], @e [@e], @f [@f], @g [@g], @h [@h], @i [@i], @x [@x], @y [@y] UNION ALL

SELECT 'Expected Values', 72, 507, 492, 114, 65412, 65079, 123, 456;

And we can see that we get the expected results.

Okay, time to attack this challenge. What we need to determine is what is the value being returned from wire “a”. First off, we will load in the instructions:

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

DECLARE @InputText VARCHAR(MAX);

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

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

These instructions are short enough to not need to be split into segments, so we can proceed straight to the next step, in which a temporary table is created to hold these instructions. In this query, I also determine which bitwise operation is being performed, what the destination wire is, and what the source locations are. I’m also generating a SQL statement to run to use to update the destination. All of this information, and a placeholder to store the resultant value, are all put into this temporary table.

IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE dbo.#temp;
CREATE TABLE #temp (
    ItemNumber  INTEGER PRIMARY KEY CLUSTERED,
    Item        VARCHAR(8000),
    [AND]       BIT,
    [OR]        BIT,
    [NOT]       BIT,
    [LSHIFT]    BIT,
    [RSHIFT]    BIT,
    Destination VARCHAR(2) UNIQUE,
    Source1     VARCHAR(15),
    Source2     VARCHAR(15),
    SQLCMD      VARCHAR(8000),
    Value       INTEGER
);

WITH cte1 AS
(
    SELECT  ds.*
    ,       ca0.[AND]
    ,       ca0.[OR]
    ,       ca0.[NOT]
    ,       ca0.[LSHIFT]
    ,       ca0.[RSHIFT]
    ,       ca3.Destination
    ,       CASE WHEN ca0.[NOT] = 1 THEN SUBSTRING(ds.Item, ca4.PosSpace1+1, ca5.PosSpace2 - ca4.PosSpace1 - 1)
            ELSE ca7.Source1
            END AS Source1
    ,       CASE WHEN ca0.[AND] = 1 OR ca0.[OR] = 1 OR ca0.LSHIFT = 1 OR ca0.RSHIFT = 1 THEN SUBSTRING(ds.Item, ca5.PosSpace2+1, ca6.PosSpace3 - ca5.PosSpace2 - 1) 
            ELSE NULL
            END AS Source2
    -- unremark to see these values
    --,       ca5.*, ca6.*, ca7.PosSpace3
    FROM    Sandbox.dbo.DelimitedSplit8K(@InputText, CHAR(13)) ds
    -- if charindex value <> 0, bit value will be 1.
    CROSS APPLY (SELECT CONVERT(BIT, CHARINDEX('AND', ds.Item)) AS [AND]
    ,                   CONVERT(BIT, CHARINDEX('OR', ds.Item))  AS [OR]
    ,                   CONVERT(BIT, CHARINDEX('NOT', ds.Item)) AS [NOT]
    ,                   CONVERT(BIT, CHARINDEX('LSHIFT', ds.ITEM)) AS [LSHIFT]
    ,                   CONVERT(BIT, CHARINDEX('RSHIFT', ds.ITEM)) AS [RSHIFT]) ca0
    -- Get everything from the last space. So, reverse the string, and get everything up to the first space.
    CROSS APPLY (SELECT REVERSE(Item)) ca1(RItem)
    CROSS APPLY (SELECT CHARINDEX(' ', ca1.RItem)) ca2(Pos)
    CROSS APPLY (SELECT REVERSE(LEFT(ca1.RItem, ca2.Pos-1))) ca3(Destination)
    -- Get the first space
    CROSS APPLY (SELECT CHARINDEX(' ', ds.Item)) ca4(PosSpace1)
    -- Get the second space
    CROSS APPLY (SELECT CHARINDEX(' ', ds.Item, ca4.PosSpace1 + 1)) ca5(PosSpace2)
    -- Get the third space
    CROSS APPLY (SELECT CHARINDEX(' ', ds.Item, ca5.PosSpace2 + 1)) ca6(PosSpace3)
    -- Get everything from the first character up to the first space.
    CROSS APPLY (SELECT LEFT(ds.Item, ca4.PosSpace1 - 1)) ca7(Source1)
    WHERE   Item > ''
    --AND     ca3.Destination <> 'b'
)
INSERT INTO #temp (ItemNumber,Item,[AND],[OR],[NOT],[LSHIFT],[RSHIFT],Destination,Source1,Source2,SQLCMD,Value)
SELECT  *
        -- declare the needed variables
,       'DECLARE @Source1 INTEGER, @Source2 INTEGER, @Value INTEGER;' +
        -- select the destination values from those sources
        'SELECT @Source1 = Value FROM #temp WHERE Destination = ''' + cte1.Source1 + ''';' +
        -- source2 isn't needed for all operations, so handle it if it is null
        ISNULL('SELECT @Source2 = Value FROM #temp WHERE Destination = ''' + cte1.Source2 + ''';', '') +
        -- set the value based upon the operation to be performed
        'SET @Value = ' +
            CASE WHEN cte1.Source2 IS NULL AND cte1.Source1 LIKE '[0-9]%' THEN CONVERT(VARCHAR(15), Source1)
                 WHEN cte1.Source2 IS NULL AND cte1.[NOT] = 1 THEN '65535 - @Source1'
                 WHEN cte1.Source2 IS NULL THEN '@Source1'
                 WHEN cte1.[AND] = 1 AND cte1.Source1 LIKE '[0-9]%' THEN CONVERT(VARCHAR(15), Source1) + ' & @Source2'
                 WHEN cte1.[AND] = 1 THEN '@Source1 & @Source2'
                 WHEN cte1.[OR]  = 1 THEN '@Source1 | @Source2'
                 WHEN cte1.LSHIFT= 1 THEN '@Source1 * POWER(2, ' + CONVERT(VARCHAR(15), Source2) + ')'
                 WHEN cte1.RSHIFT= 1 THEN '@Source1 / POWER(2, ' + CONVERT(VARCHAR(15), Source2) + ')'
            END + 
            -- if the operation generates a result, assign the value to the specified destination
            ';IF @Value IS NOT NULL UPDATE #temp SET Value = @Value' +
            ' WHERE Destination = ''' + cte1.Destination + ''';' AS SQLCMD
,       CONVERT(INTEGER, NULL) AS Value
FROM    cte1;

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

CREATE TABLE #temp (

ItemNumber INTEGER PRIMARY KEY CLUSTERED,

Item VARCHAR(8000),

[AND] BIT,

[OR] BIT,

[NOT] BIT,

[LSHIFT] BIT,

[RSHIFT] BIT,

Destination VARCHAR(2) UNIQUE,

Source1 VARCHAR(15),

Source2 VARCHAR(15),

SQLCMD VARCHAR(8000),

Value INTEGER

);

WITH cte1 AS

(

SELECT ds.*

, ca0.[AND]

, ca0.[OR]

, ca0.[NOT]

, ca0.[LSHIFT]

, ca0.[RSHIFT]

, ca3.Destination

, CASE WHEN ca0.[NOT] = 1 THEN SUBSTRING(ds.Item, ca4.PosSpace1+1, ca5.PosSpace2 - ca4.PosSpace1 - 1)

ELSE ca7.Source1

END AS Source1

, CASE WHEN ca0.[AND] = 1 OR ca0.[OR] = 1 OR ca0.LSHIFT = 1 OR ca0.RSHIFT = 1 THEN SUBSTRING(ds.Item, ca5.PosSpace2+1, ca6.PosSpace3 - ca5.PosSpace2 - 1)

ELSE NULL

END AS Source2

-- unremark to see these values

--, ca5.*, ca6.*, ca7.PosSpace3

FROM Sandbox.dbo.DelimitedSplit8K(@InputText, CHAR(13)) ds

-- if charindex value <> 0, bit value will be 1.

CROSS APPLY (SELECT CONVERT(BIT, CHARINDEX('AND', ds.Item)) AS [AND]

, CONVERT(BIT, CHARINDEX('OR', ds.Item)) AS [OR]

, CONVERT(BIT, CHARINDEX('NOT', ds.Item)) AS [NOT]

, CONVERT(BIT, CHARINDEX('LSHIFT', ds.ITEM)) AS [LSHIFT]

, CONVERT(BIT, CHARINDEX('RSHIFT', ds.ITEM)) AS [RSHIFT]) ca0

-- Get everything from the last space. So, reverse the string, and get everything up to the first space.

CROSS APPLY (SELECT REVERSE(Item)) ca1(RItem)

CROSS APPLY (SELECT CHARINDEX(' ', ca1.RItem)) ca2(Pos)

CROSS APPLY (SELECT REVERSE(LEFT(ca1.RItem, ca2.Pos-1))) ca3(Destination)

-- Get the first space

CROSS APPLY (SELECT CHARINDEX(' ', ds.Item)) ca4(PosSpace1)

-- Get the second space

CROSS APPLY (SELECT CHARINDEX(' ', ds.Item, ca4.PosSpace1 + 1)) ca5(PosSpace2)

-- Get the third space

CROSS APPLY (SELECT CHARINDEX(' ', ds.Item, ca5.PosSpace2 + 1)) ca6(PosSpace3)

-- Get everything from the first character up to the first space.

CROSS APPLY (SELECT LEFT(ds.Item, ca4.PosSpace1 - 1)) ca7(Source1)

WHERE Item > ''

--AND ca3.Destination <> 'b'

)

INSERT INTO #temp (ItemNumber,Item,[AND],[OR],[NOT],[LSHIFT],[RSHIFT],Destination,Source1,Source2,SQLCMD,Value)

SELECT *

-- declare the needed variables

, 'DECLARE @Source1 INTEGER, @Source2 INTEGER, @Value INTEGER;' +

-- select the destination values from those sources

'SELECT @Source1 = Value FROM #temp WHERE Destination = ''' + cte1.Source1 + ''';' +

-- source2 isn't needed for all operations, so handle it if it is null

ISNULL('SELECT @Source2 = Value FROM #temp WHERE Destination = ''' + cte1.Source2 + ''';', '') +

-- set the value based upon the operation to be performed

'SET @Value = ' +

CASE WHEN cte1.Source2 IS NULL AND cte1.Source1 LIKE '[0-9]%' THEN CONVERT(VARCHAR(15), Source1)

WHEN cte1.Source2 IS NULL AND cte1.[NOT] = 1 THEN '65535 - @Source1'

WHEN cte1.Source2 IS NULL THEN '@Source1'

WHEN cte1.[AND] = 1 AND cte1.Source1 LIKE '[0-9]%' THEN CONVERT(VARCHAR(15), Source1) + ' & @Source2'

WHEN cte1.[AND] = 1 THEN '@Source1 & @Source2'

WHEN cte1.[OR] = 1 THEN '@Source1 | @Source2'

WHEN cte1.LSHIFT= 1 THEN '@Source1 * POWER(2, ' + CONVERT(VARCHAR(15), Source2) + ')'

WHEN cte1.RSHIFT= 1 THEN '@Source1 / POWER(2, ' + CONVERT(VARCHAR(15), Source2) + ')'

END +

-- if the operation generates a result, assign the value to the specified destination

';IF @Value IS NOT NULL UPDATE #temp SET Value = @Value' +

' WHERE Destination = ''' + cte1.Destination + ''';' AS SQLCMD

, CONVERT(INTEGER, NULL) AS Value

FROM cte1;

When this is being assembled, the wires and gates are put together in a random order. It’s not until everything is connected up that the signals will flow through the wires. So, the code needs to recursively process this data until everything has been assembled, and then it can determine what the desired value is. Additionally, and just like the last puzzle, a cursor is going to be needed so that the values assigned from one operation are available to the next one(s) that can use it. In the above code, the SQL statement that is dynamically created and that will be run in the cursor can be seen. That dynamic code needs to get and store the source values for the operations, perform the proper bitwise operation, and then update the destination with the calculation. All of these statements will be performed in the following loop, which recursively repeats until there is an output on wire a. Finally, we get the results for wire a:

DECLARE @ROWCOUNT INTEGER;
DECLARE @a              INTEGER = NULL
,       @LoopNbr        INTEGER = 0

WHILE @a IS NULL
BEGIN
    SET @LoopNbr += 1;
    RAISERROR('

*******************************************************************************
Loop # %i
*******************************************************************************
', 10, 1, @LoopNbr) WITH NOWAIT;

    /* declare variables */
    DECLARE @SQLCMD VARCHAR(MAX);

    DECLARE curItems CURSOR FAST_FORWARD READ_ONLY FOR 
    SELECT  SQLCMD
    FROM    #temp
    WHERE   Value IS NULL
    ORDER BY ItemNumber;

    OPEN curItems;

    FETCH NEXT FROM curItems INTO @SQLCMD;

    WHILE @@FETCH_STATUS = 0
    BEGIN
        EXECUTE (@SQLCMD);
        SET @ROWCOUNT = @@ROWCOUNT;
        IF @ROWCOUNT > 0 RAISERROR(@SQLCMD, 10, 1) WITH NOWAIT;
        FETCH NEXT FROM curItems INTO @SQLCMD;
    END;

    CLOSE curItems;
    DEALLOCATE curItems;

    SELECT  @a = value 
    FROM    #temp 
    WHERE   Destination = 'a';
END;

SELECT  *
FROM    #temp
WHERE   Destination = 'a';

DECLARE @ROWCOUNT INTEGER;

DECLARE @a INTEGER = NULL

, @LoopNbr INTEGER = 0

WHILE @a IS NULL

BEGIN

SET @LoopNbr += 1;

RAISERROR('

*******************************************************************************

Loop # %i

*******************************************************************************

', 10, 1, @LoopNbr) WITH NOWAIT;

/* declare variables */

DECLARE @SQLCMD VARCHAR(MAX);

DECLARE curItems CURSOR FAST_FORWARD READ_ONLY FOR

SELECT SQLCMD

FROM #temp

WHERE Value IS NULL

ORDER BY ItemNumber;

OPEN curItems;

FETCH NEXT FROM curItems INTO @SQLCMD;

WHILE @@FETCH_STATUS = 0

BEGIN

EXECUTE (@SQLCMD);

SET @ROWCOUNT = @@ROWCOUNT;

IF @ROWCOUNT > 0 RAISERROR(@SQLCMD, 10, 1) WITH NOWAIT;

FETCH NEXT FROM curItems INTO @SQLCMD;

END;

CLOSE curItems;

DEALLOCATE curItems;

SELECT @a = value

FROM #temp

WHERE Destination = 'a';

END;

SELECT *

FROM #temp

WHERE Destination = 'a';

For Part 2, we are to change the value being supplied to wire b from it’s currently assigned value (1674) to 46065. We need to report on the new value for wire “a”. To accomplish this, I just inserted this bit of code before the cursor code:

UPDATE  #temp
SET     Source1 = 46065,
        SQLCMD = REPLACE(SQLCMD, '1674', '46065')
WHERE   Destination = 'b';

UPDATE #temp

SET Source1 = 46065,

SQLCMD = REPLACE(SQLCMD, '1674', '46065')

WHERE Destination = 'b';

Advent of Code, SQL none

Wayne Sheffield

Recent Posts

Top Posts

Archives

Categories

Blogroll

Advent of Code, Day 7

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 7

Share this:

Like this:

Related

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