Tässä tulee uusi putkapostitehtävä:
https://www.ohjelmointiputka.net/postit/tehtava.
Taikaneliöihin liittyy paljon mielenkiintoista tutkittavaa, toivottavasti tämä tehtävä innostaa siihen.
Helposti meni syvyyshaulla, joka vain generoi kaikki neliöt. Alle 100 riviä D:tä.
Tietenkin se piti ajaa kahdesti, en nimittäin älynnyt ensimmäisellä kerralla että tilausnumerot alkavat ykkösestä, toisin kuin taulukon indeksit, jossa sijaitsevat neliöni...
Onneksi CPU-aikaa meni koneellani vain vajaat 5 minsaa per ajo.
Kuinka nopeita ohjelmia olette tehneet?
Minun C-kielinen ohjelmani laskee tällä hetkellä (3 GHz tietokoneella) tehtävän taikaneliöiden yhteismäärän alle 0,1 sekunnissa ja mitä tahansa tilausnumeroa vastaavan taikaneliön keskimäärin 0,1 ja korkeintaan 0,2 sekunnissa. Kaikkien tämän tehtävän testitapausten laskemiseen kuluu reilu sekunti. (Päivitetty 19:04)
Olenko ymmärtänyt jotain väärin, vai onko tuossa tehtävässä ideana se, ettei numeroiden järjestyksellä ole mitään logiikkaa? (Paitsi se, että taikaneliöiden tilauskoodit ovat akkosjärjestyksessä, ja se että summat ovat samat vaaka- ja pystyriveillä)
Esimerkiksi taikaneliö nro. 000001 = ABOPFKGJMLDENIHC ja sitten nro. 000003 = ABOPFKJGMIDHNLEC. Miten tuon olisi voinut päätellä?
Kirjaimet saadaan muuttamalla neliön luvut merkeiksi:
Putkaposti kirjoitti:
Taikaneliöt on numeroitu niin, että jos luvut luetaan vasemmalta oikealle ja ylhäältä alas ja muutetaan kirjaimiksi (A = 1, B = 2 jne.), taikaneliöt ovat luettelossa aakkosjärjestyksessä.
Ja esim. 0003 on 3. taikaneliö (aakkosjärjestyksessä tuo merkkisarja on 3.)
Jokaiseen taikaneliöön liittyy siis tietty kirjainsarja. Kun kaikkien taikaneliöiden kirjainsarjat (549504 kpl) laitetaan aakkosjärjestykseen, taikaneliöille saadaan selkeä järjestys. Tämän järjestyksen mukaan taas päätetään tilausnumerot.
Kirjainsarjoista ABOPFKGJNIHCMLDE (000002) ja ABOPFKJGMIDHNLEC (000003) ei näe suoraan, että ne ovat peräkkäin. Mutta ei ole olemassa sellaista taikaneliötä, josta muodostettu kirjainsarja menisi niiden väliin.
Antti Laaksonen kirjoitti:
Kuinka nopeita ohjelmia olette tehneet?
Meinasin ratkaista ongelman vaihteen vuoksi prologilla, mutta taitaa olla kyseisen kielen taidot vähän ruosteessa. 15 rivin ohjelma kyllä tulostaa nätisti taikaneliöitä oikeassa järjestyksessä, mutta vaatii käyttäjän syötteen aina seuraavan ratkaisun saamiseksi. Periaatteessa kaikki ratkaisut voisi ladata muistiin listaan ja valita niistä ne halutut, mutta näytti tulkista loppuvan jonkinlainen sisäinen heap-muisti, enkä vielä jaksanut selvittää miten sitä voi kasvattaa. Näyttäisi kuitenkin siltä, että 1000 taikaneliön laskemiseen kuluu CPU-aikaan noin 1 sekunti, joten kaikkien läpikäynti onnistuisi noin 10 minuutissa.
Pitäisi varmaan sittenkin tehdä kunnon ratkaisu jollain kotoisammalla kielellä.
Juu, tuota siis kokeilin tarkoittaa rivien välistä.
Antilla on selvästi nokkela algoritmi :)
Toteutin ensin yksinkertaisen syvyyshakua käyttävän algoritmin suosikkikielelläni Pythonilla, mutta urakka oli turhaa laskentaa karsimallakin toivottoman työläs. Sen sijaan että olisin kehitellyt paremman algoritmin, toteutin saman C:llä.
Ratkaisun laskemiseen menee aikaa n. 8 min. Kielenä C, koneena 700 MHz Athlon.
Ensinnäkin, terve kaikille. Ensimmäinen postaukseni. Täytän tässä profiilini, jahka jaksan.
Löysin Putkan tuon syksyn älykkyyskilpailun takia ja kiinnostuin nyt tästäkin ongelmasta. Python-kielinen ratkaisuni toimii tällä hetkellä tarpeeksi nopeasti: 1 min 11 sekuntia 1,6 GHz AMD Turion-koneessa (mutta 32-bittinen Windows). En käytä niinkään hakua vaan kombinatoriikkaa.
Koodi ainakin oli suoraviivaista kirjoittaa. Lisää siitä sitten myöhemmin.
Pitää nyt ensin tarkistaa, että tulokseni ovat oikein. Lähetän ne juuri kohta eteenpäin. Pienoisen ohjelmaiseni lähetän Antille parin päivän sisällä, kunhan vielä vähän siivoan sitä. Saattaapa pikkuisen nopeutuakin, jos sopivasti tekee.
...
No, sepä menikin läpi. Palautetta sai heti.
Vielä tuosta ohjelmastani:
Saimme sen Antin kanssa nopeutettua 31:een sekuntiin (mittaus samalla koneella). Vieläkin on optimoinnin varaa, mutta jääköön nyt odottamaan sen ohi, että Putkapostin kilpa-aika loppuu, ja ratkaisut voidaan julkaista. Kuulemma ratkaisuni oli sen verran omaperäinen, että sitä kelpaa muillekin näytellä...
Menee hieman offtopiciksi, mutta ihan vähän vain:
Taikaneliöistä on ollut aiemminkin näköjään puhetta. Löysin mielenkiintoisen artikkelin joka myös hieman käsittelee näitä ja miten äärellisten kuntien teoria liittyy näihin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.