Advent of Code, dag 2

De eerste puzzelomschrijving

Nadat we de eerste dag hadden opgelost gaat het verhaal van de vermiste Senior historicus verder. Laten we de rest van de historici gaan helpen om hem te vinden. Het verhaal vervolgt bij de Red-Nosed Reindier nucleaire energiecentrale:

While the Red-Nosed Reindeer nuclear fusion/fission plant appears to contain no sign of the Chief Historian, the engineers there run up to you as soon as they see you. Apparently, they still talk about the time Rudolph was saved through molecular synthesis from a single electron. They're quick to add that - since you're already here - they'd really appreciate your help. 

The unusual data (onze input) consists of many reports, one report per line. Each report is a list of numbers called levels that are separated by spaces. For example:

7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9

The engineers are trying to figure out which reports are safe. The Red-Nosed reactor safety systems can only tolerate levels that are either gradually increasing or gradually decreasing. So, a report only counts as safe if both of the following are true:
- The levels are either all increasing or all decreasing.
- Any two adjacent levels differ by at least one and at most three.

Analyze the unusual data from the engineers. How many reports are safe?

In bovenstaand voorbeeld betekent dit dat alleen de eerste en laatste regel uit het voorbeeld als "veilig" bestempeld mogen worden. We moeten de puzzelinput dus gaan testen op de twee regels en beide moeten waar zijn. 

We gaan er in deze puzzel in eerste instantie vanuit dat alle rapporten onveilig zijn en wanneer een rapport aan de regel voldoet dan zetten we deze op veilig. 

CREATE TABLE #Input (
[Level] varchar(255) NULL)

CREATE TABLE [input2024].[Day2] (
[Report] int IDENTITY(1,1) NOT NULL,
[Level] varchar(255) NULL,
[Safe] int DEFAULT 0)

CREATE TABLE #StringSplit (
[Report] int NOT NULL,
[Value] int NOT NULL,
[Ordinal] int NOT NULL)
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
-- Read lines into table
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
BULK INSERT #Input
FROM 'C:\*****\Advent of Code\2024\Input\Day2.txt'
WITH 
 (
   FIELDTERMINATOR = ' ', 
   ROWTERMINATOR = '\n' 
 )

INSERT INTO [input2024].[Day2] ([Level])
SELECT [Level] FROM #Input

Door de puzzelinput op deze manier in te lezen zorgen we ervoor dat elk rapport door midden van een eigen ID te herkennen wordt. Daarnaast hebben we ingesteld dat geen enkel rapport veilig (safe) is door deze standaard in te vullen met een 0 waarde. Als een rapport veilig gezet wordt veranderen we de 0 in een 1. Door deze 1 te sommeren weten we uiteindelijk hoeveer rapporten veilig zijn en kunnen we een antwoord op de vraag geven. 

Om te bepalen door welke waarde een getal gevolgd wordt kunnen we gebruik maken van de LEAD functie in SQL. Voorwaarde daarvoor is dat de rapporten per getal in een rij worden uitgelezen in plaats van alle getallen in één kolom. 

INSERT INTO #StringSplit ([Report], [Value], [Ordinal])
SELECT t1.Report
      ,convert(int, ss.[value]) AS [value]
      ,ss.[ordinal]
FROM  [input2024].[Day2] t1
CROSS APPLY string_split(t1.[Level], ' ', 1) AS ss

Om de juiste volgorde te kunnen blijven volgen heb ik de ordinal waarde aan de tabel toegevoegd. De ordinal waarde geeft aan op welke positie de string_split functie een getal heeft gevonden. In andere programmeertalen wordt dit ook wel de index genoemd. 
Doordat we aan elk rapport een ID hebben toegevoegd weten we ook welke getallen bij elkaar horen.

Zoals gezegd kunnen we door gebruik te maken van de LEAD functie bepalen wat het verschil is met het volgende getal. Daarnaast kunnen we bepalen of het verschil positief, negatief of 0 is. 

