Tulipa taas puuhattua Rustia hauskuudeksi ja hyödyksi. Joulu-uv-loma on yli puolivälissä ja AoC-koodikalenteri tehtynnä. Seuraa jo kolmas laatuaan pohdiskelu vähänkään mielenkiintoisemmista tehtävistä, joita oli viitisenkymmentä aina joulupäivään asti. Pitkästä aikaa tuli harrastekoodattua pidempi ajanjakso kerralla ja olipa hauskaa, vaan ei juuri muuhun sitten ehtinytkään.
Elikkäs
Advent of Code on kokoelma kisakoodaustyyppisiä tehtäviä, joita aukeaa joka päivälle kaksi kappaletta. Ensimmäisen ratkaiseminen avaa saataville toisen. Taustalla on mukaansatempaava tarina joulupukista. Pukki pitää pelastaa (tai ainakin etsiä) milloin mistäkin; tänä vuonna teema keskittyy avaruuteen. Viime vuonna seikkailtiin ajassa ja toissavuonna tietokoneen sisällä.
Pieniä algoritmipähkinöitä ratkaisemalla oppii ratkaisemaan pieniä algoritmipähkinöitä. Eipä siinä mitään -- algopähkinät ovat kosmisen mukavia nakerrettavaksi -- mutta ennemmin tai myöhemmin koodaan Rustilla itte vaikka kokonaisen jonkun pelin. Yhtä ajatusta on pyöritelty myös koodaavan veljen kanssa toisinaan. Alkaa varmaan käydä kärsimättömäksi jo. Niin kyllä alan minäkin.
Rust on uudehko (vrt. C tai C++) systeemiohjelmointikieli. Raudanläheistä koodia viimeiset N+1 vuotta tunkanneena Rustin monenlaiset ominaisuudet koodiergonomian, muistiturvallisuuden, luotettavuuden ja muun vastaavan ympärillä ovat oikein tervetulleita ja omassa päässäni helposti ymmärrettäviäkin. On mukavaa, kun kääntäjä ajattelee samalla lailla kuin itse. Toisaalta monille se kääntäjä ja vaativa tyyppijärjestelmä ja objektien eliniät voisi olla este. Rustia hetken koodanneena tuottaa välittömästi parempaa C:tä ihan kummemmin ajattelematta, mutta bugeja jää. Samoja konsepteja voi soveltaa, muttei ole kääntäjää niitä tarkistamassa.
Eräänä tavoitteena on toistaiseksi ollut se, etten käytä kummempia ulkoisia kirjastoja vaan tutustun tehtäviä tehdessä pelkästään standardikirjastoon. Ainoana poikkeuksena on toiminut regex-crate, koska syötteen parsiminen on toisinaan turhan kurjaa eikä syötteen lukeminen varsinaisesti ole näissä tehtävissä homman pihvi. Tänä vuonna valtaosa inputista parsiutui ilmankin ihan helpolla.
On tämä edelleen vähän opettelua mutta sanoisin, että kun referenssimanuskan ja ohjekirjan ei tarvitse lojua jatkuvasti vierellä ja yöpöydällä, niin kyse on pikemminkin treenaamisesta kuin ihan uuden opettelusta.
Enemmän taustaa Aocista ja Rustista ja tästä touhuamisesta voi lukea vaikka noista yhden ja kahden vuoden ikäisistä blogauksista.
Sitten niihin eri päivien pulmapeleihin.
5, emulaattori jo alkukuusta
Suureksi ilokseni voin huomioida, että tänä vuonna viime vuosistakin tuttu virtuaalimasiinateema alkoi jo toisena päivänä ja jatkui ihan jokaisena parittomana päivänä viidennestä eteenpäin. Päivänä 9 masiinasta tuli lopullinen siinä mielessä, että sen käskykanta oli täysin speksattu. Muina myöhempinä päivinä piti vähän puljata välillä I/O:n hallintaa. Ei siis lopulta erityisen jännittävää sinänsä kun koneesta tuli niin äkkiä valmis, mutta konetta käyttävää softaa on tarjolla monena päivänä eli jos/kun innostuu reverse-engineeraamaan niin tekemistä riittää.
Viitospäivän tehtävät sinänsä eivät sisältäneet muuta erityistä Intcoden oikeaoppisen suorituksen toteuttamisen lisäksi. Inputtina oli kasa koodia ja puzzlen vastauksena jotain lukuja, joita kone laskee. Käskykannan voi käydä tuolta tehtäväsivulta katsomassa, mutta tiivistetään tähän:
- summaa kaksi lukua keskenään
- kerro kaksi lukua keskenään
- lue yhden luvun syöte johonkin muistipaikkaan
- pursota jokin luku ulos koneesta
- vertaa lukua nollaan ja hyppää jonnekin jos oli nolla tai ei
- vertaa kahta lukua toisiinsa ja säilö tulos muistiin
- konffaa osoitteistuksen kantalukua (päivänä 9)
- pysähtymiseen on toki myös oma käskynsä
Tässä koneessa ei ole esim. pinoa eikä yleiskäyttöisiä rekistereitä, vaan jokainen käsky käpistelee koodissa kirjoitettuja vakiolukuja tai koneen muistista löytyviä lukuja. Muistipaikkojen osoitteistukseen on tarjolla vielä kantaluvun konffaaminen siten, että kaikkiin muistiosoitteisiin summataan taikarekisteriin ennaltasäilötty arvo.
On syytä huomioida, että itse suoritettava koodi ja sen käsittelemät luvut ovat samassa muistiavaruudessa jolle ei ole speksattu sen kummempia suojauksia. Ohjelma voi muokata itseään miten vaan (esim. käskyjen operandeja muuttamalla tai veivaamalla käskyjen tilalle toisia).
Rustpuuhassa ei erityistä mainittavaa tälle päivälle. Opcodeja loopataan läpi ja syötteitä ja paluuarvoja puljataan kun puljataan. En tehnyt käskyistä kummempaa enum-ihanuutta kuten ennen tuon itsemuokkautuvuuden takia (spoiler: disasm-työkaluun tein!).
7, useampi samanaikainen virtuaalimasiina
Tehtävän temppu oli kaikkien mahdollisten inputtipermutaatioiden kokeileminen yhdistettynä siihen, että virtuaalikoneita on viisi kertaa enemmän kuin tavallisesti eli tasan viisi kappaletta. Eikä siinä kaikki: niiden signaalitulot ja -lähdöt ovat kytketty toisiinsa. Kakkoskohdassa ne jopa muodostavat silmukan. Eri vehkeissä ajavat softat saattoi ajaa inputista outputtiin asti, eli mitään kovin nokkelaa suoritusmekanismia ei tarvittu.
Tällä tehtävällä voisi vaikka harjotella Rustin rinnakkaisuusominaisuuksia. Nämä eri vahvistimet saa pyörimään eri säikeissä ja sitten niiden toisilleen viestintä onkin jonkinlainen viestijonoharjoitus. Iteraattorirajapintojen toteuttamistakin voisi jumpata permutaatioiden läpikäynnillä. Tosin toistaiseksi copypastesin wikipediasta rekursiivisen algon.
9, täysi virtuaalimasiina
Osoitteistuksen kantaluku tuli mukaan tässä vaiheessa. Sen lisäksi, että opcodet voivat osoitella muistiin inputtia tai outputtia varten, muistinosoitusparametreihin voidaan säätää summautumaan jokin tietokoneen erikseen jemmaama luku eli jonkinasteinen segmenttirekisteri. Päivän pähkinä oli tuon tuen koodaaminen, eikä varsinaista algoritmiratkaistavaa ollutkaan, kunhan riitti ajaa syötteenä annettu softa.
Tykkään, että monissa näistä pulmista on joko taustatarinassa tai itse tehtävänannossa joku opettavainen juju; tälläinen osoitteistusmoodi löytyy usein oikeistakin tietokoneista. (Koko kuvitteellinen Intcode jo alusta alkaen pohjautunee johonkin avaruusaluskoneeseen. Pitää ottaa selvää.)
Pulmien kirjoittajakin kirjoittaa toivovansa, että hauskanpidon lisäksi opittiin uutta. Tykkään tästä filosofiasta.
10, melkein tein rationaaliluvut
Pulman syötteenä oli ideaalisessa tasossa oleskelevia täydellisen pistemäisiä asteroideja, koska sehän on kovin tavallinen avaruudessa esiintyvä esiintymä.
Ekassa vaiheessa piti katsella yhdenmuotoisia kolmioita, kun haettiin optimaalista tähystyspaikkaa asteroidien joukosta: jostain näkyy ympäriinsä katselemalla enemmän kuin mistään muista. Näkyvyys estyy vain, jos tähystyslinjalla on useampi avaruusklöntti täydellisesti samalla linjalla. Niiden etäisyydestä pelaajaan eri koordinaattiakseleilla muodostuu yhdenmuotoiset kolmiot.
Kun kuukautta ei ollut vielä kulunut kummoisesti, niin holtittoman epätehokas bruteforce-haku riitti tähän tehtävään. Pari kertaluokkaa enemmän asteroideja, niin olisi voinut kiinnostaa tehdä jokin avaruudenjakorakenne kiihdyttämään kiikarointia.
Ei ykkösvaiheessa vielä mitään erityistä, mutta kun hyvä tähystyspaikka löytyi, niin sitten piti ammuskella muut asteroidit mäsäksi "valtavalla laserilla". Laseria pyöritetään ympäriinsä, ja kun asteroidit ovat säännöllisessä ruudukossa pelin päähenkilön ympärillä, niin niistä pitää jotenkin laskea sellainen järjestys että posahtavat sopivasti vuorotellen. Järjestysnumerolla 200 olevan kappaleen koordinaatit pitäisi selvittää.
Rust-mielessä tuossa ei ollut tajunnanräjäyttävää erityisyyttä, mutta sen sijaan rupesin nysväämään hauskaa kulmanvertailua rationaaliluvuilla enkä kuitenkaan tehnyt sitä loppuun saakka kun liukuluvut riittivät, mutta mainitaan nyt kuitenkin: kun origon ympärillä on erilaisia pisteitä jotka täytyy käydä läpi kasvavan kulman järjestyksessä, niin näkyvät pisteet voidaan järjestää sen mukaan, mitkä niiden etäisyyksien suhteet ovat eri koordinaattiakseleilla. X- ja Y-deltoista saadaan taas muodostettua kolmioita, ja niitähän laitetaan järjestykseen tangenttifunktiota tavallaan laskemalla eli laventamalla y/x-suhteita samannimisiksi jne.
Piirtäisin kuvan jos viitsisin. Näissä tehtävissä on aina veikeää ajatella, että miten kelvollisena mikäkin ratkaisu pysyisi holtittoman kokoisella syötteellä. Kun tehtävä speksaa asteroideja avaruudessa, niin voitaisiin olettaa niitä olevan niin määrissä, että ohjelmointikielessä saatavilla olevista liukuluvuista loppuu bitit kesken eikä kaukana olevia voida erottaa toisistaan.
11, hauska ohjelma ja pieni tyyppi-inferenssihämminki
Parittomina päivinä tehtävä liittyy siihen Intcode-konekieleen. Nyt syöte on ohjelma, joka ajaa robottia ympäriinsä. Robotille annetaan syötteeksi tietoa sen ympäristöstä. Tehtävän eri vaiheissa robotti käyttäytyy varsin eri lailla; ensimmäisessä se haahuilee kaoottisesti ja toisessa se piirtää merkkigraffataidetta. Tämän voisi vaikka joutessaan reverse-engineerata.
Rustin kanssa tuli kumma juttu vastaan. Tähän closureen tarvitaan tuo hashmapin tyyppi eksplisiittisesti, vaikka closurea kutsutaan myöhemmin vain yhdestä paikasta aina samalla panelin arvolla:
let input = |panel: &HashMap<_, _>, x, y|
if *panel.get(&(x, y)).unwrap_or(&false) { 1 } else { 0 };
(Ehkä booleanin voisi muuttaa intiksi lyhyemminkin, mutta se ei ole pääasia.) Jos panelin tyyppiannotaation poistaa ja yrittää taas kääntää, niin kääntäjä pahastuu:
error[E0282]: type annotations needed
Veikkaan, että hashmappi kykenisi vaikka implisiittisesti muuttumaan toiseksi tyypiksi, jolta myös löytyisi joku get. Täytyypi tutkailla, jos kääntäjältä tai joltain vaihtoehtotyökalulta voisi kysyä, että mikä tässä nyt oli ambigöössiä.
12, helppoa geneerisyyttä vaan
Ei tainnut olla toka eikä kolmaskaan kerta aoccihistoriassa, kun tehtävänä on simuloida taivaankappaleita tai muita vastaavia kappaleita. Aikansa vispattuaan nuo muutamat kappaleet palaavat lähtötilaansa, eli simulaatio on syklinen. Syklin pituus on kuitenkin sen verran suuri, että aikaa saisi viettää tovin jos toisenkin naiivilla ratkaisulla. Mutta mikä se sykli on?
Syklisyyttä esiintyy eri taivaankappaleiden eri koordinaateissa ja niiden nopeuksienkin akselien suhteen. Kun näistä sykleistä löytyy jokainen, niin lopullinen sykli lasketaan pienimpänä yhteisenä monikertana niistä. Syklinhaku on suunnilleen yleistetty, ja sille passataan callback-funktio, joka ottaa taivaankappaleen ja palauttaa sen ominaisuuden, jonka syklisyyttä ollaan etsimässä:
fn fully_overlapping<F: Fn(&(Vek, Vek)) -> i16>(hist: &[Vec<(Vek, Vek)>],
a: usize, b: usize, len: usize, moon_ix: usize, moon_prop: F) -> bool {
(&hist[a..(a + len)]).iter().zip(&hist[b..(b + len)])
.all(|(amoons, bmoons)| moon_prop(&amoons[moon_ix]) == moon_prop(&bmoons[moon_ix]))
}
Callback-funktiot ovat triviaaleja closureja taulukossa:
let moon_props: &[Box<dyn Fn(&(Vek, Vek)) -> i16>] = &[
Box::new(|&(a, _)| a.0),
Box::new(|&(a, _)| a.1),
Box::new(|&(a, _)| a.2),
Box::new(|&(_, b)| b.0),
Box::new(|&(_, b)| b.1),
Box::new(|&(_, b)| b.2),
];
Jos toi nyt oikeasti kääntyy kutsuttavaksi funktiopointteriksi inlineytymisen sijaan, niin on aika hidasta koodia, mutta mistäpä sitä arvaa miten fiksusti kääntäjä huomaa että mitkä funktiot kyseessä. Jokainen samantyyppinen closure on kuitenkin uniikki tyyppi, eli niitä on vaikeaa laittaa taulukkoon ja loopata ympäri. Toisaalta niitä on vain kuusi, eli heappiin boxaamisen sijaan ne voisi ehkä esittää suorempaan kääntäjän käytettäviksi. Pitäisi palata asiaan. Olisi kuitenkin parempiakin tapoja tehdä nämä korrelaatiotestit, eli en välttämättä optimoi tätä ei-ees-parasta menetelmää.
13, voi veljet kolikkopeli
Koodimielessä ei kovin kummosta, ellei sitten puuhaa pelille kunnollista käyttöliittymää ja makeeta graffaa. Intcode-inputtina oli Breakout-peli, jota piti automaattipelata tai sitten pelata käsin, kunnes peli loppuu ja loppupistemäärä selviää. Kerrassaan ilahduttava tehtävä.
************************************ * * * xx x xx xx xx xxx xxx * * x xx xx xx xxxx x xxxx x * * xx xxx x x x xx x * * x x x x x xxx x * * xxxx x xx x x xxx * * xxxxx x x x x x xx x x x * * xx xxxx xxxx x x x x xxx * * x xx xx x xx x xx xx x * * x x x xxxx xx xx x * * xxx x x xx xxx x x * * xx xx x xxx xx x xxx xx * * x x x xx xxx xx xx xx x * * x x x x xx x x xx x x xx x * * * * o * * * * * * - * * *
15, hakuongelma
Intcode-inputti on pyörivinään kauko-ohjauslaitteessa, jolla komennetaan robottia korjaamaan avaruusaluksen happilaitteistoa. Vuotava happivehje piti löytää ja paikata siten, että happi täyttää avaruusaluksen eristetyn labyrintin. Robottia piti ensin ohjata syvyyshaulla ja kerätä alueesta karttaa, ja täyden kartan jälkeen löytyneen happipömpelin toiminnasta laskettiin tavallaan flood fill -algoritmi eli vaikka leveyshaku. Näitä simppeleitä algojumppatehtäviä on aina ihan kiva tehdä, kun perus systeemisofta-päivätyökoodissa ei välttämättä hakujuttuja usein näe.
explore(&mut computer, &mut grid, 0, 0, LOCATION_OPEN); let oxy_coords = *grid.iter().find(|(_, &v)| v == LOCATION_OXYGEN).unwrap().0; let oxy_distance = bfs(&grid, (0, 0), Some(oxy_coords))[&oxy_coords]; let flood_fill_minutes = *bfs(&grid, oxy_coords, None).values().max().unwrap(); (oxy_distance, flood_fill_minutes)
18, hakuongelma veikeämmällä verkkorakenteella
Avaruusteemaa seuraten nyt ollaan Neptunuksen kuita tarkastelemassa. Tritonilta löytyy holvi jossa kiinnostaa avaimet. Kaikki avaimet keräämällä pääsee tarinassa eteenpäin. Avainten keräämistä hankaloittaa se, että jokaiselle avaimelle on holvilabyrintissä vastaava ovikin. Koska on kiire, niin vastaukseksi kelpaa vain lyhyin mahdollinen reitti, jolla kaikki avaimet kerätään.
Kauppamatkustajan ongelmia on aina kiva ratkoa kun eivät ole liian helppoja. Touhusin koodia sen kummemmin miettimättä, että dijkstra-haun etäisyyskartan tila meni vähän vinksin vonksin, ja sen jälkeen sotkin jotain muuta niin että kyseessä ei ole dijkstra-algo enää ollenkaan.
type GdistMap = HashMap<char, (usize, Keys)>; // but <(char, Keys), usize> might be more correct
Avaimia on varsinaisessa inputissa joka aakkoselle yksi. Näistä voi rakentaa verkon, jonka solmuina toimii tieto siitä, minkä avaimen päällä pelihahmo seisoo ja mitkä avaimet löytyy taskusta. Sotkin kuitenkin avainkokoelman mukaan etäisyystietoon kävellyn matkan lisäksi solmu/etäisyys-hashmapin väärälle puolelle. Löytyi se vastaus noinkin, kun rakensi verkon kaaret siten, että otetaan huomioon matkalla olevat ovet ja päämäärästä löytyvä uusi avain ja kun vähän veivasi hakusilmukan keskiössä olevaa prioriteettijonoa siten, että avainten lukumäärää optimoidaan jopa ennen käveltyä etäisyyttä. Pitäis vielä veivata koodi oikein päin ja nakertaa hakualgoista geneeriset versiot joita kutsuu joillain callbackeilla. Ehkä.
######################################### #.................C...#...#.......#.....# #.###################.#.#.###.#.###.#.#V# #...Z...#.......#.....#.#...#.#...#.#.#.# #.#####.#.#####.#.#####.###.#.###.#.#.### #.#.....#k..#...#...#...#.#.#...#...#...# #.#.#.#####.#.#####.#.#.#.#.#.#########.# #.#.#.#.....#.#...F.#.#.#...#.#...#...#.# #.#.###.#####.#.#######.#.#####.#.#.#.#.# #.#...#.#.....#...#.....#.......#.#.#.#.# #.###.#.#.#######.#.#############.#.#.#.# #.#...#.#.......#.#...#...#.....#.#.#.#.# #.#.###.#######.#.#.#.###.#.#.###.#.#.#.# #.#...........#.#.#.#...#...#...#.#.#...# #.###########.#.#.#####.#.#####.#.#.###U# #...#.#.....#.#.#.......#.#...#.#.#...#.# ###.#.#.###.#.#.#########.###.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.......#.....#.#.#.#.#.# #.#.#.#.#.#.###.#####.#.#####.#.#.###.#.# #.....#.#.......#...#.#...#...#...#...#.# #######.#########.#.#####.#.#######.###.# #.....#...#...#.S.#.#j..#...........#.#.# #.###.###.#.#.#.###.###.#############.#.# #.#.....#.#.#.....#...#.......#.........# #.#####.#.#.#######.#.#######.###.####### #.#.E.#.#.#.#...#...#...#...#...#.....#.# #.#.#.#.#H#X#.#.#.#.#####W#.###Q#####.#.# #...#.#...#.#.#.#.#.#...#.#...#.#...#.#.# #####.#####.#.#.#.###.#.#.###.#.#.###.#.# #...#.#.....#.#.#...D.#...#.#.#.#.....#.# ###.#.#.#####.#############.#.#.#.#####.# #...#...#..........o........#...#......g# #.#.#####.###########.#################.# #.#.....#.#.....#...#.........#.......#.# #.#######.###.#.#.#.#######.#.#######.#.# #.#.....#...#.#...#...#...#.#.........#.# #.#.###.###.#.#######.#.###.#####.#####.# #.#.#.#...#...#.#.....#...#.....#.#.....# #.#.#.###.#####.#.#######.#####.###.##### #.......#.....................#.......... #######################################.@
Päivän kakkosvaiheessa haku muuttui siten, että holvilabyrinttejä onkin neljä erillistä ja pelihahmoja eli robotteja on yksi kuhunkin. Muuttuu vaan hakualgon käyttämän verkon solmutieto silleen, että muistetaan jokaisen paikka. Kävelty kokonaisetäisyys lasketaan silti yhteisille askelille ja kerätyt avaimet ovat jaettua omaisuutta. Tein kauheeta copypastaa kun piti vaan saada valmiiksi.
Rust-mielessä tästä ei ole korostettavissa vielä yksittäistä kielen ominaisuutta, mutta täytyy taas todeta, että pienienkin juttujen koodaaminen on kerrassaan ergonomista näin staattisesti tyypitetyksi kieleksi. Ergonomiaa voi löytyä C++:sta sitten suunnilleen samoissa mitoissa, mutta Rustin kanssa voi nukkua yönsä rauhassa tietäen, että muistivirheitä ei kääntyvässä koodissa ole ja turhia kopioita ei tule yhtään silleen kuten plusplussassa helposti.
Perutaan tuosta äskeisestä ettei ole yksittäistä ominaisuutta. Mainittakoon, että onpas kätevää kun voi periä strukteille kaikenlaista oletuskäytöstä joita mm. hashmapit ja binaryheapit osaavat käyttää. Kun struktini sisältää tavallista dataa jonka hashaamisesta en välitä itse, niin struktille voidaan yhdellä rivillä periä oletushash joka varmaan laskee joka jäsenelle niiden oletushashit ja jotenkin yhdistää sen. Kun taas strukteja täytyy laittaa järjestykseen, niin oletusjärjestys lukee jäsenet järjestyksessä ja vertailee niitä (esim. xyz-avaruusvektorissa eri koordinaatteja vuorotellen). Tein sitten kerättyjä avaimia esittävälle bitmappi-intille omat vertailut siten, että avainten lukumäärän perusteella järjestetään. Muuhun riitti oletukset.
20, jälleen luolaseikkailua
Ei tästä päivästä sen kummempaa sanottavaa kuin että oli hyvin paljon samaa kuin päivässä 18. Merkittävin osuus teleporttinodeja käsittelevästä tehtävästä oli saada se muotoiltua silleen, että dijkstran haku toimii taas. Tällekin päivälle voi korostaa noita ergonomialöpinöitä. Kaikki vaan toimii ja koodi on välillä niin ekspressiivistä, että pitää ihan pysähtyä miettimään että mitäs tää nyt tekeekään jonka kirjoitin minuutissa ja tarttee kaksi minuuttia ajattelemista. Vaikka Rust sallii tyyppi-inferenssin monessa paikassa, niin silti niitä tyyppejä pitää kirjoittaa ihmistä varten.
Vähän hävettää taas tuo hakufunkan copypasteaminen. Ehkä oikeesti kokeilen reitinhakutehtävien yhdistämistä minimivaivalla. Liikaa jos geneerisöi niin tyyppien kanssa homma lähtee lapasesta, kun copypastettavaa ei oikeasti ole kauhean paljoa. Siinäkin on rajansa että jossain vaiheessa toisto alkaa olla ihan hyväksyttävää. Tästä muutama sana myöhemmin.
23, viisikymmentä virtuaalimasiinaa
Seiskapäivän seuraajaksi tuli tehtävä, jossa avaruusaluksen verkkotekniikka on mäsä ja se pitää tehdä itse uudestaan. Erinäisten sääntöjen perusteella nuo 50 vekotinta lähettelevät toisilleen paketteja. En vieläkään selvittänyt, miten Rustin säikeistys- ja synkronointijutut toimivat, eli tehdään toistaiseksi yksinkertaisemmin.
Päivän 7 pulmassa eri emuloitavat laitteet lukivat syötteen, laskivat jotain, ja pursottivat dataa ulos. Siten niitä saattoi ajaa inputista outputtiin ja siirtyä sitten seuraavaan. Tämänpäiväisessä sen sijaan ajettava ohjelma ei välttämättä pysähdy aikoihin eikä luekaan mitään, ja tehtävä oli speksattu vähän epämääräisesti, niin teinkin viidellekymmenelle rinnakkain ajavalle verkkolaitteelle skedulerin eli eventtihandleriloopin, joka steppaa kutakin vuoronperään vähän eteenpäin.
Voisi olla kivempaa pitää virtuaalikoneen logiikka jossain etäällä tästä verkkolaitteiden tai ylipäätään useampien virtuaalikoneiden konseptista. Sen lisäksi, että nuo voisi paiskata eri säikeisiin ajelemaan, voisinkin tätä kautta tutustua (vielä unstableihin) generaattoreihin. Jokainen virtuaalikoneen päälooppi voisi ajaa coroutinessa ja yieldata sieltä jotain i/o:ta ulos sitten kun sellaista tapahtuu. Noin päin voisin kuvitella tämän tehtävän logiikan siistimmäksi kuin tälläisen, jossa joka konetta ajetaan samassa pääloopissa vuoronperään.
Kenties kokeilen muokata tuon vain iteraattoreiden kautta toimivaksi.
25, tonttupainohuijaus tekstiseikkailussa
Joulupäivän ainoa ja aocin päättävä tehtävä oli parittomien päivien tapaan Intcode-puuhaa. (Viimeisen tehtävän toka puolisko saadaan kaupan päälle kunhan aiemmat tehtävät on tehty.) Parsimiseen riitti tekstinkäpistely rivi riviltä, joskin johonkin parserikirjastoon pitää tutustua joskus kun vanhat Rust-tyypit väittävät hyväksi.
Päivän varsinainen haaste olisi selviytyä suht yksinkertaisesta pulmasta nopeasti, mutta oma tavoitehan on vain Rust-treenaaminen joten edes yritin koodata siististi sen sijaan että täysii. Tekstiseikkailupeli avaruusaluksessa on peli, ja itseä kiinnostaa ohjelmointi vähän enemmän kuin pelaaminen, eli eipä tullut koodattua tuolle pelille itse pelattavaa komentokehotetta. Seikkailupelin tekstisyötteen parsiminen tarkasti vaati paikoittain tarkkuutta, mutta johdonmukaisuudessaan ei kuitenkaan tuottanut ongelmia. Vaikka tekstiä onkin verrattain niukasti käsiteltäväksi, niin jokaisen stringiallokaation kohdalla tuli pohdittua, että saisko tämänkin vältettyä jotenkin. Ihan turhaa optimointia.
Jo tehtävänannossa vihjattiin, että tavaroita kannattaa kerätä matkan varrella. Reppu ja tasku ovat kauko-ohjattavalla droidilla käytännössä äärettömät, eli riitti selata koko alus läpi ja poimia kaikki matkan varrelta löytyvä. Kaikkea ei kuitenkaan voinut poimia. Kaikki spoilerit voi käydä katsomassa koodista, mutta jos esim. jonkun valonlähteen kerää, niin mörkö hyökkää ja peli loppuu.
== Navigation == Status: Stranded. Please supply measurements from fifty stars to recalibrate. Doors here lead: - north - east - west Items here: - giant electromagnet Command?
Kun pelialue on saatu kartoitettua, niin voi marssia suoraa tietä taskut täynnä roinaa painetunnistuslattiaa edeltävälle checkpointille. Alkaa maistua puulta jo nämä copypastettavat leveyshaut. Ehkä tosiaan hifistelen niille jonkun geneerisen rajapinnan. Mikäli oikea määrä roinaa on mukana, niin saa huijattua itsensä painetunnistuslattian yli joulupukin luokse salasanan äärelle. Riitti kokeilla osa vaihtoehdoista läpi pudottamalla tavaraa checkpointtiin, ja löytyi oikea. Virtuaalikoneen muistista saa triviaalisti otettua kopion, jota vasten voi pelata kokeilun läpi, eikä tarvitse murehtia alkuperäisestä pelin tilasta. Toisaalta tavaroiden läpikäynnin saisi hauskasti optimoitua Grayn koodin avulla.
for bitmap in 0..options {
let forget = inventory.iter().enumerate()
.filter(|(i, _item)| (bitmap & (1 << i)) == 0)
.map(|(_i, item)| item.as_str())
.collect::<Vec<&str>>();
if attempt_weight(&computer, &forget, direction) {
return forget;
}
}
Varsinainen voittostrategia olikin sitten vain muutama rivi:
fn embark(computer: &mut Computer) -> String {
// [ ... ]
crawl_dungeon(computer, &mut map, &mut Some(&mut inventory));
enter_checkpoint(computer, &map, &mut Some(&mut inventory));
let direction = floor_direction(&map);
let useless_items = reach_correct_weight(&computer, &inventory, &direction);
drop_stuff(computer, &useless_items);
communicate_line(computer, &direction);
read_room(computer, &mut None);
let line = read_line(computer);
assert_eq!(line, "Santa notices your small droid, looks puzzled for a moment, \
realizes what has happened, and radios your ship directly.");
// [ ... ]
Reverse-engineerausta
Kunnon reversaussessio on kuin kunnon debuggaussessio eli kuin rikosjännärin nautiskelua. Nämä Intcode-ohjelmat ovat siinä määrin pieniä ja helppoja, että johtolangat ovat verrattain lastenleikkiä eli tuskin jokaista tulee tutkittua. Yhden tutkiskelin läpi jo ja ehkä seuraan joitakin johtolankoja tuosta viimeisen päivän tekstiseikkailustakin. Kiinnostaa nähdä, että onkohan laadittu käsin vai kenties jollain työkalulla, ja että ylipäätään millainen hökötys se on. Kaiken toimivan ja toimimattoman sisään kurkistaminen on aina antoisaa puuhaa.
Tein pienen disasmaustyökalun, jolla Intcoden numerolistan saa vähän ihmisluettavampaan muotoon. Disassembleri pursottaa ulos suoran assylistauksen ja control flow graph -nimellä menevän basic block -analyysin tuloksen, eli läjän laatikoita joissa suoritus menee aina alusta loppuun ja viivoja laatikoiden välille. Jos laatikon viimeinen rivi on ehdollinen hyppykäsky, niin laatikosta lähtee kaksi nuolta. Jos laatikkoon johtaa useampi nuoli, niin usemmasta haarasta voidaan päätyä sinne. Laatikon viimeisin rivi ei aina välttämättä ole hyppykäsky, sillä laatikoiden esittämät lohkot on pilkottu siten, että hypyt ovat aina lohkon alkuun.
Elikkäs Rust
Nämä tehtävät olivat kuin suklaalevyn tai vihreiden kuulien nakertamista. Kivaa on niin kauan kuin niitä on suussa tai vielä pöydällä jäljellä, mutta nyt tyhjiä käärepapruja rapistellessa ihmettelee, että mitäs seuraavaksi. Sokeripöhnää aiheutuu koodista sentään vähän vähemmän.
Kuukauden teemana on ollut uudehkolla kielellä puuhaaminen ilman kummempaa kirjastotukea ulkopuolelta. Tais olla jo neljäs kerta putkeen, kun aoccaan näitä Rustilla, eli ihan alusta ei tarttenut lähteä sitä kirjaa lukemaan. Klikkailen silloin tällöin vastaantulevia Rustiin liittyviä tekstejä niin pysyy mieli edes vähän virkeänä, mutta täytyisi joku koodiprojektikin ottaa kehiteltäväksi pitkin vuotta. Vastaavia koodipähkinäkokoelmia on saatavilla, mutta pidetään vain AoC perinteenä ja koodataan muulloin jotain oikeaa softaa.
Standardikirjastossa on kaikenlaista kivaa joka puolelta C++:n ja Haskellin väliltä. Yleensä mitä sitten ei ole niin löytyy jonkun muun ylläpitämänä. Ilmeisesti aika hyvä osa standardityökalulaatikon sisälmyksistä toimisi omaa kerneliä tai mikrokontrolleriprojektiakin koodatessakin. Osaa jutuista ei saa mukaan ellei tarjoa Rustille heap-allokaattoria, mutta joka tapauksessa tilanne lienee parempi kuin vaikka C++:n kanssa, jota päin Rust kilpailee.
Kuten jo aiemmin mainittu, niin ergonomiaa on tarjolla pieniinkin softiin. Usein kehutaan erityisesti isoissa softissa toimivia konsepteja mm. objektien elinaikaan ja rinnakkaisuuteen liittyen, mutta kyllä tää on hirmu kiva käyttää pikkujuttuihinkin. Ennen tein kaikenlaisia pikkutyökaluja Pythonilla. Jatkossa entistä enemmän Rustilla. Dynaamisesti tyypitetystä sotkusta ei ota selvää enää sen jälkeen, kun aikaa on kulunut jokunen päivä.
Mainittakoon satunnaisena sekamelskana noista pikkuasioista if let x, kaiken sortin pattern-kiva, iteraattorit, slicet, option-tyyppi, 128-bittiset kokonasluvut, tuplet, summatyypit, oletus-immutability ja debug-printtien defaultformatointi.
Omia iteraattoreita tai hassuja uusia traitteja en oikeen koodannut. Ensi vuoden aocciin voisi ottaa tavoitteeksi ylihifistellä kaikki tehtävät jotenkin pellesti niin että oppisi muutakin kuin perusteet kunnolla.
Isompina kivoina toki täytyy mainita (taas?) tyyppi-inferenssi ja lifetime-jutut. Toisaalta kuten päivän 20 kohdalla piti todeta, niin pitää niitä tyyppejä välillä kirjoittaa vaikkei tarttis jotta pysyy homma lapasessa. Toinen hassu juttu arvattujen tyyppien ansiosta on semmonen, että välillä saattaa pyöritellä vahingossa viittauksia (kuten C:ssä pointtereita) tietämättään. Otetaan joku tälläinen:
iteraattori.filter(tavaraa).sitätätä(muuta).collect::<Vec<_>>();
Collect osaa kerätä iteraattorilähteestä dataa kaikenlaisiin tietorakenteisiin. Vektori pitää mainita erikseen, mutta sen sisältö päätellään. Joskus voi tulla vaikka vahingossa Vec<&u32> kun pitäisi tulla Vec<u32> ja sitten ollaankin jahtaamassa pointtereita kun tuota käydään läpi, kun kokonaislukujen käpistely olisi ollut tarkoitus. Kävi tälleen ainakin kerran, kun huomasin vasta myöhemmin koodia refaktoroidessa, että hei, tuo tyyppi ei nyt täsmääkään funktion paluutyyppiin.
Lifetimeongelmista joissa rustc pelastaa ja g++ ei on myös mainittava yksi erityistapaus. Päivänä 25 kävi läheltä piti -tilanne, jossa cepen kanssa olisin ollut jahtaamassa invalidoitunutta pointteria eli segfaulttia joskus myöhemmin riippuen siitä, missä järjestyksessä tekstiseikkailun huoneita käydään läpi. Rekursiivinen kartanetsintä (sorsan funktio crawl_dungeon()) otti huonenimi/huonestrukti-hashmapin huonestruktiin viittauksen juuri lisättyyn (tyyliin C++:n unordered_map::emplace()) huoneeseen käyden sen huoneen ovia läpi. (Huonestruktia on turha kopioida tässä vaiheessa.) Ovet ovat neljän mittaisessa taulukossa, joka kertoo mihin ilmansuuntaan voi kävellä. Nämä ovet loopataan huonestruktista läpi. Joka ovelle crawl_dungeon() ia kutsutaan uudestaan. Tässä vaiheessa olisi pitänyt hälytyskellojen soida. Ehkä C++:ssa kilisee vähän helpommin, kun auto ja auto& ovat eri asiat, mutta olin jo ehtinyt unohtaa, että tämä loopattava taulukko sijaitsee hashmapin omistamassa muistissa joka saattaa lähteä alta pois kun mappiin lisätään huoneita syvemmällä rekursiossa ja se reallokoi. Ongelma ratkesi tekemällä kopio siitä pienestä ovitaulukosta.
error[E0499]: cannot borrow `*map` as mutable more than once at a time
--> 25.rs:247:33
|
233 | let room = match map.entry(xy) {
| --- first mutable borrow occurs here
...
244 | for (_door, &dxy) in room.doors.iter()
| __________________________-
245 | | .zip(door_xy.iter())
246 | | .filter(|&(&door, &_dxy)| door) {
| |___________________________________________- first borrow later used here
247 | crawl_dungeon(computer, map, dxy);
| ^^^ second mutable borrow occurs here
C++
Hifistelylläkin on toisaalta rajansa. Eräässä Aalto-opiston robottiharjoitustyössä vuosia sitten jäi aika karvas maku suuhun Boostin graph-kirjastosta. Vilkaise vaikka A*-haun referenssiä. Toki, homma on geneerisöity silleen yleispätevästi että toimii aivan mihin vaan, mutta menee ensin hetki ymmärtää että kuinka kummassa tuota käytetään mihinkään muuhun kuin kirjaston esimerkkiin.
Vaatii vähän erikoiset käyttötapaukset tai oikein heikon luoton omaan ohjelmointitaitoon, että ottaa tuon libran sen sijaan, että koodaa ne muutamat rivit jotain leveyshakua. Jotta saa täysin geneerisen leveyshaun puljattua omaan verkkotyyppiinsä, niin saa tehdä liimakoodia jonkin aikaa ja ihmetellä viikon verran niitä neljäätuhatta viestiä kääntäjältä. Ookoo, noissa on kaikenlaiset visitorit ihan joka väliin mikä monimutkaistaa puuhaa entisestään ja jos kaipaa vain etäisyyskarttaa niin geneerisyysaste voi pysyä hallussa, mutta kuunteles tätä. Jos riittää A*-haku johonkin yhteen pisteeseen koko kartan solmujen sijaan, niin hausta ei toki palata normaalisti vaan heitetään poikkeus kun muuta tuo kirjasto ei tue.
Löysin irkkilokeista Valgrind-lokia tuolta seitsemän vuoden takaa. Piti aikoinaan kääntää Valgrind uudestaan itse, jotta sai debugattua tuota Boost-mössöä, kun funktion prototyyppi ei mahtunut kovakoodattuun neljän kilon bufferiin:
==13641== by 0x409402: void boost::breadth_first_visit<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >, boost::d_ary_heap_indirect<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, 4ul, boost::vector_property_map<unsigned long, vertexindexasdmap>, boost::shared_array_property_map<float, vertexindexasdmap>, std::less<float>, std::vector<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, std::allocator<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor> > >, boost::detail::astar_bfs_visitor<grid_heuristic<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >, float>, grid_visitor<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor>, boost::d_ary_heap_indirect<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, 4ul, boost::vector_property_map<unsigned long, vertexindexasdmap>, boost::shared_array_property_map<float, vertexindexasdmap>, std::less<float>, std::vector<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, std::allocator<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor> > >, boost::reference_wrapper<my_pred_map>, boost::shared_array_property_map<float, vertexindexasdmap>, boost::reference_wrapper<my_dist_map>, edge_weight_map, boost::associative_property_map<std::map<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, boost::default_color_type, std::less<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor>, std::allocator<std::pair<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor const, boost::default_color_type> > > >, boost::closed_plus<float>, std::less<float> >, boost::associative_property_map<std::map<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, boost::default_color_type, std::less<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor>, std::allocator<std::pair<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor const, boost::default_color_type> > > > >(gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > > const&, boost::graph_traits<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > > >::vertex_descriptor, boost::d_ary_heap_indirect<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, 4ul, boost::vector_property_map<unsigned long, vertexindexasdmap>, boost::shared_array_property_map<float, vertexindexasdmap>, std::less<float>, std::vector<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descriptor, std::allocator<gridgraph<std::vector<std::vector<bool, std::allocator<bool> >, std::allocator<std::vector<bool, std::allocator<bool> > > > >::vertex_descr
Käännöslokiakin löysin jostain arkistosta. Ei siitä templatekauhutarinasta sen enempää.
Lispistä vielä
Rustiahan tässä vain tehdään ns. jalat maassa. Muutaman vuoden nuorempi veli on ottanut tavaksi tunkata vapaa-ajallaan Schemellä kaikenlaista aoccitehtävistä C-parseriin. Joko Nuutti vain on paljon mua taitavampi (ihan todennäköistä) tai sitten vain kaikki mitä lispeistä sanotaan on ihan tosijuttua. Koodista saa ilmeisesti helposti täydellisen eleganttia. Toisaalta kun koodissa ei ole matemaagisen ilmaisun kannalta mitään turhaa, niin koodi ei vielä välttämättä pyöri ihan niin täysii kuin matalan tason natiivikielillä. Hyi joku tulkki ja roskienkeruu. Toisaalta löytyy luonnollisesti coroutinet ja toimiva häntärekursio ja kaikkee.
Lueskelin jokunen aika sitten itseäni sivistääkseni erästä kulttiteosta ja melkein tuli paha mieli kun tajusin mistä on kyse ja että en vielä osaa lispata. Oikeesti haluaisin raapia jostain vuoden verran harrasteaikaa Haskellinkin ymmärtämiseen, mutta Lisp ois varmaan helpompi ensin ja molempien älyämisestä ei liene haittaa.
Täytyypä joka tapauksessa tarkistaa löytyisikö työpaikan kirjastosta vaikka SICP ja sitten viettää jokunen pitkä talvi-ilta sen kanssa.
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.