soodan sivut

arkisto

231 kirjotelmaa.

avainsanat

Joulukuun tunnistaa siitä, että saa koodailla menemään tonttutarinan parissa. Advent of Coden teema on aina joulun pelastaminen tavalla tai toisella. Ihan tuttu juttu nyt jo ja tämä on näemmä viides raportti ja kuudes kerta. Pelin teema on joka vuosi sama, eli pitää ryhtyä tarinan päähenkilöksi pelastamaan joulu, ja ohjelmointikieli on taas sama. Tällä kertaa joulupukin reen avaimet vietiin vahingossa meren pohjalle eikä korvatunturille. Sinne siis.

Näitä päivittäisiä kaksiosaisia koodipelejähän tehtiin jo 2020, 2019, 2018, 2017 ja 2016 mutta viimeisestä en tainnut blogata. Taustalöpinää naputtelen joka kerta vähemmän, ja aiemmat toimivat hyvänä referenssinä. Tämänvuotinen taustalöpinä loppuu suunnilleen tähän.

Tarkastellaan kiinnostavia päiviä pelin taustatarinan, kulloinkin soveltuvan algoritmin tai ylipäänsä koodin tai hyvän mielen kannalta. Joku yksinkertainen DFS tai pino ei (enää) ole mainittavan kiinnostava, ellen sitten mokaa jotain ja opi samalla.

Koitin ottaa vuoden teemaksi koodata näitä vähän harjoitellen Rustin traitteja ja muuta koska harjoitus tekee metsurin. Aiemmista vuosista ja satunnaisista harrastekoodailuista tarttui riittävä rutiini muihin perusjuttuihin iteraattoreista lifetimeihin asti, mutta kukin ratkaisu on niin lyhyt ja kertaluontoinen, ettei tätä softakehitykseksi voi kutsua. Traiteilla överigeneerisöiminen ei sitten joka päivä tapahtunutkaan, kun piti tehdä samana päivänä jotain muutakin, mutta ehkä jälkikäteen näihin voisi palata rakentaakseen jotain kivoja täydellisiä lumihiutaleita joihin ei oikean elämän softassa ole aikaa?

1, josko geneerisempää

Jo ykköstehtävään kikkailin tälläisen, joka ei olisi dynaamisemmin tyypitetyssä kielessä temppu eikä mikään. Mutta nyt on tyypit kyseessä käännösaikana. Piti kaivella skannatusta meren pohjasta kohtia, joissa pohja syvenee, ja kakkososassa pohjaa keskiarvotettiin kolmella näytteellä. (Noista toki liukuva keskiarvo aiheuttaa semmosen hauskan ilmiön, että w0 + w1 + w2 > w1 + w2 + w3 sievenisi muotoon w0 > w3)

fn deepenings<I, V>(it: I) -> usize
where I: Iterator<Item = V> + Clone, V: std::cmp::PartialOrd {
    it.clone().zip(it.skip(1))
        .filter(|(prev, next)| next > prev)
        .count()
}

fn increase_count(depths: &[u32]) -> usize {
    deepenings(depths.iter())
}

fn increase_count_windowed(depths: &[u32]) -> usize {
    deepenings(depths.windows(3).map(|w| w[0] + w[1] + w[2]))
}

Mainitsen tän jo ykköspäivästä korostaakseni, että miten kivasti tuo kääntäjä tälläisissä pleb-tilanteissa osaa neuvoa jos vaikka tuon PartialOrdin unohtaa:

error[E0369]: binary operation `>` cannot be applied to type `&V`
 --> 1.rs:6:37
  |
6 |         .filter(|(prev, next)| next > prev)
  |                                ---- ^ ---- &V
  |                                |
  |                                &V
  |
help: consider further restricting type parameter `V`
  |
