Technology

Fast track -rekryssä painotettiin funktionaalisuutta

November 27, 2013

Read time 6 min

Julkaisimme jokin aikaa sitten Fast track -ohjelmointiongelman ja saimme yli 150 vastausta. Tehtävä oli Project Eulerin ongelma numero 8. Tarkoitus oli löytää suurin viiden peräkkäisen numeron summa 1000-merkkiä pitkästä merkkijonosta.

Valitsimme JavaScriptin, koska sitä osaa todella moni ja se on myös helppo ajaa suoraan selaimessa. Tämä mahdollistaa nopean palautteen omasta ratkaisusta. JavaScript on myös siitä hyvä, että sillä voidaan toteuttaa ratkaisu monella eri tyylillä: imperatiivisesti, funktionaalisesti tai vaikka code-golfaamalla. Oletus oli, että tämä saattaisi jakaa ratkaisujen kenttää laajemmin.

Millainen oli mielestämme hyvä vastaus?

Sanottakoon alkuun, että oikeaa vastausta ei tämänlaiseen tehtävään ole, koska vaatimuksia ei sen enempää asetettu kuin että kirjoita “elegantti” ratkaisu. Emme esimerkiksi antaneet mitään suorituskykyvaatimuksia koodille. Tuomaristolla oli kuitenkin joitain kriteereitä mielessä, joilla vastauksia arvioitiin.

Ominaisuus, jota arvostimme koodissa yli muiden, oli tässä tehtävässä funktionaalisuus. Tämä siksi, että funktionaalinen ohjelmointi sopii erityisen hyvin listojen ja ylipäätään tietorakenteiden transformointiin. Hyvä funktionaalinen vastaus kertoo selkeästi sen mitä koodissa tehdään, ei miten se tehdään. Se koostuu irrallisista yleiskäyttöisistä funktioista, joilla ei varsinaisesti ole mitään tekemistä juuri tämän tehtävän kanssa.

Ratkaisua tämänlaiseen tehtävään on hyvä siis miettiä jakamalla se vaiheisiin. Perus funktionaalinen ratkaisu voisi mennä esimerkiksi näin:

  1. luodaan merkkijonosta lista numeroita
  2. jaetaan lista viiden numeron listoihin
  3. lasketaan tulo jokaisen viiden numeron listasta
  4. valitaan listasta isoin numero.

Saimme jonkin verran vastauksia, joissa numeroiden osittaminen viiden numeron pituisiin taulukoihin oli toteutettu underscoren ’map’-funktiolla, hakemalla osia alkuperäisestä taulukosta indeksejä käyttäen:

 _.map(xs, function (value, i, arr) {
   // pilkotaan listaa tyyliin arr.slice(i, i + 5)
 })

Tällä päästään eroon for-loopin syntaxista, mutta se muistuttaa silti enemmän imperatiivista for-looppia kuinmap funktion oikeaa funktionaalista käyttötarkoitusta. Taulukon alkioiden käsittely indeksejä käyttäen onvirhealtista ja paljastaa implementaatioyksityiskohtia, se ei ole kovin deklaratiivista koodia. map-funktiolle annetun funktion tarkoitus on käyttää sille annettua listan yksittäistä elementtiä. Yllä olevassa koodissa arvoa ei käytetä ollenkaan.

Moni oli näin tehnyt tietysti siksi, että underscoren mapkuten myös Array.prototype.map ottaa huomioon rajapinnassaan, että JavaScriptin ainoa listoihin käytettävä tietorakenne on taulukko eikä linkitetty lista. Näin ei olefunktionaalisissa kielissä.

Luonnollinen tapa loopata listan yli funktionaalisella tyylillä on rekursio:

function partition(xs) {
   if (xs.length < 5) return []
   else return [_.take(xs, 5)].concat(partition(_.rest(xs)))
 }

Rekursiota oli myös käytetty hyvin monessa vastauksessa.

Funktionaalinen tyyli sopii hyvin tämän tehtävän ratkaisuun, mutta tehtävän voi toteuttaa monella eri tyylillä. Saimme paljon vastauksia, jotka eivät olleet funktionaalisesti toteutettuja, mutta jotka olivat tuomariston mielestä kiitettäviä vastauksia.

Suorituskyvyn optimointi

Saimme jonkin verran vastauksia, joissa algoritmin suorituskykyyn oli kiinnitetty paljon huomiota. Monet lähettivät meille kaksi vastausta: toinen lyhyempi ja toinen suorituskyvyltään enemmän optimoitu versio. Tämä oli hyvin positiivinen yllätys. Oli mielenkiintoista nähdä, kuinka paljon optimoitu ratkaisu usein pidentää vastausta ja samalla myös tekee algoritmin ymmärtämisen melkoisesti vaikeammaksi. Kielivalinta osui kohdalleen myös tässä mielessä, sillä JavaScript mahdollistaa hyvin erilaisia vastauksia.

Hyvä funktionaalinen vastaus JavaScriptissä on hyvinkin todennäköisesti melko huono suorituskyvyltään. Tämä johtuu siitä, että objekteja luodaan paljon, ja listan yli saatetaan kävellä moneen kertaan. Asiaa ei myöskään auta se, että JavaScriptissa ei ole häntäkutsuja, vielä.