;with cte_lead AS (
    SELECT [Report]
          ,[Value]
          ,LEAD([Value]) OVER(PARTITION BY [Report] ORDER BY [Ordinal]) AS [NextValue]
          ,[Value] - LEAD([value]) OVER(PARTITION BY [Report] ORDER BY [Ordinal]) as [Diff]
          ,CASE 
            WHEN [Value] - LEAD([value]) OVER(PARTITION BY [Report] ORDER BY [Ordinal]) > 0 THEN 1
            WHEN [Value] - LEAD([value]) OVER(PARTITION BY [Report] ORDER BY [Ordinal]) < 0 THEN -1
            ELSE 0
            END AS [PosOrNeg]
    FROM #StringSplit

Door de positieve waarde naar 1 en negatieve waarde naar -1 te zetten kunnen we testen of het aantal getallen in een rapport overeenkomt met de uitspraak of er alleen negatieve of positieve waarden inzitten. Bij een LEAD is er altijd een value NULL omdat deze geen opvolgende waarde heeft. Hierdoor moet het aantal regels uit een rapport altijd 1 meer zijn dan de absolute waarde van de PosOrNeg kolom. 
Daarnaast kunnen we bepalen of het verschil per opvolgende nummers in het rapport 1, 2 of 3 is doordat we per rapport het maximale verschil kunnen bepalen. Als dit verschil groter is dan 3 dan voldoet het rapport niet aan de eisen en mogen we het rapport niet als veilig beschouwen.
Deze regels kan je bepalen door het volgende:

, cte_rules AS (
    SELECT [report] 
          ,MAX(ABS([Diff])) AS [MaxDiff]
          ,COUNT([Report]) -1 AS [Expected]
          ,ABS(SUM(case when [NextValue] is not null then [PosOrNeg] else NULL end)) AS [SumPosOrNeg]
    FROM cte_lead
    GROUP BY [report]
    )

Indien de MaxDiff groter is dan 3 voldoet het rapport niet aan de eisen. Daarnaast moeten de Expected en de absolute som van de Positieve of negatieve getallen gelijk zijn aan elkaar.
Op deze manier kunnen we bepalen welk rapport op veilig gezet kan worden. 

UPDATE t1
SET [Safe] = 1
FROM [input2024].[Day2] t1
INNER JOIN cte_rules t2
    ON t2.[Report] = t1.[Report]
WHERE t2.[MaxDiff] IN (1,2,3)
    AND t2.[Expected] = t2.[SumPosOrNeg]

Nu we weten welke rapporten veilig zijn kunnen we deze tellen. Een sommatie van de Safe kolom geeft de juiste uitkomst van de puzzel! De eerste gouden ster is binnen!

Puzzel 2: The Problem Dampener

The engineers are surprised by the low number of safe reports until they realize they forgot to tell you about the Problem Dampener.

The Problem Dampener is a reactor-mounted module that lets the reactor safety systems tolerate a single bad level in what would otherwise be a safe report. It's like the bad level never happened!

Er mag dus één fout in het rapport zitten. Door net te doen alsof het getal dat de fout veroorzaakt niet bestaat is het mogelijk om een rapport toch als veilig te markeren. 

In principe kunnen we dezelfde regels gebruiken als hiervoor. Het enige dat we moeten doen is bepalen of het verwijderen van een nummer ervoor zorgt dat het rapport wel voldoet aan de gestelde regels. Dit kunnen we doen door bij alle rapporten steeds één getal uit te sluiten van het rapport. Als dan de code voor de regels bepaald dat het rapport veilig is, dan kunnen we deze bij het vorige resultaat optellen. 
Omdat we bij de eerste vraag de Ordinal van een getal hebben opgeslagen kunnen we een while loop maken die over elke ordinal waarde gaat. Die specifieke waarde hoort bij het getal dat uitgesloten wordt van de test. Het aantal keer dat de while loop af moet gaan is de maximale ordinal van alle rapporten. 

WHILE @CurrentOrdinal <= @MaxOrdinal
BEGIN
    
    ;with cte_unsafeLevels AS (
        SELECT t1.[Report]
              ,t1.[Ordinal]
              ,t1.[Value]
        FROM [#StringSplit] t1
        INNER JOIN [input2024].[Day2] t2
            ON t2.[Report] = t1.[Report]
            AND t2.[Safe] = 0
        WHERE t1.[Ordinal] != @CurrentOrdinal
    )

Vervolgens testen we de regels op dezelfde manier als we bij vraag 1 hebben gedaan. Op het moment dat een rapport veilig wordt verklaard zal deze de volgende keer dat de while loop gaat niet meer mee worden genomen in de test.
Na het uitvoeren van de test en de update van de veilige rapporten verschuift de while loop met 1 ordinale positie en wordt het volgende nummer uit de onveilige rapporten gehaald.

    ,cte_lead AS (
        SELECT [Report]
              ,[Value]
              ,lead([value]) over(partition by [report] order by [Ordinal]) AS [NextValue]
              ,[value] - lead([value]) over(partition by [report] order by [Ordinal]) as [Diff]
              ,CASE 
                WHEN [value] - lead([value]) over(partition by [report] order by [Ordinal]) > 0 THEN 1
                WHEN [value] - lead([value]) over(partition by [report] order by [Ordinal]) < 0 THEN -1
                ELSE 0
                END AS [PosOrNeg]
        FROM cte_unsafeLevels
        )
    , cte_rules AS (
        SELECT [report] 
              ,MAX(ABS([Diff])) AS [MaxDiff]
              ,COUNT([Report]) -1 AS [Expected]
              ,ABS(SUM(case when [NextValue] is not null then [PosOrNeg] else NULL end)) AS [SumPosOrNeg]
        FROM cte_lead
        GROUP BY [report]
    )
    UPDATE t1
    SET [Safe] = 1
    FROM [input2024].[Day2] t1
    INNER JOIN cte_rules t2
        ON t2.[Report] = t1.[Report]
    WHERE t2.[MaxDiff] IN (1,2,3)
        AND t2.[Expected] = t2.[SumPosOrNeg]

    SET @CurrentOrdinal = @CurrentOrdinal + 1

END

Door nu wederom het aantal veilige rapporten te tellen komen we uit op het antwoord voor vraag 2 van vandaag. 

SELECT SUM([Safe]) AS [Antwoord2] FROM [input2024].[Day2]

Het probleem van de Red-Nosed Reindier nucleaire energiecentrale is hiermee opgelost!

Reacties: