Uusi putkapostitehtävä on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Tässä tulee vielä lisätehtävä, jonka vastauksen voi lähettää tähän keskusteluun esim. ROT13-salattuna: Kehitä mahdollisimman tehokas algoritmi, joka tarkistaa, onko ruudukossa neljä sormustinta, jotka muodostavat suorakulmion. Kun ruudukon sivunpituus on n ruutua, O(n4)-aikainen algoritmi on helppoa keksiä. Mutta kuinka paljon pystyt vielä parantamaan tästä?
Alle 10:n sormustimen ratkaisuja ei muuten hyväksytä, joten ei kannata lähettää sellaisia. Jos se lukeekin jossakin, tämä tieto ei rekisteröitynyt minun silmiini :-)
Iltapuhteeksi voisi yrittää rakentaa kunnon ratkaisua. Mukava pulma.
Ihan mukavan oloinen tehtävä minustakin, mitä nyt olen katsellut. Voisipa koittaa jonkun ratkaisun kehitellä, kun muutamaan edelliseen en ole osaa ottanut.
Lisäksi tuota lisätehtävääkin voisi koittaa, vaikkakaan en kovin paljoa noihin aikavaatimuuksiin ole tutustunut.
Vartin verran meni tehtävän lukemisesta 24 sormustimen ratkaisun lähettämiseen, tehtävä ratkesi ohjelmoimatta. Heti perään keksin vielä paljon näppärämmän ratkaisun, kun havaitsin yhteyden erääseen aiempaan putkapostitehtävään.
Lisätehtävään taitaa tulla suoralta kädeltä O(n3)-aikainen ratkaisu. Paremman pohtimiseen täytynee käyttää muutama lisäminuutti.
Käsin kokeilemalla säälittävät 19, bruteforcella ei onnistu millään / ei ole sataa vuotta aikaa odottaa laskua kun vaihtoehtoja on 2^64 = paljon, joten...
... cvgv xbxrvyyn enaqbzvn. 2 zvywbbann xregnn gälfva fnghaanvfryyn ynvggnwnyyn, xhvgraxva wbxn ynvgbyyn gnexvfgnra rggrv ghyr fhbenxhyzvbvgn nagnn hfrvgn xlzzravä engxnvfhwn 24:ääa zhhgnzna frxhaava fvfäyyä.
Yhdyn Metabolixiin sen verran, että varttihan tuossa meni ratkoessa käsin, eli aika helppo putkaposti, kun minäkin sen osasin (ja tämähän oli ensimmäinen, johon osallistuin)! Ero minun ja Metabolixin tavassa on se, että sain lopullisen avun tyttökaveriltani, joka nöyryytti minua ratkaisemalla tämän paperille juuri ennen omaa tulostani. Sittenpähän yhdessä piirtelimme tarkistussuorakulmioita. :)
User137 kirjoitti:
Käsin kokeilemalla säälittävät 19, bruteforcella ei onnistu millään / ei ole sataa vuotta aikaa odottaa laskua kun vaihtoehtoja on 2^64 = paljon - -
Millaisen bruteforce-ratkaisun olet kehittänyt? Oman ohjelmani tuloste on muodoltaan tällainen:
C:\nyrre\ohjelmointi\harjoitukset>pposti 0: 22 1: 22 2: 23 3: 22 4: 21 5: 22 6: 23 7: 22 8: 23 9: 22 10: 22 11: 22 12: 23 13: 23 14: 22 15: 22 16: 21 17: 21 18: 21 19: 21 20: 22 21: 22 22: 23 23: 22 24: 23 25: 24
Toisella kerralla:
C:\nyrre\ohjelmointi\harjoitukset>pposti 0: 22 1: 22 2: 21 3: 24
Ratkaisussa kesti reilusti vähemmän, mitä noiden rivien tulostamisessa printf:n avulla. Lopullinen ratkaistu lauta tulostui lauta.txt-tiedostoon. Tosin en ole varma siitä, luokitellaanko omani bruteforceksi, sillä olihan minulla "pari" ehtolausetta ja hieman logiikkaa seassa. Tarkoitus oli kuitenkin loopata ratkaisusilmukka 1000 kertaa läpi (ohjelma ehti mussuttaa neljäskymmenesosan siitä). ;)
edit. ups, en huomannut lukea tarkasti ROT13-viestiäsi (väsymyksen piikkiin)! Noh, ihastelkoon joku muu ohjelmani huimaa saavutusta.
Minä aloitin ratkaisun varsinaisen etsimisen 2x2-laudalta ja kasvatin laudan kokoa, josko vaikka löytäisin jonkin säännön. Kovin hyvää sääntöä en löytänyt ja skippasin koon 7x7, kun rupesi kyllästyttämään. Ratkaisu 8x8:aan löytyi helposti, mutta pitihän sitä vähän pohtia, että se varmasti on paras mahdollinen. Nyt olen jotenkuten siitä vakuuttunut, että 24 on maksimi.
Tästä saisi pelin. Aloitetaan tyhjältä laudata ja vuorotellen laitetaan yksi sormustin siihen. Pelin voittaa, jos voi oman vuoronsa alussa ennen siirtoaan osoittaa laudalla olevan suorakulmion.
Oikea ilmaisu on "Hä, hä! Tuossa.", jos pelaatte kotona :) :)
Pääsin about 5 minuutin mietinnällä tulokseen 22. Loppujen lopuksi tuo on todella looginen ja yksinkertainen tehtävä.
Kun nyt niin moni on jo 24 saanut niin millaisia optimointikikkoja tuohon olette keksineet? Tietääkseni yhtäläistä 24 tuloksissa on että joka pysty ja vaakarivillä näyttää olevan aina 2-4 nappulaa, mikä on vain hatara arvaus. Tuokaan optimointi ei silti näytä riittävän "bruteforce" ohjelman ajamiseen joka siis käy läpi kaikki mahdolliset lailliset vaihtoehdot (rekursiivisella funktiolla).
Kaikki mahdolliset asettelut voi käydä läpi, mutta wbaxva ireena bcgvzbvagvn gneivgnna. Ehhqhxba fnenxxrvgn ibv nwngryyn xnuqrxfna ovgva zhbqbfgnzvan yhxhvan, wbgra ehhqhxxb flagll inyvgfrznyyn xnuqrxfna gäyynvfgn yhxhn. Gäzä abcrhggnn cnywba frxä ehhqhxba zhbqbfghfgn rggä fhbenxhyzvbruqba gnexvfghfgn. Yvfäxfv fnenxxrvgn ibv invugnn xrfxraääa zvryva zääeva, wbgra unhffn ibv yvfäxfv inngvn, rggä inyvggnin yhxh ba rfvz. xnvxxvn rqryyvfvä yhxhwn fhherzcv. Zhvgnxva yäurfglzvfgncbwn xnvxxvra nfrggryhwra fryivglxfrra ba ineznfgv byrznffn.
Paperilla sain minuutissa tai kahdessa tuloksen 21. Kai tuosta miettimällä saisi vielä enemmän.
Mitään hienompaa teoriaa en ole vielä keksinyt noiden ruudukoiden muodostukseen. Nyt on meneillään brute force -ratkaisu, tosin vaatii kovasti optimointia. Vaatii hyviä optimointeja, jos tahtoo voimalla ratkaista. Pelkästään 20 nappulaa kuin voi asetella laskujen mukaan 1,96*10^16 tavalla ja niiden muodostaminen on jo oma hommansa.
Vaihtoehtoja pitäisi saada rajattua pois aika runsaastikin ja yksinkertaisia konsteja pitäisi löytyä/löytää.
Voisi koittaa tuota omaa voimaan perustuvaa ratkaisua sen verran kehitellä, että jonkinlaisen tuloksen sillä saa. Katsoo mitä tästä syntyy.
Toinen ratkasu olisi tietysti keksiä joku hieno algoritmi mikä ratkaisisi ongelman nopeasti ja elegantisti. Sitä voisi myöhemmin miettiä.
Tämä tehtävä oli luonteeltaan hyvin samanlainen kuin aikaisempi jalkapalloliiga. Molemmissa 'hienon' ja täydellisen ratkaisun keksiminen on vaikeaa tai laskennallisesti työlästä, mutta molempiin tehtäviin löytyy helposti 'hyvä' ratkaisu, joka on usein lähellä täydellistä. Pienillä ruudukon suuruuksilla, tuo hyvä ratkaisu on usein sama kuin täydellinen ratkaisu. Esimerkiksi ruudukon koilla 16,32,64 löytyy nopeasti ratkaisut joissa sormustimia mahtuu 67,189 ja 477 kappaletta. Kaksi ensimmäistä lienee parhaita ratkaisuja ja kolmaskin aika lähellä.
Xälggäzäav engxnvfh abvffn zbyrzzvffn grugäivffä ba nvina crehf ynnghn byrin fvzhybvgh wääuqlglf (fvzhyngrq naarnyvat) ryv xälgäaaöffä fbcvinfgv buwnggh fnghaanvfinyvagn, wbffn nyhffn inyvagnna yvvggll rarzzäa fnghaanvfhhggn wn ybcchffn fvveelgääa inva xbugv cnerzcnn engxnvfhn.
Tuohon lisätehtävään pikaisesti miettimällä on olemassa algoritmi, joka toimii tyhjälle taulukolle ajassa O(n^2) ja täydelle O(n^3/2), jos halutaan löytää kaikki suorakaiteet.
Crehfvqrnygnna fryynvara, rggä ehhqhxxbn xälqääa yäcv eviv xreenyynna wn xnvxxv evivygä yölglarrg fbezhfgvacnevg zrexvgääa ehhqhxba xbxbvfrra nchgnhyhha gnv invugbrugbvfrfgv unwnhghfgnhyhha, wbf zhvfgvn cvgää fääfgää. Wbf xnuqrygn evivygä yölgll fnzn cnev, ba ehhqhxbffn aryvö. Gäffä gnhyhxba yäcvxälagv ba B(a^2) wn cnevra rgfvzvara evivygä B(a/2).
Lisätehtävä:
Zrexvgääa gnexvfgrggninn nfrgryznn zngevvfvan, wbaxn nyxvb ba abyyn, wbf ehhgh ba gluwä wn lxfv, wbf fvvaä ba fbezhfgva. Xnuqra gäyynvfra zngevvfva innxneviva cvfgrghybba ghyrr fhzzna bfnxfv neib lxfv, wbf infgnnivffn cnvxbvffn zbyrzzvffn evirvffä ba fbezhfgva, zhhgra abyyn. Xbxb cvfgrghyb xregbb fvvf xhvaxn zbagn fnznffn cnvxnffn byrinn fbezhfgvagn aävyyä evirvyyä ba.
Wbf zngevvfva xregbb genafcbbfvafn xnaffn, ghybba ghyring rev innxnevivra cvfgrghybg. Cääqvntbannyvyyn bing innxnevivra cvfgrghybg vgfrafä xnaffn, zhggn wbf zhh nyxvb xhva cääqvntbannyvyyn byrin ba neibygnna fhherzcv xhva lxfv, xregbb fr, rggä fra ghbggnarvyyn evirvyyä ba byyhg nvanxva xnxfv lugrvfgä nyxvbgn. Fvvfcä wbf wn inva wbf wbxnvara ghybzngevvfva rv-qvntbannyvnyxvb ba lxfv gnv abyyn, ba gnexvfgrggnin engxnvfh xryibyyvara.
Xnyyrva bcrenngvb ba zngevvfvghyb. Fr ba nyyr a:a xbyznggn cbgraffvn, wbgra gäzä ba cnenaahf lyyäbyrinna.
Ratkaisuni lisätehtävään on sama kuin FooBatin, ja samasta vanhasta tehtävästä sain apuakin, löytyi tiettyjä yhtäläisyyksiä.
Inefvanvara grugäiä engxrfv wbaxva ireena ryrtnagvzzva: Znvavgha cnevruqba crehfgrryyn xhxva cnev fnn rfvvaglä inva luqryyä evivyyä. Revynvfvn cnerwn xnuqrxfna ehhqha yrilvfryyr evivyyr yölgll xnxfvxlzzragäxnuqrxfna. Xha uhbzvbvqnna, xhvaxn zbagn cnevn evivyyr ghyrr zvyyäxva fbezhfgvazääeäyyä, wn zhbqbfgrgnna gäzäa cbuwnygn rev znuqbyyvfhhqrg, aäuqääa, rggä ba xnxfv yhxhzääeäwnxbruqbxnfgn, wbvyyn fbezhfgvzvn znughvfv lugrrafä xnxfvxlzzragäivvfv. Aävfgä xhzcvxnna rv xhvgraxnna gbvzv xälgäaaöffä (xbfxn evivyyr zhbqbfghing cnevg rviäg byr gbvfvfgnna evvcchznggbzvn), wbgra gälgll ynfxrhghn fnnghha ghybxfrra. Aäzä fbezhfgvzrg gnnf ibv nfrgryyn gälfva ybbtvfrfgv xbyzrn ivabevivä (rafvzzävara, gbvara wn arywäf) cvgxva.
Innostuinpa leikkimään vähän JavaScriptillä, ja tällaisen sain aikaiseksi:
http://cs.helsinki.fi/u/partel/misc/putka/
Voittaa ainakin kynän ja paperin.
(toimii IE:llä vähän huonosti, mutta se taitaa kiusata vain Anttia ;)
Tämä tehtävähän on siinä mielessä vähän ikävä, että optimaalinen ratkaisu löytyi ainakin omalla kohdallani testattuani ensimmäistä ideaani. 24 saa yksinkertaisesti ihan sillä, että nybvggnn xrfxrygä, ynvggnn fcvennyvzhbqbffn wbxnvfra ehhqha wäewrfglxfrffä wbxn rv ivryä yhb fhbenxhyzvbgn. Jokainen voi sitten selittää itselleen miksi tuo toimii.
map_ kirjoitti:
Innostuinpa leikkimään vähän JavaScriptillä, ja tällaisen sain aikaiseksi:
Voisitko vielä lisätä mahdollisuuden muuttaa ruudukon kokoa? Nimittäin muunkin kokoisia ruudukoita olisi kiinnostavaa tutkia kuin vain shakkiruudukkoa.
Seuraava haaste on kehittää jokin yleinen selkeä menetelmä, jota noudattamalla muodostuu paras tulos ruudukon koosta riippumatta. Lisäksi menetelmän toimivuus olisi hyvä perustella tavalla tai toisella. Menetelmän tulisi olla sellainen, että ruudukon voisi täyttää aivan suoraviivaisesti ja suuretkin ruudukot syntyisivät nopeasti. Esim. jos Laitisen menetelmä tuottaisi aina parhaan tuloksen, se olisi esimerkki tällaisesta menetelmästä (mutta tuottaako se?).
Hieman osviittaa tutkimuksiin saa osoitteesta:
Antti Laaksonen kirjoitti:
Voisitko vielä lisätä mahdollisuuden muuttaa ruudukon kokoa?
Lisätty.
Testasin tuota map_in javascript-viritelmaa ja sain 24.
Samoin, sillä (rot13) fcvennyvyyn.
[rot13]Testaanpa vain onko täällä toiminnassa tommoinen rot13-tagi.[/rot13]
EDIT: Eipä ole, mutta voisi olla aika kätsy?
Totta.
Alg gbvirraar gbgrhghv!
Byv cnxxb grfgngn.
Nakyy ei-sotkettuna tuossa uusin viesti -lootassa.
Helpohko. Onkohan näppärää tapaa todistaa ilman massiivista tapaustarkastelua, että laudalle ei mahdu 25 sormusta?
^
Kirjoitin ohjelman, joka kykeni löytämään 24 sormustimen ratkaisun max. 25 yrityksellä. Se ei kyennyt löytämään yhtäkään 25 sormustimen ratkaisua edes kymmenellätuhannella yrityksellä, joten en usko laudalle mahtuvan 25 sormustinta, ellei se sitten ole todella harvinainen tapaus.
Menetelmäni perustui satunnaisten koordinaattien arpomiseen. Ohjelma arpoo koordinaatin, tarkistaa, onko laudalla siinä kohdassa sormustinta. Jos on, arvotaan koordinaatteja, kunnes vapaa paikka löytyy. Kun vapaa paikka löytyy, ohjelma tarkistaa, muodostuuko laudalle kyseisen siirron jälkeen suorakulmio. Jos muodostuu, palataan arvontavaiheeseen. Tätä toteutetaan maksimissaan sata kertaa / siirto. Jos sadalla yrittämällä ei löydy toimivaa siirtoa, puhdistetaan lauta sormustimista ja aloitetaan alusta. Ohjelman tulosteen löydät aiemmasta kommentistani. Koodia voin jakaa, jos joku haluaa selata sitä (mitä kylläkin epäilen...).
Aihe on jo aika vanha, joten et voi enää vastata siihen.