soodan sivut

7, keulittu puurakenne

Seiskatehtävän hakemistorakenteen olisi jollain helpolla kielellä parsinut ja laskenut menemään jo inputtitekstiä lukiessa, mutta ei tässä. Inputtina olisi lättänä hakemistorakenne, siitä tehdään ohjelman sisäinen representaatio puurakenteeksi.

Päättömässä päämäärässäni oli parikin ongelmaa. Ongelma yksi oli ihan tehtävissä, mä nyt vain halusin tehdä iteraattorin kun iteraattorit on rustissa kova juttu. Eksplisiittisellä rekursiolla toki tämä ensin ratkaistiin niin, että olisi joku referenssi-implementaatio johon verrata.

Hakemistorakennetyyppi on vähän tuollainen rekursiivinen summatyyppi jo itsessään, ja listauksen parsimien puurakenteeksi vaati Rc-RefCell-huijauskoodia kun säilöin viittauksen nykyhakemistoon jotenkin tyhmästi. Refcellit olisi kai voinut purkaa tuosta rakenteesta uloskin parsimisen jälkeen, mutta koitin väkisin tehdä hankalasti kun niin kai oppii paremmin.

No joka tapauksessa tiedostojärjestelmä-puurakenteen hakemistojen kokojen läpikäynti iteratiivisesti vaatii vähän säätöä, onnistui sinänsä ihan hyvin pienellä pinomiettimisellä, mutta kun se tyyppi itsessään on rekursiivinen ja refcellin sisältöä voi borrow()oida vain vähän kerrallaan. Tavallisessa rekursiossa tämä hoituu luonnostaan funktiokutsupinossa, iteratiivisesti taas ei niinkään kun teoriassa lifetimet voivat mennä väärällä tavalla ristiin, mutta löytyi taikatemppu nimeltä recursive_reference josta pitää kirjoittaa joskus kunnolla. Hirmuinen hack ja samalla mahtava purkka, irrottaa lifetimepinon ohjelman suorituspinosta. Oispa ekspressiivisempi ohjelmointikieli, saiskohan näitä pinoja abstraktoitua pidemmällekin.

Tietorakennetta puljatessa piti tuon rekursiotyypin takia vuotaa noita viittauksia Ref::leak()illa, joka kumma kyllä on käytettävissä suoraan kunhan merkkaa cell_leak-featuren päälle. Leakin lisäksi oli joku muukin vaihtoehto joita jossain sivubranchissa lokaalissa gitissäni homehtuu, ainakin yksi unsafetemppu lifetimejen transmutella joka - selvästi nähdään - on ihan OK kun katsotaan miten nuo säilötään pinoon. Siitä varmaan kirjoitan myöhemmin lisää kun oli oikeasti aika jännää ja täytyy tehdä kunnon katsaus paremmalla ajalla.

self.stack.push(EntryVisit::Visiting(0));
let evec: std::cell::Ref<'a, _> = contents.borrow();
// FIXME don't leak
let evec = std::cell::Ref::leak(evec);
for ent in evec.iter() {
    self.stack.push(EntryVisit::Incoming(ent));
}

Se unsafetemppu olisi jotain tälläistä:

let evec = container.borrow();
let entry = Ref::map(evec, |v| &v[i]);
let val_ref = Some(unsafe {
    std::mem::transmute::<Ref<'_, _>, Ref<'a, _>>(
        entry
    )
});

8, kartta listalistassa

Metsäkartta olisi varmaan paras säilöä vähän abstraktimmassa muodossa, mutta joskus kaksiulotteiset inputit näissä tehtävissä on ihan tehtävissä noinkin, että kartan solut on riveittäin vektoreissa ja ne rivit taas vektorissa. Konsistenttiuden vuoksi kuitenkin aina noin tehtyäni murehdin, että oispa ollut helpompi laittaa tämäkin hashmappiin, jota indeksoitaisiin koordinaatilla. Siihenkin auttaisi joku aoc-tehtäviin kohdennettu minikirjasto.

9, tässä onkin hashmapkartta

Tänäänkin oli kyseessä kaksiulotteista maailmaa, ja nyt kun kartan rajat eivät ookaan hyvin määritellyt, niin näköjään tein just hashmapilla.

