Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointiputka: Putkaposti 2: Ruudukkoanagrammi

Sivun loppuun

Antti Laaksonen [14.10.2005 16:20:57]

#

Nyt uusi tehtävä on näkyvillä:
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ruuana

Tämä tehtävä on haastavampi, mutta kaikki oikeaan muodostelmaan johtavat siirtosarjat hyväksytään.

JTS [14.10.2005 18:19:35]

#

Kysytään nyt että ymmärsinkö nyt varmasti oikein oikean alanurkan kirjain "A" on tämä mainostettu "tyhjä ruutu"?

Tuxe [14.10.2005 18:21:12]

#

Tuonhan piti vaihtua kuukausittain, mutta nyt on kulunut vasta viikko. En ehtinyt ratkaista ensimmäistäkään kun vasta eilen huomasin sen. Voisiko nuo vanhatkin tehtävät jättää saataville?
Mielestäni olisi myös hyvä idea lisätä tuonne se keskustelualue, jollaista joku jo ehdottikin. Ja niin että vain oikean vastauksen lähettäneillä on pääsy sinne.

Antti Laaksonen [14.10.2005 18:21:21]

#

JTS: Ymmärsit oikein. Tyhjän ruudun kohdalla on aina A-kirjain ruudukon pohjakuvioinnin takia.

Antti Laaksonen [14.10.2005 18:25:30]

#

Kaikki tehtävät ovat sivulla:
https://www.ohjelmointiputka.net/postit.php

Tämä tehtävä ilmestyi siksi jo nyt, koska ensimmäinen osoittautui varsin helpoksi. Ainakin aluksi tehtävien julkaisutahti on epäsäännöllinen.

JTS [14.10.2005 23:10:52]

#

182, mutta ainakin algoritmi on 100% oma... Pitänee koittaa parantaa vielä (tai no samapa tuo, kunhan en viimeiseksi jää ;)

Latska [14.10.2005 23:40:12]

#

Et jää. Minun satunnaislukuihin perustuva puolivalmis algoritmi on varmasti huonompi.

peran [14.10.2005 23:42:23]

#

Onkohan Antilla haluja/mahdollisuuksia vertailla ensimmäisen putkapostin tuloksia, ja lähetellä eri vastauksia?
Erityisesti kiinnostaisi tietää kenen ratkaisu on otollisin Ordo-arvo ja kenen ratkaisu tekee nopeimmin 1-1000000 alueen.
Tämä toinen tuli sen verran nopeasti, että taidan passata sen.

P.S. Voisikohan putkapostin sykliä vähän pidentää, jotta päästään katsomaan eri ratkaisuehdotuksia, ja keskustelemaan niistä.

Latska [14.10.2005 23:45:26]

#

peran kirjoitti:

P.S. Voisikohan putkapostin sykliä vähän pidentää, jotta päästään katsomaan eri ratkaisuehdotuksia, ja keskustelemaan niistä.

Antti taisi sanoa tuossa edellisessä aiheessa, että tämä saattaa olla aluksi vähän epämääräinen, mutta sitten tämä vakiintuu kyllä.

Kahkonen [16.10.2005 03:25:08]

#

Jotain vinkkiä voisi antaa tähän tehtävään. En ole näitä liikkuvien laattojen pelejä tottunut vääntämään.

VilleP [16.10.2005 11:56:34]

#

Kahkonen kirjoitti:

Jotain vinkkiä voisi antaa tähän tehtävään. En ole näitä liikkuvien laattojen pelejä tottunut vääntämään.

Voithan ainakin aluksi kaivaa jostain vastaavankaltaisen pelin esiin (esim. sähköisessä muodossa hakukoneen avustuksella) ja yrittää etsiä jonkinnäköistä ratkaisumenetelmää vaikka käsin. Jos intoa riittää, tehokkaampien ratkaisujen löytämiseksi kannattanee tutustua yleisemmin tekoälyohjelmoinnin teoriapuoleen (internetistä löytyy).

Antti Laaksonen [16.10.2005 12:36:03]

#

