Keskustelu: Koodit: SQL: Advent of Code 2025 (SQLite)

Koetan ratkoa tänä vuonna Advent of Coden tehtävät SQL:llä, tarkemmin käyttäen SQLiteä. Tavoitteeni on laatia tehtäviin ratkaisut, jotka voi suorittaa SQLite-tulkissa. Kunkin ratkaisun tulisi lukea Advent of Coden tekstitiedosto ja rakentaa sopivat taulut, joiden avulla ratkaisun saa laskettua SQL-kyselyllä.

Viime vuonna osallistuin ensimmäistä kertaa Advent of Codeen, kun ratkoin tehtävät QBasicilla. Tämän ansiosta minulla on nyt hyvä ennakkokäsitys siitä, mitä voi odottaa tehtäviltä. Tänä vuonna Advent of Code on muuttunut niin, että kalenterissa on vain 12 luukkua, eli ratkottavaa on vähemmän kuin viime vuonna.

SQLiten käyttäminen tehtävissä on kuitenkin uudenlainen haaste, koska SQLite ei ole varsinaisesti ohjelmointikieli vaan sillä käsitellään tietokantoja. En ehkä olisi lähtenyt haasteeseen, ellei SQLiten manuaalissa olisi esimerkkikyselyjä, jotka piirtävät Mandelbrotin joukon ja ratkaisevat sudokutehtävän. Näiden esimerkkien perusteella Advent of Coden suorittaminen SQLitellä ei pitäisi olla mahdotonta.

Päivä 1

Tehtävän ensimmäisessä osassa annetaan kassakaapin lukon kääntösarja ja tehtävänä on laskea, montako kertaa käännösten jälkeen lukko on asennossa 0. Tein tähän seuraavan ratkaisun:

CREATE TABLE Rotations (rotation TEXT);

.import day1.txt Rotations

UPDATE Rotations SET rotation = REPLACE(rotation, 'L', '-');
UPDATE Rotations SET rotation = REPLACE(rotation, 'R', '+');

SELECT SUM(point0) FROM (
    SELECT (50 + SUM(B.rotation)) % 100 = 0 AS point0
    FROM Rotations AS A, Rotations AS B
    WHERE B.rowid <= A.rowid
    GROUP BY A.rowid
);

Tauluun Rotations luetaan ensin syötetiedoston rivit. Tässä on kätevä SQLite-tulkin komento .import, joka lukee rivit tiedostosta tauluun. Tämän jälkeen merkit L (vasen) ja R muutetaan muotoon - ja +, jotta käännöksiä pystyy käsittelemään paremmin lukuina.

Lopuksi lasketaan kääntösarjan jokaiseen kohtaan käännösten summa siihen asti. Kun summan jakojäännös 100:lla on 0, kyseessä on mukaan laskettava kohta. Tässä on kätevää, että SQLitessä taulussa on automaattisesti sarake rowid, joka kertoo rivin id-numeron.

Tehtävän toinen osa on muuten samanlainen, mutta mukaan tulee laskea myös käännöksen aikana esiintyvät kohdat, joissa lukko on asennossa 0. Jos lukkoa käännetään useita kierroksia, tulee ottaa huomioon, että asento 0 tulee vastaan useita kertoja. Tein seuraavan ratkaisun:

CREATE TABLE Rotations (rotation TEXT);

INSERT INTO Rotations (rotation) VALUES ('+0');
.import day1.txt Rotations

UPDATE Rotations SET rotation = REPLACE(rotation, 'L', '-');
UPDATE Rotations SET rotation = REPLACE(rotation, 'R', '+');

CREATE TABLE Events AS
    SELECT (50 + SUM(B.rotation)) % 100 AS pos,
           FLOOR((1000050 + SUM(B.rotation)) / 100) AS round
    FROM Rotations AS A, Rotations AS B
    WHERE B.rowid <= A.rowid
    GROUP BY A.rowid
;

SELECT SUM(point0) FROM (
    SELECT (B.pos = 0) +
           ABS(A.round - B.round) -
           (A.round < B.round AND B.pos = 0) -
           (A.round > B.round AND A.pos = 0) AS point0
    FROM Events AS A, Events AS B
    WHERE A.rowid + 1 = B.rowid
);

Tässä lasketaan lukon asento samalla tavalla kuin ensimmäisessä osassa mutta lisäksi lasketaan lukon kierros FLOOR-funktiolla. Tässä lisäsin pohjalle suuren luvun 1000050, jotta ei tarvitse miettiä erikseen tapauksia, joissa kierros on positiivinen tai negatiivinen.

