Technology

Fast track, osa kolme – koodaa Out Run lempikielelläsi

May 19, 2014

Read time 2 min

Järjestyksessä kolmatta fast track -tehtävää varten muutimme jälleen hieman tehtävänantoa. Edelliset kaksi tehtävää toteutettiin selainpohjaisella lomakkeella, ja niiden ratkaisuissa käytettiin Javascriptiä. Palasimme ensimmäisestä fast trackista tutun Project Eulerin pariin, mutta valitsimme edellistä hieman haastavamman ongelman: tällä kertaa vuorossa oli tehtävä numero 67. Tehtävän sai nyt ratkaista monella eri ohjelmointikielellä. Selvästi suosituin vastauskieli oli Javascript, mutta saimme vastauksia myös Scalalla, Javalla, Clojurella, Haskellilla sekä Rubylla.

Yksi tehtävän suurimpia haasteita on ratkaista, kuinka pyramidin muodostamia reittiavaruuksia käsitellään tehokkaasti. Naiivi algoritmi käy vuorotellen läpi jokaikisen mahdollisen polun numerosta toiseen, suurinta mahdollista yhteissummaa etsien. Tällainen algoritmi toimii muutamalla kymmenellä rivillä nopeasti. Jokainen rivi kuitenkin tuplaa tarvittavien laskutoimitusten määrän. Niinpä algoritmi kaatuu omaan tehottomuuteensa, kun läpikäytävien polkujen määrä lisääntyy eksponentiaalisesti rivimäärän kasvaessa.

Elegantimpi tapa ratkaista tämä tehtävä on kääntää numeropyramidi ylösalaisin ja aloittaa ensimmäisen rivin sijaan pyramidin pohjalta. Jokaista numeroa vasten verrataan kahta sen alapuolella olevaa numeroa, ja lisätään niistä suurempi valittuun numeroon. Tätä summausta jatketaan kumulatiivisesti rivi kerrallaan ylöspäin edeten, kunnes päästään pyramidin huipulle asti, ja jäljellä on vain yksi luku. Tällä tekniikalla koko pyramidi käydään ainoastaan kerran läpi. Allaoleva kuva havainnollistaa tätä ratkaisutekniikkaa.

Screenshot 2014-05-16 16.25.14

Malliratkaisu

Olemme aiemminkin tässä blogissa esitelleet Euler-tehtävien elegantteja funktionaalisia ratkaisuja, eikä tämänkään tehtävän funktionaalinen malliratkaisu ole poikkeus. On oikeastaan yllättävää, kuinka samalta kahdella hyvin erilaisella kielellä toteutetut ratkaisut voivat näyttää:

Scala


println(
  scala.io.Source
    .fromFile("triangle.txt")
    .getLines
    .toList
    .tail
    .map(_.split(" ").map(_.toInt).toList)
    .foldRight(List[Int]()) { (list:List[Int], memo:List[Int]) => 
      list
        .zip(memo.sliding(2).map(_.max).toList.padTo(list.size, 0))
        .map((it:(Int, Int)) => it._1 + it._2)
    }
    .head)

Coffeescript


zip = (lists...) -> [0...lists[0].length].map (i) -> lists.map (it) -> it[i]
partition = (list) -> zip list[0..-2], list[1..]
max = (nums) -> Math.max.apply(Math, nums)
sum = (nums) -> nums.reduce ((a, b) -> a + b ), 0

console.log(
  require('fs')
    .readFileSync('triangle.txt')
    .toString()
    .split('n')
    .slice(1)
    .map((line) -> line.split(' ').map (num) -> parseInt(num, 10))
    .reduceRight((memo, row) ->
      if memo?
        zip(row, partition(memo).map(max)).map(sum)
      else
        row
    ).pop())

Jätimme omaan käyttöömme koodatun tehtävän tarkistusautomaatin paikoilleen herokuun – sen lähdekoodit löytyvät GitHubista.

Ratkaisisitko itse ongelman tyylikkäästi ja jollain muulla tavalla? Olisiko kenties jokin muu kieli omiaan tällaisten haasteiden ratkomiseen? Ota kantaa ja kommentoi!

Never miss a post