Nuo min- ja max-extentit voisi vaikka cachettaa tai jotain, ei perffin takia vaan kätevyyden niin, ettei tarvitsisi vähän väliä copypasteta eri tehtäviin tätä:

let it = visits.keys().chain(knots.iter());
let minx = it.clone().map(|&(x, _)| x).min().unwrap();
let maxx = it.clone().map(|&(x, _)| x).max().unwrap();
let miny = it.clone().map(|&(_, y)| y).min().unwrap();
let maxy = it.clone().map(|&(_, y)| y).max().unwrap();

mutta toisaalta eri päivinä kartta on ihan aavistuksen erilainen ja karttatyypin geneerisyyttä pitäisi vähän viitsiä suunnitella.

11, apinoita ja alkulukuja

Päivän apinat paiskovat numeroita ympäriinsä ja laskutoimituksesta uhkaisi tulla kamalan isoja lukuja. Luvut kuitenkin voi rajoittaa jakojäännöksellä nähtävillä olevien alkulukujen tulon alle.

let post_op = match monkey.op {
    Op::Sum => item + arg,
    Op::Mul => item * arg,
} / worry_ease % (2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23);

Alkuluku on tyypillinen AoC-gotcha, en muista miten keksin tuonkin mutten muista huijanneeni. Kun alkulukuja on elämässä tuijottanut tarpeeksi ja laittaa lukuja vierekkäin, niin kyllä sen näkee että ne on alkulukuja.

13, lifetimekeulimista

Puumaisten rekursiivisten sisäkkäislistatyyppien vertailusta tuli ilahduttavan siisti. Tässä en tehnyt sisäistä puurakennetta vaikka se onkin esitetty vain lättänästi, vertailu on helppo tehdä suoraan pareittain. Pitää vähän reversata että näkyy miksi toi Equal-tyyppi kärrää näitä tekstinpätkiä mukana, vissiin vertaillaan jo vertailtuja pätkiä edelleen.

AoC-tehtävissä tulee harvoin tarve oikeasti rustmaisille ominaisuuksille, mutta tänään piti vähän jumpata lifetimeillä. Keksin Ordering-tyyppien kaltaisen customtyypin kahden erikoistekstinpätkän vertailuun, koska standardikirjaston on suunnitellut fiksu poppoo ja sieltä kannattaa lainata ideoita. Erityisesti kohdissa then_right ja then_left esiintyvät lifetimejen muuntumiset olivat aika hauska oivallus. Turha tuota selittämään, koodista näkee.

impl<'a, 'b> CompareResult<'a, 'b> {
    fn then_right<'c>(&self, next: &'c [u8]) -> CompareResult<'a, 'c> {
        match *self {
            CompareResult::Equal(l, _) => CompareResult::Equal(l, next),
            // explicit "rename" to generate new lifetimes
            CompareResult::Less => CompareResult::Less,
            CompareResult::Greater => CompareResult::Greater,
        }
    }

16, hauska hakualgo lähti käsistä

Reitinhaku on perinteinen AoC-ongelma. Joskus elefantti tulee mukaan etsimään ja hakuavaruudesta tulee aiempaa hankalampi. Joku dijkstra/a*-sovellus tästä kai tuli, en edes muista enää.

struct Node {
    vidx: usize,
    elephant: usize,
    vstates: OpenMap,
    timeleft: i64,
}

Hakualgohommat on yleensä tosi hauskoja, erityisesti jos karttoja on loogisesti sisäkkäin, mutta tässä jäi vissiin tilavektorit suunnittelematta, jotkut heuristiikat kesken ja hienompi geneerisempi versio sivubranchiin. Jospa ns. ensi vuonna ehtisi katsoa mitä tapahtuikaan, voi käyttää esimerkkinä siitä miten hakualgon toteutus epäselväytyy kun käsitteet on algoloopissa sekaisin.

17, syklintunnistus geneerisemmäksi

Tässä vissiin pelattiin tetristä mutta varsinainen kakkosvaiheen ongelma oli, että peliä ajetaan kamalan kauan. Sellaisista pitää selvästi nähdä tai vaihtoehtoisesti plottailla dataa, että jokin signaali alkaa toistaa itseään.