Kun tiedetään lukon asento ja kierros jokaisen kahden peräkkäisen käännöksen välillä, tämän perusteella voidaan laskea asennon 0 esiintymiskerrat.

Päivä 2

Tehtävän ensimmäisessä osassa annetaan lukuvälejä ja jokaisesta lukuvälistä tulee laskea summa välillä olevista luvuista, joissa on samat numerot kahdesti peräkkäin (esim. 12321232). Tein seuraavan ratkaisun:

CREATE TABLE Ranges (first INTEGER, last INTEGER);

.separator "-" ","
.import day2.txt Ranges

CREATE TABLE Doubles AS
    SELECT value || value AS double FROM generate_series(1, 99999)
;

SELECT SUM(D.double)
    FROM Ranges AS R, Doubles AS D
    WHERE D.double BETWEEN R.first AND R.last;

Tässä tehtävässä syötetiedostossa on yksittäinen rivi, jossa on lukuvälejä pilkuilla erotettuina. Tämän tiedoston pystyy lukemaan kätevästi tauluun Ranges ilmaisemalla komennolla .separator, että merkki - erottaa sarakkeet ja merkki , erottaa rivit.

Ratkaisun ideana on, että taulu Doubles sisältää mahdolliset luvut, joissa on samat numerot kahdesti peräkkäin. Koska syötetiedoston suurin luku on alle 10¹⁰, tätä suurempia lukuja ei lisätä tauluun. Tämän taulun perustana on SQLite-tulkin funktiolla generate_series luotu taulu, jossa on kaikki luvut annetulta lukuväliltä.

Kun taulut Ranges ja Doubles on luotu, niitä käyttäen pystyy laskemaan vastauksen.

Tehtävän toinen osa on muuten samanlainen, mutta nyt tarkastellaan lukuja, jossa toistuu vähintään kahdesti samat numerot. Yksi tapa laskea vastaus on käyttää samaa ideaa kuin ensimmäisessä osassa:

CREATE TABLE Ranges (first INTEGER, last INTEGER);

.separator "-" ","
.import day2.txt Ranges

CREATE TABLE Repeats AS
    SELECT CONCAT(value, value) AS repeat
        FROM generate_series(1, 99999)
    UNION
    SELECT CONCAT(value, value, value) AS repeat
        FROM generate_series(1, 999)
    UNION
    SELECT CONCAT(value, value, value, value) AS repeat
        FROM generate_series(1, 99)
    UNION
    SELECT CONCAT(value, value, value, value, value) AS repeat
        FROM generate_series(1, 99)
    UNION
    SELECT CONCAT(value, value, value, value, value, value) AS repeat
        FROM generate_series(1, 9)
    UNION
    SELECT CONCAT(value, value, value, value, value, value, value) AS repeat
        FROM generate_series(1, 9)
    UNION
    SELECT CONCAT(value, value, value, value, value, value, value, value) AS repeat
        FROM generate_series(1, 9)
    UNION
    SELECT CONCAT(value, value, value, value, value, value, value, value, value) AS repeat
        FROM generate_series(1, 9)
    UNION
    SELECT CONCAT(value, value, value, value, value, value, value, value, value, value) AS repeat
        FROM generate_series(1, 9)
;

SELECT SUM(X.repeat)
    FROM Ranges AS R, Repeats AS X
    WHERE X.repeat BETWEEN R.first AND R.last;

Koska syötetiedoston suurin luku on alle 10¹⁰, toistomäärä on enintään 10 ja kaikki tarvittavat toisteiset luvut voi muodostaa tauluun Repeats yllä olevalla tavalla. Tämä ratkaisu ei ole kuitenkaan kovin tyylikäs.

Tässä on toinen ratkaisu, joka muodostaa taulun Repeats rekursiivisesti:

CREATE TABLE Ranges (first INTEGER, last INTEGER);

.separator "-" ","
.import day2.txt Ranges

CREATE TABLE Repeats AS
WITH RECURSIVE pairs(base, repeat) AS (
    VALUES (1, 1)
    UNION
    SELECT base + 1, repeat + 1 FROM pairs
        WHERE base + 1 < 1e5 AND repeat = base
    UNION
    SELECT base, CONCAT(repeat, base) FROM pairs
        WHERE repeat * base < 1e10
)
SELECT DISTINCT repeat FROM pairs WHERE base <> repeat;

