soodan sivut

7, triviaalissa rekursiossa on jotain kaunista

Tarkoitus oli, etten hihkuisi jokaisesta helposta silmukasta. Yhtälöiden karanneiden operaattorien bruteforcehaku olikin mallia helppo silmukka, mutta jostain syystä pitää hihkua. Jollain oikeasti funktionaalisella laiskalla dynaamisella kielellä tästä ja monesta muusta olisi varmaan golfaantunut todella lyhyt.

Jos syöte olisi paljon vaikeampi, niin rekursiot voisi päättää aiemminkin, kun yhtälöt oli rakennettu siten, että välitulos voi vain kasvaa. Jos välitulos olisi etsittyä lopputulosta isompi, niin haussa voisi säästää koneaikaa. Kun koko vastaus löytyy 60 millisekunnissa niin koneaika on koodausaikaa halvempaa.

9, tarkkaa indeksointia

Siinä missä helppo rekursio implementoituu intuitiolla uneksien, jotkut päivät vaativat jo aika tiukkaa keskittymistä kynän ja paperin äärellä. Tarpeeksi kun elämässään koodailee, niin kehittyy väkisinkin hajuaisti off-by-one-bugeille, ja tietyt patternit saavat kuudennen aistin kutittelemaan vaarasta. Saatoin puristaa kynää tiukasti.

Fiksut meriolennot tarvitsivat apua kiintolevyn tilan optimointiin. Tarkan indeksoinnin lisäksi koodista tuli ihan kiva Rustin summatyyppien ansiosta, kun levytila on pätkiä tietueita, joista kukin on joko jonkun mittainen tyhjä tai jonkun mittainen tiedosto.

12, 2D-karttahommaa

Nyt laskeskeltiin peltolänttien rakennuskustannuksia tasaiselta ruudukolta. Yksinkertaisella floodfillillä löytyy naapuruston pinta-ala, ja ympärysmitta on yhtä kuin neljä reunaa kullekin solulle, paitsi että jokainen uusi löytynyt naapuri vähentää summaa yhdellä, kun se jakaa "seinämän" jo aiemmin lasketun ruudun kanssa.

Tehtävän toisessa vaiheessa ynnättiin yhtenäisten reunojen lukumääriä. Yhtenäinen reuna on kahden nurkan väliin jäävä (tasaruudukossa x- tai y-suunnassa aina suora) jana, eli ehkä helpommin olisi voinut laskea pelkät kulmat kun on ekvivalentti pulma. Tein kuitenkin aamulla aivottomasti mitä käskettiin, ja ikäänkuin floodfillasin taas jokaisen löytyneen pohjoispuolen seinämän. Itä-, etelä- ja länsiseinämät löytyvät pyörittämällä karttaa ja ajamalla samaa algoa uudesta näkökulmasta.

Tuntuu, että tälläiset 2D-gridiviritykset menevät aina jotenkin väkisin silmukoilla ja että joku parempi tapa on oltava jossain neljännessä ulottuvuudessa nauramassa olan yli. Jonain syyspäivänä kehitän vielä paremman miniohjelmointikielen 2D-gridiviritysten esittämiseen, niin vähenee boilerplaten pursottaminen.

13, jokavuotinen avaruusyhtälötehtävä

AoC-pulmissa on tavallisesti noin yksi koordinaatistoahdinko oikein isoilla luvuilla, eikä tämä vuosi ollut poikkeus. Pelikoneessa on x- ja y-nappulat kouran liikutteluun ja palkinto jossain kohdassa kouran poimittavana. Mitään CRT:tä ei sentään tarvittu vaikka kakkososan numerot olivatkin galaktisia. Vähän tarkkuutta tarvittiin havaitsemaan siisti kaava sen tarkistamiseen, että pääseekö koordinaatteihin kokonaisluvuilla.

14, jokavuotinen väenjakaja

"Ajele silmukkaa kunnes joku joulupuun muotoinen kuva ilmestyy" ei varsinaisesti ole sellainen tehtävänanto, jonka perusteella voisi saman tien suunnitella mitään varmaa algoritmia sen joulupuun löytämiseksi. Jotkut vähän suuttuvat tälläisistä ja toisia ei kauheasti kiinnosta epämääräisyys. Itse olen jälkimmäisessä no problem -leirissä.

Ensin piirsin robottien muodostaman alueen jokaisella liikkumisiteraatiolla ja vähän tuijottelin, kunnes löytyy ihmissilmällä jotain jännää. Robottien pelikenttä on 101 ja 103 merkkiä leveä -- alkulukuja, kuinkas sattuikaan. Mittojen johdosta robottien liikkuminen on suunnilleen 101 ja 103 iteraation välein tavanomaista kiinnostavampi, niin ei tarvitse katsella ihan tuhansia muotoja. Tein tekstimuodossa ja zoomasin fontin pieneksi; jotkut piirsivät ihan kuvatiedostoja ja antoivat kuvankatseluohjelman esikatselun auttaa. Lopulta koodasin automaattitunnistuksen sellaisella heuristiikalla, että joulukuusikuviossa on monta robottia keskenään yhdessä rykelmässä.

