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.