Tänään alkaa peruskoulun ja lukion oppilaille tarkoitettu ohjelmointikilpailu Datatähti, jonka ohjeet ja tehtävät ovat sivulla:
http://www.cs.helsinki.fi/u/mnykanen/datatahti/
Tämän vuoden ohjelmointitehtävien aiheena on mayaintiaanien lukujärjestelmä ja pakeneminen robottien vartioimasta labyrintista. Teoriatehtävissä pyydetään määrittelemään käsitteitä ja kysytään tietotekniikkaa mullistaneista laitteista ja käyttökelpoisista ohjelmointikielistä.
Tähän kilpailuun kannattaa osallistua! Myöhemmin pidettävässä valmennuksessa oppii paljon ohjelmoinnista, ja kilpailumatkat ovat mukavia. Kilpailuaika päättyy 15.11.
Ohjelmointitehtävät ihan hauskoja, mutta teoriatehtävät eivät innosta pätkän vertaa. Eli taitaa jäädä osallistumatta.
Reitinhakutehtäviä ei tueta. Ratkaisen vissiin ainakin tuon ensimmäisen ohjelmointitehtävän, ja jos jaksan tehdä sen toisenkin voin osallistuakin. Katsotaan nyt.
Vaikuttaa hieman helpommalta kuin viimevuonna, voisi jopa yrittää osallistua. :P
Itsekkin juuri katselin, eiköhän tuo numerotehtävä ainakin suju, reitinhausta ei kyllä tiedä. Jos koodailut sujuvat riittävän hyvin voisi jotain esseitäkin kirjoitella.
pwc kirjoitti:
Ohjelmointitehtävät ihan hauskoja, mutta teoriatehtävät eivät innosta pätkän vertaa.
Tämä ei ole mikään este osallistumiselle, voit osallistua myös vastaamatta teoriatehtäviin. Suurin osa (n. 50%-70%?) pisteistäkin tulee yleensä juuri ohjelmointitehtävistä.
Tuo maya numero juttu oli melko simppeli.. meni reilusti alle vartti tehdä ohjelma.. tosin loppu nolla ( @ ) jää vielä joskus laittamatta mutta se on helppo fiksata.
Taitaa tosin tulla vielä onglemia noissa isommissa luvuissa (käyttää inttejä)
Ensimmäinen tehtävä vaikuttaa vähän turhankin helpolta, kun on vieläpä käytettävissä sekunti aikaa yhteen lukuun. Reitinhakualgoritmit eivät ole itselleni vielä oikein avautuneet, mutta katsotaan nyt, jos vaikka tänä vuonna tulisi osallistuttua.
Molemmat ohjelmointitehtävät taitavat olla nyt valmiina :) Kiitokset 1. tapauksessa Putkapostille (Palindromiluvut; tuli samalla perehdyttyä noihin lukujärjestelmiin moneltakin kannalta) ja 2. tapauksessa viime vuotiselle PacMan-tehtävälle, jonka sain tuossa pari kuukautta sitten lopultakin ratkottua kunnolla. Harmi, että jälkimmäiseen ei meinaa keksiä järkevää, erityisen haastavaa testisyötettä, jolla voisi tarkistaa aikarajojen pitävyyden...
Viime vuonna pisteytys oli 60% ohjelmoinneista ja 40% esseistä. Lukiosarjassa ei siis kannata jättäytyä ohjelmoinnin varaan, vaikka olisikin varma täydellisyydestä.
msdos464: Älä sano, että oli simppeli, jos ohjelmasi ei ratkaise kaikkea :)
Antti Laaksonen kirjoitti:
Myöhemmin pidettävässä valmennuksessa oppii paljon ohjelmoinnista, ja kilpailumatkat ovat mukavia.
Saa sitä jo aika hyvin osatakin, jos meinaa valmennukseen asti päästä :)
Mahtaakohan yläastesarjassa olla kova taso, vai onko tietoa kellään?
Viime vuonna satuin tuon peruskoulusarjan voittamaan :)
Alkukilpailussa oli 5 osallistujaa, tulin kolmanneksi pelkillä ohjelmoinneilla, joista toinen oli vajavainen. Loppukilpailuun pääsi kolme. Loppukilpailun ohjelmointini oli periaatteeltaan täysin oikea, mutta pienen bugin takia sain vain noin 20% pisteistä, ja silti voitin. Se varmaan kertoo jo paljon tasosta :)
Luulenpa minäkin keksineeni, kuinka kakkostehtävä kannattaa ratkaista. Eilen vielä tehtävä oli minulle suuri mysteeri, mutta aamulla ratkaisu olikin kirkkaana mielessäni. Nyt pitää enää kirjoittaa itse ohjelma...
Viime vuosina tosiaan peruskoulusarjassa on pärjännyt melko vaatimattomilla suorituksilla. Tämän vuoden ensimmäinen ohjelmointitehtävä on varmaankin juuri kohdennettu niille, jotka eivät ole aikaisemmin osallistuneet tämmöisiin kilpailuihin.
Ainakaan esseiden tähden ei kannata jättäytyä kilpailusta, sillä niiden kirjoittaminen ei ole mikään ylivoimainen urakka.
Jesh! Vaikka olenkin kokematon ohjelmoija, niin vaikuttaa siltä että minulla on tosiaankin mahdollisuuksia! Millainen on datatähden loppukilpailu?
Loppukilpailu oli ainakin viimeksi kaksioisainen. Kilpailijat jaettiin kahteen ryhmään, joista toinen suoritti ensin ohjelmointiosuuden ja toinen kirjallisen. Ruokailun jälkeen (järjestetty niin, etteivät eri ryhmät kohtaa) vaihdettiin paikkoja.
Kirjallisella puolella kyseltiin tietotekniikka-alan tunnettuja henkilöitä (yhdistä nimi ja kuva ja kerro lyhyesti, kuka henkilö on), spekuloitiin viestinlaitteiden kehittymistä ja sen mahdollisuuksia tulevaisuudessa ja mietiskeltiin, millaisia riskejä pitää huomioida suurelle käyttäjäyhteisölle rakennettavassa tietoverkossa (esim. koulun koneverkko). Näihin oli aikaa pari tuntia, mikä ainakin minulle riitti varsin hyvin rajallisten tietojeni purkamiseen. Ehdin loppuajalla kirjoitella paperin kääntöpuolelle ShellSort-algoritmin C:llä ja Pascalilla :)
Ohjelmointitehtävään oli aikaa kolme tuntia. Tehtävä oli tiivistettynä tällainen:
lainaus:
Ympyrän kehälle kirjoitetaan tasavälein kokonaisluvut 1, 2, 3,..., N. Näin syntyneeseen kellotauluun piirretään viivoja (mahdollisesti kaarevia) siten, että ne eivat leikkaa toisiaan eivätkä ympyrän kehää. Ne voidaan piirtää joko ympyrän sisä- tai ulkopuolelle. Tee ohjelma, joka tutkii, miten piirros tulisi tehdä tai onko se edes mahdollinen.
Ohjelmasi lukee syötteensä tekstitiedostosta
kello.in.Ensimmäinen rivi koostuu kahdesta kokonaisluvusta 1 <= N <= 1200 ja 1 <= M <= 3600, joiden välissä on välilyöntimerkki. Luku N kertoo, montako lukua ympyrän kehällä on. Luku M kertoo, montako viivaa on piirrettävä.
Tiedosto jatkuu M rivillä. Jokainen niistä sisältää kaksi kokonaislukua P ja Q. Tällainen rivi kertoo, että ympyrän kehälle kirjoitetut luvut P ja Q on yhdistettävä viivalla.
Vastaus tulee kirjoittaa tiedostoon
kello.out.Jos syötteelle ei ole ratkaisua, vastaus on pelkästään numero 0.
Jos syötteelle on ratkaisu, se tulostetaan seuraavasti: Ensimmäiselle riville tulostetaan numero 1. Tiedostossa on lisäksi M riviä, joilla on joko numero 0 tai 1. Numero 1 tarkoittaa, että vastaavan syöterivin viiva on piirrettävä kellotaulun sisäpuolelle. Numero 0 taas tarkoittaa, että se on piirrettävä kellotaulun ulkopuolelle.
En nyt jaksa sitä esimerkkikuvaa piirrellä... Piirtäkää itse, niin ymmärrätte :)
Ensimmäinen tehtävä on ihan turhankin helppo
Toimintaperiaatteenhan keksii teyhtävän lukiessa, toteutuksessa kai tuo luvun suurus ainoastaan pakottaa tekemään "purkkaa".
unsigned long long ei ole ANSI:ta :(
Vaikka pelkällä -ansi:lla ilman -pedantic vipua se vaan herjaa warningii -> kääntyy; Ei kyl jaksa kysyä onko sen käyttö "lailista"
Toiseen tehtävään ratkaisu tuli keksittyä kanssa pienen miettimisen jälkein. Vasta tänään sain tosin aikaa tehdä sen. Ja se jopa toimii. Tai ainakin omilla testi-inputeilla.
Harmillista että sellaista 1000x1000 sokkeloa ei oikein voi käsin piirtää.
Ja nuo rajat ovat kyllä olleet ennenkin sellaiset että ei aika lopu eikä muisti jos tekee "oikein". Ainakin mun mopo (380MHz) selviä reilusti alle rajan. Vois polkee vanhan SS5 käyntiin ja kattoa miten se pörrää :P
Esseistä, ainakin epäsuorasti sanotaan että ne on noin sivun pituisia, sellaisethan kirjottaa parissa tunnissa. Mutta silti ihmetyttää, mitä niillä haetaan tähän kilpailuun. Voi tosin ehkä kirjottaakin.
Metabolixin mainitsema kuvatehtävä ihmetyttää. Mä just ja just muistan Torvaldsin ja Bill Gatesin ja öö Jef Raskin, vai mikä hän oli. Sit on joukko joiden nimiä kyllä tietää ja mitä ehkä ovat tehneet, mutta en kyllä tiedä, miltä mahtavat näyttää (esim K&R ja Stroustrup).
Siis vain peruskoulun ja lukion oppilaille? Ei ammattikouluille? DAMN!
msdos464 kirjoitti:
Tuo maya numero juttu oli melko simppeli.. meni reilusti alle vartti tehdä ohjelma.. tosin loppu nolla ( @ ) jää vielä joskus laittamatta mutta se on helppo fiksata.
Taitaa tosin tulla vielä onglemia noissa isommissa luvuissa (käyttää inttejä)
Siinähän se vaikeus piileekin, ettei voi käyttää long tai int -muuttujia.
Itsekin harkitsen osallistumista jos saan jotain järkevää aikaan tuosta kakkostehtävästä, ykkösestä kun saa helposti pisteet ja esseet ovat vain mekaanista googlen käyttöä.
tomaattigeeni kirjoitti:
msdos464 kirjoitti:
Taitaa tosin tulla vielä onglemia noissa isommissa luvuissa (käyttää inttejä)
Siinähän se vaikeus piileekin, ettei voi käyttää long tai int -muuttujia.
Niin.. mutta ei senkään pitäisi olla suuri este. :)
msdos464 kirjoitti:
tomaattigeeni kirjoitti:
msdos464 kirjoitti:
Taitaa tosin tulla vielä onglemia noissa isommissa luvuissa (käyttää inttejä)
Siinähän se vaikeus piileekin, ettei voi käyttää long tai int -muuttujia.
Niin.. mutta ei senkään pitäisi olla suuri este. :)
Onko 64-bittinen matematiikka lasten leikkiä?
Minä keksin ratkaisun parin tunnin miettimisen jälkeen, eikä tarvinnut mennä low-leveliin.
aWW kirjoitti:
msdos464 kirjoitti:
tomaattigeeni kirjoitti:
msdos464 kirjoitti:
Taitaa tosin tulla vielä onglemia noissa isommissa luvuissa (käyttää inttejä)
Siinähän se vaikeus piileekin, ettei voi käyttää long tai int -muuttujia.
Niin.. mutta ei senkään pitäisi olla suuri este. :)
Onko 64-bittinen matematiikka lasten leikkiä?
Minä keksin ratkaisun parin tunnin miettimisen jälkeen, eikä tarvinnut mennä low-leveliin.
Ei kai pitäisi lupailla ennen kuin on toteuttanut sen, mutta ei pitäisi olla liian iso ongelma. En tiedä viitsiikö tässä kertoa paljoa ohjelman toiminta tavasta... kun tuo kisa on kuitenkin vielä kesken.
Onko kukaan muu osallistumassa yläastesarjaan ohjelmointiputkasta kuin minä (khyl täytyy osallistua, vaikka sitten vaan sillä ensimmäisellä ohjelmointitehtävällä ja esseevastauksilla)?
Tulihan se ohjelma ihan valmiiksi.. tein sen kyllä javalla, eikä sillä saa syystä tai toisesta osallistua. No samapa se, tekemällä oppii :)
12678793212349897984621321789 = * ****!!! **!! ***! ****! ** *!! **!!! *** **** ***! ** ****! **!! *! **** *!!! *** ** @ ***! ! **** ****! ****!
msdos464 keksi näköjään myös sen parhaan tavan :) Tai siis jonkin niistä.
TeeVee: Khyl kannattaa osallistua, voi vaikka voittaa vahingossa ;) Etenkin, kun peruskoululaisia ei ole kovin monta; eivät ole aivan helppoja tehtäviä, jos ei ole ollenkaan kokemusta.
Mitenkäs, onko moni saanut jälkimmäisen ohjelmoinnin ratkottua?
Mahtavatkohan ne tarkistajat lukea lähdekoodeja ollenkaan? Olisihan se kurjaa, jos minun hieno vikasietoinen systeemini jäisi aivan huomiotta :)
No ainakin todennäköisesti sen verran lukevat lähdekoodeja, ettei ole mitään haittakoodia tms mukana :|
Ja eikös ne kattele koodeja sitten jos tulee tasapeliä, vai tehtiinköhän niin jossakin muussa kilpailussa? En nyt varmaksi mene sanomaan, mutta joku tuollainen muistikuva olisi itselleni jäänyt..
(Eipä ole tänne taas vaihteeksi tullut kirjoiteltua...)
Nyt kun katsoo mikä oli peruskoulusarjan taso, niin harmittaa, etten osallistunut siihen viime vuonna. Nyt pitää osallistua sitten isojen poikien sarjaan ;)
Mut, eka tehtävä oli suht. simppeli, nopeasti sain kasaan ohjelman joka osaa jopa tuon tehtävässä suurimmaksi mahdolliseksi määritellyn luvun, 1000000000000000000. Toinen tehtävä olikin sitten astetta haastavampi. Pari yritystä meni metsään (algoritmi oli sieltä jostain syvältä...) mutta kolmas versio ratkaisee nuo suht. nätisti. Pienen optimoinnin jälkeen tuollainen 1000x1000-mappikin menee alle sekunnin (genmap1 1000, 2 roboa vastakkaisissa nurkissa, 0.6s).
Ja niille jotka ovat liian laiskoja värkkäämään itse ohjelmia noiden mappien tekoon, laiton esille 3 ohjelmaa joilla voi generoida kenttiä. Roboja mikään niistä ei lisää, sen voi tehdä käsinkin, mutta itse kentän perusrungon generointiin ne ovat mukavia. En nyt tässä käyttöohjeita kerkeä antamaan kun pitää mennä tekemään matikan koe, mutta sorsia lukemallahan tominnan pitäisi selvitä ;)
Osoite noille ohjelmille: http://nullkey.ath.cx/~stuff/datatahti/
msdos464 kirjoitti:
Tulihan se ohjelma ihan valmiiksi.. tein sen kyllä javalla, eikä sillä saa syystä tai toisesta osallistua. No samapa se, tekemällä oppii :)
12678793212349897984621321789 = * ****!!! **!! ***! ****! ** *!! **!!! *** **** ***! ** ****! **!! *! **** *!!! *** ** @ ***! ! **** ****! ****!
Onko tuo varmasti oikein? Itse sain
12678793212349897984621321789 = *! @ ***!!! ! !!! *** ** **! !!! ***! **!!! **** ****!! !! @ ****! ****!! *** ! **** ****! ****!
Ratkaisin huvikseni tehtävän Pythonilla, jolla tuo muunnosfunktio mahtuu kolmelle riville (def-rivi + 120 merkkiä sen jälkeen).
Edit: Koko ratkaisu mahtuu neljälle riville, 193 merkkiä.
Chiman kirjoitti:
msdos464 kirjoitti:
12678793212349897984621321789 = * ****!!! **!! ***! ****! ** *!! **!!! *** **** ***! ** ****! **!! *! **** *!!! *** ** @ ***! ! **** ****! ****!
Onko tuo varmasti oikein? Itse sain
12678793212349897984621321789 = *! @ ***!!! ! !!! *** ** **! !!! ***! **!!! **** ****!! !! @ ****! ****!! *** ! **** ****! ****!
Kyllä sen _pitäisi_ olla oikein.. ainakin ohjelma antaa oikean tuloksen luvuille 15000, 30512, oho.. 323245 antaa ihan väärän tuloksen :S
3232451 antaa taas oikein.
323245111 väärin. On jotain ongelmaa, jos luvussa olevien numeroiden määrä on jaollinen kolmella :P tuo 12678793212349897984621321789 ei kyllä ole semmoinen. Joku muukin voisi antaa tuosta tuoloksen, niin saisi vähän varmuutta että kummalla on oikein. Ainakin omassa ohjelmassa on vielä joitakin bugeja.
tuo on vähän liian iso numero (mm. oman tein sillai että se 10^18 on maksimi)
ja voihan sitä käsinkin tarkistaa (ei kyllä jaksa)
Minä saan myös saman kuin Chiman, eli msdos464 pääsee korjailemaan ohjelmaansa. Varmaan kannattaa saman tien rakentaa siihen vielä tarkistuskin.
// Z-maze.c
#include <stdio.h>
#define SIZE 1000
int main() {
FILE *maze;
int x, y, i;
maze = fopen("maze.in", "w");
fprintf(maze, "%d\n", SIZE);
for(x=0; x<SIZE-3; x++) fputc('#', maze);
fprintf(maze, "..#\n");
fprintf(maze, "#X");
for(x=2; x<SIZE-1; x++)
if(!((x+1)%3) && !(x&0x1)) fputc('#', maze);
else fputc('.', maze);
fprintf(maze, "#\n");
for(y=2; y<SIZE-2; y++) {
fputc('#', maze);
if(!((y+1)%6)) fputc('#', maze);
else fputc('.', maze);
for(x=2; x<SIZE-2; x++)
if(!((x+y)%3)) fputc('#', maze);
else fputc('.', maze);
if(!((2*SIZE-1-y)%6)) fputc('#', maze);
else fputc('.', maze);
fputc('#', maze);
fprintf(maze, "\n");
}
fputc('#', maze);
for(x=1; x<SIZE-2; x++)
if(!((2*SIZE-1-x)%3) && ((2*SIZE-1-x)&0x1)) fputc('#', maze);
else fputc('.', maze);
fprintf(maze, "R#\n");
fprintf(maze, "#..");
for(x=0; x<SIZE-3; x++) fputc('#', maze);
fprintf(maze, "\n");
fclose(maze);
return 0;
}
// 0,125 sMetabolix kirjoitti:
Minä saan myös saman kuin Chiman, eli msdos464 pääsee korjailemaan ohjelmaansa. Varmaan kannattaa saman tien rakentaa siihen vielä tarkistuskin.
Selvä... pitää katsoa mitä häikkää siinä vielä on :)
os kirjoitti:
// Z-maze.c
...
// 0,125 s
Itsellä 0.142s (jos tuon ratkomista tarkoitit...)
Pyry ja os: Mitä mahtavat koneenne olla? Minulla meni tuohon 0.28s (user), kone 2.0GHz Athlon XP. Ja olihan tuo varmasti "tylsä"?
Metabolix kirjoitti:
Pyry ja os: Mitä mahtavat koneenne olla? Minulla meni tuohon 0.28s (user), kone 2.0GHz Athlon XP. Ja olihan tuo varmasti "tylsä"?
Tylsäksi oma ohjelmani tuon luokittelee, väittää selviävänsä 329350 siirrolla. Laskennan hoitaa Pentium IV 2GHz, tietovarastona toimii PC133-muisti, eikä emon (intelin kurja toimistomalli) väylänopeuksissa ole hurraamista. Edellä taisin mainita, että omalle algorimilleni raskain mahdollinen vaihtoehto hurahtaa lävitse 0.6s omalla kokoonpanollani, mutta vastaavasti kaverin koneella (AMD Sempron 2600+, DDR400) menee 0.26s. Eli eiköhän tuo ohjelma mene testikokoonpanolla aikarajojen sisään ;)
Niinja kääntäjälle annetut parametrit ovat "-O2 -static -ansi", kuten datatähden sivustolla mainittu.
Eli minulla olisi vielä vähän optimoinnin varaa :) Toivottavasti algoritmi on riittävän hyvä, kun en jaksa korjailla.
Mikä on tuo raskain mahdollinen syöte?
1000x1000-kenttä, oma nappula keskellä, robot vastakkaisissa nurkissa siten, että kenttä on kuitenkin tylsä (keskelle muodostuu sellainen kapea "käytävä", jonne robot eivät "ylety").
Edit: muistin väärin, eli kenttä ei ole kys. tilanteessa tylsä.
Edit2: http://nullkey.ath.cx/~stuff/datatahti/maze.in.
Minulla sen ratkomiseen meni peräti vähemmän kuin edelliseen, 0.26s, jos robotteja on kaksi, tai 0.29s, jos niitä on kolme.
Kannattaisiko tuo ehkä gzipata? Megan tiedosto kuitenkin, pelkkiä pisteitä.
Minulla taasen ohjelma nopeutuu jos robottien määrää lisätään. En nyt viitsi kertoa miksi, sillä muuten paljastaisin ehkä liikaa toiminnasta. Noh, kunhan kilpailuaika on umpeutunut, laitan omat ratkaisuni esille, toivoen että joku muukin tekee samoin. Mielenkiintoista nähdä sitten miten kukin on ohjelmansa tehnyt.
Edit: bzip on tehokkaampi ;)
Joo, varmasti voin tämän julkaista. Saas nähdä, lähtisikö tästä koodista pienellä säädöllä vielä lisää tehoa irti... Jos nyt kuitenkin... :)
phadej@pimio:~/cvs/dt06$ time ./maze real 0m0.594s user 0m0.580s sys 0m0.010s phadej@pimio:~/cvs/dt06$ cat maze.out 329350 phadej@pimio:~/cvs/dt06$ cat /proc/cpuinfo processor : 0 vendor_id : AuthenticAMD cpu family : 5 model : 8 model name : AMD-K6(tm) 3D processor stepping : 12 cpu MHz : 379.902 cache size : 64 KB fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 1 wp : yes flags : fpu vme de pse tsc msr mce cx8 pge mmx syscall 3dnow k6_mtrr bogomips : 758.57
Et aika nopia mull o :P
toisalta tässä on toinen 1000x1000 kenttä, tylsä, itse saan 920. Aikaa menee about samanverran.
http://phadej.daug.net/files/maze.in
Pitäisi jaksaa nyt vaan esseet kirjottaa ja ehkä kokeilla omalla 2800+ Athlonilla.
Se on nyt sellainen juttu, että lähetin juuri ohjelmointivastaukseni ja esseevastaukset on lähetetty tänään aikaisemmin :) En olisi uskonut että osallistun kisaan, mutta yläastesarjan surkea taso kannusti erittäin paljon, toivottavasti osallistujia on enemmän kuin yksi ;D
edit: pääseekö valmennukseen yläastesarjalaisetkin?
TeeVee: Käsittääkseni kyllä, valintaperusteena on sekä alku- että loppukilpailun ohjelmointitehtävien pistemäärä. Yleensä vain parhaat lukiolaiset tahtovat (valitettavasti?) olla parempia, ja kaikkia ei valmennukseen oteta kuitenkaan.
Lähetän kohta vastaukseni, mitäs, viidettä kertaa :) Pientä säätöä yhä, vaikka eipä sillä ole oikeellisuuden kannalta ollut enää merkitystä, ja nopeuteenkin vain minimaalinen vaikutus (noin 5%).
Kaksi esseetä (4. ja 5.) jaksoin kirjoittaa sunnuntai-iltana, enkä niitäkään turhan huolellisesti.
Pitäisiköhän tässä huolestua, vai eikö vastausten vastaanottokuittausta yksinkertaisesti lähetetä?
Metabolix, en tunne hirveää pettymystä, kun ei pääse yläastesarjalaiset valmennukseen, varmasti itseopiskeluna on vielä PAALJON opittavaa :))
En ole saanut vastaanottokuittausta myöskään. Postissa pyysin postitätiä laittamaan sen lähetysajankohdan siihen tarkasti ylös, jolloin hän printtasi siihen sen, näkyi sekunnilleen kellonaika ja päiväys ynm.
Khyl sitä on nyt tyytyväinen, mutta tuossa kilpailussa huomasi, että turhan nopeasti aloittelijat hyppäävät grafiikkakirjastoihin kiinni, kannattaa ensin käyttää kielen standardiominaisuuksia ja sitten vasta lisäkirjastoja!
TeeVee: Kyllähän sitä itseopiskeltavaakin on, mutta itse on helpompi opetella käytännön ohjelmointia (siis juuri niitä grafiikkakirjastoja ja muutenkin kielen perusteita), kun tuolla taas opetettaisiin nimenomaan tietorakenteita ja algoritmeja, joita taas on minusta hieman kuivaa opetella itsekseen, varsinkin, kun hankalammissa asioissa on lähteenä pelkästään englanninkielistä, alan termistöllä höystettyä tekstiä.
Toisaalta nämä alkukilpailutehtävät ovat sellaisia, että niiden tasolle pääsee kokeilemalla ja keräämällä kokemusta. Loppukilpailutehtävät myös, eikä olympialaistehtävissäkään ole kuin muutama, jotka todella vaatisivat tuota opetusta. Niissä vain tulee vastaan se, että kaiken pitää tulla liikaa miettimättä, kun samana päivänä pitää tehdä kolme tehtävää, jotka olivat suunnilleen tätä tasoa tai hieman kovempia.
Joo, olen itsekin huomannut sen, että on todella tylsää opiskella perusrakennetta, mieluiten sitä olisi grafiikkakirjaston kanssa väsäämässä peliä tai vastaavaa :)
Mutta itse olen kiirehtinyt noiden kanssa, olisi pitänyt aikaisemmin tajuta vain opiskella esim, tiedoston käsittelyä. En ollut opetellut, joten jouduin kisan aikana opettelemaan. En ollut harjoitellut merkkijonokirjaston käyttöä kyllin hyvin, jouduin senkin opettelemaan samalla kun koodasin. Edes pintaa raapaisten pitäisi kaikkea opiskelle edes vähäisen, mutta tälläiselle nuorelle, yksinkertaiselle pääkopalle se on vaikeaa :D
Vaikka kilpailu on ohi, niin silti yritän katsoa vähän tuota toista tehtävää, jos vaikka saisin sen ratkaistua vähän pidemmän ajan kuluessa. Vanhojakin voisi yrittää googlettaa "näytä välimuistissa" ominaisuuden avulla. Tälläiset tehtävät ovat erittän mainioita oppimaan standardirakenteita, huomasin sen :))
Vastaukset tuli lähetettyä suunnilleen kolmelta (postileima tulee siis tämän päivän puolelle). Ohjelmointitehtävät laitoin tietysti molemmat, mutta teoriatehtävistä jaksoin kirjoittaa vain määrittelyt ja viitosesseen (2 ohjelmointikieltä). Saas nähdä miten noilla pärjää, tein kuitenkin esseen ja määrittelyt huolella että kyllä uskoisin niistä pisteitä saavani.
Ja huomenna sit laitan ne ohjelmointini jonnekkin, josta halukkaat voivat käydä katsomassa ja toteamassa että onpas huonoa koodia ;)
Ps. Lopullinen versio maze:sta ratkaisi sen hitaimman kentän 0.23s
Ps2. Mayatehtävä tuli sit tehtyä Casio FX-9860G -laskimellekkin, haluaako joku koodin? :D
teevee: vaikka mitä peliä tekisit, niin on pakko miettiä niitä tietorakenteita ja jonkinlaista ai:ta, ellei sitten tee tosi yksinkertaista peliä.
Laitanpa nyt näkyviin tuon aiemmin mainitsemani Python-ratkaisun. Ensin pelkkä (selkeähkö) muunnosfunktio, jonka or-kikka ei tosin kuulu tasokkaaseen koodiin:
from math import log
def maya(x):
s = []
for t in (20 ** i for i in range(int(log(max(x, 1), 20)), -1, -1)):
s.append('*' * (x / t % 5) + '!' * (x / t / 5) or '@')
x %= t
return ' '.join(s)Sitten epäsuositeltava, tiivistetty täysversio:
from math import log
x = int(file('maya.in').read())
file('maya.out','w').write(' '.join('*'*(t%5)+'!'*(t/5) or '@' for t in \
(x%20**(i+1)/20**i for i in range(int(log(max(x,1),20)),-1,-1))))Chiman kirjoitti:
... s.append('*' * (x / t % 5) + '!' * (x / t / 5) or '@') ...
Python näyttää varsin mukavalta, pitää varmaan tässä joskus opetella.
Kuten lupasin, http://nullkey.ath.cx/~stuff/datatahti/maya.cpp ja http://nullkey.ath.cx/~stuff/datatahti/maze.cpp (kummatkin UTF-8)
Siitä sitten ottamaan selvää...
Tässä yksi kätevä tapa ratkaista tehtävä nro. 2:
(2 ruudun välinen etäisyys = pienin määrä seinät huomioivia siirtoja, joilla sankari voi liikkua toisesta ruudusta toiseen, robotteja ei tässä tietenkään huomioida. Mikäli seinät estävät täysin ruutujen välillä liikkumisen, voidaan niiden välinen etäisyys ajatella äärettömäksi)
Lasketaan ensin n*n taulukkoon se(n)(n) lyhin etäisyys ruudukoon jokaisesta ruudusta alkuperäiseen X:n (sankarin?) ruutuun. Tämän voi tehdä esim. yksinkertaisella ns. BFS - algoritmilla lineaarisessa ajassa taulukon koon n*n suhteen.
Tämän jälkeen lasketaan toiseen n*n taulukkoon re(n)(n) lyhin mahdollinen etäisyys ruudukon jokaisesta ruudusta johonkin robottien aloitusruutuun. Tämä etäisyys käytännössä kertoo, montako siirtovuoroa robottien on suoritettava, jotta ainakin yksi niistä pääsisi alkutilanteesta ko. ruutuun asti. Tämäkin vaihe voidaan suorittaa yhdellä BFS:llä lineaarisessa ajassa n*n suhteen, kunhan BFS:n suoritusjono alustetaan alussa kaikilla robottien aloitusruuduilla.
Seuraavaksi huomataan, että sankari voi alkutilanteesta päästä ruutuun (i,j) jos ja vain jos se(i)(j) ei ole 'ääretön' ja se(i)(j) < re(i)(j). Tämän voi helposti todeta pienen tutkistelun jälkeen.
Tämän huomion perusteella riittää käydä läpi jokainen ruudukon reunalla oleva tyhjä ruutu, valita niistä sankarin kannalta paras, ja palauttaa vastaukseksi tätä parasta ruutua vastaava lyhin etäisyys. Mikäli yhtään sankarin tavoitettavissa olevaa ruutua ei reunalta löydy, ei ruudukko olekaan tylsä.
VilleP kirjoitti:
Lasketaan ensin n*n taulukkoon se(n)(n) lyhin etäisyys ruudukoon jokaisesta ruudusta alkuperäiseen X:n (sankarin?) ruutuun. Tämän voi tehdä esim. yksinkertaisella ns. BFS - algoritmilla lineaarisessa ajassa taulukon koon n*n suhteen.
Miksi pitäisi ensin laskea X:n etäisyys kaikista ruuduista? Omassa ratkaisussani ainakin riitti, että laskettiin lähimmän robotin etäisyys kustakin ruudusta ja sitten tässä tietorakenteessa tehdään haku X:lle sillä säännöllä, että ruutuun ei voi mennä, jos matka siihen suurempi tai yhtäsuuri kuin jonkin robotin. Seinät voidaan merkitä luvulla 0, joten ne tarvitse mitään ylimääräisiä tarkasteluja. Ratkaisu tietenkin löytyy, jos X päätyy reunaruutuun ja ratkaisua ei ole, jos hakujono tyhjenee.
Täysin optimoimaton ratkaisu dijkstran ja binary heapin avulla toimi helposti alle puolen sekunnin noilla muutamalla 1000x1000 testiruudukoilla. Näin jälkeenpäin ajatellen pelkistetty BFS ihan perusjonolla olisi toiminut nopeammin, mutta dijksta tuli selkärangasta automaagisesti.
Kuten luvattu: (linkki vanhentunut)
En viitsinyt mayassa 64-bittistä integeriä käyttää, kun se ei käsittääkseni kuulu tiukkaan standardiin. Siksipä teinkin version, joka muuntaa vaikka 128-numeroisen luvun (tai miksei isommankin, jos muistinvaraus olisi dynaaminen), tuossa kun ei ollut aikaraja mistään kotoisin.
Mazessa taas tein yksinkertaisimman (riittävän nopean) mieleen tulleen ratkaisun vähäisillä optimoinneilla, panostaen enemmänkin koodin kokoon kuin nopeuteen. Ideana oli, että listalle kerätään kierroksella muuttuneet ruudut (aluksi siis ne, joissa on joku), ja joka kierroksella käydään edellinen lista läpi (merkitään viereisiin ruutuihin lyhyemmät matkat) ja kerätään taas muuttuneita uuteen listaan. Heti, kun X on päätynyt reunalle mutta robo ei, on vastaus löytynyt.
Esseistä kirjoitin siis kaksi. Esittelin kielinä QB:n merkittävänä aloittelijoille (vaikka en sitä hyvänä valintana pidäkään, niin käytetty se ainakin on), ja C++:n ohjelmistoalalta (vaikka Java olisi voinut olla parempi, tai jokin uudempi). Merkittävinä keksintöinä esittelin transistorin, mikropiirin ja magneettisen tiedontallennuksen.
Minä tein kakkostehtävän oikeastaan samalla tavalla kuin FooBat. Tosiaan tavallinen leveyshaku riittää hyvin tähän tehtävään: ensin lasketaan robottien lyhimmät matkat ruutuihin, sitten tarkastetaan, pääseekö pelaaja mitään reittiä kartan reunalle. Tietenkään robottien tai pelaajan ei kannata missään tilanteessa pysyä paikallaan.
Alkukilpailun tuloksia voi odottaa tammikuun alussa.
FooBat kirjoitti:
Miksi pitäisi ensin laskea X:n etäisyys kaikista ruuduista?
No eipä miksikään, mutta esittämälläni tavalla ratkaisu oli mielestäni helpompi muotoilla täsmällisesti ja todistaa oikeaksi vähemmällä käsienheiluttelulla. Varsinaisen ohjelmani toteutin itse asiassa laskematta kertaakaan kumpaakaan etäisyyslistaa kokonaisuudessaan, vaan sen sijaan vuorottelemalla leveyssuuntaisen haun vaiheita robottien ja sankarin välillä.
http://phadej.daug.net/files/dt06/
maya on aika purkkiratkaisu
maze on vähän erikoinen verrattuna noihin esitettyihin, mutta toimii ja suhteellisen nopeastikin. tai tarkemmin katsottuna sekin olisi ollut c++ vähän nätimpi, mut tuli nyt tehtyä c:llä.
Tässä minun näkemykseni ratkaisuista (raa'at versiot):
http://koti.mbnet.fi/jusic/shared/code/
Aina oppii jotain uutta.
Maze toimii tehden syvyyshakua (BFS) yhden askeleen kerrallaan, samalla tavoin kuin Metabolixin ratkaisu. Tulipa tehtyä ainakin hauskahko "reaaliaikainen" debug-tulostus tähän.
Mayan toteutin laiskasti long long -tyypillä, joka sitten ei täysin toimikaan ANSI-standardin C:llä.
Vastasin kaikkiin (mielestäni melko puuduttaviin) esseekysymyksiin, merkittävinä laitteina esittelin mikroprosessorin, levyaseman (magneettiset sekä optiset) ja verkkokortin, kielinä C++ ja Java.
Parasta onnea kisaan itse kullekin.
Osasin itse tehdä vain mayan.
Toteutin sen olioratkaisulla, jossa jäsenfunktioina on luvun lataus, konvertointi ja tallennus. Osoittimella hoidin muistinvarauksen kätevästi. Varmaan aivan turhaa, mutta hyvää harjoitusta aloittelijalle :D
En usko menestykseeni, mutta ainakin tuli opittua jotain :)
Datatähden alkukilpailun tulokset ovat nyt tulleet:
http://www.maol.fi/index.php?id=63
Tänä vuonna pisteraja nousi todella korkeaksi. Osallistujia oli myös viime vuosia enemmän. Listalta erottuu koko joukko minulle tuttuja nimiä. Muutamien kanssa näemme loppukilpailussa!
#5 - Laaksonen Antti - Ressun lukio, Helsinki - 88 pistettä.
Epäilyttää, että Antti ei tunnista itseään ;-) Taitaa olla tuttu nimi kyseessä.
Mutta Antti ei varmaankaan koe itseään "koko joukkona". Onhan tuolla paljon muitakin samoja nimiä kuin viime vuonna.
Olisi kiinnostava nähdä taas tarkemmat pisteytykset, eli ohjelmoinnit ja esseetehtävät erikseen. Hieman jäi kiinnostamaan, mistä on 30 pistettä mennyt, kun ei loppukilpailupaikka auennut :)
Yläastesarjan ainut osallistuja ;PP
lainaus:
Loppukilpailuun kutsutaan lukiosarjan 12 parasta.
Perskele, eikö yrittänyttä palkita :D
Jaa, postia tuli sittenkin. Onko nyt tosiaan niin, että on yhä toivoa päästä olympiavalmennukseen, vaikka ei päässytkään loppukilpailuun? Jotenkin erikoisen oloinen järjestely tämä on, siksi pitää oikein ääneen ihmetellä :)
Sähköpostiviesti Datatähden alkukilpailijoille kirjoitti:
Kansallisessa Datatähti-kisassa on myös esseeosuus, jota ei ole kansainvälisissä ohjelmointiolympialaisissa. Sen vuoksi sinulla on mahdollisuus tehdä verkkokilpailuna se sama ohjelmointitehtävä, jonka Datatähti-loppukilpailijatkin tekevät. Olympiavalmennettavat valitaan kaikkien Datatähti-ohjelmointitehtävien yhteispisteiden perusteella.
Verkkokilpailu pidetään torstaina 2.2.2006 klo 18-21, eli heti Datatähti-loppukilpailun päätyttyä.
(... ilmoittautumisohjeet yms.)
Metabolix kirjoitti:
Onko nyt tosiaan niin, että on yhä toivoa päästä olympiavalmennukseen
Eiköhän siellä voi käydä. Minä en pärjännyt aikoinani MAOLin matikkakilpailussa kovinkaan hyvin, mutta kyllästyin oppitunneilla, kun kaikki oli tuttua. Osallistuin omakustanteisesti matikkavalmennukseen ja täytyy myöntää, että valmennuksesta oli erittäin paljon hyötyä. Aina kannattaa miettiä ongelmia, joissa on haastetta, mutta jotka eivät ole ylivoimaisia ratkottavaksi. Ainakin minulle oli helppoa mennä matikan ylppäreihin ja aloittaa yliopisto-opinnot, kun olin käynyt pari vuotta valmennuksessa.
Metabolix kirjoitti:
Onko nyt tosiaan niin, että on yhä toivoa päästä olympiavalmennukseen, vaikka ei päässytkään loppukilpailuun? Jotenkin erikoisen oloinen järjestely tämä on, siksi pitää oikein ääneen ihmetellä :)
Samalla tavalla näyttää olevan fysiikassa. Kisassa oli perussarja (kakkosille) ja avoinsarja (kolmosille), vain avoimesta pääsi loppukilpailuun. Itse olin perussarjassa seitsemäs, ja sain tällaisen viestin
MAOLin maili kirjoitti:
Kirjevalmennuksen yhtenä tavoitteena on innostaa teitä hyvät osallistujat pohtimaan fysiikan tehtäviä yleensäkin, mutta myös löytää Suomea kansainvälisiin olympialaisiin edustamaan lähetettävä viisihenkinen joukkue.
Eipä tuonne käytännössä varmaankaan mitään mahdollisuuksia ole mutta tuo valmennus on ihan mielenkiintoinen. Mukavan haastavia tehtäviä.
Olisiko jollakulla mahdollista lähettää finaalikierroksen tehtävät? Etenkin datatähti ja matikka kiinnostaa.
En tiedä, missä määrin noita saa levittää... Mutta huhutaan, että Datatähtitehtäviä löytyisi osoitteesta (linkki vanhentunut).
Ihan kiva tehtävä. Kyllä niitä saa käsittääkseni levitellä aika vapaasti. Tekijänoikeuslakihan suojaa vain teoksen ulkoasun, ei asiasisältöä. Lakipykälän voipi lukea tästä, 22§.
Aihe on jo aika vanha, joten et voi enää vastata siihen.