16, vihdoin sitä dijkstraa

Jälleen eräs AoC-standardi on yksi tai useampi reitinhakuongelma joko tasaisessa 2D-ruudukossa tai jossain abstraktimmassa graafissa. Tämänkertaisessa olisi 2D-ruudukkolabyrintti, jossa lähdöstä maaliin on useampi saman mittainen reitti riippuen vähän matkalla tehdyistä mutkista.

Normaalisti ihan sama mikä niistä valitaan. Kakkososassa pitikin etsiä paras katsomopaikka metriikalla, että näköala on hyvä jos ruutu on osa jotakin sopivaa reittiä maaliin. No onneksi perusdijkstrasta saa ulos naapurustokartan, eli mistä mentiin mihin kun lähdettiin alusta. Tätä polkua takaperin kulkien voidaan kätevästi haarautua joka kerta, kun naapureita on useampia, ja merkataan uniikit ruudut toiselle kartalle laskettavaksi.

17, tavanomainen tavukoodin kääntäminen

Se noin jokavuotinen tavukoodin takaisinmallinnus eli reverse-engineeraaminen tulee yleensä vasta ihan loppukuusta. Nyt tuntui aikaiselta. Obfuskoitu algoritmi suorittaa laskutoimituksia yhdestä syöteluvusta ja printtaa pieniä lukuja, jotka vaikuttavat satunnaisilta. Näennäisen satunnaisuuden vuoksi on aika hankalaa löytää syöte, jolla pyydetty lukujono ilmestyy tulokseen. Askartelin koodin Rustiksi ja sitten erottuukin, että syöteluvusta luetaan tulokseen kolmen bitin pätkiä joista kutakin vähän sekoitetaan pseudosatunnaiseksi. Nyt sitten tietty tuloste löytyy kokeilemalla syötteeseen aina kolme bittiä kerrallaan. Olemassaolevat bitit eivät enää vaikuta seuraavaan tulosteeseen. Ensin looppasin väärään suuntaan ja hakuavaruudesta tuli aika iso, ja nolosti vasta vähän myöhemmin sopivampi ratkaisu ns. paljastui minulle unessa.

18, seuraava reitinhaku

Kartan dijkstraaminen suunnilleen määrittää rajan kiinnostavalle tehtävälle, paitsi reitinhaussakin on sellainen loopataan vaan läpi -mallin haastavuusluokka ja loput. AoCeissa onneksi ainakin tehtävän kakkososa on jälkimmäistä sorttia. Tällä kertaa kartta olikin hauskasti annettu putoavien esteiden muodossa ja kysymys on, että kauanko kestää ettei enää pääse perille asti. Ainakin natiivikoodi on ihan tarpeeksi nopeaa, että väkisinkin ajaa saman reitin joka kerta alusta uudelleen. Tarpeeksi nopea kolme sekuntia on kuitenkin vähän nolo. Kun kuitenkin ennen jotain ajanhetkeä pääsee perille ja sen jälkeen ei, niin binäärihaullapa nopeutettiin 0.013 sekuntiin.

19, memoizattu rekursio

Kun kilpakoodailua askartelee kerran vuodessa, niin välissä unohtuu DP:n tarkka määritelmä. Silti jos joku tuntuu intuitiivisesti DP:ltä niin tälläinen, missä ilman täyttää rekursion valloittava tuoksu ja pulma menee triviaalisti toistuviksi alipulmiksi. Kylpypyyhkeiden saatavilla olevista kuvioista voi rakentaa periaatteessa äärettömästi eri kuvioita, kun niitä vain ompelee peräkkäin. Toiveena on kuitenkin lista tiettyjä kuvioita ja kysytään, että mitkäs niistä voi olemassaolevista hahmoista rakentaa ja monellako eri tavalla. Vastaus on ihan helppo, kokeillaan jokaista pyyhekuviota toivotun kuvion alkuun ja jos täsmää, niin näyttää että löytyisi ja toistetaan sama jäljelle jäävällä loppukuviolla. Jos jää lopulta jäljelle tyhjä toive, niin löytyi yksi mahdollisuus.

Nopeaksi tälläisen saa memoizella, joka on glorifioitu käsite siitä, että cachetetaan kaikki löydetyt vastaukset.

20, kilparata kummasti määriteltynä