Jo aiemmissa syklitehtävissä vaivasi päätä toistuvuuden tunnistaminen aina käsin uusiksi. Tähän tuli melko geneerinen tunnistusalgoritmi (jos bruteforcea voi algoritmiksi sanoa) sekä ekstrapolointi N askelta eteenpäin. Näköjään signaali oli kuitenkin jonkinlainen kaikkien menneiden integraali, ja ekstrapolointi laskee sen mukaan.

struct CycledSignal<T>(Vec<T>);
struct Cycle<'a, T>(usize, &'a [T]);

Bruteforcen sijaan tuonkin varmasti voisi tehdä fiksusti, mutta nämä syklit ovat niin lyhyitä että samapa tuo. Tärkeintä tempussa oli ylipäänsä hahmottaa, että joku sykli sieltä löytyi.

19, jonkinlainen hakutehtävä

Mineraalirobottien päivästä jäi mieleen, että olipa hauska ja toisaalta että voiko tuollainen ratkaisu muka toimiakin. Bruteforce-DFS:llä mentiin, paitsi jokunen heuristiikka piti hakuavaruuden edes jotenkin järkevän kokoisena niin, että ratkaisu löytyy parissa sekunnissa. Pari sekuntia natiivikoodille on kyllä aoc-tehtävissä iäisyys, eli parannettavaa olisi.

Robottimatikka näytti ensin siltä, että voisi tuon varmaan laskea takaperinkin muuttujia laventamalla tai muuten vaan jotenkin helpommin yhtälöryhmillä, ehkä kuten muutama vuosi takaperin onnistui. Nyt kuitenkin oli mukana myös aikadimensio monimutkaistamassa.

20, simppeli linkkilista

Sanovat että Rustin lifetimejen kanssa tuplalinkitetty lista on vaikein tietorakenne. No varmaan on jos sen tekee klassisen geneerisesti, mutta kun numeroiden pyörittelyä varten otetaan vakiokokoinen areena, niin homma toimii kuin ajatus. Se mitä tässä oikeastaan piti ratkaista on unohtunut jo, tehtävänannon perusteella aika obskuuria hässäkkää. Toisaalta indeksien kanssa pelaaminen on yleisessä tapauksessa kauhean vaarallista, kun indeksi on vähän kuin pointteri mutta vailla mitään takeita osoitettavan datan invalidoitumisesta. Toisaalta siihenkin on tarjottu ratkaisuja.

fn insert_after(links: &mut [Link], pos: Lidx, link: Lidx) {
    let (left, right) = (pos, at(links, pos).1);
    at_mut(links, left).1 = link;
    at_mut(links, right).0 = link;
    *at_mut(links, link) = (left, right);
}

fn insert_before(links: &mut [Link], pos: Lidx, link: Lidx) {
    insert_after(links, at(links, pos).0, link);
}

21, hupaisa yhtälösievennys

Kun apinat huutelevat numeroita, niin muodostuu rakenne, joka ratkaistaan näköjään koodista kerrankin löytyvän kommentin mukaisesti:

((4+(2*(x-3)))/4) = ((32-2)*5)
 (4+(2*(x-3)))    = (((32-2)*5)*4)
    (2*(x-3))     = ((((32-2)*5)*4)-4)
       (x-3)      = (((((32-2)*5)*4)-4)/2)
        x         = (((((32-2)*5)*4)-4)/2)+3

Valitsin yhtälön symbolisen vatkaamisen saman tien sieventämisen sijaan kun tuntui että näin on enemmän hifi, eikä laskutoimituksia huku jos niitä vaikka tarvittaisiin johonkin. Ei kai tarvittu mutta summatyyppien kanssa tää toimii kuin ajatus. Nätimpi ois tullut varmaan vasta lispillä.

22, kuution pinnalla kävelemistä

Kuutioprojekti jäi viime vuoden tehtävistä eniten mieleen, ehkä siksi, että hifistelin ratkaisualgon geneerisen elegantiksi usemman päivän aikana joulupuuron äärellä. Kartassa on syötteenä kuution pinnat auki purettuna tasolle, ja pinnalla pitää liikuskella kartan symbolien perusteella. Kuution pinnan voi "purkaa" ("unwrap") tahkoiksi eri tavoilla näin:

  #   #     #     #    #
#### #### #### #### ####
  #  #     #   #     #

