Technology

Fast track, osa kaksi – Avaruudessa ja koodauksessa yksinkertaisuus on valttia

March 25, 2014

Read time 3 min

1960-luvulla NASAlla oli ongelma: astronauttien piti avaruuslennon aikana kirjoittaa lukuisia muistiinpanoja paperille. Olemassaolevissa muistiinpanovälineissä oli kuitenkin jokaisessa omat ongelmansa, eikä avaruudessa kirjoittamiseen sopivaa kynää ollut löytyä. Kuulakärkikynät eivät toimi painottomassa tilassa, ja jopa lyijykynien kärjestä lohkeileva grafiitti on sähkönjohto-ominaisuuksiensa takia avaruusaluksessa hengenvaarallista. Pahimmillaan pienen pieni grafiitinpalanen saattaisi leijailla lentolaitteistojen piirilevyille ja aiheuttaa oikosulun. Sama ongelma vaivasi myös Neuvostoliiton avaruusohjelmaa.

Sitkeästi hengissä sinnittelevän urbaanilegendan mukaan nämä kaksi maata ratkaisivat ongelman täysin vastakkaisilla tavoilla. Huhu kertoo, että NASA olisi käyttänyt miljoonia dollareita kehittääkseen painottomassa tilassa toimivan kynän, kun taas Neuvostoliitto selvisi ongelmasta huomattavasti edullisemmin – käyttämällä tavallisesta paperikaupasta saatavia rasvakyniä.

Tosiasiassa Fisher-yhtiö otti avaruuskynän henkilökohtaiseksi haasteekseen, ja kehitystyön päätyttyä kyniä ostivat ja käyttivät sekä NASA että Neuvostoliitto. Tarinan ydin ja opetus on kuitenkin siinä, että yksinkertaisuus on valttia. Helpoin ratkaisu on usein elegantti ja samalla kustannustehokas.

Yksinkertaisuutta painotimme tällä kertaa myös fast track -tehtävässä ja vastauksien arvioinnissa. Itse tehtävän toteutus noudatteli samaa kaavaa kuin ensimmäinen fast track-tehtävämme, ja tehtävänantona oli toteuttaa morsesignaalia luettavaksi tekstiksi kääntävä Javascript-funktio. Edellisestä fast track -tehtävästä poiketen tällä kertaa vastaus ei kuitenkaan voinut olla puhdas funktio, sillä sen palautusarvo riippuu aiempien kutsujen argumenteista.

Esimerkkivastaus

Reaktorilainen Toni Strandell vastasi allaolevalla tavalla, ja kuvaili omaa vastaustaan seuraavasti:

Ei ehkä kovin mehukas, mutta ratkaisu kuitenkin. Musta tää oli vain datan mallinnushomma, toi koodihan ei tee juuri mitään.

Alla Tonin esimerkkikoodi:

var morse = (function () {

 var morseTree = {
   'dit': {
     'value': 'E'
   , 'dit': {
       'value': 'I'
     , 'dit': {'value': 'S', 'dit': {'value': 'H'}, 'dah': {'value': 'V'}}
     , 'dah': {'value': 'U', 'dit': {'value': 'F'}}
     }
   , 'dah': {
       'value': 'A'
        ...
     }
   }
 , 'dah': {
        ...   
    }
 }

 var handle = morseTree

 return function morse(signal) {
   if (signal === PAUSE) {
     var letter = handle.value
     handle = morseTree
     return letter
   } else {
     handle = handle[signal]
     return
   }
 }

})();

Kuten Tonin esimerkkivastauksesta (ja tältä Wikipedia-sivulta) näkyy, morsekoodissa kirjainvaihtoehdot ovat järjestettävissä puurakenteeseen. Varsinaisen purkukoodin tehtäväksi jää tällöin ainoastaan kulkea puun solmuja pitkin sisääntulevan signaalin mukaisesti. DIT-signaalilla valitaan puun seuraava vasemmanpuoleinen solmu, ja DAH-signaalilla vastaavasti oikeanpuoleinen. Tonin esimerkkivastauksessa on hyvin kiteytetty juuri se, mitä tehtävän vastaukselta tällä kertaa haettiin: se on elegantti ja luettava ja vastaa esitettyyn ongelmaan.

Lisää esimerkkivastauksia

Toinen tämän ratkaisun variantti on enkoodata morsekoodin diktonominen puu yhtenä merkkijonona (“ etianmsurwdkgohvf” jne). Sisääntulevan signaalin mukaan liikutetaan pointteria. Jokaisella signaalilla pointterin arvo kerrotaan kahdella, jonka jälkeen DIT-signaalilla pointterin arvoon lisätään yksi, ja DAH signaalilla kaksi merkkiä. PAUSE-signaalilla luetaan merkkijonosta pointterin arvoa vastaava kirjain, ja resetoidaan pointteri takaisin nollaan. Tämä ratkaisu on hyvä esimerkki siitä, miten tärkeää luettavuus on koodin ymmärtämisessä. Vaikka varsinainen ratkaisun lähdekoodi onkin huomattavasti lyhyempi kuin aiempi esimerkkiratkaisu, sen ymmärtäminen on myös huomattavasti vaikeampaa.

Esimerkki merkkijonon käyttämisestä hakupuuna:

merkkijono: " etianmsurwdkgohvf...

signaali: .-
pointterin arvo: ((0 * 2 + 1) * 2 + 2) = 4 = A

signaali: ...
pointterin arvo: (((0 * 2 + 1) * 2 + 1) * 2 + 1) = 7 = S

Varsinainen tämän postauksen otsikon mukainen pihvi kiteytyykin kolmanteen tyypilliseen vastaukseen, joita tämänkertaiseen Fast Track -tehtävään saimme. Ratkaisun ydin itsessään noudattaa perusajatusta morseaakkosista puurakenteessa, mutta menee merkkijonopuun käsittelyssä toiseen äärilaitaan.

Koska Javascript-kielessä itsessään ei ole puurakenteen käsittelyyn tarkoitettuja funktioita, osalla hakijoista suurin osa vastauksen lähdekoodia keskittyi implementoimaan joko binääripuun tai trie-rakenteen, useimmiten käyttäen Javascriptin prototyyppipohjaista perintää. Tämän jälkeen morsekoodi purettiin puun noodeille, ja loppuosa ratkaisusta noudatteli ylläolevia esimerkkejä. Tällaisen yleiskäyttöisen puurakenteen löytäminen ja generalisointi voi tietenkin olla hyvä idea, mutta valintaa tehtäessä on mielestäni varottava liiallista abstraktiota. Aivan kuten avaruuskynäesimerkki osoittaa, toisinaan yksinkertaiset ratkaisut kestävät parhaiten aikaa.

Lopuksi

Kiitos kaikille vastauksen lähettäneille. Otamme mielellämme jatkossakin vastaan koodia, vaikket olisikaan juuri nyt vaihtamassa työpaikkaa. Mielelläni haluaisin myös kuulla teiltä palautetta tästä tehtävästä! Oliko tämän kertainen fast track -tehtävämme vaikeustasoltaan liian helppo, sopiva, vai turhan hankala?

Kuva: mrbill (CC-BY)

Never miss a post