4 | where I: Iterator<Item = V> + Clone, V: std::cmp::PartialOrd{
  |                                    +++++++++++++++++++++++++

Jee. C++:ssa lähin vastine olisi kai ne konseptit joihin näköjään vuosikymmenien suunnittelun jälkeen on suunnilleen päästy?

3, toinen traittihäkkyrä

Nyt päähenkilöä ympäröivän sukellusveneen diagnostiikkareportista on laskettava vähän bittejä. Tunkkasin tuon onelinerin riippumattomaksi kokonaisluvun tyypistä, mutta en tiiä oliko tässä nyt sitten järkeä. Joistain todella yleishyödyllisistä jutuista voisi kerätä vuosien mittaan hypoteettista aoc-kirjastoa, mutta tää pätkä käy taulukon numerot läpi ja laskee, että monessako niistä on joku tietty bitti päällä. Ei kovin yleishyödyllinen.

// no idea what I am doing
fn one_bits<T>(numbers: &[T], bitpos: T) -> usize
where T: BitAnd<Output = T> + Shl<Output = T> + PartialEq + From<u8> + Copy {
    numbers.iter().filter(|&&x| (x & (T::from(1u8) << bitpos)) != 0u8.into()).count()
}

Aika mötkö. En ees käytä tuota kuin u32:lle eli ei edes säästä copypastaa kuin teoriassa. Joitain crateja näköjään on tälläisten tilanteiden helpottamiseksi.

4, generic_const_exprs

Tein oman tyypin jollekin pelilaudalle. Pelilauta on geneerinen ja sopii mille vaan koolle. Ei siitäkään tarvinnut kuin 5x5 pelilaudan, mutta tulipa tutustuttua siihen, miten tuo tehtäisiin:

struct Board<const N: usize> where [(); N * N]: {
    numbers: [u32; N * N],
    marked: [bool; N * N],
}

impl<const N: usize> Board<N> where [(); N * N]: {
    fn new(numbers: [u32; N * N]) -> Self {
        Board { numbers: numbers, marked: [false; N * N] }
    }

Vähän hassu tuo tyhjä bound mutta kääntäjä ehdotti että laitan sellaisen. Olkoon niin, laitetaan googlauslistalle. Pitempään rustannut kaveri ehdotti, että liittyy varmaan siihen, miten kääntäjä laskee nuo geneerisillä consteilla tehdyt laskutoimitukset ja miten kertolaskun tulos pitää jotenkin olla tiedossa jo noin aikaisin.

error: unconstrained generic constant
 --> 4.rs:7:14
  |
7 |     numbers: [u32; N * N],
  |              ^^^^^^^^^^^^
  |
  = help: try adding a `where` bound using this expression: `where [(); N * N]:`

8, työläs mutta hauska päättelytehtävä

Taustatarinassa on sen verran tiedettävää, että kannattaa lukea se ensin ja katsoa koodi sitten. Seitsensegmenttinäyttöjä on piuhoitettu sukellusveneessä huonosti ja pitäisi selvittää mikä signaali vastaa mitäkin segmenttiä. Onneksi niistä on pino yhdistelmiä tiedossa.

Tämän haluan vielä myöhemmin sovittaa geneeriseen yhtälöryhmäratkaisimeen joka pitää koodata ensin (tai luntata viime vuodelta; näköjään päivät 16 ja 21 sivuavat aihetta), mutta noiden päätteleminen käsin oli aika hauskaa. Löytyi sopiva joukkotietotyyppi, jolla voi suunnilleen tehdä aritmetiikkaa kätevästi. Kun numeronäytön ruutu näyttää tältä:

 aaaa
b    c
b    c
 dddd
e    f
e    f
 gggg

niin voidaan selvästi järkeillä mm. että:

  • ykkönen on osat c ja f
  • seiska on osat a, c ja f
  • osa a on seiskan ja ykkösen erotus
  • osa d on kahdeksikon ja nollan erotus
  • ja niin edelleen

Tuli mieleen, että tosi ilmaisuvoimaisilla jutuilla tehtävä aritmetiikka tietyissä piireissä on jo vanhahko juttu mutta siistiä ja uusissa jutuissa myös selkeä juttu. Pitäis tutustua ja leikkiä vähän.

13, ihan liian geneeristä hauskaa

Kun tuplet ovat liian kivoja käyttää, niin niitä käyttää pienten taulukoidenkin sijaan eikä tajua että voisi vaan indeksoida ja geneerisöidä sen taulukkoindeksin. Kyllä mä tän tiesin jo tuota hässäkkää kirjoittaessa, mutta maistui hifistellä aavistuksen verran liian pitkälle. Tehtävänä oli taitella "paperia" vaaka- ja pystysuuntaisesti, ja, no:

fn generic_fold<F, T>(dots: &mut HashSet<(i32, i32)>, flip_predicate: F, transform: T)
where
F: Fn(&(i32, i32)) -> bool,
T: Fn(&(i32, i32)) -> (i32, i32)
{
    let moving_part: HashSet<_> = dots.drain_filter(flip_predicate).collect();
    dots.extend(moving_part.iter().map(transform));
}

fn axial_fold<S, R>(dots: &mut HashSet<(i32, i32)>, axis_selector: S, axis_ref: R, flip_coord: i32)
where
S: Fn((i32, i32)) -> i32,
R: Fn(&mut (i32, i32)) -> &mut i32,
{
    generic_fold(dots,
                 |&p| axis_selector(p) >= flip_coord,
                 |&p| {
                     let mut pnew = p;
                     *axis_ref(&mut pnew) = flip_coord - (axis_selector(p) - flip_coord);
                     pnew
                 });
}

fn fold_along_x(dots: &mut HashSet<(i32, i32)>, flip_coord: i32) {
    axial_fold(dots, |p| p.0, |p| &mut p.0, flip_coord);
}

fn fold_along_y(dots: &mut HashSet<(i32, i32)>, flip_coord: i32) {
    axial_fold(dots, |p| p.1, |p| &mut p.1, flip_coord);
}

Järkevästihän tuossa ois sopivan koordinaatin palauttavan funktioparametrin sijaan käyttänyt vaan numeerista indeksiä silleen, että ei axis_selector(p) vaan p[axis]. No olihan tarkoitus kuitenkin hifistellä överigeneeriseksi ja edes tänpäiväisessä se suunnilleen tapahtui. Vielä kun tuon hashsetin heivaisi tyyppiparametriksi niin täähän toimisi mihin tahansa etäisesti koordinaatin kaltaisiin asioihin. Vaivataan päätä tosi paljon ja säästyy noiden kahden koodirivin (drain_filter ja extend) kirjoittamiselta, hyödyllistäkö??

15, tietysti dijkstra

Ei ole AoC-kalenteria ilman reitinhakuja, ja joku noissa aina on kovin mukavaa. Koodissa ei kummempaa nokkeluutta haun suhteen kun joka kerta ilahduttaa miten helppo ja looginen nakki Dijkstran hakualgoritmi on toteuttaa. Algo itse ja sen data olisi kiva eriyttää toisistaan harjoituksen vuoksi, vaikka algo itse on vain muutaman rivin mittainen ja se on aina nopeampaa ja helpompaa tuossa vauhtikisassa kirjoittaa tiiviisti yhteen. Tai siis algohan on tavallaan muutakin kuin tuo pieni silmukka prioriteettijonoineen, mut sitten toisaalta ei, kun verkon rakennehan on vain dataa.

Reitinhakuihin olisi muuten kirjastokin jonka sorsa vain korostaa käsitystä siitä, että se algoritmin ydin on vain muutamia rivejä ja tyyppiparametrien viemä tila on sorsan tokeneista jo merkittäviä määriä.

Tässä vaiheessa on sopivaa iloita siitä, että koodikalenterin laatija on selvästi nähnyt aina vaivaa taustatarinoihin. Tällä kertaa tuota reittiä on muodostamassa joitain hämyisiä kotiloita joista harva lienee kuullutkaan. Koodiharjoitus olikin biologian luento.

No mainitaan se, että näitä tehdessä on hyvä harjoitella vanhanaikaisten imperatiivisten looppien välttelyä ja tehdä sama homma eri muodossa mutta paljon vaik... vähän erikoisemmin; kun dataa vain menee sisään ja dataa tulee ulos eikä muokata eksplisiittisesti mitään, niin on monesti helpompaa nähdä mitä tapahtuu. Tässä tämmönen funktionaalinen hässäkkä, jolla kustakin yhdestä karttasolusta muodostuu 5*5:

let map: HashMap<(i32, i32), i32> = chitons
    .iter().enumerate().flat_map(|(y, row)| {
        row.iter().enumerate().flat_map(move |(x, &ch)| {
            (0..5).flat_map(move |tiley| {
                (0..5).map(move |tilex| {
                    (
                        (w * tilex + (x as i32), h * tiley + (y as i32)),
                        wrap_chiton_risk(tilex, tiley, ch as i32)
                    )
                })
            })
        })
    })
.collect();

16, bittejä ja rekursiivista parsimista

Tontuilta tulee Buoyancy Interchange Transmission System -koodauksella jotain informaatiota. Speksin bittivirtaa käsittelee helpoiten vain bittivirtana ja toisaalta siitä erotetut rekursiiviset paketit tietokenttineen ovat ihan ortogonaalinen ongelma. Tyypilliset AoC-tehtävät koostuvat yhdestä selkeästä ongelmasta, mutta joskus mukana on näköjään kaksikin.

Bittipuliveivaus tulee ihan selkäytimestä ja tehtävän yksinkertainen sisäkkäisten pakettien rakennekin oli aamutokkurasta huolimatta ihan selkeä. Siitä huolimatta (tai juuri siksi) tästä jäi keskimääräistä kivempi fiilis; ehkä pitäisi ottaa harrastusprojektiksi joku isompikin parseri.

Tässäkin on sitten tilaisuus hifistellä jonain päivänä tuo formaatin läpikäynti geneeriseksi eri osia varten. Tehtävän ensimmäisessä osassa tarkastellaan vain pakettien versiokenttiä. Toinen osa sitten läpikäy pakettien varsinaisen datan, ja ynnäilee niiden sisältämiä laskutoimituksia. Koska "tiedostoformaatti" on selkeästi määritelty, siihen voisi tehdä jonkun geneerisen rajapinnan. Aamukoodatessa oli yksinkertaisempaa copypasteta parserifunktiot ja muuttaa tietokenttienlukulogiikka. Tyypillisesti taas koodia aina luetaan enemmän kuin kirjoitetaan, ja tämäkin on vähän liiankin kuiva koulukirjaesimerkki siitä, miten formaatin läpikäyntilogiikka bittivirrasta kuuluisi suunnitella erilleen siitä logiikasta, joka sitä formaatin dataa oikeasti käyttää. (Alkaa tulla inhonhytinät XML:stä, kun muistuu mieleen javaisat pakko-opinnot ja DOM- ja stream-parsintavaihtoehdot.)

19, avaruusjumppaa

Avaruuteen -- tai siis merenpinnan alle -- ammuttu luotain jakautuu edelleen pieniksi majakoiksi ja skannereiksi. Kukin skanneri näkee jonkin osan kaikista majakoista, ja jokaiselle skannerille löytyy kaveriskannereita, jotka näkevät keskenään samoja majakoita. Majakoiden koordinaatit tunnetaan suhteessa kuhunkin havaitsijaskanneriin. Tästä tiedosta sitten skannerien sijainnit pitäisi selvittää, mistä selviää mm. skannatun tilavuuden koko.

Majakoita on sen verran vähän, että hakuprosessi onnistuu ihan bruteforcella vääntämällä, kokeillen nykyistä yhdistelmää majakoista ja kutakin toistaiseksi tuntemattomista majakoista yhteen. Lisäkikka hommassa on, että kukin majakka voi olla kääntynyt mihin tahansa 24 mahdollisista orientaatioista, missä naamataulu osoittaa jotakin pääkoordinaattiakselia pitkin eespäin.

Prosessi on kuin palapelin kasaaminen väkisin: pöydällä on löydetyt palat, ja uusista paloista koitetaan vuoronperään kutakin pyörittelemällä sitä kaikkiin mahdollisiin kulmiin ja koittamalla, että mihin kohtaan reunakuvio täsmää jos täsmää. Pyörittely ja iteratiivinen täsmääminen olivat yllättävänkin suoraviivaisia implementoitavia, ja ratkaisu löytyi ns. ykkösellä. Bruteforcepyörittelystä jäi kyllä vähän optimoitavaa. Joku viime vuosien päivistä, oisko ollut just vuotta aiemmin, olikin aika hauska palapelitehtävä. Muistan miten ratkaistiin veljen kanssa vähän eri tavoin.

Oikeassa elämässä pisteet eivät yleensä osu kohdilleen ihan täsmälleen, ja pisteitä on eri joukoissa eri määrät miten sattuu.

21, pitää se dp:kin olla

Useimmiten päivän pulman ensimmäistä osaa riittää vähän muokata toista osaa varten. Tällä kertaa kyseessä oli noppapeli, joka piti koodata ihan kokonaan uudestaan toista osaa varten. Pohjustustehtävän logiikka enimmäkseen päti edelleen.

Noppapeliä pelataan sukellusveneen tietokonetta vastaan ja tehtävän kakkososassa kolmitahokas noppa haarauttaa todellisuuden kvanttimaisesti kolmeen osaan kutakin vaihtoehtoa kohti. Kun noppaa heitetään pelissä aika paljon, niin tästä tulee ammattilaisten kielellä ns. tosi paljon noppaheittoja eikä bruteforcelaskenta enää sovikaan. Kun tehtävänannon luku on kokoluokkaa 444356092776315, niin akuutista kylmästä hiestä tietää että yksi kerrallaan summaaminen ei käy kuuloonkaan.

Osoittautui, että tämähän on selkeä dynamic programming -pulma. Noppapelissä liikutellaan pelinappuloita vain kymmenen ruudun mittaista kehärataa pitkin, ja peli voitetaan 21 pisteen jälkeen. Se, millaisilla noppaheitoilla mihinkin tilaan on päästy, ei ole merkityksellistä. Näin ollen pelissä on erilaisia tiloja luokkaa 10 * 10 * 21 * 21, joista kukin tila tietää, miten moneen ensimmäisen ja miten moneen toisen pelaajan voittotilaan siitä on mahdollista päästä.

Selvästi tilat, joissa ensimmäisellä pelaajalla on pisteitä 21, saavat arvokseen yksi voitto ensimmäiselle pelaajalle ja nolla toiselle; tämä on rekursiivisen haun (ei se fraktaalikoiran äännähdys) päätepiste. Tuloksena tehtävän pulmaan kiinnostaa, montako voittoa pelaajat saavat tilasta, jossa nappuloiden sijainnit ovat jotain tiettyä ja kummankin pelaajan keräämä pistemäärä on nollassa. Noppaheitoilla saadaan paljon tiloja, joiden tulos on laskettu jo; sellaiseen 10 * 10 * 21 * 21 kokoiseen taulukkoon kun merkataan nuo pelitulokset, niin ratkaisu sievenee lähes klassisen fibonaccirekursion tyyliin.

Yksi AoC-koodailun parhaita puolia on tehtävien tarpeettoman syvä pohdiskelu lähipiirin kanssa. Veljen kanssa dp:n määritelmää, häntärekursiota, lispiä ja muuta yleishyödyllistä aprikoidessa havaittiin, että se sellainen tiiliskividominohan on aika hupaisa analogia rekursiivisesta laskennasta: kukin dominokalikka osuu seuraavaan, kunnes seuraavaa kalikkaa ei olekaan ja viimeinen kaatuu maakosketukseen saakka. Tästä sitten "call stack" palaa nopeasti ylöspäin stack frame kerrallaan. Sama meininki visualisoi myös tehokkaasti, mitä häntärekursiossa jätetään tekemättä, kun jokaista tiilenpalaa varten ei tarvitakaan omaa stack framea.

22, CSG

Tänään vitkuteltiin sukellusveneen reaktoria, joka koostuu pienistä kuutioista. Inputti on suorakulmaisia särmiöitä, joiden määrittämiä kuutioita kytketään päälle tai pois; lopuksi lasketaan, montako kuutiota jäi päälle.

Särmiöt kattavat niin monta kuutiota, että ihan yksitellen niitä kuutioita ei voi vitkuttaa. Muodostetaan siis avaruudesta (tai siis merestä) kokoelma särmiöitä, jotka eivät leikkaa toisiaan ja joiden sisältämät kuutiot ovat päällä. Pulman vastaus on näiden särmiöiden tilavuuksien summa.

Särmiöohjeet (tilavuus ja päälle vai pois) käydään yksi kerrallaan läpi. Jos kuutioita kytketään päälle, niin täytyy toki tarkistaa päällekkäisyys olemassaolevien särmiöiden kanssa. Jos uusi osuu johonkin olemassaolevaan, niin leikataan se 3*3*3 kuutioksi, joiden lisäystä yritetään samalla tavalla uudelleen, kunnes törmäyksiä ei osu. Jos taas kuutioita kytketään pois, niin muodostetaan uutta avaruutta siten, että leikkaukset poistettavan alueen kanssa jätetään lisäämättä. Leikkaus suoritetaan samalla 3*3*3 menetelmällä.

Tuo leikkausmenetelmä meni vähän hassusti väkisin koodaten, koska näitä pulmia koodailee menemään aamutokkurassa. Sanotaan, että leikkaaja leikkaa leikattavaa siten, että jokaisen tahkon "taakse" voi jäädä tilavuutta; oletetaan, että sitä aina jää, niin ei tule erikoistapauksia. Tyhjät tilavuudet voidaan jättää lopuksi huomiotta. Tilanne on suunnilleen tämän grafiikan kaltainen, paitsi 3D:ssä:

+----------+
|----------|
|----------|
|----------|
|---xx-----|
|---xx-----|
|----------|
+----------+

Oikeasti x:llä merkitty voi olla ihan kyljessäkin kiinni. Erotetaan tuosta ne eri alueet eri kirjaimilla:

+----------+
|AAABBCCCCC|
|AAABBCCCCC|
|AAABBCCCCC|
|DDDxxEEEEE|
|DDDxxEEEEE|
|FFFGGHHHHH|
+----------+

Tuo x:llä merkitty leikkaajatilavuus voi toki olla koko kalikan kokoinen siten että mitään ei jää jäljelle, tai sivuta yhtä tai useampaa reunaa. Tässä 2D:ssä alueista A-H muodostuu kahdeksan tilavuutta; 3D:ssä noita mahdollisuuksia on yhdeksän per sivu, ja sivuja on kuusi; 9*6 olisi 54 särmiötä, mutta symmetrian vuoksi niitä on oikeasti vain se 3*3*3 eli 27. Jostain syystä tuo naiivisti copypastettu sotkuni joka tuotti 54 kappaletta tuotti kuitenkin myös oikean vastauksen.

Vähän parempi tapa olisi jakaa tuo avaruus akseli kerrallaan pienemmiksi, vaikka 2D:ssä ensin vaakatasossa halki:

+----------+
|AAABBCCCCC|
|AAABBCCCCC|
|AAABBCCCCC|
+----------+

+----------+
|DDDxxEEEEE|
|DDDxxEEEEE|
|FFFGGHHHHH|
+----------+

ja sitten pystytasossa halki.

+---+  +-------+
|DDD|  |xxEEEEE|
|DDD|  |xxEEEEE|
|FFF|  |GGHHHHH|
+---+  +-------+

Näin ollen tilavuuksia ABC voisi käsitellä yhtenä, sekä DF:ää. Ehkä nuo pitäisi pilkkoa leikkaajakappaleen kummaltakin puolelta, mutta silti kombinatorinen tilavuusräjähdys ei olisi niin paha ongelma niinkuin tässä (ennen siistimistä 27 blobiin):

[
    top_front_left, top_front_right, top_back_left,
    top_back_right, top_front_mid, top_back_mid,
    top_left_mid, top_right_mid, top_mid_mid,
    front_bottom_left, front_bottom_right, front_top_left,
    front_top_right, front_bottom_mid, front_top_mid,
    front_left_mid, front_right_mid, front_mid_mid,
    left_bottom_back, left_bottom_front, left_top_back,
    left_top_front, left_bottom_mid, left_top_mid,
    left_back_mid, left_front_mid, left_mid_mid,
    bot_front_left, bot_front_right, bot_back_left,
    bot_back_right, bot_front_mid, bot_back_mid,
    bot_left_mid, bot_right_mid, bot_mid_mid,
    back_bottom_left, back_bottom_right, back_top_left,
    back_top_right, back_bottom_mid, back_top_mid,
    back_left_mid, back_right_mid, back_mid_mid,
    right_bottom_back, right_bottom_front, right_top_back,
    right_top_front, right_bottom_mid, right_top_mid,
    right_back_mid, right_front_mid, right_mid_mid
].iter().cloned().filter(|blob| blob.volume() != 0).collect()

Ylipäänsä moni muukin menetelmä olisi kai toiminut. Esimerkiksi jotkut kuulemma laskivat poistettavat kalikat negatiivisena tilavuutena sen sijaan, että positiivisista olisi pyyhkinyt niitä pois.

Tälläinen kolmiulotteinen jumppaaminen on silti aina kivaa ja tulee mieleen ihan aiemman elämän reiskaaminen ja CSG-optimoinnit. Pitää vielä implementoida tuo akseli kerrallaan halkominen siksi, että tulisi lihasmuistista ensi kerralla.

23, lisää hakualgoa

Päivänä 15 verryteltiin vähän dijkstrailua. Näihin katkarapuihin tulikin A*, kun mokasin ensin verkon tilojen kanssa ja kuvittelin, ettei dijkstralla ehdi perille hyvän sään ajoissa. No tulipa tehtyä vaikka vika oli muualla. Tässä kartassa A*:n heuristiikasta ei ole haittaakaan.

Hakuongelmat mallinnetaan verkkona, ja kun tässä tilasta toiseen siirrytään liikauttamalla äyriäinen paikasta toiseen, niin on taas hupaisaa että hakualgon sisällä on hakualgo. Taitaa olla ihan perinteinen aoc-pulmaformaatti taas.

Sitä voi vain arvailla, että oliko tahallinen jäynä, mutta tehtävänannossa sanottiin että tuollainen merieliö "ei liikahda käytävästä huoneeseen paitsi [erinäisiä ehtoja]" ja tietysti näitä ihmiskielen ohjeita koodiksi kääntäessä tulkitsin tuon kirjaimellisesti, ja tästähän haku jäi jumiin kun tiloja tulikin hakugraafiin vähän liikaa. Merieliö voi joissain tilanteissa kulkea huoneesta toiseen ihan suoraan, mutta kyllä se silloinkin käy käytävän kautta; tuolla logiikkapolulla ei vain käsitelty käytävää eksplisiittisesti. Olisi pitänyt syödä tehtävänanto ensin omaan päähän ja pursottaa koodi sieltä. Jäi välivaihe suorittamatta.

Toisenkin bugin tein kun leveyshausta tuli älyhäiriössä syvyyshaku, ja eihän sellainen löydä suorinta reittiä heti ekalla visiitillä.

24, perinteinen reversaustehtävä

Viimeisen jännän päivän tehtävä oli mukamas ajaa keksittyä assyä virtuaalikoneessa, paitsi että sillä olisi pitänyt analysoida sen verran monta lukua, että ei olisi vastaus ehtinyt aatoksi pakettiin. Reverse-engineeraus ei mahdu ihan samaan muottiin näiden muiden päivien kanssa, kun ratkaistava algoritmi on pyöriteltävä aika lailla päässä. Ite tykkään tästäkin.

Tehtäväinputti on jokaisella pelaajalla ilmeisesti sama muutamia vakioita lukuunottamatta; tavoitteena on keksiä sekä isoin että pienin luku, jotka assyhässäkkä hyväksyy. Assyhässäkkä eli tehtäväinputti koostuu toistuvasta hahmosta, joka tekee jokaiselle luvun numerolle jotakin; osoittautuu, että numeroita laitetaan pinoon ja jos hyvin käy niin myös otetaan pinosta. Hyvin käy, jos numeron ero pinon päällimmäiseen on jokin tietty. Pino on toteutettu yhtenä lukuna sen kuvitteellisen koneen rekistereissä; kutakin numeroa kohti on riittävästi bittejä.

Muistaakseni aiempien vuosien assyreversaukset vaativat aina vähän käsityötä vastauksen kaivamiseksi. Voin olla väärässäkin. Tämänkertainen ei ainakaan vaatinut (tuon rakenteellisen tutkimisen jälkeen), kun inputista sai kaiveltua ne taikaluvut määrittämään numeroiden keskinäisiä suhteita:

for (i, chunk) in program.chunks(18).enumerate() {
    match chunk {
        &[
            Instruction { opcode: Inp, a: VAR_W, b: Arg::Num(0) },
            Instruction { opcode: Mul, a: VAR_X, b: Arg::Num(0) },
            Instruction { opcode: Add, a: VAR_X, b: AVAR_Z },
            Instruction { opcode: Mod, a: VAR_X, b: Arg::Num(26) },
            Instruction { opcode: Div, a: VAR_Z, b: Arg::Num(division) },
            Instruction { opcode: Add, a: VAR_X, b: Arg::Num(compare) },
            // etc stuff
        ] => {
            if division == 1 {
                stack.push((i, offset));
                // not possible to take the branch because this holds
                assert!(compare >= 9);

Patternmatchaaminen on kaikkein voimakkain koodirakenne. Tulee samalla varmistettua, että syötteen muoto on taatusti oletetunlainen. Ei kyllä mitään hajua siitä, millaiseksi tuo kääntyy.

Lopuksi

Näköjään puolet noista 25 päivästä pääsivät tälle listalle. Mielestäni aika moni.

Rust on paras juttu ja toteutan edelleen jatkossa kaiken uuden softan sitä käyttäen. Tähän vois copypasteta viimekertaisen johtopäätöksen; näkemys ei ole siitä muuttunut. Muistetaan kuitenkin, että nämä joulukuupäiväpähkinät ovat nimenomaan algoja eivätkä esim. softakehitystä, eli ohjelmointikielestä tulee sivuttua vain joitain nurkkia.

Koodiprojekteja on hidastanut kaikenlainen muu, mutta kuten aiemmin tuli mainittua niin ainakin osaan leipoa hyvää leipää hapanjuuresta. Ei tartte lisähiivaa ollenkaan ja kohoaa ihan huikeesti. Seuraava vaihe olisi varmaan sitten oppia muukin kuin tuo yksi resepti; voisin viitsiessäni aloittaa havainnoimalla empiirisesti leipomisparametrien osittaisderivaatat.

Luulenpa, ettei sitä aiemmin mainittua lumihiutalehommaa tuu tehtyä taaskaan loppuun. Jospa vaikka edistäisin viimein jotain jolla on merkitystä, eli niitä muita harrasteprojekteja edes epsilonin verran. Viime päivinä oon vain seikkaillut avaruudessa näköradion kautta.

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.

Nimimerkki:

Spammibottiesto: Mikä on neljän ja nollan erotus? (vastaus numeroina)