Putka Open on viiden vuoden välein järjestettävä monivaiheinen kilpailu, jonka aiheena on algoritmien ohjelmointi. Ensimmäinen kilpailu oli vuonna 2015 ja tänä vuonna on jälleen kilpailun aika!
Kilpailun aikataulu on seuraava:
Jokainen kierros alkaa perjantaina klo 18:00 ja päättyy sunnuntaina klo 23:00. Tehtävien ratkaisuja voi lähettää milloin vain näiden aikojen välillä.
Loppukilpailuun kutsutaan 10 osallistujaa, jotka saavat Putka Open -t-paidan. Lisäksi 10 t-paitaa arvotaan niiden kesken, jotka osallistuivat jokaiselle kierrokselle mutta eivät päässeet loppukilpailuun.
Tarkemmat ohjeet julkaistaan kilpailun alkaessa 4.9. Tervetuloa mukaan!
Mahtavaa, että tällaisia kisoja järjestetään. Koodaan yleensä javascriptillä, mutta koitan nyt kahdessa viikossa opetella käyttämään c++:aa tuohon kisaan. Sekun on paljon parempi kisakoodaukseen.
edit. tai siis ennemminkin koodaisin sitten c++:lla sellaisia tehtäviä mihin javascript ei kykene, esim. isojen lukujen käsittely
Onko muuten nodejs käytettävissä kisassa?
Kisan alustana on CSES, ja lämmittelynä voikin tehdä sieltä löytyviä tehtäväsarjoja.
AtskaFin kirjoitti:
Onko muuten nodejs käytettävissä kisassa?
Lopullista päätöstä kielistä ei ole tehty. Teknisesti Node.js on mahdollinen, mutta kisaohjelmoinnissa se ei usein ole tehokkain väline.
No uskoisin kerkeäväni opiskella c++:n syntaksin jotenkin tulevaan kisaan.
Metabolix kirjoitti:
Teknisesti Node.js on mahdollinen, mutta kisaohjelmoinnissa se ei usein ole tehokkain väline.
Olen tehnyt cses:n tehtäväsarjoja jonkun verran ja olen kyllä huomannut NodeJs:n heikkoudet varsinkin raskaammissa rekursiivissa funktioissa. Todella yksinkertaisenkin funktion pelkkä kutsuminen tuntuu vievän hieman aikaa. Rekursiivisessa funktiossa miljoonien kutsujen jälkeen alkaakin nuo pienet hidasteet viemään paljon aikaa. Tuolloin ei auta kuin katkaista rekursiivisen funktion hakuhaaroja mahdollisimman paljon erilaisilla ehdoilla. Kokeilin kerran kirjoittaa saman rekursiivisen funktion c++:lla, joka suoritti saman koodin murto-osassa Noden suoritusajasta.
Toinen hieman ärsyttävä asia cses:ssä on se, että NodeJs skriptin käynnistäminen vie n. 0.43s aikaa. Tuo on melko iso pala annetusta sekunnin ajasta.
AtskaFin kirjoitti:
No uskoisin kerkeäväni opiskella c++:n syntaksin jotenkin tulevaan kisaan.
Onneksi se on melko samanlainen kuin JS. Pitää vain muistaa muuttujien tyypit ja tuntea yleisimmät tietorakenteet (vector, set, map). Nykyään auto-sanan käyttö säästää paljon vaivaa muuttujien tyyppien kirjoittamisessa.
AtskaFin kirjoitti:
Todella yksinkertaisenkin funktion pelkkä kutsuminen tuntuu vievän hieman aikaa.
Funktiokutsut ovat tosiaan usein hitaita erityisesti tulkattavissa kielissä, ja myöskään C++:ssa niitä ei voi olla rajattomasti sisäkkäin. Kannattaa opetella muuttamaan rekursio silmukaksi. Yksinkertainen esimerkki on vaikka Fibonaccin lukujonon laskeminen joko taulukkoon tai muutaman muuttujan avulla. Periaate on hyvin samanlainen myös monimutkaisemmissa rekursioissa.
Yleinen kisaohjelmoinnin väline on myös dynaaminen ohjelmointi. Se tarkoittaa käytännössä, että rekursion tulokset tallennetaan välimuistiin toiston välttämiseksi tai optimaalisemmin ”välimuisti” lasketaan järjestyksessä helpoista tapauksista lähtien (hyvänä esimerkkinä taas Fibonaccin lukujono).
Mutta se spoilereista.
Metabolix kirjoitti:
Funktiokutsut ovat tosiaan usein hitaita erityisesti tulkattavissa kielissä, ja myöskään C++:ssa niitä ei voi olla rajattomasti sisäkkäin. Kannattaa opetella muuttamaan rekursio silmukaksi.
Ja monestihan tuon voi jättää kääntäjän tehtäväksi, esim. rekursiivinen Fibonaccin lukujono 8th ohjelmointikielellä:
: fib \ n -- fib(n)
dup 1 n:> not if
;;
then
n:1- dup n:1- recurse swap recurse n:+ ;Voidaan kirjoittaa vaikka muotoon:
: fib-tail \ n a b -- n
>r \ n a
>r \ n
n:1- \ n=n-1
dup 1 n:> not if
drop
r> \ a
r> \ a b
n:+ \ a+b
;;
then
r> \ n a
r> \ n a b
dup rot \ n b a b
n:+ \ n b a+b
recurse ;
: fib \ n -- fib(n)
dup 1 n:> not if
;;
then
0 1 \ n a b
fib-tail ;Jolloin kääntäjä yleensä optimoi rekursiivisen kutsun pois (tail recursion) ja muuttaa hypyksi...
Aihe on jo aika vanha, joten et voi enää vastata siihen.