Olipa kerran taas aika kevyen koodivenyttelyn joulukuun aikana, kun Advent of Code starttasi tavalliseen tapaan. Jäi sellainen olo, että tällä kertaa yksikään tehtävä ei varsinaisesti jäänyt mieleen kovin kummoisena, ja keskimäärinkin vaikeustaso oli vähän helpompi. No, vuoden teemanakin oli relata aiemmilta joulupukinpelastuskeikoilta ja matkustella lomasaarelle. Näin noin kuukausi pelin loppumisen jälkeen on hyvä perinteisesti vähän reflektoida.
AoC ja Rust
Tein näitä myös 2019, 2018 ja 2017 eli jonkun noiden linkkien takaa voi käydä katsomassa mistä oli tarkemmin kyse tässä jokavuotisessa kisakoodiharrastuksessa. tl;dr: Rust on juuri sopivan lowlevel ja samalla ergonominen, että sopii ainakin meikäläisen kouraan. Advent of Code on kokoelma pieniä kaksiosaisia aivopähkinöitä. Käsitellään joitain päiviä, joista jäi ehkä jotain muistiin. Spoilereita tiedossa.
Näiden kisakoodipuuhien lisäksi on tekeillä kolme ihan oikeaakin ohjelmaa Rust-harjoitukseksi. Niistä joskus myöhemmin.
7 hakurakenneverryttelyt
Lentomatkalle valmistautuessa on kiinnitettävä huomiota laukkuihin. Tällä matkalla laukut ovat värjättyjä ja menevät sisäkkäin, ja sisäkkäin, ja niin edelleen. Kullekin värille on määritelty, mitä laukkuja sisään sopii ja montako. Ykkösvaiheen kysymys oli kumminkin, että kuinka moni laukku voi jonkin säännön kautta sisältää kultaisen laukun?
Omasta mielestä tähän sopi ilmiselvästi semmonen kikka, että kun tehtävän syötteessä on annettu tuollainen suunnattu verkkorakenne, niin rakennetaanpa verkko toiseen suuntaan (eli montako laukkua annetun värisen laukun ympärille sopii). Haku noin päin on nopeampi suorittaa, kuin väkisinhakemalla annetut säännöt ja pitämällä siinä kirjaa luvuista. Pieni off-by-one-bugi tuosta piti selvitellä mikä on aika tavallista. Oikeastaan raavin päätä aamulla ihan kunnolla, mutta kun tuo on nyt auki kirjoitettuna niin ihan selväähän se on että miksi. Hakualgo laski kultaisen laukun itsensäkin mukaan siihen kokonaismäärään.
Tehtävän kakkosvaihe olikin sitten verrattain naurettavan helppo, kun annettu tietorakenne eli tuo kassiverkko piti käydä läpi sellaisenaan ja laskea, mitä sen kullankiiltoisen laukun sisään sopii yhteensä. Veikkaan, että kun oli vasta päivä seitsemän, niin ykköskohdassa haettiin yksinkertaisempaa bruteforcea.
Rustista ei kai mitään kummempaa. Kaikki on vaan kovin mukavaa ja kääntäjä on ajan kanssa vaan nopeutunut ja muuttunut entistäkin ystävällisemmäksi.
8 assyhommaako
Aiempina vuosina on ollut muistaakseni ainakin yksi virtuaalikonetehtävä, ja monesti tehtävä on eskaloitunut jonain seuraavina päivinä eteenpäin. Tällä kertaa ei, mutta elättelin toivoa. Spekseissä oli yksinkertainen pelikonsoli, joka ajaa muutamaa assykäskyä. Jostain syystä sille annettu ohjelma ikilooppasi, ja tehtävänä oli tunnistaa, mihin tilaan softa jää. Ohjelma oli sen verran pieni, että tästä selvittiin ihan ajamalla sitä ja seuraamalla, mitkä instruktiot on nähty aiemmin.
Kakkosvaiheessa tajuttiin, että yksi osa annetusta ohjelmasta on mäsä ja jokin käskyistä pitää vaihtaa toisenlaiseksi, jotta ohjelma päättyisi. Kun päättyminen on määritelty helposti ja ohjelma oli pieni, niin riitti vaan kokeilla kaikkea. Ei kummempaa analyysiä hyppyoffseteista eikä basic block -graafia. Elättelin toiveita jatkokehityksestä, mutta se aiemman vuoden intcode-hässäkkä piti assykutkutusta yllä. Melkein palasin disasmaamaan sitä.
Rustin summatyypit ja match-rakenne ne vaan aina toimivat nimenomaan tälläiseen niin mukavasti, että kun töissä koodaa C:tä niin melkein itkettää. Paitsi että kyllä tässä nimenomaisessa tehtävässä tagged unioneilla ja switch-caseilla ois vielä ihan siististi selvinnyt, mutta ylipäänsä match on paras juttu.
9 prefix sum
Tällä kertaa lentokoneen portti pursottaa numeroita, ja määritelty numerosarja voisi olla jokin erikoinen tunnettu juju. Ykkösvaiheessa etsitään vain bruteforcella lukua, joka ei ole kahden aiemmista viidestä summa. Kakkosvaiheen kysymys oli löytää jokin summa jatkuvasta alijoukosta, joka täsmäisi annettuun suht satunnaiseen lukuun. Ajattelin aiemman vuoden vastaavaa kaksiulotteista ratkaisua kun en saanut päähäni sanaa tälle yksiulotteiselle vastineelle kuin vähän myöhemmin. Ei sen kummempaa.
Jäin miettimään, että mitä käytännön eroja lienee välillä std::iter::once(x) vs. &[x].iter(). std::cmp::Ordering on btw. paras juttu.
10 tribonacci
Nyt sen käsikonsolin akku loppui kesken lennon, mutta onneksi lentokoneessa on töpseleitä. Matkassa on mukana sovittimia, joilla jännitteenkaltaisen suureen saa täsmäämään seinän ja vekottimen välillä. Ensimmäinen vaihe tehtävästä koostui lähinnä pulma-asettelun tajuamisesta; toisessa vaiheessa täytyi suorittaa hakualgoritmi etsimään, monellako tavalla sovittimet voi järjestää.
Koska töpseliverkon alijoukkoja voi järjestellä holtittoman paljon uudelleen ja uudelleen, niin itselle tuntui järkevimmältä DP:ttää eli memoizettaa välituloksia ja nyt kun katsoo, että miten tuo ajaa, niin taitaa olla melkein suora looppi lopusta alkuun summaten lukuja toisiinsa. Myöhemmin kuulin, että täähän on jonkinlainen tribonacci-sekvenssi. Piti lukea tuostakin wikipediasta koko päivä, mutta luin vain hetkisen.
Nyt harmitti, että se std::iter::once() ei toimi std::slice::Windows() in kanssa, kun windows() on vain sliceillä eikä iteraattoreilla. Oisin halunnut ketjuttaa pari iteraattoria.
13 jakojäännöslooppi
Lentokentältä kulkee busseja, joiden reitit ovat syklisiä ja eri mittaisia. Jo ihan lähtöasetelma haisee kongruenssiyhtälöryhmältä eli jakojäännöksiltä missä en ole kovin hyvä kun mokoma pysyy hyvänä vain harjoituksen kautta. Kakkosvaiheessa täytyi selvittää yhtälöryhmän ratkaisua silleen hankalaan malliin, että kunkin bussin pitää lähteä minuuttia myöhemmin kuin aiempi eikä suinkaan samaan aikaan. Vähän huijasin ja huomasin taikasanan chinese remainder theorem, ja sit olikin vaan wikipediasta koodiksi -ongelma. Ilmeisesti tää onnistuisi monellakin eri menetelmällä, joista tuo on ns. mallisuoritus.
Ei sinänsä liity Rustiin, mutta nyt kun katson tuota koodia, niin ois pitänyt tehdä häntärekursiona eikä looppina, kun tuosta loopista ei saa enää mitään selvää. Iteraatioita ei tule kovin montaa, eli ihan sama että optimoituuko edes. Koodaan uusiksi seuraavassa elämässä.
14 bittioperaatiota
Yllättävän lyhyellä taustatarinalla siirryttiin bitinnypläämiseen, joka onneksi taipuu kuin mummolla villasukka. Signaalinkäsittelyprossun ominaisuudelta haiskahtava bitinsiirtelymenetelmä heiluttelee tehtävässä tiiviisti pakatun luvun bittejä epätiiviimmiksi, ja osoittautuu, että joissain prossuissa tosiaan on tälläinen, kuten x86-assyssä PDEP ("Parallel bit deposit"). Käytetään varmaan jossain SIMD-hommissa tai kryptossa, perus hämyopettavainen aoc-insight. Samalla esiteltiin ns. kelluva piuha, joka ei ole oikeestaan kytketty mihinkään signaalilähteeseen. Tehtävän käsitys tuosta oli vaan aikamoinen superpositio mitä ei tavallisesti tapahdu. Kirjailijan vapaus venyttää fysiikan lakeja on rajaton.
Sanokaa mitä sanotte, mutta mun mielestäni tuo Rustin huutomerkkioperaattori bitwise-NOTina on hirveen huono juttu. Tildemerkki taisi olla jossain muinaisessa kielen versiossa box-syntaksia? Kääntäjä sentään älähtää, että miten se kaikista bitinnypläyskielistä tuttu merkki pitää muuttaa jotta kääntyisi, mutta näyttää silti niin väärältä.
16 yhtälöryhmä eliminoitavaksi
Kun saatavilla on pino junalippuja joiden kenttien nimistä ei tiedetä mitään mutta tiettyjen kenttien (penkkirivi, junavaunu yms.) lukurajat tunnetaan, ja tehtäväsyöte on muotoiltu mukavasti, niin kentät voidaan päätellä yksi kerrallaan. Tälläiset eliminaatiotehtävät ovat aika tavallisesti helppoja kolmiomatriiseja sekoitettuna, ja joku työpaikan AoC-keskustelussa totesi, että rivit ja sarakkeethan voi vain järjestää takaisin kolmiomatriisiksi. Tällöin ratkaiseminen on helppoa.
Itse looppasin ja eliminoin tälläisestä yksi kerrallaan rivit tai sarakkeet, joissa on vain yksi elementti:
caebd 1 xx xx 4 x 2 xx x 0 xxxxx 3 x x
Sitten kun tuon matriisin älyäisi järjestää kolmion muotoon, niin eliminoinnin voisi suorittaa rivi tai sarake kerrallaan:
abcde 0 xxxxx 1 xxxx 2 xxx 3 xx 4 x
17 soluautomaatti
Game of Life -soluautomaatti on varmaan ihan perinne jo, paitsi että ei ihan, kun Conwayn pelissä on tietynlaiset säännöt ja AoC:n soluautomaateissa on vähän vaihtelevat. Tämän päivän tehtävässä ensimmäisen ja toisen vaiheen erona oli soluavaruuden dimension kasvu kolmesta neljään. Koska tuon toteutin ihan triviaalisti suunnitelmana ajatella myöhemmin, niin dimension lisäys tarkoitti käytännössä yhtä sisäkkäistä looppia lisää muutamaan paikkaan.
Tämä on hyvä pikkukoodi, jolla voi tutkia myöhemmin kahta temppua: pelin säännöt (sen suhteen, että montako naapuria tarvitaan hengissä pysymiseen jne) eivät sinänsä liity avaruuden dimensioihin; jokin avaruusrajapinta voisi tarjota ydinpelilogiikalle iterattorin tietyn koordinaatin naapurikoordinaatistosta, ja toki koordinaatistotyyppi voi olla joku geneerinen kun se vaihtelee dimension mukaan. Lisäksi tuo sisäkkäisten looppien puliveivaaminen käy tylsäksi, eli voisi käyttää jotain jo implementoitua tai implementoida sen karteesisen tulon itse.
19 säännöllisiä lausekkeita
Nyt ollaan taas lentokentällä, ja MIB ottaa yhteyttä. Osa viesteistä on mäsänä, mutta onneksi tiedetään, että minkä muotoisiin viesteihin voi luottaa. Tehtävässä on määritelty kielioppirakenne, johon osa inputista täsmää; tämän inputtipuolen perusteella luetaan varsinaiset viestit. Kuinka ollakaan, säännöistä voi rakentaa regexin ja parsia viestit sitten ulkoisella regexkirjastolla, mikä luonnollisesti ei ole yhtään huijaamista.
Tuo tuntui kuitenkin huijaamiselta, jotenka tottakai iltapäivällä piti koodata se pieni parseri itse. Pakko myöntää, että kun parserien kirjoittaminen ei ole oma leipätyö, niin kun tuo meni koodaten jossain inspiraatioflowssa, en enää ihan ymmärrä mitä tapahtui (en luntannut!). Rekursiivinen parserihässäkkä katsoo, täsmääkö viesti joihinkin sääntöihin (joita voi olla periaatteessa rekursiivisesti holtittoman monta vaihtoehtoa). Parserihässäkkä on funktio, joka palauttaa tiedon siitä, mikä osa viestistä jäi vielä lukematta - tai oikeastaan useamman moisen vaihtoehdon, kun syntaksipuussa voi olla useampi täsmäävä vaihtoehto. Jos vaihtoehdoissa on tyhjä merkkijono, niin koko homma löytyi. Aina kun jokin pätkä alusta näyttää täsmäävän, kokeillaan että täsmääkö siitä jatkuva loppupätkä myös.
Tehtävän kakkososassa tuotiin mukaan vähän jännyyttä, kun pariin sääntöön luotiin viittaus itseensä. Tyhmästi tekemällä tässä olisi jäänyt ikilooppiin, ja regexit eivät ihan tue äärettömyyttä, mutta purkkasin ensin regexejä varten tuohon unrollaamisen kymmenkunta kertaa; artesaaniparseri selvisi ilman kamalia kikkoja, kun rekursiosäännössä ei ole tokenia itse koskaan ensimmäisenä, vaan toisto on muotoa "8: 42 | 42 8" eikä esim. "8: 42 | 8 42" ja "11: 42 11 31" eikä esim. "11: 11 42 31".
Rustin summatyypit on paras juttu ja borrow checker ei edes älähtänyt kuin kerran, eli kai tää alkaa sujua. Vähän hermostutti liian helpot vektoriallokaatiot joita tulee varmaan turhan paljon jos jotain voisi preallokoida, mutta onpa tarpeeksi nopee toistaiseksi.
20 pikseleitä bitteinä ja dfs ja taas pikseleitä
Aiemman päivän viesteistä mukamas selvisi satelliittikuvia. Satelliitin monta kameraa ottavat kukin vain palan kokonaiskuvasta, joka pitää koota palapelin tavoin kun kuvat ovat saapuneet missä sattuu järjestyksessä. Tämä palapeli on tavallaan ihmisten palapelejä helpompi, kun 10x10 pikselin kuvien reunat koodaavat melko lailla yksiselitteiset kuvaparit. Kuvia oli 144 kappaletta, mistä piti suorittaa valistunut arvaus rivien välistä lukemalla, että kokonaiskartta on neliskanttinen eli koostuu 12 kuvasta kanttiinsa. Suoritin palojen täsmäämisen ihan syvyyshakuna verkossa, jossa tilasiirtymiä kuvasti se, että pala asetetaan aiemmin laitetun viereen; palat aseteltiin vasemmasta ylänurkasta (tai oikeastaan mistä tahansa nurkasta, orientaatiolla ei ole niin väliä) eteenpäin rivi kerrallaan. Vaihtoehto olisi ollut lätkiä paloja toistensa viereen jolloin ensimmäinen pala voisi olla jokin muukin kuin tuo nurkka (mitä vertailtiinkin joulupöydässä veljen kanssa).
Palojen asettelussa tuli kikkailtua koska voi: reunan pikselit sai koodattua kunkin yhteen 16-bittiseen lukuun, ja reunoja voi vertailla ihan vertailemalla näitä lukuja (varmaan tämän bitti-implementaation ja monochrome-kuvankäsittelyn välille oisi voinut hifistellä vielä yhden abstraktiovälin). Toisaalta kuvapalikoiden pyörittäminen ja kääntäminen vaatii tarkkuutta vaativat uudelleenjärjestelyoperaatiot johonkin väliin. Kikkailin edelleen ajonaikanopeusoptimoinnin siten, että pyöritin pelkästään näiden palakuvien reunoja; varsinainen kuva pyöriteltäisiin myöhemmin kasaan, kun pyörittelyn aikana vain pidetään yllä minimaalista informaatiota siitä, missä muutamasta (= kahdeksan) vaihtoehdosta orientaatio on. Tää meni vähän työlääksi kun koodasin verboosisti ettei mene ihan epäselväksi, mutta hauskaa kikkailua.
Toinen osa tehtävästä olikin sitten merimonsterien etsimistä lopullisesta kuvasta, josta piti vain pyyhkiä pois nuo kuvapalojen kohdistusreunat. Koko kuvakin täytyi toki pyöräyttää oikeaan asentoon vertailua varten. Muutamat indeksoinnit piti tarkistaa useampaan kertaan - valitettavasti AoC ei tarjoa kunnollisia yksikkötestejä... Kun koko kuva mahtui 128 bittiin (Rustissa muuten on 128-bittiset kokonaisluvut ja ai että!), niin merimonsterien haku oli jälleen hassu aivojumppmatemppu bittimaskeilla.
.#..###..........#O#.............#..#..#.#.....O# O##..OO..#.OO....OOO.#...#...O.#..OO....OO...#OOO #O..O#.O.#O..O#.O#.#....#.....O..O..O..O..O..O...
21 joukko ja mappi ja taas eliminaatio
Tänä vuonna AoC ei seikkaile avaruudessa, mutta tuntemattomilta kieliltä ei voida välttyä taaskaan. Tehtävän ydin oli aivan kuin päivän 16 tuntemattoman kielen selvittäminen, paitsi puettuna vähän eri muotoon ja sisältäen vähän joukko-oppia (helppoa, koska joukkotietotyyppi löytyy kielestä jo). Ensiksi ruuista ja niiden sisältämistä allergeeneista nakerreltiin vähän tietokantaa tarkastelemalla, että mitkä ruokien sisällöistä voisivat olla mitäkin allergeeneja, ja poissulkemalla joitain selviä keissejä. Nyt kun tiedetään, että mitkä ainesosat voisivat hyvinkin mahdollisesti olla mitäkin allergeeneja tai kääntäen, niin redusoidaan tilanne suorittamalla samanlaista matriisieliminaatiota kuin päivässä 16.
Rustin hashmappirajapinta jätti toivomisen varaa, kun halusin poistaa jotain arvon enkä avaimen perusteella. Siinä missä C++:n unordered_mapille voi sanoa std::find_if ja saada tietotyypin oman sisäisen iteraattorin sinne tietorakenteen sisään, jolla voi suorittaa että unordered_map::erase() niin hashmapin muuten niin erinomainen Entry-api (joka tuota iteraattoria lähimpänä lienee) ei sisällä mitään poistomenetelmää. Poistettavan asian hashaaminen tuplasti ei ole oikeasti kovin paha tässä tilanteessa, mut koodista näkyy epäeleganttius.
Lisäksi remove_entry() ei huoli sisäänsä viittausta, joka hashmapin entrystä saataisiin, koska remove_entry haluaa asian, jonka elinaika on olemassa funktiokutsun ajan; poistettava asia lähtee kesken kaiken pois, eikä funktio voi vetää mattoa itsensä alta. Pelkkä funktiokutsun tasoinen lifetimeseuranta ei riitä tässä tilanteessa; ehkä Entry-apiin leipominen unsafen kautta voisi toimia, kun ei sitä viittausta enää sen jälkeen tarvita, kun se poistettava yksilö on löytynyt.
Rustin hashmappi käyttää sisäisesti tätä kirjoittaessa hashbrown-nimistä implementaatiota, jossa taisi olla vähän laajemmat rajapinnat. Ehkä tää hoituu joskus. Pitäisköhän itse ajaa asiaa?
23 linkkilista
Joku rapu haastaa kisaamaan. Pelin idea on pyörittää jotain kuppeja ja voi veljet niitä pyöritelläänkin, kun päivän kakkososassa krapu heiluttelee miljoonaa mukia kymmenen miljoonaa kertaa. Näistä kisatehtävistä pitää nähdä selvästi, että mikä on iso luku; monesti ratkaisua ei löydy ihmisen odottamassa ajassa, ellei seurattavista lukuarvoista löydy jotain säännönmukaisuutta jos kyseessä on iso luku. Monena vuonna jokin tehtävistä on vaatinut, että tunnistetaan sykli. Kymmenen miljoonaa on kuitenkin pieni luku; tähän kuuluu kovakoodata verrattain hyvä koodi ja bruteforcettaa sitä, kun luku ei ole mitään triljoonaluokkaa.
Rust on tunnettu siitä, että linkitetty lista on maailman kurjin tietorakenne. Kun pyöriteltävien kuppien järjestystä piti seurata, mutta niitä oli kätevästi vakiomäärä, niin mukien seuraava muki -osoittimet riitti koodata vakiokokoiseen taulukkoon: indeksointi on helppoa, ja taulukon arvoina on vaan indeksejä. Ei referenssejä, ei lifetimeongelmaa, toisaalta off-by-one-bugeja joka paikassa joita edes taulukon ohi indeksoinnin tarkistus yleensä löydä, ja raakaindekseissä ei saa borrow checkeriltä mitään apua.
Lopuksi
Rust on paras juttu ja toteutan edelleen jatkossa kaiken uuden softan sitä käyttäen (paitsi viime vuodet on aika niukasti viitsinyt kehittää omaa softaa kun töissä tyhjenee koodikutkutusbufferi, ja kotona on kiva käyttää aikaa mm. keittiössä). Ja kun return-statementin pois jättäminen on suositeltavaa, niin funktioista tulee lyhyitä kivoja lausekkeita ja koodista funktionaalista. Ainakin kivoimmissa tapauksissa. Ja kun kaikki on lausekkeita niin kaikki on konsistenttia.
fn bags_inside(bag_contents: &HashMap<&str, &Vec<(u32, String)>>, owner: &str) -> u32 {
bag_contents.get(owner).unwrap().iter().map(|(organ_count, organ_name)| {
// this many bags, and equally many units of contents of this bag kind
organ_count + organ_count * bags_inside(bag_contents, organ_name)
}).sum()
}
Sit kun osaan Rustia kunnolla, niin opettelen seuraavaksi vaikka lispaamaan.
0 kommenttia
Oma kommenttisi
Mielipide tämän sivun asiasta? Kirjoita toki. Älä raapusta kuitenkaan ihan asiattomia juttuja.
Jos on yksityisempää asiaa, tarkkaa kysyttävää tai aihetta pidemmälle keskustelulle, käytä yhteydenottolomaketta kommentoinnin sijaan.
Hölmöt kommentit saatetaan moderoida pois jälkikäteen.