Kaikki putkapostit jäävät arkistoon, eli ne voi ratkoa jälkeenpäinkin. Myöhemmin julkaistaan toki myös tehtävien ratkaisutapoja sekä sanallisina että koodiesimerkkeinä. Tarvittaessa voidaan antaa myös vinkkejä hankaliin tehtäviin.

setä [18.10.2005 21:17:36]

#

Kyllä Antti on nyt kehitellyt kinkkisen tehtävän, jossa oma äly sopivan ohjelman myötäilemänäkään ei näytä pärjäävän tekoälylle. Mielenkiinnolla odottelen noita 54-siirron ratkaisuja.

ajv [19.10.2005 12:10:41]

#

Joo, erittäin mielenkiintoinen tehtävä. Ei tule omaan pieneen mieleeni suoraan mitään kuningasideaa tuon ratkaisemiseksi. Täytyy yrittää jotain tuossa viikonloppuna jos kerkeis.

Chiman [21.10.2005 12:00:01]

#

Oikein hyvä tehtävä. Tälläkin kertaa tuli laadittua algoritmi kokonaan omin avuin, vaikka netistä löytyisi runsaasti apuja. Duunijutuissa ei kannata lähteä liikaa säveltämään itse ja tuhlaamaan siten aikaa, mutta tällaisten parissa on mukava testata omia taitojaan.

Taidan tyytyä tuohon tulokseen 78.

Kahkonen [23.10.2005 01:00:43]

#

Hmm... millä nimellä tämän tyyppisiä pelejä edes kutsutaan?

Kahkonen [23.10.2005 22:20:40]

#

Noista tehtävistä voisi olla linkit tänne keskusteluun...

Jaska [25.10.2005 02:06:02]

#

Kahkonen kirjoitti:

Hmm... millä nimellä tämän tyyppisiä pelejä edes kutsutaan?

Olen ainakin yhdestä tekoälyn kurssiprujusta lukenut nimen liukupeli.

egaga [25.10.2005 13:20:59]

#

AI: A Modern Approach -kirjassa tämän tyyppisiä kutsutaan sliding-block puzzle -peleiksi. Suomennos voisi olla vaikkapa liukulaattapeli.

setä [25.10.2005 19:51:09]

#

Antti Laaksonen kirjoitti:

Kaikki putkapostit jäävät arkistoon, eli ...

Tuo linkki arkistoon voisi olla myös Putkapostin tehtäväsivuilla eikä vain tällä kekustelualueella.

Metabolix [25.10.2005 19:53:38]

#

Sehän onkin, otsikossa nimittäin. "Putkaposti: "

setä [25.10.2005 20:18:14]

#

Niinpä onkin. Se ei vaan näkynyt kuin viemällä kohdistin otsikon päälle. Siis ei näy sinisenä ja alleviivattuna kuten linkit yleensä.

Megant [25.10.2005 20:25:37]

#

Eikö se kannattaisi lisätä tuonne linkkiriville?

ajv [25.10.2005 23:21:56]

#

Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
Voi koittaa pärjääkö oma äly noille tekoälyille :)

Seuraavaksi vois alkaa miettiin sitä tekoälyy tohon

VilleP [26.10.2005 10:12:39]

#

ajv kirjoitti:

Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
Voi koittaa pärjääkö oma äly noille tekoälyille :)

Seuraavaksi vois alkaa miettiin sitä tekoälyy tohon

Kätevä ohjelma. Putkapostin ratkomista ajatellen varsin hyödyllisiä ominaisuuksia olisivat vielä UNDO-toiminto ja käytetyn siirtosarjan tulostaminen.

coaster [26.10.2005 17:20:27]

#

ajv kirjoitti:

Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
...

Aivan upea!

Mutta pakko on sanoa, että siinä on pieni bugi (toisinaan), eli joskus siinä pystyy siirtymään vinottain.

Deewiant [26.10.2005 19:37:50]

#

coaster kirjoitti:

Mutta pakko on sanoa, että siinä on pieni bugi (toisinaan), eli joskus siinä pystyy siirtymään vinottain.

