Datatähti 2012 -kilpailu alkaa tänään:
http://users.utu.fi/knuutila/datatahti/
Kilpailuun voivat osallistua peruskoulun ja lukion oppilaat. Alkukilpailu on 18.10.–1.11.2011, ja sen perusteella valitaan osallistujat loppukilpailuun, joka pidetään Helsingin yliopistolla helmikuun alussa.
Datatähteen kannattaa ehdottomasti osallistua, jos algoritmien ohjelmointi kiinnostaa. Tervetuloa mukaan!
Mietin ensimmäisessä tehtävässä ohjelmointikielitarjonnan ja nopeustavoitteen huomioiden, että saakohan esim. C:ssä käyttää inline assemblyä? Vai pystyykö jossain kielistä laskemaan suoraan kaksi 64-bittistä lukua yhteen ja tarkistamaan yli menevän bitin prosessorin carry-flagista?
Olisi mukava osallistua, mutta kun ei saa enää. Olisi ihan kiva kun tulisi myös yliopisto-opiskelijoille samanlainen kilpailu.
Tämän vuoden tehtävät 1 ja 3 näyttävät pikaisesti katsottuna sellaisilta, että parhaiten niissä pärjää etsimällä netistä valmiin algoritmin.
Saa nähdä, jaksanko osallistua, tehtävät näyttävät sellaisilta, ettei niistä saa helpolla pisteitä, eikä minulla ole nykyään kovin paljoa koodausaikaa.
Saakos tehtävien ratkaisussa käyttää putkan koodivinkkejä?
Toi isojen kokonaislukujen kirjasto on sinänsä outo, että lopussa voi tehdä oletuksen pituudesta mutta tirat on tehtävä ilmeisesti ilman tätä oletusta. Saakohan tuossa tehtävässä olettaa, että luvut on mahduttava keskusmuistiin vai pitääkö tarkastaa, onko koneeseen kytketty esim. muistitikkuja, joille lukujen bittejä voi tunkea jos muualle ei mahdu?
tirat on ilmeisesti tietorakenteet? Tottakai oletukena on se, että muuttujat/luokat säilötään muistissa kun niitä käytetään. Se on sitten ympäristön huoli sivuttaa jos ei mahdu fyysiseen muistiin kerralla. Toisaalta hyvä toteutus ei varaa aina esimerkiksi 10 megaa muistia jos käsiteltävä luku on 200 merkkiä pitkä.
Tietenkin on erityistilanteita, joissa halutaan käsitellä niin isoja lukuja, että ne on järkevämpää jo ohjelmassa tallentaa levylle ja huomioida levyoperaatioiden hitaus sovellusta kehitettäessä. Tästä kuitenkin olisi varmasti erillinen maininta.
Uskoisin, että ajatuksena on ollut että ohjelma käyttäisi pelkästään keskusmuistia, kun ainoastaan se on ilmoitettu (max 1. Gt).
En näe että tuossa olisi mitään ongelmaa, kun kuitenkaan lukuja ei tarvita kuin muutama kerrallaan muistissa ja maksimipituisia lukuja mahtuu yli 20 kerralla muistiin.
Itse käyttäisin dynaamisia taulukoita. Kaikissa operaatioissa lopputuloksen pituus on mahdollista helposti päätellä 1-2 yksikön tarkkuudella.
Grez kirjoitti:
Itse käyttäisin dynaamisia taulukoita. Kaikissa operaatioissa lopputuloksen pituus on mahdollista helposti päätellä 1-2 yksikön tarkkuudella.
Merkkijonojen ja desimaaliluvuilla laskennan puolelle taitaisi oma toteutukseni kallistua...
Jalmari91 kirjoitti:
Olisi ihan kiva kun tulisi myös yliopisto-opiskelijoille samanlainen kilpailu.
Yliopiston opiskelijoille on ainakin NCPC ja sen jatkokilpailut:
Hennkka kirjoitti:
Saakos tehtävien ratkaisussa käyttää putkan koodivinkkejä?
Koodin pitää olla itse tehtyä, mutta mallia saa toki ottaa.
-tossu-: Jos ei ole muita esteitä kuin jaksaminen, kannattaa ehdottomasti osallistua. Loppukilpailuun on ainakin viime vuosina päässyt todella helposti.
Kuvittelenko vain, vai oliko 18. päivä vielä esseetehtävänä viimevuoden tehtävä liittyen kännykän käyttöjärjestelmiin?
Se oli virhe, joka on nyt jo korjattu.
Kiusaus olisi suuri tehdä ensimmäinen tehtävä assemblyllä, sillä x86-käskykanta tukee mielivaltaisen suurilla kokonaisluvuilla laskemista sen verran hyvin.
Working with Big Numbers Using x86 Instructions
Grez kirjoitti:
Mietin ensimmäisessä tehtävässä ohjelmointikielitarjonnan ja nopeustavoitteen huomioiden, että saakohan esim. C:ssä käyttää inline assemblyä? Vai pystyykö jossain kielistä laskemaan suoraan kaksi 64-bittistä lukua yhteen ja tarkistamaan yli menevän bitin prosessorin carry-flagista?
C:ssä yhteenlaskun carry-flagin pystyy tarkistamaan purkasti näin:
tmp = a; a += b; carry = (a < tmp) ? 1 : 0;
Tiedä vaikka jotkut kääntäjät osaisivat optimoida tuon pelkäksi carryn tarkistukseksi, mutta en olisi niin optimistinen. Olen tällä periaatteella toteuttanut C:llä alkeellisen bigint-kirjaston, joka ei tue kertolaskua. x86:n MUL käsky tallentaa kertolaskussa ylimenevän osan EDX-rekisteriin, mutta siihen ei taida päästä C:llä käsiksi. Tietysti voi käyttää riittävän suuria tietotyyppejä, jolloin kertolasku ei vuoda yli.
Laskeskelin että noin 5 000 000 tavua riittäisi tallentamaan 10^7 merkkiä pitkiä kymmenjärjestelmän lukuja. Tilavaativuudeltaan noin puolet parempi kuin "triviaali" merkkijonoratkaisu. Yhteenlasku ja kertolasku veisivät aikaa O(n/M) missä n on taulukon pituus ja M on tietokoneen sanan pituus. Tehtävän kannalta ongelmaksi muodostuisi isojen lukujen muuttaminen oikeaan muotoon, enkä itse ainakaan keksi siihen helppoa ja tehokasta tapaa.
Eikös monet prossut muuten tue BCD-laskentaa (binary coded decimal) joten jos x86:kin tukee, niin tuollahan saisi erittäin kätevästi tehtyä mikäli jokin sallittu kieli tukisi niitä. Näin tulostminen ja lukeminen olisi huiman nopeaa verrattuna siihen että käytettäisiin normilukuja.
Ja mitä tuohon carryyn tuleen, niin mielestäni prossu myöskin osaa laskea huomioiden carryn, jolloin yhteen- ja vähennyslakussa voi vaan käydä koko sarjan putkeen yhdessä loopissa. Eli tokihan purkkailla voi, mutta jos kääntäjä ei tosiaan purkkaa "poista" niin suoritusnopeus on monta kertaa hitaampi.
Grez kirjoitti:
Eikös monet prossut muuten tue BCD-laskentaa (binary coded decimal) joten jos x86:kin tukee, niin tuollahan saisi erittäin kätevästi tehtyä mikäli jokin sallittu kieli tukisi niitä. Näin tulostminen ja lukeminen olisi huiman nopeaa verrattuna siihen että käytettäisiin normilukuja.
Kyllähän x86 on noita tukenut kivikaudelta asti. Nykyään taitaa x86:lla olla helpointa hoitaa BCD-aritmetiikka fpu:lla, mikä hoitaa homman 18-numeron tarkkuudella.
Käyttämäni PL/I-kääntäjä laskee fixed decimal laskut käyttäen fpu:ta. Oma testinä tehty isojen lukujen yhteenlasku toteutukseni laskee merkkijonoilla ja yhden loopin avulla käsitellen aina 17 numeroa + carryn jokaisella silmukan pyörähdys kerralla.
PL/I hoitaa muunnokset merkkijonojen ja lukujen välillä automaattisesti, joten tuohon tarvitaan vain jokunen rivi koodia.
Laitan tuon esille, kunhan pääsen kotiin asti. Halukkaat voivat sitten verrata oman koodinsa nopeutta PL/I-kääntäjän tuottamaan koodiin.
-tossu- kirjoitti:
Tämän vuoden tehtävät 1 ja 3 näyttävät pikaisesti katsottuna sellaisilta, että parhaiten niissä pärjää etsimällä netistä valmiin algoritmin.
Eikö kaikissa ohjelmointikilpailuissa pärjää parhaiten kopioimalla muiden töitä, jos ei itse osaa ohjelmoida? Jos taas osaa, niin 1 ja 3 tehtävät ratkaisee täydet pisteet saaden parissa päivässä.
-tossu- kirjoitti:
Saa nähdä, jaksanko osallistua, tehtävät näyttävät sellaisilta, ettei niistä saa helpolla pisteitä, eikä minulla ole nykyään kovin paljoa koodausaikaa.
Sama vastaus tähän: pisteitä saa hyvin jos on hyvä.
Pete2 kirjoitti:
Eikö kaikissa ohjelmointikilpailuissa pärjää parhaiten kopioimalla muiden töitä, jos ei itse osaa ohjelmoida? Jos taas osaa, niin 1 ja 3 tehtävät ratkaisee täydet pisteet saaden parissa päivässä.
Tehtävät olisi myös voitu laatia siten, ettei niihin löydä ainakaan kovin helpolla valmiita ratkaisuja. Isojen lukujen käsittelyyn on vaikka kuinka monta toteutusta, jonka kopioimalla saanee täydet pisteet. Kungigattarien asettelukin on melko tunnettu ongelma, johon löytynee valmis algoritmi.
-tossu- kirjoitti:
Pete2 kirjoitti:
Eikö kaikissa ohjelmointikilpailuissa pärjää parhaiten kopioimalla muiden töitä, jos ei itse osaa ohjelmoida? Jos taas osaa, niin 1 ja 3 tehtävät ratkaisee täydet pisteet saaden parissa päivässä.
Tehtävät olisi myös voitu laatia siten, ettei niihin löydä ainakaan kovin helpolla valmiita ratkaisuja. Isojen lukujen käsittelyyn on vaikka kuinka monta toteutusta, jonka kopioimalla saanee täydet pisteet. Kungigattarien asettelukin on melko tunnettu ongelma, johon löytynee valmis algoritmi.
Eihän tuosta ensimmäisestä tehtävästä voi saada täysiä pisteitä muut kuin paras ;D
Jalmari91 kirjoitti:
Eihän tuosta ensimmäisestä tehtävästä voi saada täysiä pisteitä muut kuin paras ;D
Ei näköjään voikaan, mutta valmis BigInt-kirjasto, jota on hyvät koodarit optimoineet ajan kanssa, lienee silti nopeampi kuin kenenkään osallistujan toteutus.
Jalmari91 kirjoitti:
Eihän tuosta ensimmäisestä tehtävästä voi saada täysiä pisteitä muut kuin paras ;D
Ennemminkin muut kuin parhaat.
Datatahti Ohjeet kirjoitti:
Laskennan nopeudesta saa pisteitä siten, että nopein toimitettu kilpailuvastaus saa 40p, hitain 1p ja muut vastaukset nopeutensa mukaan tältä väliltä.
Voidaan todeta, että väli on suljettu, koska muuten pisteytys ei olisi yksiselitteisesti määritelty kahden kilpailijan lähettäessä yhtä nopeat ohjelmat. On siis tietenkin mahdollista, että saman algoritmin kopioineet saavat molemmat täydet pisteet ( sikäli kun heitä ei diskata ).
jalski kirjoitti:
Laitan tuon esille, kunhan pääsen kotiin asti. Halukkaat voivat sitten verrata oman koodinsa nopeutta PL/I-kääntäjän tuottamaan koodiin.
Tuossa olisi PL/I toteutus isojen kokonaislukujen yhteenlaskua varten. Ottaa parametrikseen tekstitiedoston, jossa pitäisi olla pari numeroista koostuvaa riviä päätettynä rivinvaihdolla. Nuo lasketaan yhteen ja tulos kirjoitetaan ruudulle.
/**********************************************************************/
/* Takes input file as a parameter and reads two records from it. */
/* These two records containing big integers are then added together */
/* and the result is displayed. */
/**********************************************************************/
testi: proc(parm) options(main);
dcl parm char(*) varying;
dcl infile file record input env(TEXT);
dcl (l1, l2) fixed dec(17);
dcl carry fixed dec(1) initial(0);
dcl sum pic '999999999999999999';
dcl (luku1, luku2) char(32000) varying;
dcl zeros char(17) initial((17) '0');
dcl result char(32000) varying;
dcl (i, j, k) fixed bin(31);
dcl (substr, length, verify) builtin;
on undefinedfile(infile) goto no_inputfile;
on endfile(infile) goto eof;
on record(infile) goto conv_err;
open file(infile) title(parm);
read file(infile) into(luku1);
if verify(luku1, '1234567890') > 0 then signal record(infile);
read file(infile) into(luku2);
if verify(luku2, '1234567890') > 0 then signal record(infile);
j = length(luku1);
k = length(luku2);
if j > k then do;
i = mod(j, 17);
if i ^= 0 then luku1 = substr(zeros, 1, 17 - i) || luku1;
j = length(luku1);
luku2 = substr(zeros, 1, j - k) || luku2;
end;
else do;
i = mod(k, 17);
if i ^= 0 then luku2 = substr(zeros, 1, 17 - i) || luku2;
k = length(luku2);
luku1 = substr(zeros, 1, k - j) || luku1;
end;
do i = length(luku1) to 1 by -17;
l1 = substr(luku1, i - 16, 17);
l2 = substr(luku2, i - 16, 17);
sum = l1 + l2 + carry;
carry = substr(sum, 1, 1);
result = substr(sum, 2, 17) || result;
end;
result = substr(sum, 1, 1) || result;
result = substr(result, verify(result, '0'), length(result) - verify(result, '0') + 1);
put skip(2) list(result);
goto eof;
no_inputfile:
put skip list ('No input file given....');
stop;
conv_err:
put skip list ('Records should be integer numbers and terminated with CRLF on OS/2 or LF on Linux.');
eof:
close file(infile);
end testi;Pete2 kirjoitti:
Eikö kaikissa ohjelmointikilpailuissa pärjää parhaiten kopioimalla muiden töitä, jos ei itse osaa ohjelmoida?
Ainakaan Datatähden loppukilpailussa ja lukiotason kansainvälisissä kilpailuissa ei pärjää kopioimalla, koska nettiä ei saa käyttää. Tässä alkukilpailussa kyse ei välttämättä ole siitä, osaisiko tehtävät ratkaista itse, vaan siitä että haluaako käyttää aikaa pyörän keksimiseen. Hyvillä ohjelmoijilla saattaa olla parempaakin tekemistä.
Toisaalta kilpailuissa joutuu kuitenkin toteuttamaan samoja tunnettuja algoritmejä yhä uudestaan ja uudestaan, joten itsenäinen ratkaiseminen on hyvää harjoitusta.
jlaire kirjoitti:
Ainakaan Datatähden loppukilpailussa ja lukiotason kansainvälisissä kilpailuissa ei pärjää kopioimalla, koska nettiä ei saa käyttää.
Mitäs materiaalia siellä muuten on käytettävissä? Itse käyttämissä kehitystyökaluissa kirjastojen dokumentaatiokin on netissä, joten mitä materiaalia siellä sitten mahtaa koneella olla. Toisaaltahan nuo tehtävät on usein sellaisia, että ihan perustoimintoja kummallisemmille jutuille ei ole tarvetta.
Kilpailukoneille on ladattu cppreference.com tai joku vastaava sivusto, jota saa selata lokaalisti. Kerran se oli SGI:n STL-opas. Käyttiksenä oli aina Linux ja käytin monesti man-pageja kun tarvitsin tietoa C:n standardikirjastoista. Jonkin sortin C++-opas pdf:nä löytyi ainakin pari kertaa työpöydältä, mutta ei sellaisen lukemiseen ole aikaa.
Pascalille jotain vastaavaa.
jlaire kirjoitti:
Tässä alkukilpailussa kyse ei välttämättä ole siitä, osaisiko tehtävät ratkaista itse, vaan siitä että haluaako käyttää aikaa pyörän keksimiseen.
Viimeaikaisen loppukilpailutason perusteella epäilen kyllä aivan muuta. Tosin kai huonompikin koodari saa sentään kahdessa viikossa jotain aikaan.
Olisi jännä tietää, minkä verran pisteitä BigInt-tehtävästä saisi pelkällä long-tyypillä (tai long double -tyypillä).
Lukemisen ja tulostamisen voi Grezin esittämässä ratkaisussa saada varsin nopeaksi myös tavalla, joka ei edellytä BCD-operaatioita: voi käyttää 32-bittisten arvojen sijaan 9-numeroisia arvoja. Tuskinpa ohjelman suoritusaika kuitenkaan jää tulostuksesta kiinni muillakaan järkevillä toteutustavoilla.
Grez kirjoitti:
Mitäs materiaalia siellä muuten on käytettävissä?
Yleensä tehtävät ovat luonteeltaan sellaisia, ettei kehitysympäristön dokumentaatiolla ole paljonkaan väliä. Enintään joutuu C++:n kanssa vähän arpomaan, oliko tietyssä STL-luokassa nyt insert, push vai push_back. Jos STL:n sisältö ei ole ennestään tuttu, tuskin sitä ehtii kilpailutilanteessa ruveta opettelemaan.
Metabolix kirjoitti:
Lukemisen ja tulostamisen voi Grezin esittämässä ratkaisussa saada varsin nopeaksi myös tavalla, joka ei edellytä BCD-operaatioita: voi käyttää 32-bittisten arvojen sijaan 9-numeroisia arvoja. Tuskinpa ohjelman suoritusaika kuitenkaan jää tulostuksesta kiinni muillakaan järkevillä toteutustavoilla.
Juu, pohdintani koskikin ihan puhtaasti sitä mahdollisuutta, että olisi voinut tehdä esim. yhteenlaskuloopin konekielellä, jolloin olisi voinut vaan loopissa ajaa ADD-komentoa ilman minkäänlaista tutkimista tai branchaysta. Tietenkin jos kirjoittaa esim. C:llä, jossa Carry-flagia ja muita rekistereitä ei voi hyödyntää, niin silloin ei ole järkevää miettiä BCD:tä.
Grez kirjoitti:
Enintään joutuu C++:n kanssa vähän arpomaan, oliko tietyssä STL-luokassa nyt insert, push vai push_back. Jos STL:n sisältö ei ole ennestään tuttu, tuskin sitä ehtii kilpailutilanteessa ruveta opettelemaan.
No itse en ole hirveästi ulkoa opetellut pitkään aikaan mitään. Sielläkin varmaan on käytössä IDE:t, jotka tarjoilee oikeat kirjotusmuodot ja eri parametrivaihtoehdot. Mutta jos näin ei olisi niin sitten voisi kyllä silloin tällöin kaivata dokkareita. Joskus joissain huonoissa systeemeissä on myös sellaisia parametreja, joista ei voi olla varma halutaanko siinä vaikka aika sekunteina vai millisekunteina, niin sekin olisi hyvä pystyä tarkistamaan. Olipas huono esimerkki.
Ja tosiaan kuten molemmat totesimmekin, tehtävien luonteesta johtuen tuskin hirveän monimutkaista kirjaston käyttöä tarvitaan.
Olisin halunnut tänä vuonna päästä osallistumaan Datatähteen, mutta taaskaan en ollut vielä jaksanut opetella ohjelmointia niin hyvin että edes viitsisin osallistua. :< Pitänee katsoa ensi vuonna uudestaan...
Aihe on jo aika vanha, joten et voi enää vastata siihen.