SELECT SUM(X.repeat)
    FROM Ranges AS R, Repeats AS X
    WHERE X.repeat BETWEEN R.first AND R.last;

Tässä on ideana muodostaa ensin pareja muotoa (base, repeat), jossa base on toistettava numerosarja ja repeat on numerosarjaa toistamalla saatu luku. Rekursion avulla kaikki parit voidaan muodostaa lähtien pohjatapauksena parista (1, 1). Taulun Repeats saa nyt luotua repeat-arvoista.

Tämä ratkaisu on aiempaa monimutkaisempi mutta tiiviimpi ja yleisempi, koska kaikkia toistomääriä ei tarvitse luetella erikseen.

Tässä tehtävässä lukuvälit ovat sen verran pieniä, että kaikki tarvittavat toisteiset luvut pystyi laskemaan etukäteen. Tehtävä olisi selvästi vaikeampi, jos luvut olisivat niin suuria, ettei tämä ole mahdollista.

Päivä 3

Tehtävän ensimmäisessä osassa tulee etsiä numerojonosta kahden numeron yhdistelmä, joka on mahdollisimman suuri luvuksi tulkittuna. Tein seuraavan ratkaisun, joka käy läpi kaikki mahdolliset kahden numeron yhdistelmät ja valitsee niistä suurimman:

CREATE TABLE Banks (bank TEXT);

.import day3.txt Banks

CREATE TABLE Digits AS SELECT value FROM generate_series(1, 9);

CREATE TABLE Joltages AS
    SELECT CONCAT(A.value, B.value) AS value,
           CONCAT('%', A.value, '%', B.value, '%') AS pattern
    FROM Digits AS A, Digits AS B
;

SELECT SUM(max_voltage) FROM (
    SELECT MAX(J.value * (B.bank LIKE J.pattern)) AS max_voltage
    FROM Banks AS B, Joltages AS J
    GROUP BY B.bank
);

Ratkaisu perustuu LIKE-operaattoriin, jonka avulla voi tarkastaa, että merkkijonon muoto on halutunlainen. Esimerkiksi %9%5% tarkoittaa merkkijonoja, joissa on jossain kohdassa ensin numero 9 ja sen jälkeen numero 5.

Tehtävän toisessa osassa tulee etsiä vastaavalla tavalla 12 numeron yhdistelmä, joka on mahdollisimman suuri. Tässä tein rekursiivisen ratkaisun, joka muodostaa yhdistelmän numerot vasemmalta oikealle:

CREATE TABLE Banks (bank TEXT);

.import day3.txt Banks

WITH RECURSIVE patterns(pattern, bank, pos) AS (
    SELECT '%_%_%_%_%_%_%_%_%_%_%_%_%', bank, 2 FROM Banks
    UNION
    SELECT CONCAT(SUBSTR(P.pattern, 1, P.pos - 1),
                  D.value,
                  SUBSTR(P.pattern, P.pos + 1)),
           P.bank, P.pos + 2
    FROM patterns AS P, generate_series(1, 9) AS D
    WHERE P.pos <> 26 AND
          P.bank LIKE CONCAT(SUBSTR(P.pattern, 1, P.pos - 1),
                             D.value,
                             SUBSTR(P.pattern, P.pos + 1))
)
SELECT SUM(result) FROM (
    SELECT REPLACE(MAX(pattern), '%', '') AS result
    FROM patterns
    WHERE pos = 26
    GROUP BY bank
);

Tässäkin ratkaisussa on käytössä LIKE-operaattori. Alussa jokainen numero voi olla mikä tahansa (_) ja rekursion joka askeleella ensimmäinen _-merkki korvataan numerolla.

Yllä oleva ratkaisu on toimiva ja antaa oikean vastauksen esimerkkisyötteellä, mutta se on liian hidas testisyötteellä. Sain kuitenkin ratkaisun riittävän tehokkaaksi tekemällä pienen optimoinnin:

CREATE TABLE Banks (bank TEXT);

.import day3.txt Banks