Kun aamulla silmien edessä on kartta ja se näyttää reitinhaulta, niin koodataan geneerisellä reitinhaulla. Ei olisi tarvinnut dijkstraa tähän kun kartassa on yksi ainut mutkitteleva reitti, meni kuitenkin kun helppoa copypastaa. Väitän kumminkin, että tehtävänannossa oli jotain epäselvää kun kakkososaa piti pyöritellä pidempään kuin olisin halunnut. Kilparadalla voi suorittaa huijauskoodeja eli skipata osan radasta, ja jotenkin kummassa aloin ensin pitämään kirjaa skippausaskelista dijkstrahaun mukana vaikka helpomminkin voisi tehdä kunhan rata kerran on löydetty. Radan jokaisen askelparin voi vaikka käydä läpi ja kokeilla säästyykö aikaa.

21, rekursio memoizattuna

Kaikuuko? No hakuavaruus on ihan erilainen kuin päivässä 19, mutta näin noin vuoden jälkeen on näistä vähän samat vibat. Avaruusaluksen värkissä on näppäimistö, jota ohjaa robottikäsi, jota ohjaa näppäimistö, jota ohjaa robottikäsi, ja niin edelleen joitakin kertoja (tehtävän toisessa osassa 25). Toiveena on näppäillä ensimmäiseen tietty lyhyt koodi mahdollisimman lyhyellä robottien ohjeistuksella. Tulee aika pitkiä näppäilysekvenssejä, jotka löydetään kokeilemalla rekursiivisesti.

Toivottu nappulasekvenssi on kuin reitti graafirakenteessa, ja reitin kukin siirtymä on taas nappulasekvenssi sitä ohjaavassa näppäimistössä. Muistan jonkun turhan typon takia debuganneeni turhan pitkään, ja tietorakenteet tuli valittua vähän tyhmästi kun ratkaisukoodista tuli pöljä kun näppäimistön ruudukkorakenne on sekä tietorakenteessa että kovakoodattuna algon koodissa, ehkä korjaan joskus jos alkaa ahdistaa. Ehkä ois helpompaa, jos ajattelisi kuten kunnon filosofimatemaatikko eikä rakentaisi rekursiorakennetta joka päivälle uusiksi ihan hiekanjyvistä vaan standardeimmilla abstraktioilla.

23, tyypillinen loppukuun huijausheuristiikka

Noin jokavuotinen haaste mallia "voisipa olla tosi kenkku yleisessä tapauksessa mutta syöte kai sattuu olemaan poikkeuksellisen helposti rakennettu" löytyy tietokoneverkkomallin rakenteesta. Ryhmä tietokoneita on kytketty toisiinsa sikin sokin, ja päivän pääongelma eli kakkososa on löytää syötteestä suurin joukko koneita, joista kukin on yhteydessä joukon kaikkiin muihin koneisiin. Verkkoteoriassa tämä graafi on ns. täydellinen. Keksin aamulla sellaisen algoritmin, että ensin jokaisesta solmusta katsottuna otetaan sellainen joukko solmuja, joihin tuo solmu on yhteydessä. Ynnätään yksi näiden solmujen ("kaikki pelaajan naapurit, ei pelaajaa itse") muodostaman verkon lukumäärään. Lopulta etsitään sellainen muodostunut verkko, jonka lukumäärä on suurin. Patologinen tapaus syö varmaan aika paljon muistia jos koko verkko on oikein iso ja yhteyksiä on rutkasti. Eipä tuo valgrindin mukaan hörppää kuin kolmisen megaa yhteensä ja ajaa 17 millisekunnissa. Jos joka nodelle tulisi koko loppuverkko, niin kai dataa tulisi O(n^2), ja (3380 solmua)^2 on kumminkin vain 11 miljoonaa.

24 hieno cepemäinen overengineer

Ekaksi hauska lainaus irkistä:

< jpa> koska kasvoin TIMiä pelaten niin nykyäänkin suunnittelen systeemit niin että niissä on kalamalja jonka särkyessä kissa kävelee salaluukun yli josta se tipahtaa tuuletinta päin kytkien sen päälle ja sitten ilmapallo törmää saksiin ja puhkeaa [ ... ] mutta kun tuon tekee C++:lla niin se näyttää paljon järkevämmältä

The Incredible Machine on paras peli ja C++:n templatesekoilu menee joskus turhan pitkälle. Onneksi suunnilleen saman voi tehdä Rustillakin kun asioille saa tyyppiparametreja.

Päivän tehtävä on keksiä full adder -tyyppisestä logiikkapiirikaaviosta pieleen menneet piuhat. Piiriä voisi simuloida kuten ensimmäisessä osassa pyydetään ja selvittää, mitkä syötebitit vaikuttavat mihinkin tulosbitteihin, ja käännellä väärin menneitä johtoja. Johtoja on aika monta, niin väkisin kaikkien kokeileminen ei kelpaa.

