Taas oli joululoma kooditouhuineen ja nyt vuoden vaihduttua odotellaan, että minkähänlaisia haavoittuvuuksia Intel tarjoaisi tällä kertaa. Joko viime kerrasta on tosiaan vuosi? Reilu pari vuotta sitten piti harjoitella Rustia ja niin edelleen, vuosi sittenkin puljasin koodikalenteria ja nyt on taas samasta kyse. Oli joulukuu ja sen myötä Advent of Code 2018, jonka otin jälleen tekosyyksi harjoitella Rustia. Seuraa tajunnanvirtaa koska otan aina liian vähän muistiinpanoja ja jos nyt kerrankin ja hei tällähän voisi aloittaa vaikka uudenvuodenlupauksen.
Rust? AoC?
Näitä voisi avata tässäkin mutta osoitan vain lukijan tuonne viimevuotiseen raporttiin. Tiivistetysti sanotaan vaikka, että Rust on olevinaan melko tykätty ohjelmointikieli, joka sopii natiiviudessaan C:n yms. reviirille ja tarjoaa silti oikein moderneja ominaisuuksia, muistikorrektiutta ja mieletöntä ergonomiaa. Advent of Code on yksinkertaisesti hauska jouluaiheinen tarina, joka etenee algoritmisilla kisakoodaustyylisillä ongelmilla, jotka ratkaistaan yleensä kirjoittamalla pieni ohjelma.
Omat ratkaisut löytyvät Githubissa olevasta reposta. Pidemmittä puheitta katsotaanpa missä tehtävissä tuli opittua tai ajateltua epsilonia enemmän. Vertaan ehkä välillä C:hen tai C++:aan. Siellä sun täällä on varmaan pieniä vinoja tyyliseikkoja, jotka Clippyllä vielä myöhemmin korjailen harjoitukseksi (lol niinpä vissiin, sama on vielä tehtävänä viimevuotisillekin koodinpätkille). Koodista itsekseen höpöttäminen oikeasti viisastaa.
Vähän olen kyllä myöhässä (viimeisen ratkaisun sain valmiiksi viikko sitten), sillä pari turhauttavaa tehtävää saivat jumiin, yksi viikko hukkui hektisessä palaveerauksessa työreissulla Intiassa ja niin edelleen. Vaan tulipa kuitenkin tehtyä ja oli hauskaa, vaikken kisavauhtiin ehtinytkään. Lopulta ehkä kivointa hommassa oli pohtia näitä veljen kanssa mm. lumisessa metsässä tallustellen.
8, eka kunnon rekursiotehtävä
Puretaan datapaketti, joka koostuu puurakenteesta. En vaivautunut kuitenkaan rakentamaan varsinaista puuta vaan siirryin itse numerovektorissa vaan eespäin. Ei tässä mitään ihan kummempaa, kunhan oli edes vähän epätriviaali. Onkos tämä iteraattorin kloonaus nyt ihan kosher ja sai miettiä että mites tämä menisi C:nä, pointteri vaan tuossa ja data siellä.
Rustin iteraattoreihin täytyy tutustua joskus ihan tarkkuudella, jotta näkisi, että missä vaiheessa tyyppitieto varsinaisesta datasta hukkuu ja minkälaista iteraattoria voi vaikka random-accessoida vs. vain stepata yksi kerrallaan eteepäin. POD-taulukoille nämä suunnilleen vastaavat pointtereita, mutta iteraattoreilla voi tehdä generaattorimeininkiäkin eikä alla välttämättä ole eksplisiittistä dataa.
Vaikka tätä ei tarvinnut miettiä pienen inputtikoon takia tarkemmin, ehkä löytyy temppu jolla iteraattoria voi edistää enemmänkin kuin yhden verran kerrallaan tai sitten tuo looppi sattuu optimoitumaan yhdeksi pointterin summaukseksi:
fn skip_node_recursive(v: &mut Iter<u32>) {
// [ ... ]
for _ in 0..metadata_entries {
v.next();
}
9, vaihteeksi linkitetty lista
Ehkä tähänkin tehtävään olisi jokin päheä analyyttinen ratkaisu, mutta erikoistapauksen takia se ei näyttänyt ilmiselvältä joten bruteforcetin. Melkein kaikissa näistä on niin pieni inputti, että algon aikakompleksisuus voi olla hyvinkin huono ja silti ratkaiseminen kestää alle sekunnin. Nyt joulutontut pelaavat keskenään ringissä jotain peliä jolle oli vain annettu tarkat säännöt. Erikoistapaus on välillä datan rakenteesta riippuva mutatointi.
Kokeilin triviaaliratkaisua vektorilla, mutta dataa on melko lailla ja se muuttuu koko ajan, eli kopiointia tulee hirmuisesti. Tuli taas kunnon throwaway-koodia, sillä seuraavaksi premature-optimoin tuplalinkitetyn listan triviaalilla allokaattorilla (heappihan on tunnetusti sairaan hidas) eli uusia nodeja tökitään vektorin perään, nodeja ei oikeasti poisteta muistista, ja linkit osoittavat vain taulukon indekseihin sillä data ei koskaan liiku mihinkään. Varsinainen puzzle meni ihan suoraviivaisesti tehtävänannon perusteella, eli kai tässä tuli jumpattua Rustin kirjoittamista perusarkiseen tapaukseen.
Kunnolla jos olisi tehnyt, niin olisi voinut vaikka lukea siitä, miten hankalaksi Rust oikeasti tekee linkitetyt listat ja soveltaa tähän tehtävään. Ja täähän on oikeasti tosi huono tietorakenne mihinkään varsinaiseen dataan. Paitsi kernelissä taas listoja on joka puolella, sillä kzalloc()oitu data ei mielellään liiku mihinkään.
11, viimein oikeasti algokivaa
Ei tässäkään niinkään ollut mitään erityisen kiinnostavaa Rustin suhteen mutta ratkaisua sai aavistuksen verran kikkailla. Päämääränä on valita paras polttokennokoordinaatti ilmeisesti jotta aikamatkustus onnistuisi. Oikeastihan tässä ilmeisesti haettiin summed-area tablea joka oli ihan sormenpäillä mutta en ihan saanut päähäni. Täytyy raapia päätä enemmän. Triviaaliratkaisu laskisi konvoluutioasioita uudelleen ja uudelleen; tunkkasin gittilokin mukaan kolmetoista sekuntia kestävän ratkaisimen, joka optimoi yhdellä lailla muttei monella muulla.
Lasketaan neliön sisältämien lukujen summaa ja neliön koko kasvaa yhdellä joka iteraatiolla, ja "hieno optimointi" on vain että lasketaan uuden neliön reuna eikä sen sisälle jäävää aiemmin laskettua pienempää neliötä aina uudelleen. Neliöiden laskeminen kuitenkin aloitetaan alusta joka koordinaatista, vaikka nekin voisi tuolla lailla tavallaan cacheta laskemalla ensin joka ruudulle summa ylänurkasta ja sitten pyörittelemällä nurkista alineliön arvo. Varmaan korjaan vielä.
Rusthauskaa tässä oli lähinnä nuo iteraattorijumpat joita tulee tahallaan verryteltyä. Kaksiulotteinen summajuttu lasketaan esim. tällä lailla: (Alueen nurkan summauksen voisi periaatteessa vaihtaa tuohon rangejen alustukseen)
fn square_power(x0: i32, y0: i32, serial: i32, sz: i32) -> i32 {
(0..sz).flat_map(|y| (0..sz).map(move |x| {
fuel_cell_power_level(x0 + x, y0 + y, serial)
})).sum()
}
12, aocille tyypilliset oivallukset
Tarina johdattaa tunneliin, jossa on pitkä määrä kukkaruukkuja. Ruukkujen kasvit lisääntyvät soluautomaattimeiningillä. Jutun juju on, että tehtävän ykkösosa on helppo (soluautomaattimeininkiä iteroidaan vaivaiset 20 generaatiota), ja kakkososassa pitäisi pyöritellä numeroita yhtäkkiä 50000000000 kertaa. Kun ruukkujen sisällöt tulostaa joka kerta, ei vielä 20 iteraation päästä erotu mitään kummempaa mutta hetken päästä ns. nähdään selvästi (tyypillistä), että ruukkujen data konvergoituu tiettyyn kuvioon, joka ainoastaan siirtyy (omalla inputillani) oikealle päin tietyn verran. Tästä voidaan sitten ekstrapoloida ratkaisu helposti vakioajassa.
Koska kukkaruukkuautomaatti voi liikuskella levitessään vasemmalle ja oikealle, niin tämäntyyppisissä tulee monesti käytettyä vaikka hashmappia varsinkin jos data menee vielä hajalleen, sillä vektorin tms. kasvattelu kumpaankin suuntaan tälläisellä nimenomaisella tavalla on jokseenkin ärsyttävää. Riitti kuitenkin allokoida tarpeeksi eli aika vähän varakapasiteettia reunoille siihen saakka, että aloilleen asettunut syklipatterni löytyy.
Rustin suhteen tässä itse ehkä onnuin kaikista eniten, sillä en voi väittää koodia millään lailla elegantiksi. Ehkä palaan myöhemmin asiaan. Mainittakoon silti, että range-indeksointi on kivempaa kuin näkkileipä:
// pots: &[u8] let current = &pots[i-2..=i+2]; // current: &[u8]
15, runsaasti koodattavaa
Tarkoilla säännöillä speksattu luolatappelu melkein lannisti aika moneksi päiväksi, kunnes meni jokainen yksityiskohta oikein. (Oikeassa elämässä olisi kirjoitettu kattavat testit ja sitten kohdennettu testi olisi kannustanut korjaamaan, mutta tässä ei viitsinyt, ja ainoastaan esimerkki-inputtien kanssa iterointi on kurjaa testattavaa.) Luolassa kulkevat tontut ja peikot (tanssivat, heikot / haisevat haaskat horjuvat pois) osaavat alkeellisen reitinhaun (joka toki tehdään itse) ja lähitaistelun; kartalla olevat yksiköt kulkevat ensin vastatiimin yksiköitä päin ja sitten alkavat mättää kunnes nirri on pois.
Reitinhakuun riitti yksinkertainen leveyshaku; Rust tarjosi melkeinpä pelkästään ergonomiaa eikä edes borrow checker tarvinnut erityisempiä uhrilahjoja. Leveyshaun jonon tilatyyppiin sisällytin paikan ja etäisyyden lisäksi sen, mihin suuntaan alkuruudusta lähdettiin; tehtävänanto määritteli jotakuinkin joka välissä missä olisi voinut tulla epäselvyyksiä että samanarvoisista koordinaateista valitaan se, joka on ensimmäisenä "reading orderissa": ylhäältä alas, vasemmalta oikealle. Täten monen yhtä lyhyen reitin kokoelmasta valitaan yksiselitteisillä säännöillä joku tietty. Ja tässähän meni helposti homma pieleen.
Reiteissä oli monta eri vaihtoehtoa haettavana; riitti kuitenkin hakea etäisyys pelaajan pisteestä kerralla jokaiseen muuhun kiinnostavaan karttapisteeseen sen sijaan, että olisi tehnyt hakua aina uudestaan, mikä olisi hidastanut hommaa aika lailla.
Reitinhaun alustus menee siis näin, kun pelaaja sijaitsee koordinaatissa (x, y) ja liikkua voi vain vasemmalle tai oikealle:
let mut queue = VecDeque::new();
// [ ... ]
for &(xi, yi) in &[(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] {
if walkable(map, units, xi, yi) {
queue.push_back((xi, yi, xi, yi, 0));
distances.insert((xi, yi), (0, xi, yi));
}
}
Tavallisestihan voitaisiin laittaa jonoon vain yksi alkupiste. Tässä se mihin päin pelaajan pisteestä lähdettiin on reitin ominaisuus. Hakulooppi onkin sitten ihan tavallinen:
while let Some(current) = queue.pop_front() {
let (xi, yi, x0, y0, dist) = current;
// ... bfs ...
Ja sitten, kun haku on tehty ja pathinfos sisältää etäisyydet ja reading orderin mukaisen alkupisteen per vihusijainti, voidaan käydä viholliset (e) läpi ja tarkastella niiden naapurustot:
for dst in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
let e_x = e.x + dst.0;
let e_y = e.y + dst.1;
if let Some(&(dist, sx, sy)) = pathinfos.get(&(e_x, e_y)) {
in_range.push((dist, e_x, e_y, sx, sy));
}
}
Lopulta kun mahdolliset reitit on kerätty, niin järjestetään ne, jotta saadaan paras: (varmaan sort_unstable_by_key olisi vielä mukavampi)
// sort by distance, then by reading order of goal (i.e., y then x),
// then reading order of move
in_range.sort_unstable_by(|a, b|
(a.0, a.2, a.1, a.4, a.3).cmp(&(b.0, b.2, b.1, b.4, b.3)));
Oikeasti riittäisi vain hakea maksimi tuon paremmuuspisteytyssäännön perusteella eli kokonaisen taulukon järjestäminen olisi liian hienoa, mutta jossain välissä koodi oli liiankin abstraktia eikä tässä vaiheessa tiedetty, että reiteistä riittää tällä kertaa vain yksi.
Vihujen valikointi on tarkkaa:
let enemies = units.iter_mut().filter(
|e| e.charclass != player.charclass && e.hp > 0);
let in_range = enemies.filter(
|e| (e.x - player.x).abs() + (e.y - player.y).abs() == 1);
Välttääkseni joissain paikoissa referenssien keljuudet kaikki pelaajat ovat listassa jonka järjestys ei muutu koskaan. Pelaajat voivat toki menettää elämänilonsa holtittoman paiskomisen takia, ja jossain välissä bugasikin niin, että joku haudattu pelaaja vahingossa tappeli naapuriensa kanssa, kun hyvinvointipisteitä ei otettu juuri siinä huomioon. Tämän voisi ehkä myös hifistellä vahvemmalla tyypityksellä huvin vuoksi.
16, taas enumkivaa
Kuten viime kerralla niin myös tänäkin vuonna oli tietysti virtuaalikoneaiheisia tehtäviä useampikin. Tässä lähdettiin taas assemblykoodin ajamiseen (tai tulkkaamiseen), kun päähenkilön mukana on tietokone, josta löytyy toinen toistaan hienompia ominaisuuksia. Täytyy vaan mainita, että kyllä noilla summatyypeillä ja patternmatchailulla tälläinen menee ergonomisesti.
Tässä tehtävässä oli kuitenkin pieni lisämauste aiempiin verrattuna. Ajettava ohjelma oli toki mukana, mutta numerokoodien mappaus opcodeihin täytyi tehdä annetun esimerkki-input-output-parien perusteella. Ehkä tuosta olisi monimutkaisemmankin säännöstön saanut, sillä tämä ratkesi yllättävän helpolla askel kerrallaan hakemalla aina jäljellä olevista tuntemattomista opcodeista se, joka sattuu ainoana täsmäämään annettuihin esimerkkeihin. Poissulkemalla ristiriitoja olisi saanut lisähaastetta.
Funktion deduce_coding() ydin on vain:
while !ops_remaining.is_empty() {
for (i, mapping) in found_codes.iter_mut()
.enumerate()
.filter(|(_, m)| m.is_none()) {
if let Some(op) = unique_match(i, samples, &ops_remaining) {
ops_remaining.remove(&op);
*mapping = Some(op);
}
}
}
Siitä summatyyppiergonomiasta sen verran, että:
let c = &mut machine.regs[inst.out];
*c = match inst.opcode {
Addr => ar + br,
Addi => ar + bi,
Mulr => ar * br,
// ...
17, muuten vain kiinnostavaa rekursiota
Veden valuminen maastossa savesta muodostuneisiin kippoihin ja kuppeihin sai aikaiseksi floodfill-tyyppisen rekursiopuljauksen. Vesisimulaatio oli määritelty siten, että vesi putoaa alaspäin, täyttää törmätessään reitin vasemmalle ja oikealle, ja reunalle päästessään valuu taas alas.
Pari kertaa sai muistaakseni aloittaa alusta kun rekursiopuljauksessa tuli joku ylitsepääsemätön designbugi, jonka huomasi vasta implementoidessa. Lopulta päädyin pudottelemaan "pisaroita" speksatusta lähtökoordinaatista piste kerrallaan; pisara kuitenkin maahan osuessaan jakautuu kahtia ja lähtee skannaamaan vasemmalle ja oikealle. Vaakasuuntapisara voi törmätä seinään tai pudota reunalta. Jos molemmat törmäävät seinään, törmäysfunktio täyttää löytyneeseen kulhoon vesikerroksen. Jos ainakin toinen putoaa reunan yli, niin vaakasuuntahaku rekursoi putoamiskohdasta uuden pisaran ja törmäysfunktio täyttää kartalle tähän kohtaan "vesikanavan" eli aluetta, jossa vesi on käynyt mutta josta se valuu pois.
Peli loppuu, kun kaikki pisarat ovat pudonneet määritetyn alueen ulkopuolelle. Sitten lasketaan, paljonko jäi vettä lillumaan ja paljonko vettä koskaan koski johonkin ruudukon ruutuun.
Vasemman ja oikean pisaran tilapäättelystä tuli aika hauska match-lauseke. Muuttujat l ja r ovat tupleja, joissa on tapahtuman tyyppi sekä vaakasuuntainen kulkuetäisyys. Water on vettä ja Channel merkitsee vesikanavaa, johon vesi ei jää lillumaan.
// cannot fall anymore, so disperse around
let l = left(g, x - 1, y);
let r = right(g, x + 1, y);
match (l, r) {
((BounceWall, xl), (BounceWall, xr)) => {
g.fill(xl, xr, y, Water);
return BounceWall;
},
((FellCliff, xl), (FellCliff, xr))
| ((Exit, xl), (FellCliff, xr))
| ((FellCliff, xl), (Exit, xr))
| ((BounceWall, xl), (FellCliff, xr))
| ((FellCliff, xl), (BounceWall, xr)) => {
g.fill(xl, xr, y, Channel);
return FellCliff;
}
((Exit, xl), (Exit, xr))
| ((BounceWall, xl), (Exit, xr))
| ((Exit, xl), (BounceWall, xr)) => {
g.fill(xl, xr, y, Channel);
return Exit;
}
}
18, hauska sykliasia taas
Kuten tehtävässä 12, tässäkin oli olevinaan ihan järjetön soluautomaattimeininki tällä kertaa puunhakkuuaiheisena, jota ajettaisiin melkein ikiajat kunnes päätellään kartalle jäävän tilan arvo. Onneksi simulaation debugprinteistä nähtiin selvästi, että metsän rakenne saavuttaa ennen pitkää pyörivän spiraalin kartan nurkkaan, joka paiskoo kartalle puunhakkuuaaltoja, vaikka alkuasetelma vaikutti satunnaiselta. Näitä hauskoja AoC-tyylisiä oivalluksia jälleen.
|##...................|||||||##................... ###.................|||||||####................... ##................|||||||####..................... ................|||||||####.................|..... ..............|||||||####.................|||||... ............|||||||####.................|||||||||. ..........|||||||####.................|||||||||||| ........|||||||####.................|||||||###|||| .......||||||####.................|||||||#######|| .......||||####.................|||||||####...#### ......||||###.................|||||||####.......## ......|||##.................|||||||####........... .....||||##...............|||||||####............. .....|||##..............|||||||####............... ....||||##............|||||||####................. ....|||##...........|||||||####................... ...||||##.........|||||||####..................... ...|||##.........||||||####.................|..... ..||||##........|||||####.................|||||... ..|||##.........|||####.................|||||||||. .||||##........||||##.................|||||||||||| .|||##.........|||##................|||||||###|||| ||||##........||||##..............|||||||#######|| |||##.........|||##.............|||||||####...#### |||##........||||##...........|||||||####.......## ||##.........|||##..........|||||||####........... ||##........||||##........|||||||####............. |##.........|||##.........|||||####............... |##........||||##........||||####................. ##.........|||##.........|||###................... ##........||||##........||||##.................... ..........|||##.........|||##...............|..... .........||||##........||||##.............|||||... .........|||##.........|||##............|||||||||. ........||||##........||||##..........|||||||||||| ........|||##.........|||##.........|||||||###|||| .......||||##........||||##........||||||#######|| .......|||##.........|||##.........||||####...#### ......||||##........||||##........||||###.......## ......|||##.........|||##.........|||##........... .....||||##........||||##........||||##........... .....|||##.........|||##.........|||##............ ....||||##........||||##........||||##............ ....|||##.........|||##.........|||##............. ....||||##........||||##........||||##............ .....|||##.........|||##.........|||##.....||..... .....||||##........||||##........||||##..##|||.... ......|||##.........|||##.........|||######|||.... ......||||##........||||##........|||||###||||.... .......|||##.........|||##.........||||||||||.....
Eipä Rustin suhteen mitään erityistä oivallusta, mutta tässäpä mukava koodinpätkä, jolla löydetään syklin pituus inputin perästä, missä sykli on toistunut jo jonkin aikaa:
fn cycle_len(v: &[usize]) -> usize {
for len in 1.. {
let a = v.iter().rev();
let b = v.iter().rev().skip(len);
if a.zip(b).take(len).all(|(a, b)| a == b) {
return len;
}
}
unreachable!()
}
En ole vielä ihan varma, että onko siistimpää looppailla periaatteessa äärettömästi noin, että indeksi tulee forrista ja loopin perään tarvitaan unreachable!() jotta kääntäjä olisi samaa mieltä, vai niin, että indeksiä mutatoitaisiin käsin ikiloopissa (loop { ... }).
Reuna-arvojen kiusallisuus iski tässä(kin) siten, että kun soluautomaattihomman täytyy katsoa naapurustoa laskiessaan seuraavaa generaatiota, niin reunimmaiset indeksoisivat kartan yli ellei niitä ohjelmoi erikseen. Indeksointia voi tehdä vain tyypillä usize mutta nollan arvoisesta usizestäpä ei voi tavallisesti miinustaa nollaa suurempaa tai koodi panikoi. Paitsi että käänsin nämä useimmiten optimointiflagi päällä (rustc -O) jolloin noita ylialivuototarkasteluita ei tule mukaan eikä koodi panikoi. Taulukon indeksointi on joka tapauksessa rajatarkastettu, eli usizen wrappaaminen suureksi luvuksi ei haittaisi:
match *map.get(yi)
.unwrap_or_else(|| &default_row)
.get(xi)
.unwrap_or_else(|| &default_yard) {
TREE => trees += 1,
19, reverse-engineering-aamiainen
Kuten perinteikästä on, nyt annettiin sille aiemmin implementoidulle virtuaalikoneelle sellainen ohjelma, että sen ajaminenpas kestää kovin pitkään, sillä se ajaa hitaaksi tehtyä algoritmia. Ei riitä enää vain tulkata koodia, eikä natiivikoodikaan käy, vaan tutkitaan assyä ja katsotaan mitä ohjelman olisi tarkoitus tehdä. Sitten optimoidaan triviaalisti ja ajetaan hieman muokattu versio. Päivän juju oli, että taikalaitteen manuaalista löytyi että programcountteri olikin tavallinen rekisteri, jota voi muokata suoraan. Control flowsta tulee kiinnostavampaa.
Konvergoitunut menetelmäni näihin menee osimoilleen näin:
- Muutetaan koodi C-tyyliseksi, joka on omaan silmään nopeampi lukea: addi 4 16 4 -> r4 += 16 tai mulr 1 2 3 -> r3 = r1 * r2
- Instructionpointteri on omalle inputilleni nelosrekisteri, eli muokataan seuraavaksi r4:n tilalle sana IP, jotta se erottuisi selvemmin
- Edelleen tässä tehtävässä instructionpointterin käpistelyt sai muutettua absoluuttisiksi hyppykäskyiksi, joista osa riippui aiemmin lasketuista vertailuista
- Nyt kun hypytkin tiedetään, niin katsotaan ehdottomat hypyt ees ja taas ja merkitään ne johonkin
- Ehdollisten hyppyjen kanssa saa olla enemmän tarkkana ettei mene väärin päin; merkitään nekin
- Basic blockit voi vaikka piirtää paperille jotta menee varmasti oikein, tai jos on rohkea niin voi decompiloida suoraan C-mäiseksi iffeillä ja gotoilla
- Gotot (jotka tyypillisesti menevät näissä tehtävissä taaksepäin) venkslataan selvästi nähdään -refaktoroinnilla silmukoiksi
- Viimeistellään koodi vaikka kääntyväksi Rustiksi, ja tehdään ehkä pieni muutos nyt kun homma on selvä
Tässä nimenomaisessa tehtävässä kikka-algo laski kaikki luvut, jotka jakavat inputtiluvun, joka on kovin suuri. Yhden loopin voi muuttaa pysähtymään vähän aiemmin, ja lasku olikin pian valmis.
Puzzleinputtini näytti muistiinpanoissa pienen mutiloinnin jälkeen seuraavanlaiselta:
0 jmp 17 ----------------------v
1 r1 = 1 v <` <`
2 r2 = 1 <` v ^ ^
3 r3 = r1 * r2 <` ^ v ^ ^
4 r3 = r5 == 1 ^ ^ v ^ ^
[r5==1] ´< 5 jeq 7 ^ ^ v ^ ^
v 6 jmp 8 -v ^ ^ v ^ ^
`> 7 r0 += r1 v ^ ^ v ^ ^
8 r2 += 1 <´ ^ ^ v ^ ^
9 r3 = r2 > r5 ^ ^ v ^ ^
[r2>r5] ´< 10 jg 12 ^ ^ v ^ ^
v 11 jmp 3 --------------^ ^ v ^ ^
`> 12 r1 += 1 ^ v ^ ^
13 r3 = r1 > r5 ^ v ^ ^
[r1>r5] `< 14 jg 16 ^ v ^ ^
v 15 jmp 2 ------------------^ v ^ ^
`> 16 ret v ^ ^
17 r5 += 2 <´ ^ ^
18 r5 *= r5 ^ ^
19 r5 *= 19 ^ ^
20 r5 *= 11 r5=(r5+2) * (r5+2) * 209 ^ ^
21 r3 += 4 ^ ^
22 r3 *= 22 ^ ^
23 r3 += 21 r3=(r3+4) * 22 + 21 ^ ^
24 r5 += r3 ^ ^
[r0=1] ´< 25 IP += r0 ^ ^
v 26 jmp 1 ------------------------------´ ^
`> 27 r3 = 27 ^
28 r3 *= 28 (756) ^
29 r3 += 29 (785) ^
30 r3 *= 30 (23550) ^
31 r3 *= 14 (329700) ^
32 r3 *= 32 (10550400) ^
33 r5 += r3 ^
34 r0 = 0 ^
35 jmp 1 ----------------------------------´
Rustina tämä sama sitten on melko suoraan muunnettuna:
fn a(m: &mut M) {
m.r5 = (m.r5+2) * (m.r5+2) * 209;
m.r3 = (m.r3+4) * 22 + 21;
m.r5 += m.r3;
m.r3 = 10550400;
m.r5 += 10550400;
m.r0 = 0;
f(m);
}
fn f_orig(m: &mut M) {
m.r1 = 1;
m.r2 = 1;
loop {
m.r3 = m.r1 * m.r2;
if m.r5 == m.r3 {
m.r0 += m.r1;
}
m.r2 += 1;
if m.r2 > m.r5 {
m.r1 += 1;
if m.r1 > m.r5 {
return;
}
m.r2 = 1;
}
}
}
Optimointikikka oli muuttaa koodia sen sijaan, että vertailtaisiin toista pyöriteltävää kertolaskun tekijää r2 lukuun r5, jonka tekijöitä ollaan hakemassa...
if m.r2 > m.r5 {
... verrataankin sitä tuloa, joka saadaan tekijöistä r1 ja r2. Tällä säästyy suuri määrä turhaa looppaamista.
if m.r2 * m.r1 > m.r5 {
Oikeastihan koko algo kannattaisi tehdä uusiksi jos näitä tosissaan laskisi, mutta olin jo kalenterista jäljessä ja halusin päästä eteenpäin seuraavaan tehtävään riittävän hyvällä ratkaisulla. Tämän optimoinnin olisi voinut selvästi nähdään -päätellä myös assystä venkslaamatta rustiksi ja sitten ajaa virtuaalikoneessa, joka piti aiemmin implementoida kuitenkin. Touhusin silti tähän asti.
Kun instructionpointteria voi käpistellä ihan tavallisilla opcodeilla, niin tuli väkisinkin mieleen, että jotain hämärää tilakonetta (vaikka jotain määrää RAM-muistia rekisterien lisäksi) voisi simuloida toistamalla ohjelman koodia hirmu monta kertaa pötköön konkatenoimalla ja hieman muuttelemalla. Oikea ohjelma eli tilan haara valittaisiin tilan perusteella, ja jos ohjelman pituus on kakkosen potenssi, niin bittioperaatioilla voidaan vaikka hypätä toiseen haaraan, jossa on eri tila.
Samaa ajatusta ilman bittikikkailua käytti opiskeluaikana eräs opiskelutoveri ns. vähän huijaamaan peruskurssin ohjelmointiympäristössä, jossa piti olla muka yksinkertainen robottia ohjaava assembly-kaltainen kieli. Robotille saikin muistia kun yhden bitin lisää saa aina sillä, että tuplaa ohjelman. Jos bitti on 0, ollaan ajamassa ensimmäistä ohjelman kloonia. Jos 1, niin toista.
21, reverse-engineering-iltapala
Aavistuksen monimutkaisempi tehtävä oli reverse-engineerata aikamatkustuksen aktivaatiokoodi siten, että aika jotenkin glitchaa ja ylivuotaa (selvästi jossain koneen rekistereistä). Seuraamalla jotakuinkin samaa algoritmia kuin yllä esitelty havaitaan jokunen sisäkkäinen looppi. Ohjelma tuntuu tuottavan melko satunnaisia lukuja ja decompiloituna se hyvinkin ainakin näyttää kovasti jonkinmoiselta LCG:ltä. Looppihirvitys osoittautuu tarkemmalla tarkastelulla bitshiftiksi. Decompilointi käsin oli niin ilahduttavaa touhua, että tekisin sitä mielelläni vielä lisää ja ehkä voisin vaikka aloittaa jonkun hienon cfg-analyysi-disasmerin Rust-projektina, joka ei tulisi koskaan valmiiksi.
Tästä satunnaisgeniksestä pitäisi sitten löytää jokin luku, jolla ohjelma pysähtyy sopivasti, ja sehän pysähtyy jos generoitu pseudosatunnaisluku vastaa syötettä ohjelmalle. Ohjelman täytyisi ajaa pitkään muttei kuitenkaan ikuisesti. Jos syöte on huono, se ajaa ikuisesti. Elävätköhän oikein huonot ihmisetkin ikuisesti tai ainakin pidempään?
Hieman arvailevaa näkemystä soveltamalla havaitaan, että numerothan alkavat taas toistaa itseään kuten päivinä 12 ja 18. Täältä sitten etsitään sykli ja sopivasti syklin viimeinen alkio on tuo pisimpään ajava luku, joka kun annetaan syötteenä niin aikakoneasia pysähtyy.
22, dijkstra-haku tällä kertaa
Nyt seikkaillaan luolastossa pelastamassa jonkun satunnaisen partaukon kaveria. Ei mitään hajua, kenestä voisi olla kyse. Luolasto koostuu ruudukosta (montako ruudukkotehtävää tänä vuonna oikein on?) jonka määrittää implisiittisesti sarja sääntöjä, jotka vaikuttavat melko lailla pseudosatunnaisgenikseltä taas. Eroosiotason mukaan luolastossa on kolmea eri maastotyyppiä ja taso lasketaan solun satunnaisluvusta. Tehtävänä on päästä luolaston läpi.
Maastotyyppeihin sopii erilaiset varusteet, ja vaihtomatriisin voisi tehdä datana mutta match-lausekkeita on kiva harjoitella:
fn equipment_fits(rt: RegionType, eq: Equipped) -> bool {
match rt {
Rocky => eq != Neither,
Wet => eq != Torch,
Narrow => eq != Gear,
}
}
Varusteiden vaihtamiseen menee aikaa. On taas reitinhaun aika; tässähän on implisiittinen graafi jossa kaksi ulottuvuutta ovat luolan koordinaatit ja kolmantena käytetään päälle puettua varustetta, eikä ihan triviaali BFS enää kelpaakaan eli tehdään sitten Dijkstra-haku. Veljen koodaama hakualgo oli kuulemma kuitenkin BFS, jossa huijattiin lisäämällä graafiin tiloja odotusajan mukaan; saman kikan taisin tehdä viime tai toissa vuonna johonkin tehtävään. Ruudusta toiseen siirtyminen kestää yhden ajan, joka ruutuun ei pääse ihan millä vaan varusteilla, ja varusteiden vaihtaminen kestää seitsemän aikaa. Matka alkaa origosta ja kädessä on lamppu.
distances[d_idx(0, 0, Torch)] = Some(0);
Rustin standardikirjastossa on näppärästi binaryheap-tietorakenne. Lisäksi nämä tuplet vaan toimivat joka paikassa niin mukavasti että ai että. Suoritetaan haku alusta sinne loppuun siten, että hakuavaruuden koordinaatisto on luolaston koordinaatit sekä kussakin koordinaatissa pidettävä varuste (joita oli kolme erilaista). Pikkuvika sai bugaamaan hieman, kun vahingossa optimoin verkon varusteenvaihtoedget pieleen; vastaukseksi tuli oikea luku, mutta jostain syystä reitti teki erikoisen kiertotien. Yksinkertaisemmin menee, kun liikkumisen ja tarvikkeen vaihdon mallintaa rehellisesti erillisinä edgeinä.
// equipment changing edge
for &eqj in &[Gear, Torch, Neither] {
test_and_insert((xi, yi, eqj), dist + 7, &mut distances, &mut heap);
}
23, avaruudellista hahmotusta
Aiemman tehtävän kaveri osoittautui poroksi. Ettei olisi punainen kuonokin, kun erottui luolastosta niin kirkkaana. Poro vain sattui olemaan heikossa kunnossa, ja nyt sitä pitäisi parantaa tulevaisuudesta spawnanneilla nanoboteilla. Botit ilmestyvät sinne tänne ympäriinsä ja kullakin on tietty toimintasäde. Paras paikka itselle on sellainen, johon ulottuu suurin mahdollinen määrä nanobotteja. Etäisyys botista lasketaan manhattan-tyyliin, eli botti on oktaedrin muotoinen.
Kun maailma onkin kolmiulotteinen, niin nyt ei sovi enää ihan yksinkertainen gridihaku. Reiskaamisessa kokeneena tein tietysti BSP-haun, mutta voi kiesus mikä offbyone-meininki tästä tuli. Koordinaatit ovat kokonaislukuja ja puljasin tehtävän sen mukaan niin, että boundingvolumet eli tässä tapauksessa AABB:t kattavat ikäänkuin avaruusgridin diskreettejä soluja.
impl Aabb {
// [ ... ]
fn size(&self) -> Vec3 {
// discrete size: [0, 1] occupies two cells
self.max - self.min + Vec3::new(1, 1, 1)
}
fn center(&self) -> Vec3 {
// Sort of (self.min + self.max) / 2 but round towards negative
// infinity so that splitting works consistently in both sides of
// zero. One aabb can be split into [min, center] and [center + 1,
// max] where min <= max in both as long as the split dir has a size
// of >= 2. For even sizes, both have same size. For odd sizes,
// center cell becomes part of left.
self.min + (self.max - self.min) / 2
}
Leikkaustesti botin ja axis-aligned-bounding-boxin kanssa tuli tehtyä ehkä turhankin geneerisesti. Syytän veljeä. Kiitos Nuutti. Jälkiviisaasti arvioimalla varmaan noilla manhattanetäisyyksillä tämä menisi samaan tyyliin kuin laatikon ja pallon vertailu, joka on melko lailla yksinkertaista puljaamista, mutta enpä tiedä varmasti. Kokeilen kuitenkin josko jokin taso erottaisi laatikon ja oktaedrin toisistaan, ja tasoiksi testataan kuution kaikkia pintoja, oktaedrin kaikkia pintoja sekä sellaisia pintoja, jotka lepäisivät oktaedrin reunoilla (särmä särmää vasten -törmäys, kun verteksit olisivat kuitenkin kaukana erillään).
Pitääkin ensi tilassa kokeilla pallonkaltaista leikkaustestiä. Jos toimii, niin pääsee eroon näistä hirmu monista tasoyhtälöistä. Ottaisin tasohöylän mieluummin ja puuseppäilypajan.
fn bot_face_separates(aabb: &Aabb, bot: &Bot) -> bool {
let (north, south, east, west, front, back) = (1, -1, 1, -1, 1, -1);
// d = -n . p for fixed p (a corner)
// q . n + d = 0 for any q on plane
let planes = [
(Vec3::new(east, north, front),
-(east * (bot.p.x + bot.r) + north * bot.p.y + front * bot.p.z)),
(Vec3::new(east, north, back),
-(east * (bot.p.x + bot.r) + north * bot.p.y + back * bot.p.z)),
Joka tapauksessa avaruuden kaikkien pisteiden kokeileminen parhaan bottitiheyden suhteen olisi tuhottoman hidasta. Tämmöinen binäärihaku ajaa vajaat puoli sekuntia sen kummemmin intersektiotestiä optimoimatta, kun botteja on tuhat ja koordinaatit ja bottien säteet luokkaa kymmeniä miljoonia. Hyvä huomio oli, että kun tasapelit bottiulottuvuustiheystilavuuksissa ratkaistaan etäisyydellä origosta, niin ensin kannatti binäärihakea paras tiheys huolimatta sijainnista ja vasta sen jälkeen tällä tiheydellä esiintyvä paras sijainti. Avaruuden jakaminen pruneutuu paljon nopeammin noin.
Parikin muuta kiintoisaa menetelmää tämän laskemiseen olisi, joita saatan vielä kokeilla tai olla kokeilematta.
25, muuten vaan pieni ja söpö
Viimeisenä tehtävänä tuotiin porolle kaakaota tulevaisuudesta. Reitille tarvittiin kuitenkin neliulotteisia aika-avaruuden kiintopisteitä, ja pisteistä tuli laskea tähdistöjen lukumäärä. Yksittäinen tähti liittyy iteratiivisesti muihin tähdistöihin, jos sen manhattan-etäisyys jostain muusta tähdistöstä on kolme tai alle.
while let Some(new_pt) = world.pop() {
let mut join_candidate = vec![new_pt];
loop {
if let Some(joined) = join_constellation(&mut constellations,
&mut join_candidate,
new_pt) {
join_candidate = joined;
} else {
break;
}
}
constellations.push(join_candidate);
}
Tähän sopisi itseasiassa while let Some(joined) = join_constellation(...) {, mutta else-haarassa oli joku debugprintti ja ne pois lakaisemalla rakenne jäi tuollaiseksi. Voisin vaikka vielä viimeistellä.
Tähdistöt ovat yhdessä vektorissa, josta niitä yhdistellessä poistetaan sopivasti ja lisätään takaisin siten, että borrow checker taas on maagisesti ihan hiljaa ja koodi vain kääntyy. Piti tarkistaa parikin kertaa ja naputella kommentteja dokumentaatioksi itselleni, kun meni niin hyvällä flowlla.
Yleisesti
Monesti tuli koodattua menemään vaan ja sitten vastauksen tullessa jäätyä ihmettelemään, että mitähän tässäkin nyt tapahtui, kääntyikö / toimiko se oikeasti. Piti tarkastaa, että mitäs teinkään. (Useimmiten ei käänny ekalla yrittämällä, mutta kääntäjän ehdotuksia voi melkein totella sokeasti. Silmät silti auki, jotta oppisi hommasta jotain.) Kommentteja koodin sekaan, kun noin vähällä määrällä naputtelua tapahtui jotain ovelaa.
Viime kerralla seurasin ja pläräsin dokumentaatiokirjaa taukoamatta. Oleelliset ensikosketuksen oppimiset voi käydä aiemmasta raportista lukemassa. Tai siis tämä kerta oli jo kolmas Rust-AoC-vuosi, mutta ensimmäisen unohdin konsanaan. Nyt ei tullut varsinaisesti avattua rustkirjaa eksplisiittisesti; mitä nyt muutaman googlauksen tuloksena löytyi sieltä osuma. Lihasmuisti kehittyy.
Näissä kisakooditehtävissä on kyllä se vika ohjelmointikielen harjoituksen kannalta, että ruohonjuuritason naputtelu tulee tutuksi, muttei oikean maailman ongelmia tule harjoitettua. Traitteja en kirjoittanut, en käyttänyt cargoa, riippuvuuksista oli käytössä vain Regex-crate ja sekin vain toisinaan. Kevään koodilomalla Espanjassa mietittiin itseasiassa porukalla mm. hifisteltyä Brainfuck-tulkkia Rustilla (joka olisi kiva saada johonkin kuntoon joskus) ja eräs muu oma pikkuprojekti on saanut ainakin parin epsilonin verran ajatuksia osakseen. Varmaan se perinteinen raytracerikin olisi tehtävä jonakin tummana talvi-iltana.
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.