WITH RECURSIVE patterns(pattern, bank, pos) AS (
    SELECT '%_%_%_%_%_%_%_%_%_%_%_%_%', bank, 2 FROM Banks
    UNION
    SELECT CONCAT(SUBSTR(P.pattern, 1, P.pos - 1),
                  D.value,
                  SUBSTR(P.pattern, P.pos + 1)),
           P.bank, P.pos + 2
    FROM patterns AS P, generate_series(1, 9) AS D
    WHERE P.pos <> 26 AND
          P.bank LIKE CONCAT(SUBSTR(P.pattern, 1, P.pos - 1),
                             D.value,
                             SUBSTR(P.pattern, P.pos + 1)) AND
          P.bank NOT LIKE CONCAT(SUBSTR(P.pattern, 1, P.pos - 1),
                                 D.value + 1,
                                 SUBSTR(P.pattern, P.pos + 1))
)
SELECT SUM(result) FROM (
    SELECT REPLACE(MAX(pattern), '%', '') AS result
    FROM patterns
    WHERE pos = 26
    GROUP BY bank
);

Tässä ratkaisussa on mukana lisäehto, joka ottaa merkkijonon mukaan vain silloin, kun ensimmäisen _-merkin kohdalle ei voi laittaa yhtä suurempaa numeroa. Esimerkiksi muotoa %8%_%_%_%... oleva merkkijono tulee mukaan vain silloin, kun muotoa %9%_%_%_%... oleva merkkijono ei ole kelvollinen.

Tämä optimointi tehostaa huomattavasti hakua testisyötteellä, joskin olisi mahdollista luoda syöte, jossa tämä optimointi ei riittäisi.

Päivä 4

Tehtävän ensimmäisessä osassa tulee laskea ruudukossa olevat ruudut, joissa on rulla ja joissa viereisissä ruuduissa on alle neljä rullaa. Tein seuraavan ratkaisun:

CREATE TABLE Grid (row TEXT);

.import day4.txt Grid

CREATE TABLE Rolls AS
    SELECT Y.value AS y, X.value AS x
    FROM generate_series(1, 137) AS Y,
         generate_series(1, 137) AS X,
         Grid AS G
    WHERE G.rowid = Y.value AND SUBSTR(G.row, X.value, 1) = '@'
;

SELECT COUNT(*) FROM (
    SELECT 1
    FROM Rolls AS A, Rolls AS B
    WHERE ABS(A.y - B.y) <= 1 AND ABS(A.x - B.x) <= 1
    GROUP BY A.rowid
    HAVING COUNT(*) <= 4
);

Tässä taulu Grid sisältää alkuperäisen ruudukon ja tauluun Rolls haetaan niiden ruutujen koordinaatit, joissa on rulla. Tämän jälkeen voidaan laskea haluttujen ruutujen määrä käymällä läpi kaikki ruutuparit.

Tehtävän toisessa osassa tulee simuloida prosessia, jossa löydetyt rullat poistetaan ja tämän jälkeen etsitään uusia ehdot täyttäviä rullia ja poistetaan ne jne. Päädyin laajentamaan ensimmäisen osan ratkaisua seuraavasti:

CREATE TABLE Grid (row TEXT);

.import day4.txt Grid

CREATE TABLE Rolls AS
    SELECT Y.value AS y, X.value AS x
    FROM generate_series(1, 137) AS Y,
         generate_series(1, 137) AS X,
         Grid AS G
    WHERE G.rowid = Y.value AND SUBSTR(G.row, X.value, 1) = '@'
;

CREATE TABLE AllRolls AS SELECT * FROM Rolls;

CREATE TABLE Counter (roll_count INTEGER);

PRAGMA recursive_triggers = on;

CREATE TRIGGER new_round AFTER UPDATE ON Counter WHEN OLD.roll_count <> NEW.roll_count
BEGIN
    DELETE FROM Rolls WHERE rowid IN (
        SELECT A.rowid
        FROM Rolls AS A, Rolls AS B
        WHERE ABS(A.y - B.y) <= 1 AND ABS(A.x - B.x) <= 1
        GROUP BY A.rowid
        HAVING COUNT(*) <= 4
    );
    UPDATE Counter SET roll_count = (SELECT COUNT(*) FROM Rolls);
END;

INSERT INTO Counter VALUES (0);
UPDATE Counter SET roll_count = (SELECT COUNT(*) FROM Rolls);

SELECT (SELECT COUNT(*) FROM AllRolls) - (SELECT COUNT(*) FROM Rolls);

Tässä ratkaisussa löydetyt rullat poistetaan taulusta ja triggerin ansiosta prosessi jatkuu niin kauan kuin löytyy uusia poistettavia ruutuja. Taulu Counter sisältää ruudukon tämänhetkisen rullien määrän, ja tämän taulun avulla toteutetaan triggerin aktivoituminen.