soodan sivut

5, aika hauskaa jo näin aikaisin

Eri vuosista on opittu, että suunnilleen ensimmäinen puolisko tai ainakin kolmannes päivistä on kevyttä lämmittelyä. Tuli positiivinen yllätys, että sai vähän pohtia, miten tehtävän kakkososassa piti yksittäisten lukujen läpikäynnin jälkeen rekursoida lukuvälit tiukalla keskittymisellä off-by-onejen varalta. Hyvin määritellyistä cornercasettomista rekursioista tulee aina aika miellyttävän puhtaita. Vähän kuin sudokua tai sanaristikkoa pelaisi ja jokainen täytettävä ruutu määräisi seuraavan saman tien yksiselitteisesti.

Tykkään myös tästä patternista jonka olen todennut toimivaksi vuosien mittaan, jota lienen aiemmin kutsunut "ping-pong-rekursioksi" mutten nyt löydä missä. Rekursion pääentrypointti on tuo map_to_location_range ja siitä varsinainen logiikka on eriytetty funktioon try_overlap_range joka taas kutsuu sitä entrypointtia uudestaan. Sama olisi koodata kaikki samaan funktioon, mutta tuossa on joskus jotain aika puhdasta että pääfunktio teeskentelee logiikkafunkan keksivän ratkaisun noin vaan ja logiikkapuoli sitten ikäänkuin unohtaa rekursoivansa ja käsittelee tarvittaessa rekursion puurakenteeksi leviävät alirakenteet.

10, floodfilli silmukan sisälle

Päivän inputissa olisi kaksiulotteinen karttaruudukko, josta piti kakkososassa ratkaista reitin sisältämä pinta-ala; jännää tästä teki se, että reitin muoto oli mitä sattuu, vähän kuin lenkiksi solmitun kengännauhan sotkisi pöydällä labyrinttimaiseen muotoon. Temppuni alku oli pitää huolta siitä, että polkua kuljetaan aina myötäpäivään niin, että silmukan sisäpuoli on oikealla. Oikealle puolelle sattuvasta ruudusta voi sitten käydä merkitsemään pinta-alaa triviaalilla rekursiolla. Monesti satutaan ruutuun, joka on aiemmin käyty läpi jo; välillä sitten löytyy uusi tutkimaton maasto kun kengännauhan pätkät kulkevat hetken vierekkäin ja sitten leviävät.

Algo olettaa tietyn "windingin" eli kulkusuunnan; syötteen suunta tarkistetaan askelten ristituloista (mutkista tulee -1 tai 1 suunnan perusteella) ja reitti käännetään ympäri jos sisäpuoli ei olisikaan oikealla. Kun mikä vain silmukka on suoristettuna karteesisessa ruudukossa ekvivalentisti neliö, niin ristitulojen summa on mistä vaan silmukasta käytännössä 4 tai -4 jos en ihan väärin muista.

12, regexmäistä patternmatchia

Päivän pulmapeli on kokeilla kombinatorisen räjähdyksen näköistä merkkijonokaltaista muodostelmaa eri vaihtoehdoilla. En ole vielä omaa regexengineä koodannut ja tämä on aivan lelu sellaiseen verrattuna mutta voisin kuvitella että jotain yhtäläisyyksiä on, ja olipa hauska askartelu. Kakkosvaiheen jekku oli pidentää inputtia niin, että jos ratkaisu on ihan naiivisti tehty niin laskeminen kestää varmaan Auringon sammumiseen asti. Kun koodi on hieno rekursio ja se näyttää ilman pidemmälle analysoimista DP:ltä, niin kokeillaan memoizettaa se eli cachettaa rekursion tulokset kun alijoukkoja taitaa esiintyä fibonaccirekursion kaltaisesti vähän nolot määrät. Sillähän se ratkesi, tosin kun halusin välttää kopiointeja niin tuli eksplisiittiset lifetimeannotaatiot kiusaamaan.

Tähänkin sopi aiemmin mainitun ping-pong-rekursion tyylinen osiinjakomenetelmä silleen, että patternmatchausyritykset jaetaan muutamaan sellaisenaan ymmärrettävään eri pikkufunktioon ja ne sitten kutsuvat rekursion entrypointtia. Pastetaan nyt kuitenkin pseudokoodia tähän vaikka pitkäksi menee. Memoize-cache "mem" pyörii mukana vähän keljusti mutta valmiiksi tuli, ensi vuonna keksin tuohon jonkun geneerisen makrovirityksen tai kokeilen jotain olemassaolevaa.

fn try_broken_sequence<'a>(springs: &'a [char], counts: &'a [usize], mem: &mut Mem<'a>) -> usize {
    if good_stuff {
        1
    } else if complex_stuff {
        arrangements(&springs[seq_len + 1..], &counts[1..], mem)
    } else {
        0
    }
}

