Suunnitellessamme vuoden vaihteen jälkeen seuraavaa opiskelijaekskursiota päätimme illan agendan olevan muutakin kuin yritysesittelyjä ja biljardin pelaamista. Tavoittelimme agendaksi jonkinlaista teknistä aihetta. Onneksi Gofore on täynnä innokkaita koodareita ja soveltuva aihe löytyy joskus täysin vahingossa.
Hirsipuutin – tärkeä työkalu tärkeään työhön
Hirsipuuttimen tarina alkaa eräistä illanistujaisista Tampereen toimistollamme, kun kollegamme Niko (nimi muutettu) piirsi eräälle monista valkotauluista kahdeksan viivaa. Sana oli ”töttöröö” eikä sitä arvattu ajoissa, mutta ajatus innoitti seuraavana työpäivänä uuden hirsipuun ja uusi pisara toimistokulttuurin meressä oli syntynyt.
Muutaman kierroksen jälkeen lauma teknisesti suuntautuneita ihmisiä alkoi tietysti pohtimaan ongelman automatisointia eri tavoin, osa helpottaakseen ratkaisemista, osa löytääkseen mahdollisimman kiperiä sanoja arvuutettavaksi. Yksinkertainen analyysi sanoista osoittautui nopeasti riittämättömäksi kumpaankin, joten tarvittiin paremmin itse pelaamista simuloiva ratkaisu. Hirsipuutin syntyi suorittamaan kaikille näille ratkaisuille yhteistä osuutta, eli itse pelin pyörittämistä automaattisille ratkaisimille. Pian osoittautui, että melko nopeasti tehty ratkaisin suoriutuu 99,5 % nykysuomen sanakirjan sanojen arvaamisesta enintään seitsemällä virheellä. Samalla selvisi, millaiset ominaisuudet vaikeimmilla hirsipuusanoilla on.
Hirsipuutin on toteutettu Pythonilla ja suunniteltu käytettäväksi millä tahansa ohjelmointikielellä toteutettujen ratkaisimien kanssa. Tiedon välittämiseen käytetään UNIX-filosofian mukaisesti standardeja tekstivirtoja erikseen määritellyllä protokollalla. Käynnistyksen yhteydessä hirsipuuttimelle annetaan käytettävä sanasto, arvuutettavien sanojen määrä, satunnaistamisen siemenluku ja muita olennaisia parametreja. Hirsipuutin suorittaa näiden perusteella ratkaisimen peluuttamista ja ylläpitää pistesaldoa tulosten perusteella. Tehtyjä ratkaisimia voidaan näin vertailla saatujen pisteiden perusteella tietyillä parametreilla. Opiskelijatapahtumaa varten toteutettiin referenssiratkaisin, joka toteuttaa pääosan ilmeisistä tavoista parantaa pistemäärää ja jota vastaan osallistujat saattoivat kilpailla.
No miten meni, noin niinku omasta mielestä?
Miten Hirsipuuttimen ratkaisimien koodaus sitten opiskelijoilta sujui? Jo ennen testiajoja opiskelijoiden kanssa juttelemisen perusteella pystyi sanomaan koodauksen sujuneen erittäin hyvin! Osa opiskelijoista oli kutsun mukaisesti toteuttanut ensimmäisen version jo valmiiksi ennen ekskursiota. Ratkaisimia oli koodattu useilla eri kielillä, esimerkiksi Haskellilla, C++:lla ja Javascriptilla. Kuitenkin useimmat ratkaisimet oli toteutettu Pythonilla. Luultavasti Pythonin valintaan ohjasi myös se, että sekä Hirsipuutin että GitHubissa oleva triviaali ratkaisin olivat myös toteutettu Pythonilla.
Samalla kun nautimme illan tarjoiluja aloimme valmistelemaan testiajoja opiskelijoiden ratkaisimille. Ajoimme toteutukset testikoneella ja visualisoimme tulosten kertymisen testiajoista televisioruudulle. Kaikissa testiajoissa käytettiin samaa satunnaisluvun siemenlukua ja ajettiin jokaista ratkaisinta 1000 kierrosta Hirsipuutinta vastaan. Hirsipuutin käytti sanastona nykysuomen sanakirjaa, josta oli poistettu kaikki välilyöntejä sisältävät sanat ja muut normaalista aakkostosta poikkeavat sanat. Sanoja näin rajatussa sanastossa on 92 082 kpl.
Toistuvin teema eri opiskelijoiden välillä näytti olevan merkistöongelmat. Hirsipuuttimen ja ratkaisimien testaaminen eri ajoympäristöillä oli jäänyt harmillisen vähälle Goforen puolesta ennen ekskursiota, joten näitä mahdollisia ratkaisuja merkistöongelmiin haettiin sitten yhdessä tapahtuman aikana. Teemun kohtalaisen yksinkertainen referenssitoteutus pärjäsi täysin toiveiden mukaisesti, eli sijoittui noin puoleen väliin tuloksissa. Parhaat toteutukset tehneet opiskelijat kertoivat hieman omista ratkaisuistaan ja sitä kautta muut opiskelijat saivat myös hyviä vinkkejä.
Toisen kierroksen aikana jokainen pääsi parantamaan omaa toteutustaan ja tuloksia saatiinkin toiselle kierrokselle ensimmäistä enemmän. Pistemäärät lähestyivät toisiaan, mutta eivät nousseet enää kovin paljon ensimmäisen kierroksen parhaasta. Ensimmäisen kierroksen parhaan pisteet olivat 18 515 797. Toisella kierroksella parhaan pisteet nousivat 18 548 296 pisteeseen ja ensimmäiset kolme olivat kaikki parempia kuin ensimmäisen kierroksen paras.
Eräs opiskelijoista myös havaitsi Hirsipuuttimen koodeista virheen pisteiden kerryttämisessä. Virhe aiheutti sen, että usean kierroksen ajaminen kerralla vaimentaa loppupään pisteiden merkitystä, eli alkupäässä saadut pisteet ovat merkitykseltään suurempia. Tämä ei ollut paremmuusjärjestystä haettaessa ratkaiseva tekijä, mutta erot olisivat kuitenkin voineet olla hieman selvemmät osallistujien välillä ilman tätä virhettä. Virhe oli alunperin syntynyt siinä vaiheessa, kun Hirsipuutin muokattiin soveltumaan visualisoitavaksi ekskursion aikana. Jälleen huomattiin testauksen olevan tärkeää ennen tuotantokäyttöä ja että koodiin tutustumisen jälkeen on ihan tervettä kyseenalaistaa näkemäänsä.
No, hyvinhän se meni
Sinänsä tälläinen haaste on helppo toteuttaa täysin itse valitsemallaan ohjelmointikielellä, koska tehokkuus ei ollut tässä merkittävää – tietenkin sillä reunaehdolla, että pystyimme ajamaan testiajon järkevässä ajassa. Tästä haasteesta pystyisi tekemään myös aivan erilaisen tuomalla jollain tavoin ajoajan merkittäväksi tekijäksi pisteytykseen. Paras ratkaisimen toteutus oli loppujen lopuksi C++:lla toteutettu, ja mestarin itsensä kommentti finaalin jälkeen oli yksinkertaisesti ”Mulla oli paras koodi”. Kaksi muuta kolmen parhaan joukkoon sijoittunutta toteutusta oli tehty Pythonilla ja Haskellilla, joten saimme tuloksiin mukavaa hajontaa toteutusteknisesti. Parhaissa toteutuksissa otettiin huomioon eri tavoin sanajoukosta kelpaamattomien karsiminen arvattujen kirjainten perusteella, sanojen pituuden mukaan karsinta, kirjainten todennäköisyyden laskenta jäljellä olevista sanoista ja tehokas ongelma-avaruuden osittaminen.
Ilta tietenkin jatkui palkintojen jaon jälkeen Tampereen keskustassa yhdessä opiskelijoiden kanssa. Kiitos TiTe ja Luuppi, sekä tietenkin kaikki osallistuneet!
Haluatko vaikeasti arvattavan hirsipuusanan? Valitse viiden kirjaimen sana, jonka vokaalit ovat yleisimmillä paikoillaan ja joka ei ole kielen 10000 yleisimmän sanan joukossa. Esimerkiksi ”syrjä”, joka oli toinen sana toimistohirsipuumme historiassa, jota ei arvattu.