Ratkaisin ensiksi vastauksen AoC-tyylisesti printtaamalla verkon rakenteen Graphvizin muotoon, rendaamalla siitä kuvan, ja katsomalla kuvaa kunnes vastaus löytyy. Koodilla hoitui vähän sekoilemalla siten, että seurataan kaavion muodostamaa verkkoa jokaiselle signaalille, joka sieltä pitäisi löytyä kun tiedetään logiikkaportit ja johdot yhden bitin summaukseen, ja jos jokin ei täsmää, niin pannaan viallinen johto talteen.

Palanen piirikaaviosta

Hauskuus tulee siitä, missä muodossa toivottu rakenne enkoodataan. Ensin kikkailin siten, että rakenne on rekursiivinen tyyppi tähän malliin:

let _first_xz     = Circuit::<X::<0, 0,  Xor::<                        Z::<0>>>>::verify_t(device);
let _xz           = Circuit::<X::<1, 44, Xor::<                  Xor::<Z::<0>>>>>::verify_t(device);
let _first_carry  = Circuit::<X::<0, 0,  And::<                  Xor::<Z::<1>>>>>::verify_t(device);
let _carry        = Circuit::<X::<1, 43, And::<             Or::<Xor::<Z::<1>>>>>>::verify_t(device);
let _first2_carry = Circuit::<X::<0, 0,  And::<       And::<Or::<Xor::<Z::<2>>>>>>>::verify_t(device);
let _carry2       = Circuit::<X::<1, 42, And::<  Or::<And::<Or::<Xor::<Z::<2>>>>>>>>::verify_t(device);

Näitä luetaan tyyliin "carry-bitti menee aina x-johdosta nimeltä x1..x43 and-, or- ja xor-porttien kautta z-johtoon, jonka numero on x:n numero plus yksi". Jos rakenne ei täsmää täsmälleen, niin hakualgoritmi kertoo ensimmäisen johdon nimen, joka menee väärään paikkaan.

Noita on kuitenkin vähän kelju kirjoittaa käsin ja vielä keljumpi lukea. Sain hoidettua niin, että tuli ergonomisempaa ja luettavampaa:

// x00, y00 to z00
let first_xz     = x::<0, 0>()  | xor                       | z::<0>();
// xNN, yNN to zNN for NN > 0
let xz           = x::<1, 44>() | xor |                 xor | z::<0>();
// x00, y00 to z01
let first_carry  = x::<0, 0>()  | and |                 xor | z::<1>();
// xNN, yNN to zMM for MM - NN == 1
let carry        = x::<1, 43>() | and |            or | xor | z::<1>();
// x00, y00 to z02
let first2_carry = x::<0, 0>()  | and |      and | or | xor | z::<2>();
// xNN, yNN to zMM for MM - NN == 2
let carry2       = x::<1, 42>() | and | or | and | or | xor | z::<2>();

let errors = first_xz + xz + first_carry + carry + first2_carry + carry2 | verify(device);
errors.collect::<Vec<_>>()

Pitää vielä sanoa että ne verifiointifunktiot on spesialisoitu per tyyppi, mikä varmaan bloattaa koodia holtittomasti; vaihtoehto olisi dynamic dispatchata vertailuoperaattorit rakenteen tyypin määrittämiin callbackeihin jolloin pääloopista kääntyisi vain yksi instanssi. Laitetaan sinne ääretöntä lähestyvän tehtävälistan perälle tuokin eksperimentti. Lopulta silti tulin tästä hassusta ratkaisusta oikein onnelliseksi, kun se toimi erityisesti Rustin natiivien ominaisuuksien opetteluun muita päiviä paremmin.

Lopuksi

Karttatehtäviä tuntui olevan tavallista enemmän. Rekursiolla intuitiolla ratkaistavista jäi hyvä mieli; voi johtua siitä, että päivätöissä ja muutenkin on tottunut kirjoittamaan imperatiivisilla kielillä ja funktionaalisemmat patternit ovat harvemmassa. Joka kerta sanon, että kun ajatus oli vähän treenata Rustia noin vuosikymmen sitten ja nyt ei tullut keulittua, niin ensi kerralla sitten saa overengineerata jokaisen hakualgon oikein siististi erottelemaan tietorakenteet ja algoritmit kuten oppikirjoissa utopiaa rakennetaan. Nyt 2025 AoC-päiviä on tulossa vain 12. Ehkä loppukuun voi käyttää siihen jälkikäteiskeulimiseen kun tammikuu tulee hitaammin.

Lopulta varsinaiset ongelmat ratkeavat kuitenkin kynällä ja paperilla ja monesti pitää käydä kaikki reunatapaukset läpi että onko joku joukko nyt avoin vai suljettu. Ehkä reunatapauksien ja ohimenevän indeksoinnin avuksikin löytyisi joku taikatemppu oikein etsimällä?