fn try_operational<'a>(springs: &'a [char], counts: &'a [usize], mem: &mut Mem<'a>) -> usize {
    if complex_stuff {
        arrangements(&springs[1..], counts, mem)
    } else {
        0
    }
}

fn try_consume<'a>(springs: &'a [char], counts: &'a [usize], mem: &mut Mem<'a>) -> usize {
    if counts.len() == 0 {
        try_operational(springs, counts, mem)
    } else {
        try_broken_sequence(springs, counts, mem) + try_operational(springs, counts, mem)
    }
}

fn arrangements<'a>(springs: &'a [char], counts: &'a [usize], mem: &mut Mem<'a>) -> usize {
    if let Some(x) = mem.get(&(springs, counts)) {
        return *x;
    }
    let x = match springs.first() {
        None if counts.len() == 0 => 1, // happy end of a recursion
        None => 0,
        Some('.') => arrangements(&springs[1..], counts, mem),
        Some('#') | Some('?') => try_consume(springs, counts, mem),
        _ => panic!()
    };
    mem.insert((springs, counts), x);
    x
}

14, uusiokäyttöä syklintunnistimelle

Varsinainen pohjatarina jäi sivuosaan, kun piti havaita että askarreltavalle operaatiolle pyydetyt 1000000000 toistoa on muutama liikaa. Copypastesin jekkuni nimeltä CycledSignal jostain aiemmalta vuodelta ja vähän pätsäsin, kun aiempi versio näköjään piti kirjaa integraaleista ja nyt tarvitsi vain funktion arvot sellaisenaan. En edes ollut ihan varma mitä tapahtui ja niin tuo aiemmin kehitetty syklinhavaitsija vaan havaitsi signaalista syklin ja kertoi oikean ratkaisun. Hurraa!

17, perinteinen dijkstra-reitinhaku

Joka AoC-vuodelle ei mahdu kunnon hankalaa reitinhakua kai ollenkaan ja joinain vuosina niitä on ollut useampiakin. Tällä kertaa tarina oli aika hauska ja pohjusti rajaehdot säännöille hakugraafin muodostamiseksi ruudukkokartasta. Haun verkkoviritys parametrisoitui yllättävän kivasti kakkosvaiheeseen, jossa laavameiningin sulatusastian muuttunut inertia muuttaa ruudukkokartassa suoraan matkustamisen ehtoja muttei muuta. Pitäisi taas harkita sitä dijkstran geneerisöintiä Rustin traittihommien harjoitukseksi. En edes tiedä menikö tuo ihan puhtaaksi dijkstraksi nyt, kun heuristiikka toimii puoliautomaattisesti tuolla heapin objektien vertailuissa.

#[derive(Debug, Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
struct Score {
    // incurred loss, smaller better
    heat_loss: Reverse<i32>,
    // heuristic distance, not actual;
    // just to make the heap prioritize spots close to goal
    dist_to_goal: Reverse<i32>,
}

18, jälleen monikulmion pinta-ala

En tbh ollenkaan muista mitä tapahtui, mutta koodin perusteella oli tuollainen inhottava tässä pitää tietää -harjoitus. Shoelace formula kai löytyi googlaamalla monikulmiota sopivasti tai jotain. Kun kirjoitan sen tähän niin varmaan muistan toistekin. Vähän sama kuin CRT eli harvoin elämässä mutta usein kisakoodaamisessa tarvittavia nippelitietoja. Pinta-alan olisi varmasti saanut itsekin johdettua kynällä ja paperilla, mutta kun algoritmi on keksitty niin kai sitä sitten käytetään, ei vaan tuntunut yhtä hauskalta päivältä kuin edes keskimäärin.

19, taasko lukuvälejä

Olipa jotenkin sama fiilis kuin päivässä 5, kun pyydetään taas pyörittelemään isoja pätkiä numeroita iteratiivisten lukuvälinvähennysten lävitse. Hankalaa tälläisessä on yleensä vain keskittyminen edes sen vertaa että välttää off-by-one-bugit. (Ihan kun oisin just sanonut tuon jo.) Varsinkin niin, kun ei vieläkään ole epävarma ohjelmoija onnistunut päättämään että käsitteleekö elämässään lukuvälejä poikkeuksetta oikealta avoimena vai ei (end-inclusive/end-exclusive); kummallakin on paikkansa ja joskus käy niin, että kaksi peräkkäistä lukuväliä menevätkin vahingossa päällekkäin tai jää rako väliin. Tavallaan saman hajuinen ongelma kuin ns. fencepost error. Jokunen kommentti koodiin aina auttaa hahmottelemaan.

