Kirjautuminen
Tehtävät
Kilpailu
Alkuerät ovat ohi.
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 1010, 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, value) AS repeat
FROM generate_series(1, 99)
UNION
SELECT CONCAT(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 1010, mahdolliset toistomäärät alkulukuina ovat 2, 3, 5 ja 7 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.
Päivä 5
Tehtävän ensimmäisessä osassa on annettuna id-numeroiden välejä sekä yksittäisiä id-numeroita. Tehtävänä on laskea, moniko id-numeroista kuuluu jollekin välille. Tein seuraavan ratkaisun:
CREATE TABLE Data (line TEXT);
.import day5.txt Data
CREATE TABLE Ranges AS
SELECT
1 * SUBSTR(line, 1, INSTR(line, '-') - 1) AS first,
1 * SUBSTR(line, INSTR(line, '-') + 1) AS last
FROM Data
WHERE line LIKE '%-%';
CREATE TABLE Queries AS
SELECT 1 * line AS query
FROM Data
WHERE line NOT LIKE '%-%' AND line <> '';
SELECT COUNT(DISTINCT Q.query)
FROM Queries AS Q, Ranges AS R
WHERE Q.query BETWEEN R.first AND R.last;Tässä suurin haaste oli, että tiedostossa on kahdenlaista dataa: ensin id-numeroiden välejä ja sitten yksittäisiä id-numeroita. Päädyin lukemaan ensin kaikki rivit tauluun Data ja muodostamaan sitten taulut Ranges ja Queries hakemalla rivejä sieltä.
Tehtävän toisessa osassa tulee laskea, moniko id-numero kuuluu johonkin väliin. Tässä ei oteta huomioon lainkaan tiedoston jälkimmäistä osaa eli yksittäisiä id-numeroita. Tein seuraavan ratkaisun:
CREATE TABLE Data (line TEXT);
.import day5.txt Data
CREATE TABLE Ranges AS
SELECT
1 * SUBSTR(line, 1, INSTR(line, '-') - 1) AS first,
1 * SUBSTR(line, INSTR(line, '-') + 1) AS last
FROM Data
WHERE line LIKE '%-%';
DELETE FROM Ranges AS R WHERE
EXISTS (SELECT 1 FROM Ranges
WHERE first = R.first AND last = R.last AND rowid < R.rowid);
DELETE FROM Ranges AS R WHERE
EXISTS (SELECT 1 FROM Ranges
WHERE first <= R.first AND last >= R.last AND rowid <> R.rowid);
CREATE TABLE SortedRanges AS SELECT * FROM Ranges ORDER BY first;
UPDATE SortedRanges AS R
SET first = MAX(first, (SELECT last + 1
FROM SortedRanges
WHERE rowid = R.rowid - 1))
WHERE rowid > 1;
SELECT SUM(last - first + 1) FROM SortedRanges;Ideana on poistaa ensin toistuvat välit sekä välit, jotka ovat kokonaan toisen välin sisällä. Tämän jälkeen vastaus saadaan laskettua järjestämällä välit alkukohdan mukaan ja muuttamalla välejä niin, että jokaisen välin alkukohta on myöhemmin kuin edellisen välin loppukohta.
Päivä 6
Tehtävän ensimmäisessä osassa tulee laskea laskuja, joissa sarakkeessa olevat luvut lasketaan yhteen tai kerrotaan toisillaan riippuen viimeisen rivin operaattorista. Tehtävä ei ole sinänsä vaikea, mutta SQL:ää käyttäessä tulee kaksi hankaluutta: kuinka saada tiedoston sisältö sopivaan muotoon ja kuinka toteuttaa kertolasku. Tein seuraavan ratkaisun:
CREATE TABLE Data (line TEXT);
.import day6.txt Data
UPDATE Data SET line = REPLACE(line, ' ', ' ');
UPDATE Data SET line = REPLACE(line, ' ', ' ');
UPDATE Data SET line = REPLACE(line, ' ', ' ');
UPDATE Data SET line = ' ' || TRIM(line) || ' ';
CREATE TABLE Separators AS
SELECT D.rowid AS line_id, P.value AS pos
FROM Data AS D, generate_series(1, 5000) AS P
WHERE SUBSTR(D.line, P.value, 1) = ' ';
CREATE TABLE Numbers AS
SELECT SUBSTR(D.line, A.pos + 1, B.pos - A.pos - 1) AS number
FROM Separators AS A, Separators AS B, Data AS D
WHERE A.line_id = B.line_id AND
A.rowid + 1 = B.rowid AND
D.rowid = A.line_id AND
number NOT IN ('+', '*');
CREATE TABLE Operators AS
SELECT SUBSTR(D.line, A.pos + 1, B.pos - A.pos - 1) AS operator
FROM Separators AS A, Separators AS B, Data AS D
WHERE A.line_id = B.line_id AND
A.rowid + 1 = B.rowid AND
D.rowid = A.line_id AND
operator IN ('+', '*');
CREATE TABLE Sums AS
SELECT SUM(N.number) AS result
FROM Operators AS O, Numbers AS N
WHERE O.operator = '+' AND N.rowid % 1000 = O.rowid % 1000
GROUP BY O.rowid % 1000;
CREATE TABLE LogSums AS
SELECT SUM(LOG(N.number)) AS result
FROM Operators AS O, Numbers AS N
WHERE O.operator = '*' AND N.rowid % 1000 = O.rowid % 1000
GROUP BY O.rowid % 1000;
SELECT (SELECT SUM(result) FROM Sums) +
(SELECT SUM(ROUND(POW(10, result))) FROM LogSums);Ideana on ensin poistaa riveiltä kaikki ylimääräiset välilyönnit ja lisätä rivin alkuun ja loppuun välilyönti. Tämän jälkeen rivillä olevat luvut ja operaattorit pystyy erottelemaan sen perusteella, että jokaisen luvun ympärillä on tasan yksi välilyönti.
SQL:ssä on kätevä koostefunktio SUM, jolla pystyy laskemaan yhteen lukuja, mutta ei ole vastaavaa funktiota kertolaskua varten. Tämän takia yllä olevassa ratkaisussa lasketaan summa lukujen logaritmeista, joka vastaa kertolaskua niin, että lopullinen tulos saadaan potenssilaskun avulla.
Tehtävän toinen osa on melko samantapainen, mutta laskutapa on määritelty eri tavalla, mikä aiheuttaa melko paljon muutoksia omaan lähestymistapaani. Nyt luvut muodostetaan valitsemalla numerot, jotka ovat tietyssä sarakkeessa. Tein seuraavan ratkaisun:
CREATE TABLE Data (line TEXT);
.import day6.txt Data
UPDATE Data SET line = REPLACE(line, '+ ', '++');
UPDATE Data SET line = REPLACE(line, '* ', '**');
CREATE TABLE Problems AS
SELECT
(SELECT SUBSTR(line, P.value, 1) FROM Data WHERE rowid = 1) ||
(SELECT SUBSTR(line, P.value, 1) FROM Data WHERE rowid = 2) ||
(SELECT SUBSTR(line, P.value, 1) FROM Data WHERE rowid = 3) ||
(SELECT SUBSTR(line, P.value, 1) FROM Data WHERE rowid = 4) AS number,
(SELECT SUBSTR(line, P.value, 1) FROM Data WHERE rowid = 5) AS operator
FROM generate_series(1, 5000) AS P
WHERE operator <> '';
UPDATE Problems SET number = TRIM(number);
CREATE TABLE Positions (pos INTEGER);
INSERT INTO Positions VALUES (0);
INSERT INTO Positions SELECT rowid FROM Problems WHERE number = '';
INSERT INTO Positions VALUES ((SELECT COUNT(*) + 1 FROM Problems));
CREATE TABLE Sums AS
SELECT
(SELECT SUM(number)
FROM Problems
WHERE rowid BETWEEN A.pos + 1 AND B.pos - 1) AS result
FROM Positions AS A, Positions AS B
WHERE A.rowid + 1 = B.rowid AND
(SELECT operator FROM Problems WHERE rowid = A.pos + 1) = '+';
CREATE TABLE LogSums AS
SELECT
(SELECT SUM(LOG(number))
FROM Problems
WHERE rowid BETWEEN A.pos + 1 AND B.pos - 1) AS result
FROM Positions AS A, Positions AS B
WHERE A.rowid + 1 = B.rowid AND
(SELECT operator FROM Problems WHERE rowid = A.pos + 1) = '*';
SELECT (SELECT SUM(result) FROM Sums) +
(SELECT SUM(ROUND(POW(10, result))) FROM LogSums);Toisin kuin ensimmäisen osan ratkaisussa, tässä ei poisteta riveiltä välilyöntejä vaan kerätään yhteen sarakkeissa olevat numerot. Ratkaisu olettaa, että tiedostossa on tasan viisi riviä, joista neljä ensimmäistä sisältävät lukujen numerot ja viimeinen operaattorit. Kuten ensimmäisen osan ratkaisussa, kertolaskut lasketaan logaritmien avulla.