Tämänvuotisen Datatähti-kilpailun tehtävät ovat nyt julkaistu. Mitäs mieltä olette tehtävistä? Ja kuinka moni aikoo osallistua?
Itse ajattelin tänä vuonna osallistua, jos vaan saan jotakin aikaiseksi. Ohjelmointitehtävät ovat melko hankalanoloisia, sillä en ole aikaisemmin tuontyyppisiä tehtäviä tehnyt. Esseistä vertaisverkko-ohjelmat tuntuu aika helpolta, niistä kun on karttunut kokemusta :)
Niin... ja lukiosarjaan olen osallistumassa. Tavoitteena on saada edes toisesta ohjelmointitehtävästä pisteitä...
Peruskoululaisille ja lukiolaisille tarkoitetun vuotuisen Datatähti 2005 -kilpailun ohjelmointitehtävät liittyvät siis tänä vuonna taikaneliöihin ja Pac-Man-peliin. Kirjoitustehtävissä taas udellaan tietoja kvanttitietokoneista, salausmenetelmistä ja vertaisverkko-ohjelmista. Ensisilmäykseltä tämänvuotiset tehtävät vaikuttavat mukavilta, itse ainakin meinaan osallistua kilpailuun...
Toivottavasti moni muukin "putkalainen" osallistuu kilpailuun - ja menestyy siinä!
Liika vaikeet kysymyset. :<
Tarkoittaako tuo 1.3:n "tyhjämerkki" välilyöntiä (ASCII 0x32) vai oikeasti tyhjää (ASCII 0x00)?
Ihan jeeseiltä vaikuttavat. Kakkonen varmaan vaikeahko, ykkösessä tullee ongelmaksi pelkkä vauhti. Esseetehtävät ovat helppoja, kolmosta ja nelosta pitää pikkaisen tutkia ja viitonen mennee tuosta vain.
Yleensäkin ottaen noissa ohjelmointihommissa tulee ongelmaksi se, ettei ole testikonetta. Tietysti, jos saa ne ohjelmat pyörimään alle sekunnissa omalla koneella, hyvä vain, mutta paha se on sanoa onko reilu kaksi sekuntia 1200-MHz-Duronilla alle sekunnin 3-GHz-Pentium IV:llä.
Vaikuttaa minusta hieman vaikeammilta kuin viime vuoden kysymyksen, mutta ajattelin kuitenkin osallistua ainakin ohjelmointitehtäviin. Esseistä en tiedä.
Itse ainakin aion osallistua tuohon. Voi tehdä vähän tiukkaa noiden ohjelmointitehtävien kanssa, kun c++:ssaa olen tässä yritellyt vääntää vasta muutamien viikkojen ajan. Esseet luulis menevän melko hyvin..
Tyhjämerkki on varmaankin mikä tahansa whitespace, eli mikä tahansa, josta Pascalin, C:n ja C++:n lukufunktiot pääsevät tukehtumatta ohi. Tarkistus hoidetaan todennäköisesti koneellisesti ohjelmalla, joka vain lukee kahta tiedostoa yhtä aikaa luku kerrallaan ja vertailee.
Aion kyllä osallistua. Sanoisin, että tehtävät ovat vaikeammat kuin viimevuonna, ainakin siltä kannalta, että taikaneliöstä on varmaankin syytä ymmärtää teoriaa vähän ohjelmointia pitemmällekin. Kuten Deewiant jo totesi, pullonkaulaksi muodostuu varmaankin eniten algoritmin nopeus. Viimeksi oli paljon helpompi ylittää muistirajakin.
1. tehtävän tehtävänannossa taitaa olla virhe. Esimerkkitulostuksen 1. luku on N² = 9, vaikka neliön sivu N = 3. Kuitenkin ohjeissa lukee, että ensimmäinen numero on neliön koko N.
Arvostelukin on näköjään lepsumpi, kun Pac-Man voi antaa pisteitä, vaikka aikaraja ylittyisi.
Korjaan itseäni: välilyöntihän on ASCII 32, eli 0x20 eikä 0x32. Onnistuin korjaamaan tuon väärin muokkauksessa.
Metabolix kirjoitti:
1. tehtävän tehtävänannossa taitaa olla virhe. Esimerkkitulostuksen 1. luku on N² = 9, vaikka neliön sivu N = 3. Kuitenkin ohjeissa lukee, että ensimmäinen numero on neliön koko N.
Tai sitten ohjeissa virhe, ja tarkoitettiin kuinka monta ruutua neliöstä löytää? Tuota pitäisi varmaankin kysyä.
Kysyin juuri, tuli vastaus, ja olin oikeassa. Ruudukon leveys (3) siinä pitäisi olla.
Noniin, nyt on tuo taikaneliö hoidettu - ohjelma pyörii noin kaksi sekuntia omalla 1200-megahertsisellä Duronillani, eiköhän kolme-gigahertsinen Pentium IV hoida tuon sekunnin sisään (jos ei, kannattanee vaihtaa Athloniin ;)).
Kakkonen lieneekin sitten monimutkaisempi juttu.
Onko tuossa taikaneliössä muuten käytössä vain luvut 0 - 8?
Ei oikein menny perille..
tuomas kirjoitti:
Onko tuossa taikaneliössä muuten käytössä vain luvut 0 - 8?
Siis, käytössä olevien lukujen määrä lukee tiedostossa "taika.in". Käytössä olevat luvut ovat sitten nollasta (taika.inin luku - 1):n.
Isoin luku, mikä taika.inistä voi löytyä on 999, jolloin käytössä olisi luvut 0 - 998.
Voisi kai sitä itsekin osallistua jos saa jotain aikaan. Essee-tehtävistä 4 ja 5 menevät varmaankin melkolailla suoralta kädeltä mutta 3:sta pitänee hieman tutkia. Ohjelmointitehtävät vaikuttavat ihan mielenkiintoisilta. Taikaneliö-ongelma on sinänsä helppo, että siitä löytyy webistä todella paljon tietoa.
Mul ei ainakaan oo mitään mahiksia. Iha liian vaikeet kysymykset.
Deewiant, tuomas:
taika.in sisältää luvun N, joka on neliön sivun pituus. Jokaiseen ruutuun tulee eri luku, joten luvut ovat 0 .. N² - 1. Esim. N = 3, luvut = 0 .. 8. Suurin: N = 999, luvut = 0 .. 998000.
Oma taikaneliöni täyttyy 2,0 GHz Athlonilla (2400+) alle 0,1 sek suurimmallakin neliöllä.
Niin, eikö se ole niin, että jokaista lukua nollasta ruutujen määrään pitää käyttää täsmälleen yhden kerran?
Metabolix kirjoitti:
Deewiant, tuomas:
taika.in sisältää luvun N, joka on neliön sivun pituus. Jokaiseen ruutuun tulee eri luku, joten luvut ovat 0 .. N² - 1. Esim. N = 3, luvut = 0 .. 8. Suurin: N = 999, luvut = 0 .. 998000.
Aivan, sanoin pieleen.
lainaus:
Oma taikaneliöni täyttyy 2,0 GHz Athlonilla (2400+) alle 0,1 sek suurimmallakin neliöllä.
Ihan mielenkiinnosta, kerro mitä algoritmia käytät - tietenkin vasta kilpailun jälkeen.
hunajavohveli kirjoitti:
Niin, eikö se ole niin, että jokaista lukua nollasta ruutujen määrään pitää käyttää täsmälleen yhden kerran?
(Ruutujen määrä - 1):n, muuten oikein.
itse ymmärsin että ruudukoissa käytettäisiin vain lukuja 0 - 8 jotka olivat esimerkissäkin. Aika vaikea tuo tehtävä, kun en vain keksi hyvää tapaa jolla lähteä aloittamaan..
tuomas: kyllä se lukee ihan ohjeissa:
Datatähti 2005, tehtävät.pdf kirjoitti:
Kokoa N oleva taikaneliö on N rivin ja N sarakkeen ruudukko, jonka ruutuihin on sijoiteltu luvut 0, 1, 2, 3, . . . ,N² - 1 siten, että jokaisessa ruudussa on täsmälleen yksi luku, ja jokaisen vaaka- tai pystyrivin lukujen summa on aina sama.
Mä en vielä noihin ole pahemmin tutustunut, mutta tuo taikaneliötehtävä on ainakin varsin helppo. Niissä esseissä sen sijaan on hiukkasen tekemistä.
edit: Tuo Pacman-tehtävä vaikuttaakin jo hankalemmalta ja enemmän ohjelmoinnilliselta. Taikenliön väänsinm valmiiksi matikantunnilla, mutta tuo ei ihan polkaisemalla synnykkään.
on se pacmanikin helppo kakku
Mites tuota suoritusaikaa voisi mitata linuxissa? Vaikka nopiastiahan nuo menee kuiteski
Onkos muuten kukaan päässyt loppukilpailuihin ikinä? Laaksonen ainakin :)
Minkäslaisia ja tasosia tehtäviä siellä on?
Jos teet C:llä, aikaa voit mitata vaikka time.h:sta löytyvällä clock() -funktiolla. Arvelisin.
kokeilin tuota clockkia mutta tuntui antavan aina vaan 0 ajaksi vaikka jaon sen CLOCKS_PER_SEC:llä jotta siitä olisi tullut sekunteja :(
...
Ei tarvitse enää, sain toimimaan muulla tavoin.
Pienen testailun jälkeen taikaneliössä kun N on 999 tuli tämmösiä
bluebyte@Pingu:~/C++/datatähti/taikanelio/debug/
real 0m1.491s
user 0m1.340s
sys 0m0.065s
Athlon 2400 xp (2000Mhz):llä
Heeeetkinen muuten. Luin tuota FAQ:a ja huomasin tämän:
Datatähti 2005 - tarkennuksia tehtäviin kirjoitti:
Kyllä, "ohjelmakoodin käyttämä aika" tarkoittaa juuri tätä time-komennolla saatua "user" aikaa.
Huvin vuoksi ajoin sitten Cygwinissä "time taika" ja sehän antoi user-ajaksi 0m0.015s jopa tällä 1200-MHz-koneellani! Eli tarkoittaako tuo todellakin, että "real" aika, joka oli tässä tapauksessa 0m1.784s ei vaikuta asiaan ollenkaan?
BlueByte kirjoitti:
Minkäslaisia ja tasosia tehtäviä siellä [loppukilpailussa] on?
Viime vuonna oli yksi varsin vaikea ohjelmointitehtävä ja pari kolme helppoa kirjoitustehtävää. Ohjelmointiin taisi olla aikaa kolme tuntia, kirjoittamiseen jonkun verran vähemmän.
Antti Laaksonen kirjoitti:
kolme helppoa kirjoitustehtävää
Millaisia aiheita niissä on? Siis tarvitseeko siihen jotakin erityistä tietämystä, kuten näissä alkukilpailun aiheissa, vai voiko niistä selvitä ihan yleistiedolla? Itse en ainakaan ihan suoralta kädeltä kirjoittaisi mistään noista tämän kerran alkukilpailuaiheista paljoakaan, kyllä siihen lähteitä tarvitsee.
Metabolix kirjoitti:
Millaisia aiheita niissä on?
Pikagooglauksella löytyivät vuoden -98 ja -02 loppukilpailutehtävät.
http://www.cs.uta.fi/~jyrki/datatahti-98/
http://staff.cs.utu.fi/datatahti/DTloppu-02/DT2002loppu.htm
Tein tuon taikaneliön vb.net:llä käyttäen "torus" menetelmää. Varsinaista koodia tuli noin 17 riviä. Menee reilusti alle sekunnin.
Kannattaa tosiaan huomata että tuon taikaneliö-tehtävän neliöt eivät ole perinteisiä taikaneliöitä, perinteisessä taikaneliössähän myös vinorivien summan tulee olla yhtä suuri kuin vaaka- ja pystyrivien.
tnb: Eipäs paljasteta algoritmeja ennen kisan päättymistä.
fawkz: Saahan ne vinorivitkin silti täyttää oikein.
Kuinka moni on jo saanut pacman-tehtävän ratkaistuksi? Oma algoritmini toimii yhden palikan levyisillä labyrinteillä täysin, mutta jos asettaa vaikka avoimelle laudalle pari voimatäplää, se jauhaa kaikkia tyhmiä vaihtoehtoja ja jumittaa, enkä keksi enää mitään, mitä voisin tehdä... Pitää kai tehdä koko roska alusta asti. Laitoin nyt kuitenkin ajastuksen, että laskeminen loppuu ajoissa, kun tuosta kerran saa 2/5 pistettä vaikka vastaus on liian suuri.
Itselläni on teoria mietitty loppuun Pacman-tehtävässä, ja luulenpa tietäväni myös, mitä algoritmia käytän, mutta kouluhommien takia ei ole ollut aikaa alkaa implementoimaan.
Niin ja fawkz, ne eivät ole perinteisiä myös siinä mielessä, että ne alkavat nollasta eivätkä ykkösestä. Luulen, että tästä syystä käyttämäni algoritmi ei täytä vinorivejä oikein.
Sillä ei ole mitään merkitystä, mistä numerosta neliö alkaa, kun jokainen ruutu on arvoltaan yhtä paljon suurempi ja ruutuja on joka rivillä sama määrä:
7 0 5 8 1 6 9 2 7 10 3 8 2 4 6 3 5 7 4 6 8 5 7 9 3 8 1 4 9 2 5 10 3 6 11 4 0 .. 8 1 .. 9 2 .. 10 3 .. 11
Jokaisessa on sekä suorien että vinojen rivien summa sama. Ensimmäisessä 12, toisessa 15, kolmannessa 18 ja neljännessä 21. Samassa kohti olevaa numeroa on aina vain suurennettu yhdellä, jolloin rivin summa kasvaa aina kolmella (3 * 1 = 3).
Metabolix kirjoitti:
fawkz: Saahan ne vinorivitkin silti täyttää oikein.
Metabolix: tietysti, tuntuisi kuitenkin että tuo Datatähden versio on helpompi ratkoa kuin "oikea" taikaneliö.
Metabolix kirjoitti:
Sillä ei ole mitään merkitystä, mistä numerosta neliö alkaa, kun jokainen ruutu on arvoltaan yhtä paljon suurempi ja ruutuja on joka rivillä sama määrä:
Muistan ajatelleeni samalla tavalla, mutta myös kokeilleeni eräällä neliöllä, eikä se toiminut. Tiedä sitten miksi - taisin vain kämmätä laskuissa. Testasin nyt parilla, ja hyvin toimii.
Mutta eivät ne kuitenkaan ole perinteisiä, kun eivät kerran ykkösellä ala. Nih!
Jaahas, nyt asiaa hieman tutkittuani vaikuttaisikin siltä ettei tuollainen Datatähti-taikaneliö ole sen helpompi generoida kuin perinteinenkään. Huomasin myös, että Datatähti-neliön generoimiseen kehittämäni algoritmi (eli vinoviivat eivät ole oikein) olikin todella samanlainen kuin nuo webistä löytyvät valmiit algoritmit perinteiselle neliölle.
Mutmjoo, pitänee alkaa katsella tuota Pakkimies-tehtävää.
EDIT:
--
Deewiant sanoi: "Huvin vuoksi ajoin sitten Cygwinissä "time taika" ja sehän antoi user-ajaksi 0m0.015s jopa tällä 1200-MHz-koneellani! Eli tarkoittaako tuo todellakin, että "real" aika, joka oli tässä tapauksessa 0m1.784s ei vaikuta asiaan ollenkaan?"
En usko että tuo 0m0.015s on oikea suoritusaika. Kannattanee kokeilla hommaa jollain Linux-systeemillä. Itse sain täsmälleen saman ajan user-ajaksi ajaessani MSVC:n tuottamaa binääriä Cygwin:n time:llä, mutta Cygwinin GCC:llä käännetty binääri antoi huomattavasti erilaisia aikoja.
fawkz kirjoitti:
Itse sain täsmälleen saman ajan user-ajaksi ajaessani MSVC:n tuottamaa binääriä Cygwin:n time:llä, mutta Cygwinin GCC:llä käännetty binääri antoi huomattavasti erilaisia aikoja.
Eiköhän käyttämäni MinGW:n GCC ole tarpeeksi samanlainen UNIX-GCC:n kanssa. En usko, että suuria eroja ilmenisi.
Itse otan ajastuksen vain yksinkertaisesti millisekunteina alusta loppuun (vaikka clock()-funktiolla). Jos siitä on 80% ylimääräistä, niin hyvä. Usein näissä tehtävissä taitaa olla melkeinpä niin, että jos on saanut aikaan hyvän algoritmin, se suoriutuu millä tahansa syötteellä selkeästi alle sekuntin. Jos ei, niin sitten lähetetään siinä muodossa, johon algoritmi on hiottu tiistai-iltaan mennessä. Lähdin taas pacman-ongelmaa kohti täysin uudesta näkökulmasta, joten eiköhän tästä jollakin algoritmilla selvitä. Vielä yksi konsti on hihassa, jos tämäkään ei onnistu...
Metabolix kirjoitti:
Itse otan ajastuksen vain yksinkertaisesti millisekunteina alusta loppuun (vaikka clock()-funktiolla).
Miten ihmeessä voit saada niin nopeasti 999:lläkin jos mittaat tuolla tavalla? Minulla menee ainakin 7-megaisen tekstitiedoston kirjoittamiseen reilut puolitoista sekuntia.
Jaa, tiedostonkäsittelyä ei tainnut tuossa vaiheessa vielä olla. Vedin vaan for-loopilla ohjelman läpi kaikilla sivunpituuksilla, tarkistin tulokset, ja printtasin kaikki väliajat ruudulle. Ei se tiedostonkirjoitus minulla silti noin kauan kestä, vaikka ei mahdukaan tuohon 0,1 sekuntiin.
Deewiant: en tarkoittanutkaan että Mingw:n GCC jotenkin eroaisi, vaan että jos yrität ajaa Cygwin:n "ulkopuolista" binääriä time:llä niin voit saada virheellisiä tuloksia. Ainakin minulla tuntui tulevan (Cygwin:n ulkopuolisilla binääreillä) koko ajan täsmälleen tuota samaa "0m0.015s"-aikaa. Pitää vähän tutkia asiaa vielä huomenna tai tänään.
Deewiant: kokeilin nyt tuota timeä Cygwinillä tyyliin "time notepad" ja viivyin Notepadissa hyvän tovin, tulokset:
real 0m12.114s user 0m0.015s sys 0m0.015s
Eli *älä* luota siihen aikaan.
Onko joku muu ratkaissut Pacman tehtävän. Toinen ratkaisuni on nopea, mutta joissain tapauksissa antaa väärän ratkaisun (ei osaa palata samaa reittiä takaisin).
Toinen ratkaisu antaa aina oikean vastauksen mutta hyytyy, jos pillereiden määrä kasvaa yli 10:n kun kenttä on 50*50.
Ratkaisua kannattaa hakea "keskilännen kaupankäynnistä".
mitään tietoa kuinka tarkasti noihin esseetehtäviin pitää vastata?
BlueByte: monet kysymyksistä tuntuvat olevan sen verran yksinkertaisia että tuskin niihin kovin pitkiä sepostuksia tarvitse kirjoittaa.
fawkz kirjoitti:
BlueByte: monet kysymyksistä tuntuvat olevan sen verran yksinkertaisia että tuskin niihin kovin pitkiä sepostuksia tarvitse kirjoittaa.
5-10 rivii max. ? Kvanttitietokone tehtävän ykköskohdan vastaukseen kun näyttää olevan tilaisuus sepittää paljon
Tai no onhan noihin muutamaan muuhunkin tilausuus sepittää paljon jotain ..
Eikös noihin jokaiseen kolmeen aiheeseen pidä tehdä yksi yhtenäinen essee? Kyllä siitä varmasti vähintään yhden A4:n jokaisesta aiheesta saa. Kuitenkin, jos tähän voisi vastata joku, joka on aiemminkin osallistunut..?
Tekstin sisältö on varmasti pituutta tärkeämpi. Jos kaikki kysytyt asiat on käsitelty kunnollisesti ja teksti on hyvin kirjoitettu, homman pitäisi olla hoidossa. Käytännössä sivun parin vastaus tehtävää kohden lienee hyvä.
Voisi osallistua... Hmm. Noi olis aika helppo väsätä (sanoo herra kaikkitietävä :S).
Mutta ehkä BASICILLA. Ei C++:lla.
Luuletteko, että alkukilpailusta voisi päästä läpi jos ei tuota pacman tehtävää osaa? Minun pacmanini on aivan sukka :(
Jos Pacman löytää edes jonkin reitin, niin sillä voi saada ajosta 2/5 pistettä, eli yhteensä 40% pisteistä. Eli mahdollisuuksia on huonollakin Pacmanilla (kuten omanikin toistaiseksi), mutta lukiosarjassa ei kannata silti toivoa liikoja. Hyvät esseet ja taikaneliö olisivat viimevuoden pisteytyksellä tuoneet 65/100 pistettä, ja jos Pacman saa edes jotakin oikein...
Juu, taidanpa luovuttaa, kun ei ole aikaa kyhäillä pacmaniin parempaa reitinhaku algoritmia ja koeviikkokin alkaa ensi viikolla.
Tosiaan taso hiukan noussut viime vuodesta. Taikaneliö oli kyllä melko helppo, 999x999 neliön putkauttaa jossain 1/100 sekunnissa, mut toi pacman, ei haisuakaan miten sen sais tehtyä tarpeeks nopeeks...
Minulla on nyt siihen peräti riittävän nopea algoritmi, kun nyt kävisi niin hyvä tuuri, ettei satu juuri sellaista tilannetta, jossa pieni mutta hankalasti paikattava aukko suunnittelussa antaa vahingossa liian suuren vastauksen... Voin sitten torstaina kertoa tarkemmin toteutuksesta (saattaapi olla aika omalaatuinen). En oikein jaksa kirjoittaa esseitä kun on aika niin tiukalla, toivottavasti peruskoulusarjassa pärjää ilmankin... Rohkea arvio olisi 100 pistettä taikaneliölle ja 85 pistettä Pacmanille, jos se ei mokaa kuin joka neljännessä ajossa. Tästähän tulisi viime vuoden pisteytyksellä jo 64.75 pistettä... Jos huomenna saa vielä jonkun esseen aikaan, niin sittenpä olisi semmoinenkin. Milloin nuo pitää muuten palauttaa? MAOLin sivuilla lukee kilpailuaikana "2.-16.11.", mutta kilpailuohjeissa lukee 17.11.
Vaikea päätös: Lähettääkkö vastaukset Pascalilla vai C:llä tehtyinä?
Minäkin taidan luovuttaa... Taikaneliöstä tulisi täydet, mutta on nyt ollut kaikennäköisten koulutöiden ja keskiviikkona alkavan koeviikon kanssa sen verran tärkeämpääkin puuhasteltavaa, ettei sitä Pacmania ole ehtinyt säätää. Teoria on täysin mietitty läpi mutta toteutus ei. 40 pistettä voisi saada, jos laittaa sen vain tarkistamaan, onko reittiä alusta loppuun ja jos sellainen löytyy, palauttamaan 65535 tai jotain yhtä hauskaa. Mutta kun ei ole aikaa kirjoittaa aineisiinkaan mitään fiksua ja epäilen, että 140 pistettä riittää lukiosarjassa, niin ei sitä oikein viitsi.
Jos riittää, niin sittenpähän ketuttaa :-) Mutta totta puhuen epäilen pärjääväni loppukilpailussa, en minä saa mitään fiksua ohjelmoitua niin lyhyessä ajassa ;-)
Itse osallistun näillä näkymin. Taikaneliö on erittäin nopea, mutta Pacmania en saanut niin nopeaksi että voisin olla varma sen pärjäämisestä. Mukava nähdä sitten joskus millaisia virityksiä muut ovat tuohon Pacman-tehtävään saaneet aikaiseksi. Nyt pärjääminen on pitkälti siitä kiinni, millaisia softalle syötetyt kartat ovat rakenteeltaan.
Kannattaa muistaa, että mitään ei menetä lähettämällä tuotoksiaan kilpailuun. Edelleen luulen, että loppukilpailussa olisi ihan mukava käväistä vaikkei mitään saisikaan aikaan :-)
Deewiant kirjoitti:
Minäkin taidan luovuttaa... Taikaneliöstä tulisi täydet, mutta on nyt ollut kaikennäköisten koulutöiden ja keskiviikkona alkavan koeviikon kanssa sen verran tärkeämpääkin puuhasteltavaa, ettei sitä Pacmania ole ehtinyt säätää. Teoria on täysin mietitty läpi mutta toteutus ei. 40 pistettä voisi saada, jos laittaa sen vain tarkistamaan, onko reittiä alusta loppuun ja jos sellainen löytyy, palauttamaan 65535 tai jotain yhtä hauskaa. Mutta kun ei ole aikaa kirjoittaa aineisiinkaan mitään fiksua ja epäilen, että 140 pistettä riittää lukiosarjassa, niin ei sitä oikein viitsi.
Jos riittää, niin sittenpähän ketuttaa :-) Mutta totta puhuen epäilen pärjääväni loppukilpailussa, en minä saa mitään fiksua ohjelmoitua niin lyhyessä ajassa ;-)
Hih.. ensi vuonna sitten :)
Poistin "vahingossa" nuo taikaneliöden ja pacmanien sourcet ja mitään esseitä kerkiä koeviikon takia tehdä joten pahemmin enää mitään tuotoksia lähetetä :)
Datatähti kilpailun palautus aika lienee ohi, joten tässä Pacman-ongelmaan ratkaisu tien etsimiseksi lähtöruudusta maaliruutuun:
- mallinnetaan peliruudukko nxn taulukolla Sakko
- mallinnetaan reitin tutkimissen tilanne nxn taulukolla Tila
- mallinnetaan polku n x n taulukolla Edellinen()
- Täytetään Sakko() suurilla luvuilla, Tila() arvoon Epätosi
- Laitetaan aloitusruutuun Sakoksi nolla ja Tilaksi tosi eli tutkimattomia teitä eteenpäin on vielä
Pääluuppi:Etsi niin kauan kuin löytyy ruutu, jonka Tila=tosi
- etsi ruutu (A), jossa tila on tosi : laita Tila epätodeksi
- tutki viereiset ruudut (b)
-- jos tutkittavan ruudun sakko on suurempi kuin 1 + sakko ruudussa A niin
---laita ruudun B sakoksi ruudun A sakko +1
---laita ruudun B Tila todeksi (=kannataa tutkia eteenpäin)
---laita ruudun B Edellinen(B) osoittamaan ruutua A
Pääluuppi end
Seuraamalla Maaliruudusta takaperin Edellinen taulukon avulla, saadaan selville lyhyin reitti lähdöstä maaliin.
Tee sitten taulukko jossa on kaikki mahdolliset yhteydet pilleristä pilleriin koordinaatteina.
Etsi em. menetelmällä jokaiselle pilleri-parille lyhyin yhdysreitti ja laske sen pituus.
Pilleri-yhteydet muodostavat nyt verkon jossa on n x (n-1)/2 yhteyttä, joissa siirtymäsakkona on yhteyden pituus.
Sovella em. lyhyimmän reitin etsintää ko. yhteysverkkoon siten että sakko kasvaa vain jos uusi yhteys on suurempi kuin jo käytössä olevat yhteydet!!
Kun pääluuppi taas päättyy, on maaliruudun sakko sama kuin suurin pillerien väli optimireitillä. Reitin saat selville suraamalla yhdysverkoa takaperin Edellinen() taulukon avulla.
Menetelmä hyytyy (yli 1 sek,), jos pillereiden määrä kasvaa kymmeniin.
menetelmää (ongelmaa) kutsutaan myös (keskilännen) kauppamatkustajan ongelmaksi. Uudempi nimi on A* eli A-star.
Reitinetsinnän lisäki menetelmällä voi myös optimoida saavutettavissa olevaa lopputilaa(ruutua) tai etsiä lähtöruudut, joista loppuruutu on saavutettavissa pienimmällä sakolla. Eli peliohjelmoija saa tällä aikaiseksi tekoälyä peliinsä. Algoritmi laskee ongelman kokoa "N potesiin N" ongelmasta "2 potenssiin N" ongelmaksi.
Pistä vb.net ratkaisun kunhan joudan.
tnb: Palautusaikaa on vielä tämä päivä :-)
Pitänee katsella tuota antamaasi algoritmia joskus paremmalla ajalla tarkemmin, oma ratkaisuni oli täysin erilainen ja en ollut siihen itse ollenkaan tyytyväinen.
tnb kirjoitti:
menetelmää (ongelmaa) kutsutaan myös (keskilännen) kauppamatkustajan ongelmaksi. Uudempi nimi on A* eli A-star.
Eikös kauppamatkustajan ongelma ole mahdoton ongelma, jonka muistaakseni DNA-tietokoneen piti pystyä ratkaisemaan? Eli siis ainakaan nykykoneilla se ei onnistu, joten tämä Datatähti-kysymys ei liene sama asia ;-). Ja A* on vain nopea reitinhakualgoritmi, jota ei ole mikään pakko käyttää tässä tehtävässä (mutta varmaan kannattaa sen nopeuden vuoksi, itsekin tuota ajattelin käyttää).
Itse ratkaisin Pacman-tehtävän luomalla kaikkien paikkojen kautta viimevuoden Gasoline-tyylisen reitinhakujärjestelmän. Kun tämä osoittautui aivan liian hitaaksi, lisäsin alkuun systeemin, joka täyttää tarpeettomia ruutuja seinillä. Tietyissä tilanteissa täyttäminen saattaa kuitenkin aiheuttaa liian pitkän reitin, vaikka omilla testeilläni niin ei käynytkään.
Minä toteutin Pacman-ohjelman niin, että jokaisessa käytäväpalassa on tieto pienimmästä tarvittavasta voimapillereiden määrästä loppuun asti. Ohjelma tutkii sokkelon läpikotaisin ja kulkee eteenpäin, kunnes samasta paikasta on jo parempi reitti maaliin. Silloin ohjelma palaa vanhaa reittiä takaisin.
Metabolix kirjoitti:
- - lisäsin alkuun systeemin, joka täyttää tarpeettomia ruutuja seinillä.
Minäkin mietin ensin tämmöistä, mutta tehtävä osoittautui sen verran hankalaksi, että päätin luopua ajatuksesta.
Kilpailun tuloksia voi sitten odottaa ensi vuoden alussa.
Itse sain täyttösysteemin tämänhetkiseen tilanteeseensa aika helposti, ja jos olisin aloittanut sillä menetelmällä jo aiemmin, olisin saanut viimeisetkin ongelmat korjatuksi. Ehdin välissä kokeilla jo muutamaa muutakin mahdollisuutta, mm. sitä, että lasken lopusta alkuun päin jokaiselle ruudulle lyhimmän vastauksen, mutta tätä tapaa en saanut riittävän nopeaksi, laskuaikaa kului useita sekunteja.
Tällätään tähän nyt vielä tuon taikaneliön ratkaisu tiivistettynä:
/*
..0.. ..0.. ..0.. ..0.. ..0.. ..0.. ..0.. GN07E
..... ..... ..... ..... .4... .4... .46.. M46DF
..... ..... ..... 3.... 3.... 35... 35... 35CJL
..... ..... ....2 ....2 ....2 ..... ....2 9BIK2
..... ...1. ...1. ...1. ...1. ..... ...1. AHO18
*/
int Sivu; // Luetaan tiedostosta
int MaxLuku = Sivu * Sivu; // Luku, joka ei enää tule neliöön
int I, X, Y;
int Nelio[999][999]; // Piti oikeasti varata myöhemmin (malloc, new), koska muuten ohjelma kaatui.
for (X = 0; X < Sivu; X++)
for (Y = 0; Y < Sivu; Y++)
Nelio[X][Y] = MaxLuku;
X = Sivu / 2;
Y = 0;
// Laitetaan kaikki luvut 0 .. Sivu^2
for (I = 0; I < MaxLuku; I++)
{
// Tarkistetaan reunojen varalta
if (X >= Sivu) X -= Sivu;
if (Y < 0) Y += Sivu;
// Tarkistetaan, että ruutu on tyhjä
if (Nelio[X][Y] < MaxLuku)
{
Y += 2;
X--;
}
// Tarkistetaan reunojen varalta
if (Y >= Sivu) Y -= Sivu;
if (X < 0) X += Sivu;
// Asetetaan luku ja siirrytään seuraavaan
Nelio[X][Y] = I;
X++;
Y--;
}
// Ja sitten kirjoitetaan tiedostoon.Mahtavatkohan testauksessa käytetyt syötöt ja mahdollisesti testisoftat tulla tänä vuonna jonnekin esille? Lisäksi olisi mukava ihan mielenkiinnosta nähdä time-ohjelman tulostukset jokaiselle syötölle.
Aihe on jo aika vanha, joten et voi enää vastata siihen.