Putkapostin uusi tehtävä on ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Pelin voi muuten rakentaa helposti legopalikoista. Tällaisen tein itselleni:
Onpa vähän tullut vastauksia, ei taida olla ihan helpoimmasta päästä tehtävä.
Kuinkahan nopeaksi tuo ohjelma pitäisi saada? Tuntuu tuollainen minuutin ajoaika melko pitkältä.
Niin, mikähän on syynä tehtävän heikkoon suosioon?
Minun nykyinen ohjelmani kuluttaa aikaa lähes kaksi minuuttia (3 GHz koneella), mutta sanoisin kyllä, että ohjelman voi saada paljon nopeammaksi kehittämällä mahdottomien ratkaisuiden hylkäystä haun eri vaiheissa. Onko joku onnistunut tekemään nopeampia ohjelmia ja millä keinoin?
Antti Laaksonen kirjoitti:
Niin, mikähän on syynä tehtävän heikkoon suosioon?
Itselläni innostusta rajoitti ainakin se, etten keksinyt täydelliseen ratkaisuun mitään nokkelaa ja tehokasta algoritmin tynkää. Tyytyminen raskaaseen mutta silti pähkäilyä vaativaan hakualgoritmiin ei houkuttanut tarpeeksi tällä kertaa. Lisäksi vaadittaisiin vielä lisää viilailua, jotta täydellisen ratkaisun saisi esiin järkevässä ajassa. Perfektionismiin taipuvaisena en halunnut lähteä hakemaan osaratkaisua :)
Tehtävänanto oli selkeä, joten vika ei ole siinä.
Antti Laaksonen kirjoitti:
Niin, mikähän on syynä tehtävän heikkoon suosioon?
Kiire.
Heikkoon suosioon syynä on se, että
a) yhden ratkaisun löytäminen tehtävään on suunnilleen yhtä vaikeaa kuin kaikkien ratkaisujen löytäminen
b) kyseiseen ratkaisuun ei päästä yksinkertaisella brute forcella
c) hiukan kehittyneempi algoritmi on jonkinverran työläs toteuttaa
d) kiire
Itselläni etenkin kohta d) on nyt ollut häiritsevä tekijä. Koodasin kyllä yhtenä iltana ratkaisun pohjaksi pikaisesti yksinkertaisen brute forcen, mutta odotetusti se ei ollut läheskään riittävän nopea. On tuossa parempikin ratkaisu (codeword: tetris) mielessä, mutta sen tekemiseen menee jokunen tunti enkä ole ihan varma, että sekään on riittävän tehokas.
Tiedän valmiin ratkaisun. En halua väittää toisen tekemän koodin antamaa tulosta omakseni. Toisaalta en jaksa tehdä nollasta samanlaista ohjelmaakaan.
Kopeekka kirjoitti:
Tiedän valmiin ratkaisun. En halua väittää toisen tekemän koodin antamaa tulosta omakseni. Toisaalta en jaksa tehdä nollasta samanlaista ohjelmaakaan.
Et ole ainoa. Tehtävä olisi toteutukseltaan varmasti varsin mielenkiintoinen, mutta kun ratkaisun löytää suoraan netistä niin en viitsi samanlaistakaan alkaa toteuttamaan. Tekemisen ilohan siitä lähtee kun valmis ohjelma on jo saatavilla.
Kesä mennytkin seuraavaa putkapostia odotellessa ..
FooBat kirjoitti:
b) kyseiseen ratkaisuun ei päästä yksinkertaisella brute forcella
c) hiukan kehittyneempi algoritmi on jonkinverran työläs toteuttaa
Jaa? Koska ratkaisu ei ollut lainkaan työläs toteuttaa vaan suorastaan suoraviivainen, oletan, että se on tuo bruteforce. Minuutti tosiaan menee laskennassa, tehoa on 2 GHz. Toisaalta tein tuohon sellaisen hassun optimoinnin, jota ihan jokainen ei välttämättä tule ensiksi ajatelleeksi...
Kiitos vastauksista, tämä tehtävä taisi tosiaan olla liian yleisesti tunnettu. Hakuohjelmissa on usein hankaluutena, että niistä tulee ohjelmoituna melko monimutkaisia. Kuitenkin Putkapostissa saisi mieluummin olla niin, että tehtävän ratkaisutapaa saa pohtia kauan mutta lopullinen koodaustuokio on lyhyt.
No puristin sen ratkaisun kuntoon kun alettiin painostamaan :)
Javalla noin 6 s, josta 1 s menee tiedoston tulostamiseen. Ratkaisuideana
tetris eli aletaan täyttämään peliä reunasta rivi kerrallaan. Peilikuvat ja kierrot saa helposti pois pakottamalla ristikuvion olemaan tietyn neljänneksen alueella.
Olisi tuo varmaan mennyt sillä alkuperäisellä brute forcellakin, jos sen olisi jaksanut debugata kuntoon.
Aika nopea ratkaisu, mikähän omassa ohjelmassani on vikana, kun ajatukseni oli ilmeisesti kuitenkin sama? Ehkä toteutin jonkin asian todella hitaasti, tai sitten ratkaisun nopeuteen vaikuttaa suuresti, mistä päin ja missä järjestyksessä palikoita ruvetaan sovittamaan.
Aihe on jo aika vanha, joten et voi enää vastata siihen.