Jep. Kahdesta kohtaa onnistuin tuossa: kohdasta (1, 1) kohtaan (2, 0) ja kohdasta (2, 2) kohtaan (3, 3) - jossa (0, 0) on vasen alakulma ja (3, 3) oikea yläkulma.

Tuo jälkimmäinen näyttäisi onnistuvan vain, jos siitä oikeasta yläkulmasta on siirretty palikka vasemmalle - alaspäin-siirron jälkeen ei bugaa.

Megant [26.10.2005 20:16:02]

#

Ja palikan saa myös hyppäämään yhden "yli".

ajv [26.10.2005 20:33:34]

#

Huppista joo :) Sallitut siirrot on taulukossa ja sen taulukon nollaaminen siirron yhteydessä oli unohtunu tehä loppuun... Nyt pitäs toimia paremmin.

Jtm [05.11.2005 16:36:29]

#

Eikös niitä putkaposteja pitänyt tulla kuukausittain?

ezuli [05.11.2005 18:13:53]

#

Kuukausittain ei tarkoita että uusi tulisi jokaisen kuukauden alussa.

Jtm [09.11.2005 20:10:18]

#

No nyt on jo mennyt se kuukausi, jos tarkkoja ollaan :-P

Metabolix [09.11.2005 20:24:45]

#

Ei, ei ole. 14. päivänähän tämä tämänhetkinen alkoi.

Jtm [09.11.2005 22:31:02]

#

Putkaposti alkoi 7. päivä, mutta tosin en ottanut huomioon sitä toista

ezuli [10.11.2005 14:57:06]

#

Edelleenkin kuukausittain tarkoittaa enemmänkin kerran kuussa kuin kuukauden välein.

ajv [10.11.2005 16:45:17]

#

Älkääs nyt lapset kitiskö, vaan olkaa tyytyväisiä, että Antti viitsii tuollaisia pikku pähkinöitä edes tehdä!

Antti Laaksonen [10.11.2005 18:23:13]

#

Uusi tehtävä voisi tulla ensi viikon perjantaina. Sitä ennen kannattaa pohtia Datatähti-tehtäviä, etenkin toista ohjelmointitehtävää. Mitään tarkkaa rytmiä Putkapostilla ei siis edelleenkään ole.

Jtm [21.11.2005 00:00:42]

#

Okei

jutti [23.11.2005 14:34:24]

#

Tässä olisi tällainen algoritmi:
1. Etsi kaikki mahdolliset tilanteet kymmenen siirron jälkeen ja pisteytä ne sen mukaan kuinka lähellä ratkaisua ne ovat.
2. Valitse paras, mutta älä siirry suoraan kymmenen siirron päähän, vaan tee ainoastaan yksi siirto.
3. Toista kohdasta 1, kunnes ratkaisu löytyy.

Minulla on tämä puolivalmiina C++-kielisenä, en ehkä saa sitä valmiiksi ennen seuraavaa putkapostia, mutta eihän sillä väliä.

Chiman [23.11.2005 23:01:31]

#

Sainpas kaivettua sen 54 siirron ratkaisun esiin, kun viilailin algoritmin riittävän hyväksi ja annoin hitaan koneeni jauhaa pari tuntia. Kielenä C.

Metabolix [23.11.2005 23:20:54]

#

Pitäisiköhän heittää kone bruteforcettamaan pariksi päiväksi? :)

Chiman [23.11.2005 23:43:31]

#

No, ainakaan pelkällä bruteforcella ei pärjää :) Siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa, joten eri siirtoyhdistelmiä on suunnilleen 2^54 = 18,014,398,509,481,984.

Ellei usko tuuriinsa, täytyy laskea todennäköisimmät vaihtoehdot ensin tai karsia epätodennäköiset kokonaan pois. Itse tein jälkimmäisen, ja sen virittelyssä se suurin homma olikin.

jutti [24.11.2005 01:06:28]

#