Funktionaalisissa kielissä listan käveleminen useaan kertaan voidaan monissa tapauksissa välttää laiskuudella. Laiska algoritmi on myös mahdollista toteuttaa JavaScriptillä, mutta se vaatii jonkin verran koodia, ja on varmasti hitaampi kuin yksikään saamamme vastaus. Funktionaalisessa ratkaisussa on myös potentiaalia ongelman rinnakkaistamiselle, tosin ei JavaScriptillä: on kuitenkin hyvä pitää tämäkin funktionaalisen ohjelmoinnin ominaisuus mielessä.

Deklaratiivisesti kirjoitetun ratkaisun hyvä puoli on myös se, ettei se välttämättä ota kantaa algoritmin sisäiseen toimintaan. Tällaisen koodin sisäistä toteutusta on helpompi muuttaa kuin koodin, joka on toteutettu imperatiivisella tyylillä.

Mielestämme oikeissa projekteisssa ei kuitenkaan kannata kovin paljoa kiinnittää huomiota algoritmin nopeuteen ennen kuin siitä seuraa ongelmia ja pullonkaulat on pystytty tunnistamaan mittaamalla.

Muutama esimerkkivastaus

Vastaustyyppi, jota saimme ehkä kaikkein eniten, oli suunnilleen seuraavanlainen:

function (input) {
  function product(xs) {
    return _.reduce(xs, function (x, y) { return x * y })
  }

   return _.max(_.map(input, function(value, i, list) {
     if (i > (list.length - 5)) return 0
     else return product(list.slice(i, i + 5))
   }))
 }

Huomionarvoisia tässä ratkaisussa ovat seuraavat asiat:

  • Vastaus on lyhyt ja melko selkeä.
  • map käyttää indeksejä ja koko listaa sisällään, mikä ei ole kovin funktionaalinen tapa tehdä asioita.
  • Tulot lasketaan suoraan mapin sisällä. Tällä vältetään ylimääräinen looppi, mutta parempi olisi ehkä pilkkoa taulukko ensin viidenmittaisiin osiin, ja vasta sen jälkeen laskea tulot.
  • Merkkijonon alkioita ei muuteta numeroiksi, vaan annetaan JavaScriptin muuttaa merkkijonot numeroiksi tulon yhteydessä: js> '5' * '2' => 10.

Funktionaalista sydäntä hieman enemmän lämmittävä vastaus olisi seuraavanlainen:

function (input) {
   function product(xs) {
     return _.reduce(xs, function (x, y) { return x * y })
   }

   function partition(n, step, xs) {
     if (xs.length < n) return []
     else return [_.take(xs, n)].concat(partition(n, step, _.drop(xs, step)))
   }

   var numbers = input.split('').map(function (c) { return parseInt(c) })
   return _.max(partition(5, 1, numbers).map(product))
 }

Huomionarvoista:

  • Merkkijono muutetaan eksplisiittisesti listaksi numeroita.
  • Lista partitioidaan ensin viiden numeron mittaisiin osiin. Joudumme itse toteuttamaan tämän partition -funktion, koska JavaScriptistä sitä ei löydy. Toteuttamamme partition on kuitenkin paljon yleiskäyttöisempi kuin mihin sitä tässä käytämme. Tässä on funktionaalisen ohjelmoinnin ydin: voimme yhdistellä pieniä yleiskäyttöisiä funktioita ja näin luoda jotain suurempaa kuin niiden summa.

Sitten jotain hieman muuta. Reaktorilainen Atte Kojotoimitti meille seuraavanlaisen ratkaisun:

function (input) {
   var a = [0, 0, 0, 0, 0]
   var l = input.length
   var max = 0

   for (var i = 0; i < l; ++i) {
     a[i % 5] = input[i] * 1

     var p5 = a[0] * a[1] * a[2] * a[3] * a[4]
     max = p5 > max ? p5 : max
   }
   return max
 }

Atte kertoo että ensimmäinen versio oli toteutettu J:llä:

>./ 5 */ "."0

Tästä Atte lähti toteuttamaan samanlaista sliding-window algoritmia JS:llä miettien “What would Brian Kernighan do?”

Underscore.js ja tehtävänanto

Tehtävänannossa kerrottiin, että underscore.js on käytettävissä. Sitä ei kuitenkaan ollut pakko käyttää, eikä sitä oikeastaan tarvittukaan: nykyselaimista kun löytyy mapja reduce. Underscoren _.max funktion voi myös korvata kutsumalla Math.max.apply. Sillä ei kuitenkaan ollut merkitystä ratkaisua arvioitaessa, käyttikö underscorea tai oliko ratkaisu selainyhteensopiva.

Testiohjelmamme oli sikäli hieman huono, että se hyväksyi virheellisen algoritmin. Jos algoritmi partitioi numerot osiin niin, että loppuun tulee alle viiden numeron joukkoja, hyväksyy testisovellus ratkaisun oikeana. Tämä johtuu siitä, että viimeisen neljän numeron tulo ei ole suurempi kuin suurin muualta löytyneen viiden peräkkäisen numeron tulo. Meidän olisi pitänyt siis laittaa testisyötteen viimeisiksi numeroiksi 09999.

Tehtävänannon voi myös tulkita hieman eri tavalla.

Lopuksi

Suurkiitos kaikille ratkaisun lähettäneille, myös niille ketkä eivät töitä hakeneetkaan, vaan halusivat jakaa vastauksensa muuten vain kanssamme. Toivottavasti kaikki oppivat jotain uutta tästäkin – minä ainakin opin.

Mikä olisi hyvä ratkaisu sinun mielestäsi?

Never miss a post