fn splice_left(mut lo: Part, mut hi: Part, idx: usize, less_than: i32) -> (Part, Part) {
    // a < 2006: --lo--<++hi++
    // [old lo, new hi] matches, on the left
    hi[idx] = hi[idx].min(less_than - 1);
    // [new lo, old hi] remaining, on the right
    lo[idx] = less_than;
    (hi, lo)
}

fn splice_right(mut lo: Part, mut hi: Part, idx: usize, greater_than: i32) -> (Part, Part) {
    // a > 2006: --lo-->++hi++
    // [old lo, new hi] remaining, on the left
    hi[idx] = greater_than;
    // [new lo, old hi] matches, on the right
    lo[idx] = lo[idx].max(greater_than + 1);
    (hi, lo)
}

20, syötteen erikoisrakenne

AoCille tyypilliseen tapaan ainakin yhtenä kertana on pelissä muka joku oikein huoliteltu monimutkainen viritys ja sitten sitä ei juurikaan tarvitakaan kakkoskohdassa, kun tulee sellainen twist että inputista pitää jotenkin silmillä eikä tietokoneella nähdä että eihän tätä voi löytää speksatulla algoritmilla. Piti koodata piirisimulaattori ja joo kyllä sitä käytettiinkin kakkosvaiheessa, mutta juju olisi että koko piirin ajaminen lopputulosta varten taas kestäisi kovin kauan ja kannatti tarkastella signaalipiirien muodostamaa verkkoa ihan silmillä. Verkon rakenteesta huomataan, että kannattaa simuloida vaan verkon osia kerrallaan ja sitten yhdistää niiden tulokset.

Jotkut ihmiset eivät keskustelupalstojen mukaan tykkää tälläisistä twisteistä ollenkaan kun poikkeavat tyypillisestä kisakoodin puhtaasta aina pelkästään tehtävänannon perusteella ratkaistavasta formaatista, mutta itse en pane lainkaan pahakseni ja koin tämän(kin) päivän viihdyttävänä.

21, jonkinlainen toistuva rakenne

Kuten sanottua, niin koodaamisesta on ainakin yksitoista kuukautta ja jotkut yksityiskohdat ovat päästä haihtuneet. Puutarhapalstoja oli kakkosvaiheessa aika paljon, oikeastaan äärettömästi, ja tonttu halusi askeltaa 26501365 kertaa. Ei toisaalta iso luku, mutta maatilalla on pinta-alaa niin ongelma kasvaa suunnilleen tuon neliöön eli ihan liian isoksi. Täytyi raapia päätä tovi ja katsella inputtia ja piirrellä pellollakävelemissimulaatiota, niin selvästi nähtiin, että kun on pinta-alasta kyse niin varmastikin laskettava kävelemisen määrä kasvaa neliöllisesti ja senhän voi varmaan ratkaista ihan väkisin toisen asteen yhtälöön sovittamalla.

Kartan koko oli tasan 131 ruutua, puoliväliin pääsee 65 askeleessa, ja hauskasti muuten 26501365 = 202300 * 131 + 65, melkein easter egg että vuosiluku on piilotettu johonkin taikavakioon. Kartan säännöllisyys alkaa toistua 65 askeleen jälkeen, eli simuloidaan 65 askelta ja saadaan f(0) = y0. Simuloidaan siitä vielä 131 askelta ja saadaan f(1) = y1. Sitten vielä f(2) = y2 ja ratkaistaan a, b ja c yhtälöstä y(x) = a + b*x + c*x*x. Plugataan sekaan 202300 ja vastaus löytyy. Toki simulaatiota piti ykköskohdasta vähän sovittaa näennäisesti äärettömään karttaan jossa alkuperäinen kartta toistuu riittävästi noihin kolmeen iteraatioon.

23, verkkohakualgo vaihteeksi

Yleensä reitinhakuongelmissa kaivataan lyhyintä polkua. No nyt toivotaan pisintä. Kun inputtina on labyrintti ruudukkokartalla, niin perinteeksi muodostunut optimointimenetelmä on käydä labyrintti läpi ja eliminoida suorat käytävät, jolloin jää jäljelle pienempi verkko jonka etsii nopeasti. Tässä vielä kun verkon piirtää AoCille tyypilliseen tapaan kesken tehtävän ja sitä katsoo silmillä... ihan kuin näitä jekkutehtäviä olisi tänä vuonna enemmän kuin tavallisesti. No joka tapauksessa verkosta tuli suunnattu ja syklitön eli ammattilaisten kesken helppo. Sieltä löytyy pisin reitti triviaalilla syvyyshaulla ns. väkisin. Kakkostehtävän jäynä olikin, että verkkoa muokataan niin ettei olekaan enää syklitön ja helppo. Toistaiseksi valintani on bruteforcehaku koska verkko on pieni, menee sekuntikaupalla aikaa mutta alle kymmenen eli optimoidaan seuraavassa elämässä.

24, perinteinen 3d-avaruustehtävä

Lumimyräkkä lennättelee ilmassa isoja rakeita ja kuinka ollakaan, ne tulevat jossain kohdassa kaikki törmäämään sopivasti heitettyyn kivenmurikkaan. Ykkösosassa tarkasteltiin rakeita vain 2D:ssä, ja sopivalla näkemyksellä huomataan, että kivenkin sijainnin ja nopeuden löytää rajaamalla yhden ulottuvuuden pois ja sitten kokeilemalla väkisin. Vissiin on niin harvinainen case että oli yksiselitteinen vastaus jo 2D:ssä.

Valitsemani vektorimatikka menee siten, että oletetaan ensin kivelle joku kohtuullisen pieni lentonopeus suhteessa eeppisiin koordinaattimagnitudeihin. Kokeillaan nollasta maksimiin sopivaan nopeudet x- ja y-suunnissa ja katsotaan, osuuko rakeiden lentoratoihin. Katsominen onnistuu helpommin muuttamalla rakeiden radat eli suoran yhtälöt kiven koordinaatistoon ja havaitsemalla, onko kaikille ratapareille olemassa yhteinen osumiskohta kiven mielestä. Kun löytyy, niin kiven z-vauhti saadaan etsimällä ensin osumiskohta. Osumiskohdan ajasta päätellään takaperin alkusijainti, jota tehtävässä kysyttiin.

// r_p + t*r_v = a_p + t*a_v | r_p = a_p + t*a_v - t*r_v
// r_p + u*r_v = b_p + u*b_v | r_p = b_p + u*b_v - u*r_v
// a_p + t*a_v - t*r_v = b_p + u*b_v - u*r_v
// t*r_v - u*r_v = a_p + t*a_v - b_p - u*b_v
// (t-u)*r_v = a_p + t*a_v - b_p - u*b_v
let a_p = sum(storm[0].0, mulf(t, storm[0].1));
let b_p = sum(storm[1].0, mulf(u, storm[1].1));
let r_v = mulf(1.0 / (t - u), diff(a_p, b_p));
assert!((r_v.0 - rock_vel.0).abs() < 1.0);
assert!((r_v.1 - rock_vel.1).abs() < 1.0);
// r_p + t*r_v = a_p + t*a_v | r_p = a_p + t*a_v - t*r_v
let rockpos = diff(a_p, mulf(t, r_v));
rockpos.0 + rockpos.1 + rockpos.2

25, AoCille tyypillinen päivä 25

Tuntuu kuin ennenkin viimeinen päivä olisi ollut tämmönen, että syöte on jotenkin suhteettoman hankala koodata tai laskea verrattuna siihen, että sitä vain katsoo oikeasta kulmasta. Inputtiformaatti oli vaihteeksi graafirakenne ja sieltäpä piti hakea minimum cut jonka kyllä koodasin sivubranchiin joka pitää viimeistellä myöhemmin, mutta kolme poistettavaa kaarta verkosta löytyi ihan selvästi kun verkon vaan piirsi Graphvizillä ja katsoi.

Ratkaisu ei yleisty kenekään muun syötteelle juuri nyt kun siellä on esimerkin ratkaisu ja just nuo omat verkkoreunani, mutta lisäksi tehtävässä pyydettiin kahden jäljelle jäävän aliverkon kokojen tuloa ja senhän connected_pair() laskee (poistamalla verkosta noden kerrallaan ja siirtymällä naapureihin; toimii koska aliverkoista ei pääse toisiinsa).

if edges.len() == 33 {
    remove(&mut edges, "hfx", "pzl");
    remove(&mut edges, "bvb", "cmg");
    remove(&mut edges, "nvd", "jqt");
} else {
    remove(&mut edges, "ddl", "lcm");
    remove(&mut edges, "rrl", "pcs");
    remove(&mut edges, "mbk", "qnd");
}
println!("{}", connected_pair(&mut edges));

Johtopäätös

Jäi sellainen tunne, että tällä kertaa tuollaisia ensin helppoa mutta ähäkutti -mallisia oli tavanomaista enemmän. Voi olla, että vaikeustasoa nostetaan tahallaan kun AoCin suosio kasvaa ja pitää saada lisää hajontaa pelaajien välille. Mitään ihmeellistä Rust-oivallusta ei jäänyt mieleen ja viimevuotinen recursive_reference-tutkimuskin on kesken. Taisi olla kiirettä jossain elämähommissa, muutto ja kaikkea.