Ei toi mun algoritmi toiminut kovin tehokkaasti. Tulos oli 66 siirtoa. Jonkin verran siinä pystyisi viilaamaan, mutta lähtökohta on aika heikko. Etsin kaikki mahdolliset asetelmat viidentoista siirron jälkeen, mikä oli suunnilleen suurin mahdollinen syvyys. Kone pääsi noin kolmessa sekunnissa askeleen eteenpäin. Kun pisteytin eri asetelmia, huomasin, että kulmapalat olivat tärkeimpiä, sitten reunapalat ja keskipalat, jolloin annoin eri painoarvot niille.

Chiman [24.11.2005 10:52:12]

#

jutti kirjoitti:

Tulos oli 66 siirtoa.

Et kuitenkaan lähettänyt sitä vastausta?

jutti [24.11.2005 18:11:21]

#

Ohjelmani tuotti ratkaisun, mutta itse ohjelmassa oli virhe, jota en ole korjannut. Korjaamalla virheen saatan parantaa tulosta.

Jaska [28.11.2005 02:39:27]

#

Miksi siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa. Jos tyhjä ruutu on kulmassa, sen voi siirtää 2 paikkaan. Jos tyhjä ruutu on reunassa mutta ei kulmassa, sen voi siirtää 3 paikkaan. Jos tyhjä ruutu ei ole reunassa eikä kulmassa, sen voi siirtää 4 paikkaan. Eikös siirtovaihtoehtoja ole siten keskimäärin (4*2+8*3+4*4)/16=3 kpl joka tilanteessa?

FooBat [28.11.2005 02:46:50]

#

Jaska kirjoitti:

Miksi siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa. Jos tyhjä ruutu on kulmassa, sen voi siirtää 2 paikkaan. Jos tyhjä ruutu on reunassa mutta ei kulmassa, sen voi siirtää 3 paikkaan. Jos tyhjä ruutu ei ole reunassa eikä kulmassa, sen voi siirtää 4 paikkaan. Eikös siirtovaihtoehtoja ole siten keskimäärin (4*2+8*3+4*4)/16=3 kpl joka tilanteessa?

Suuntaa, josta edellisen kerran siirrettiin ei kannata tutkia, koska siellä on jo käyty.

Jaska [28.11.2005 07:36:15]

#

Ahaa. Oletin, että brute forcessa tätä seikkaa ei oteta huomioon. Nyt selkis. Täytyypi opetella määritelmät kunnolla.

Chiman [28.11.2005 11:47:16]

#

Enpä minäkään tunne brute forcen määritelmää niin tarkasti, että tietäisin "saako" edellisen aseman jättää uusimatta. Laillinen siirtohan se on ja brute forceen käsittääkseni kuuluu kaikkien vaihtoehtojen testaaminen.

Joka tapauksessa edellisen aseman toistamatta jättäminen on ainoa triviaali keino pienentää laskentaurakkaa.

jutti [28.11.2005 12:32:16]

#

Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.

Toinen juttu, jota en ole ottanut huomioon, on että muutamaa kirjainta on kaksi kappaletta. Periaatteessa se helpottaa ratkaisua, mutta perinteisessä pelissä, jossa on luvut 1 - 15, jos murtaa pelin ja vaihtaa kahden laatan paikkaa keskenään, pelistä tulee mahdoton (pienellä varauksella, luultavasti kaksi vierekkäistä vaihtamalla pelistä tulee mahdoton). Periaatteessa on mahdollista, että ohjelma yrittää vääntää laatat sellaiseen järjestykseen, jossa esim. O-kirjaimet ovat keskenään väärin.

Chiman [28.11.2005 12:53:52]

#

jutti kirjoitti:

Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.

Kuulostaa siltä, että pelitilanteiden paremmuuden arvioinnissa on puutteita. Taidat siis sulkea 54 siirron ratkaisun pois jo aiemmin, koska jokin muu siirtosarja näyttää algoritmisi mielestä lupaavammalta laskettaessa 15 siirtoa eteenpäin. Tuttu tilanne :)

FooBat [28.11.2005 13:14:57]

#

jutti kirjoitti:

Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.