###   ##   ##     #     # ##
  ###  ###  ### ###  ####  ##
        #     #   ##    #   ##

ja sitten kun pinnalla liikutaan ja yhden tahkon reuna tulee vastaan, niin pitää hypätä tietylle vastintahkolle, joka 3D-muodossa täsmää sopivaa särmää. Oiskohan selkein ollut ratkaista tuo siellä 3D-avaruudessa 3D-vektoreilla, mutta minäpä kuljin tuossa lättänällä kartalla.

Koodi ei ota kantaa siihen, missä noista kuutionpurkumuodoista inputtikartta on esitetty. Muoto tunnistetaan automaagisesti ja sen täsmäävyys "kanoniseen muotoon" pyörityksineen otetaan talteen, eli kukin tahkoista saa nimekseen jonkun näistä jos kartta on esitetty pystytasossa:

 F
 E
BAG
 D

Tai jos esitys on vaakatasossa:

  G
FEAD
  B

Ongelma on sopivaa kompleksisuutta kun kynä ja paperi ja sakset otetaan esille

Reunalta toiselle osataan hyppiä vain tässä kanonisessa muodossa (jonka vaaka- ja pystyesitykset ovat keskenään ekvivalentit). Kun eri mallisessa kartassa pitää ylittää reuna, niin lähtötahko muunnetaan kanoniseen maailmaan, suoritetaan reunan ylitys, ja kohdetahko pulautetaan kanonisesta maailmasta taas oikeaan karttaan.

// move to the coordinate system where the wraps are defined
let (src_canon_face, src_canon_heading)
    = canonical_from_map(cube, src_faceidx, src_map_heading);

// where the edge wraps to
let (dest_canon_face, dest_canon_heading)
    = wrap_canonical(cube, src_canon_face, src_canon_heading);

// inverse-lookup the destination
let (dest_faceidx, dest_map_heading)
    = map_from_canonical(cube, dest_canon_face, dest_canon_heading);

Täsmäys tehtävän kartasta kanoniseen muotoon tehdään jotenkin niin, että jos tahko osuu kanonisen muodon tahkolle, niin muunnos on triviaalisti identiteetti. Jokainen kanonisen tahkon sopiva naapuri sitten katsotaan läpi, että täsmäisikö pyöritettynä karttaan. Pyöritykset ja offsetit otetaan talteen.

Tuli aika hauska ja eleganttikin vaikka itse sanonkin. Tai eleganttius on toki lopulta katsojan silmässä.

24, taas reitinhakua

Lumimyräköitä väistellessä tarvitsee päästä paikasta A paikkaan B. Kartta on tällä kertaa vähän implisiittisesti määritelty sen mukaan missä väisteltävää on milläkin ajanhetkellä, mutta ei se menoa haittaa.

Merkkaan vaan muistiin että tuli melko puhdas hakualgo ja tästä voi geneerisöidä sinne toolkittiin joskus. Tai no puhdas verrattuna eeppiseen tilahässäkkään norsujen kanssa. Aiemmin ajattelin, että nämä tehtäväthän ovat niin lyhyitä, että voi kovakoodata haut kuhunkin tilanteeseen - hakualgoritmit kun ovat pohjimmiltaan hyvin yksinkertaisia, ja varsinainen temppu on määritellä ongelmaan sopiva verkkorakenne ja ehkä keksiä heuristiikkoja prunaamaan hakuavaruutta. Toisaalta kun prioriteettijonosilmukkaa puukottaa riittävän kauan, niin alkaa olla mahdoton saada selvää, missä menee verkkorakenteen naapurusto ja missä reittien pituus ja hintafunktio ja niin edelleen. Jos hidasta hakua täytyy katsoa vähän kauempaa sitä optimoidakseen, niin olisi toivottavaa ettei se näytä ihan spagetilta.

Lopuksi

Aina viime kerroilla uhoan, että ensi kerralla sitten enemmän hienoa tyypitystä ja geneerisyyttä. Ei se ihan luonnostaan näköjään vielä tule. Mutta varmasti paremmin sitten ensi kerralla!

Tai ehkei nyt 2023 enää kuitenkaan, kun on nippanappa ehtinyt koodaamaan muilta hässäköiltä. Takana muuttoa ja jalkalistoja ja lumenluontia ja muuta mukavaa.