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.
Päivä 7
Tehtävän ensimmäisessä osassa tulee laskea, montako kertaa säde jakautuu, kun se kulkee ylhäältä alas ruudukossa. Jokaisessa jakautumiskohdassa säde jatkaa matkaansa alaspäin yhtä ruutua vasemmalta ja oikealta. Toteutin seuraavan ratkaisun:
CREATE TABLE Grid (row TEXT);
.mode csv
.import day7.txt Grid
CREATE TABLE Splitters AS
SELECT Y.value AS y, X.value AS x
FROM generate_series(1, 142) AS Y,
generate_series(1, 142) AS X,
Grid AS G
WHERE G.rowid = Y.value AND SUBSTR(G.row, X.value, 1) = '^';
CREATE TABLE Beams (y INTEGER NOT NULL, x INTEGER, UNIQUE(y, x));
CREATE TABLE Places (y INTEGER NOT NULL, x INTEGER, UNIQUE(y, x));
PRAGMA recursive_triggers = on;
CREATE TRIGGER new_beam AFTER INSERT ON Beams
BEGIN
INSERT OR IGNORE INTO Places VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x);
INSERT OR IGNORE INTO Beams VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x - 1);
INSERT OR IGNORE INTO Beams VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x + 1);
END;
INSERT INTO Beams VALUES (1, (SELECT INSTR(row, 'S') FROM Grid WHERE rowid = 1));
SELECT COUNT(*) FROM Places;Jostain syystä tiedostossa olevat ^-merkit aiheuttivat ongelmia .import-komennon kanssa, minkä takia lisäsin komennon .mode csv ennen syötteen lukemista.
Tässä taulu Beams sisältää kunkin säteen alkukohdan ja taulu Places sisältää säteen jakautumiskohdat. Kun uusi säde lisätään tauluun, aktivoituu triggeri, joka etsii seuraavan jakautumiskohdan.
Tauluissa on ehtoja (NOT NULL ja UNIQUE), joiden ansiosta laskenta toimii oikealla tavalla: ei lisätä olematonta jakautumiskohtaa eikä samaa kohtaa lisätä useaan kertaan. Näiden ehtojen takia triggerin INSERT-komennoissa on lisäys OR IGNORE, jotta ehdot voivat estää rivin lisäämisen mutta eivät aiheuta virhettä.
Tehtävän toisessa osassa tulee laskea, montako mahdollista reittiä on säteellä, joka valitsee jommankumman suunnan kussakin jakautumiskohdassa. Tämän voisi sinänsä ratkaista hyvin samalla tavalla kuin tehtävän ensimmäisen osan:
CREATE TABLE Grid (row TEXT);
.mode csv
.import day7.txt Grid
CREATE TABLE Splitters AS
SELECT Y.value AS y, X.value AS x
FROM generate_series(1, 142) AS Y,
generate_series(1, 142) AS X,
Grid AS G
WHERE G.rowid = Y.value AND SUBSTR(G.row, X.value, 1) = '^';
CREATE TABLE Beams (y INTEGER NOT NULL, x INTEGER);
CREATE TABLE Places (y INTEGER, x INTEGER);
PRAGMA recursive_triggers = on;
CREATE TRIGGER new_beam AFTER INSERT ON Beams
BEGIN
INSERT OR IGNORE INTO Places VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x);
INSERT OR IGNORE INTO Beams VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x - 1);
INSERT OR IGNORE INTO Beams VALUES
((SELECT y FROM Splitters WHERE x = NEW.x AND y > NEW.y), NEW.x + 1);
END;
INSERT INTO Beams VALUES (1, (SELECT INSTR(row, 'S') FROM Grid WHERE rowid = 1));
SELECT COUNT(*) FROM Places WHERE y IS NULL;Tässä tauluissa ei ole UNIQUE-ehtoja, koska halutaan laskea kaikki mahdolliset reitit, ja lisäksi NULL-arvot taulussa Places ilmaisevat ruudukon alareunaan päässeet säteet. Tämä ratkaisu antaa oikean tuloksen testiruudukossa, mutta ratkaisu on kuitenkin liian hidas varsinaiseen syötteeseen, koska se käy läpi jokaisen reitin erikseen ja reittien määrä voi olla suuri.
Päädyin tekemään toiseen osaan erilaisen ratkaisun, joka muistuttaa dynaamista ohjelmointia:
CREATE TABLE Grid (row TEXT);
.mode csv
.import day7.txt Grid
CREATE TABLE Cells AS
SELECT Y.value AS y, X.value AS x, SUBSTR(G.row, X.value, 1) AS symbol
FROM generate_series(1, 142) AS Y,
generate_series(1, 142) AS X,
Grid AS G
WHERE G.rowid = Y.value AND X.value <= LENGTH(G.row);
CREATE TABLE Counts (y INTEGER, x INTEGER, count INTEGER);
INSERT INTO Counts
SELECT y, x, symbol = 'S' FROM Cells WHERE y = 1;
CREATE TABLE Steps (y INTEGER, x INTEGER);
CREATE TRIGGER new_step AFTER INSERT ON Steps
BEGIN
INSERT INTO Counts VALUES (NEW.y, NEW.x, 0);
UPDATE Counts
SET count = count + (SELECT count
FROM Counts
WHERE y = NEW.y - 1 AND x = NEW.x)
WHERE y = NEW.y AND x = NEW.x AND
'.' = (SELECT symbol FROM Cells WHERE y = NEW.y AND x = NEW.x);
UPDATE Counts
SET count = count + (SELECT count
FROM Counts
WHERE y = NEW.y - 1 AND x = NEW.x - 1)
WHERE y = NEW.y AND x = NEW.x AND
'^' = (SELECT symbol FROM Cells WHERE y = NEW.y AND x = NEW.x - 1);
UPDATE Counts
SET count = count + (SELECT count
FROM Counts
WHERE y = NEW.y - 1 AND x = NEW.x + 1)
WHERE y = NEW.y AND x = NEW.x AND
'^' = (SELECT symbol FROM Cells WHERE y = NEW.y AND x = NEW.x + 1);
END;
INSERT INTO Steps
SELECT y, x FROM Cells WHERE y <> 1 ORDER BY y, x;
SELECT SUM(count) FROM Counts WHERE y = (SELECT MAX(y) FROM Counts);Tässä tauluun Counts lasketaan jokaiseen ruudukon kohtaan, monellako tavalla siihen voi tulla säde aloituskohdasta. Säde voi tulla suoraan ylhäältä, ylävasemmalta tai yläoikealta riippuen ruudukon jakautumiskohdista. Taulu Steps määrittelee, missä järjestyksessä ruudukon kohdat käydään läpi.
Toisin kuin aiemmissa ratkaisuissa, käytetty triggeri ei toimi rekursiivisesti vaan kaikki käsiteltävät kohdat lisätään tauluun Steps triggerin ulkopuolella.
Yllä oleva ratkaisu on sellaisenaan riittävän nopea, mutta sitä voi vielä tehostaa lisäämällä tauluihin indeksit:
CREATE INDEX idx_cells ON Cells (y, x); CREATE INDEX idx_counts ON Counts (y, x);
Tämän jälkeen triggerissä on tehokasta hakea tietoa tauluista Cells ja Counts, mikä nopeuttaa ratkaisua huomattavasti.
Antti Laaksonen kirjoitti:
[Päivän 6 tehtävässä] SQL:ää käyttäessä tulee kaksi hankaluutta: kuinka saada tiedoston sisältö sopivaan muotoon ja kuinka toteuttaa kertolasku.
Olisiko tätä helpottanut tehtävän ohje, että luvut on erotettu välilyöntejä sisältävillä sarakkeilla? – Testasin ideaa ja päädyin seuraavaan:
CREATE TABLE Data (line TEXT);
.import day6.txt Data
-- Katkaisukohdat: alku, loppu ja välisarakkeet.
CREATE TABLE Splits AS
SELECT value AS pos
FROM generate_series(1, (SELECT MAX(LENGTH(line)) + 1 FROM Data))
WHERE NOT EXISTS (
SELECT * FROM Data
WHERE 1 < pos AND pos <= LENGTH(line) AND SUBSTR(line, pos, 1) <> ' '
);
-- Sarakkeiden leveydet.
CREATE TABLE Cols AS
SELECT
split0.pos AS pos,
MIN(split1.pos) - split0.pos AS width
FROM Splits AS split0
JOIN Splits AS split1 ON split1.pos > split0.pos
GROUP BY split0.pos;
-- Data, tehtävä 1.
CREATE TABLE Fields AS
SELECT
1 AS task,
col.pos AS c,
TRIM(SUBSTR(line, col.pos, col.width)) AS field
FROM Data
JOIN Cols AS col
GROUP BY Data.rowid, col.pos;
-- Kopioidaan toimitukset tehtävään 2.
INSERT INTO Fields (task, c, field)
SELECT 2 AS task, c, field FROM Fields
WHERE SIGN(field) IS NULL;
-- Data, tehtävä 2.
INSERT INTO Fields (task, c, field)
SELECT
2 AS task,
(SELECT pos FROM Cols WHERE pos <= value AND value <= pos + width) AS c,
TRIM(GROUP_CONCAT(SUBSTR(line, value, 1), '')) AS field
FROM Data
JOIN generate_series(1, (SELECT MAX(LENGTH(line)) FROM Data))
WHERE SIGN(SUBSTR(TRIM(line), 1, 1))
GROUP BY value
HAVING field <> '';
-- Vastaukset.
SELECT task, CAST(SUM(value) AS INTEGER) FROM (
SELECT task, IF(
SUM(field = '+'),
SUM(field),
ROUND(EXP(SUM(LN(field))))
) AS value
FROM Fields
GROUP BY task, c
) GROUP BY task;Hauskaa, että logaritmista ei aiheudu haittaavia pyöristysvirheitä.
Metabolix kirjoitti:
Olisiko tätä helpottanut tehtävän ohje, että luvut on erotettu välilyöntejä sisältävillä sarakkeilla? – Testasin ideaa ja päädyin seuraavaan:
Kiitos vaihtoehtoisesta ratkaisusta!
Päivä 8
Tehtävän ensimmäisessä osassa tulee selvittää kolme suurinta komponenttia, kun tuhat pistettä yhdistetään toisiinsa järjestyksessä pisteparien etäisyyksien mukaan. Tein seuraavan ratkaisun:
CREATE TABLE Positions (x INTEGER, y INTEGER, z INTEGER);
.separator ","
.import day8.txt Positions
CREATE TABLE Circuits AS
SELECT rowid AS box_id,
rowid AS circuit_id
FROM Positions;
CREATE TABLE Connections (first INTEGER, second INTEGER);
CREATE TRIGGER new_connection AFTER INSERT ON Connections
BEGIN
UPDATE Circuits SET circuit_id =
(SELECT circuit_id FROM Circuits WHERE box_id = NEW.first)
WHERE circuit_id =
(SELECT circuit_id FROM Circuits WHERE box_id = NEW.second);
END;
INSERT INTO Connections
SELECT A.rowid, B.rowid
FROM Positions AS A, Positions AS B
WHERE A.rowid < B.rowid
ORDER BY POW(A.x - B.x, 2) + POW(A.y - B.y, 2) + POW(A.z - B.z, 2)
LIMIT 1000;
CREATE TABLE LargestCircuits AS
SELECT COUNT(*) AS size
FROM Circuits
GROUP BY circuit_id
ORDER BY size DESC
LIMIT 3;
SELECT ROUND(POW(10, SUM(LOG(size)))) FROM LargestCircuits;Taulu Connections sisältää pisteparien järjestyksen niiden etäisyyksien mukaan. Taulussa Circuits on puolestaan tietoa komponentista: ensimmäinen sarake on pisteen id-numero ja toinen sarake on komponentin id-numero.
Aluksi jokainen piste on omassa komponentissaan, ja kun kaksi pistettä yhdistetään, niiden komponentit saavat yhteisen id-numeron. Tämä idea on sama kuin union-find-tietorakenteessa, joskaan tässä ratkaisussa ei pidetä yllä puurakennetta eikä toteutus ole tehokas.
Tehtävän toisessa osassa tulee selvittää lisäyskohta, jossa kaikki pisteet kuuluvat ensimmäistä kertaa samaan komponenttiin. Tein seuraavan ratkaisun:
CREATE TABLE Positions (x INTEGER, y INTEGER, z INTEGER);
.separator ","
.import day8.txt Positions
CREATE TABLE Circuits AS
SELECT rowid AS box_id,
rowid AS circuit_id
FROM Positions;
CREATE TABLE Connections (first INTEGER, second INTEGER);
CREATE TABLE Report (first_x INTEGER, second_x INTEGER, circuit_count INTEGER);
CREATE TRIGGER new_connection AFTER INSERT ON Connections
BEGIN
UPDATE Circuits SET circuit_id =
(SELECT circuit_id FROM Circuits WHERE box_id = NEW.first)
WHERE circuit_id =
(SELECT circuit_id FROM Circuits WHERE box_id = NEW.second);
INSERT INTO Report VALUES (
(SELECT x FROM Positions WHERE rowid = NEW.first),
(SELECT x FROM Positions WHERE rowid = NEW.second),
(SELECT COUNT(DISTINCT circuit_id) FROM Circuits));
END;
INSERT INTO Connections
SELECT A.rowid, B.rowid
FROM Positions AS A, Positions AS B
WHERE A.rowid < B.rowid
ORDER BY POW(A.x - B.x, 2) + POW(A.y - B.y, 2) + POW(A.z - B.z, 2);
SELECT first_x * second_x
FROM Report
WHERE circuit_count = 1
ORDER BY rowid
LIMIT 1;Ideana on lisätä jokaisen pisteiden yhdistämisen jälkeen tauluun Report tieto siitä, mitkä ovat pisteiden x-koordinaatit sekä mikä on komponenttien yhteismäärä. Tehtävän vastaus saadaan lukemalla taulusta ensimmäinen rivi, jossa komponenttien yhteismäärä on yksi.