Itse olin yllättynyt, että tuolla algoritmilla sait noinkin hyvän tuloksen aikaan. Tässä ongelmassa nimittäin hakuavaruus on niin iso ja ratkaisuja niin harvassa, että olisin kuvitellut tuon algoritmin tekevän paljon enemmän virhearvioita tai mahdollisesti jäävän jopa pyörimään silmukkaa. Eli lyhyesti: algoritmillasi kävi tuuri tuossa tavassa, missä se laskee vain 15 siirtoa eteenpäin.

jutti kirjoitti:

Toinen juttu, jota en ole ottanut huomioon, on että muutamaa kirjainta on kaksi kappaletta. Periaatteessa se helpottaa ratkaisua, mutta perinteisessä pelissä, jossa on luvut 1 - 15, jos murtaa pelin ja vaihtaa kahden laatan paikkaa keskenään, pelistä tulee mahdoton (pienellä varauksella, luultavasti kaksi vierekkäistä vaihtamalla pelistä tulee mahdoton). Periaatteessa on mahdollista, että ohjelma yrittää vääntää laatat sellaiseen järjestykseen, jossa esim. O-kirjaimet ovat keskenään väärin.

Olet aivan oikeassa. Ei ole ainoastaan periaatteessa mahdollista vaan myös ihan oikeasti. Tämän havaitsin yrittäessäni ratkaista peliä käsin ajv:n ohjelmalla. Tämä peli on käsin ratkaistaessa hankalampi kuin normaali liukupeli. Tämä ominaisuus saattaa tosiaan haitata sinun algoritmiasi merkittävästi.

jutti [29.11.2005 14:59:22]

#

Chiman kirjoitti:

Kuulostaa siltä, että pelitilanteiden paremmuuden arvioinnissa on puutteita. Taidat siis sulkea 54 siirron ratkaisun pois jo aiemmin, koska jokin muu siirtosarja näyttää algoritmisi mielestä lupaavammalta laskettaessa 15 siirtoa eteenpäin. Tuttu tilanne :)

Olen yrittänyt vaihdella tuota pisteytystä eri tavoin. Parhaimpaan tulokseen olen päässyt Manhattan-etäisyyden neliön summalla. Eli Manhattan-etäisyys on montako askelta yksi palikka liikkuu yhteensä pysty- ja sivusuunnassa päästäkseen oikeaan kohtaan mennäkseen oikeaan paikkaan (jos edessä ei olisi muita palikoita). Lasken jokaisen palikan Manhattan-etäisyyden, jonka neliöin. Neliöt summaan yhteen. Mitä suurempi luku, sitä huonompi tilanne.

Ennen neliöintiä kokeilin kaksinkertaistaa luvun, jos palikan oikea kohta oli jommalla kummalla sivulla ja nelinkertaistaa jos oikea kohta oli kulmassa. Tällä yritin, että reunat ja kulmat hoidettaisiin ensin. Sillä taisi olla myönteinen vaikutus tulokseen.

Neliöinnillä pyrin yleensä siihen, että parempi että kaksi palikkaa on etäisyydellä 2 oikeasta paikasta kuin yksi etäisyydellä 1 ja toinen etäisyydellä 3. Tälläkin oli myönteinen vaikutus.

Kokeilin myös pythagorealaista etäisyyttä, mutta tulos huononi. Palikkahan ei voi siirtyä vinoittain.

Chiman [29.11.2005 15:42:58]

#

Ehkä osittainen spoilaaminen sallitaan, kun tehtävä on ollut näkyvillä jo 1,5 kk...

jutti kirjoitti:

Parhaimpaan tulokseen olen päässyt Manhattan-etäisyyden neliön summalla.

Tuo etäisyys saattaa olla paras pisteyttämistapa, mutta siinäkään tuskin kannattaa seurata vain yhtä, parhaalta näyttävää siirtosarjaa.

Itse toteutin pisteytyksen painottamalla oikeilla paikoilla olevia palasia sopivasti. Tuo oli erittäin kevyt laskennallisesti, kun keskittyi vain siirtyneeseen palaseen. Tosin jälkikäteen keksin yhtä kevyen tavan laskea tuo etäisyys. Et kai sinäkään laske kaikkien palojen etäisyyksiä joka askeleella? :)


Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta