Keskustelu: Ohjelmointiputka: Putkaposti 5: Museon lamput

Postipoika toi juuri uuden putkapostitehtävän:
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam

Museon sähköjärjestelmään on tullut häiriö, ja huoneiden lamppujen sulkeminen yöksi tuottaa ongelmia. Kuinka pitkäksi vahtimestarin ilta venähtää?

Miten aika määräytyy jos antaa vastaukseksi vain yhden huoneen kytkennät?

Puuttuvista huoneista tulee kustakin 3600 sekuntia lisää (eli yksi tunti). Jos vastauksessa on vain yksi huone, kytkinten painamisten määrään lisätään siis 10 * 3600 = 36000.

kerrankin kivan tehtävän keksitte.

Joo, kiva tehtävä :) Varsinkin, kun sen osasi tehdä.

Metabolix kirjoitti:

Joo, kiva tehtävä :) Varsinkin, kun sen osasi tehdä.

Muuten samat sanat, mutta osaa-verbi konditionaalissa... :)

Heh... Kyllä se oli pienen pohdinnan takana. Vihjeenä, että syvyyssuuntaisella haulla ei parane lähteä viimeistä kohtaa ratkomaan. Kone oli yön yli päällä, eikä vastausta tullut. Aamuinen oivallus taas laskee kaiken niin nopeasti, ettei tuota viitsi timellä lähteä ajoittamaan, kun tiedostonluku vie noin 100% ajasta ;) Pitää vielä illemmalla tarkistaa, josko tuolta saisi pari napsautusta pois.

Liikaa paljastamatta voin kertoa, että Metabolixin nykyisessä tuloksessa (1901) on vielä roimasti parantamisen varaa.

Hyvä tehtävä tämäkin. Erittäin yksinkertaisella algoritmilla sain jonkinlaiset vastaukset muihin paitsi kahteen huoneeseen, joissa se jää ikuiseen silmukkaan. Tiedän missä mättää, mutta fiksu ratkaisu on vielä hämärän peitossa.

Erittäin yksinkertaisella algoritmilla pääsee tuohon minunkin tulokseeni (edelleenkin 1901). Tiedän, että siitä pääsee vielä paljon ylöspäin, mutta en ole ehtinyt / jaksanut / viitsinyt kehittää parempaa ideaa =)

Edit: Kelpaako nyt? 1721, eikä ollut edes kiven takana.

Kylläpäs joutui ajattelemaan kierosti, että lopulta keksi ratkaisun L:n ja J:n ratkaisemiseksi. L oli lopulta helppo, kunhan keksi hyvän lähestymistavan, mutta J:n laskemiseen paloi mukavasti 17h.

Nyt pitäisi sitten enää keksiä, mistä Metabolix sai noi yli sata naksausta pois. Pitää varmaan tutkia, josko L huoneen ratkaisuun löytyisi jokin erilainen lähestymistapa, jolla löytyisi lisää lyhyempiä ratkaisuja kuin oma 1075.

Joo, hiukan masentaa, että Villellä on varmaan taas tähänkin ongelmaan takataskussa algoritmi, joka ratkaisee optimiratkainun noin nanosekunnissa ;)

Luulenpa, että minullakin on tällä hetkellä periaatteessa tehokkain mahdollinen idea käytössä, vaikkakin pieniä optimointeja itse koodiin olisi varmasti mahdollista tehdä. (Ville toivottavasti huomauttaa, jos olen yhä kaukana oikeasta tuloksesta.) Tämän hetken ainut "ongelma" on se, että mahdottomassa tilanteessa tulee ikuinen silmukka, kun en ole jaksanut ajatella, monenko napsautuksen jälkeen tilanteen pitäisi viimeistään olla valmis. Ja tietenkään en lähetä vastaustani, ennen kuin olen tuonkin jaksanut keksiä :) Tai ehkä sitten, kun seuraava posti ilmestyy...

Minä luulen, että Metabolixin ratkaisu ei ole optimaalinen, jos se jää ikuiseen silmukkaan.

Sanoinhan, että se jää ikuiseen silmukkaan vain, jos ratkaisua ei ole. Sillä ei nähdäkseni ole tekemistä ratkaisun optimaalisuuden kannalta. Helpostikos tuon korjaa lisäämällä silmukkaan tarkistuksen, että jos jokaista katkaisijaa on painettu riittävän monta kertaa, ilmoitetaan, ettei vastausta ole.

Metabolix kirjoitti:

Luulenpa, että minullakin on tällä hetkellä periaatteessa tehokkain mahdollinen idea käytössä, vaikkakin pieniä optimointeja itse koodiin olisi varmasti mahdollista tehdä.

Haluaisitko hieman kuvailla, miten tehokas ideasi on? (Esim. arvioidulla aikakompleksisuudella tjms.)

VilleP: Olen hirveän huono aikakompleksisuuden arvioinnissa, kun tilanne on hiemankin epämääräisempi. Laitoin kuitenkin ratkaisuttomien huoneiden varalta tarkistuksen, että jos naksautuksia on yli kaksi kertaa katkaisijoiden määrä, etsintä lopetetaan. Todistettavasti vastaus noihin tapauksiin pysyy yhä samana ja kelpaa lähetettäväksi :) En kuitenkaan halua syyllistyä spoilaamiseen, joten en tässä hirveästi ala selittää. Sittenhän se tullee esille joskus aikanaan :) Voin tietysti laittaa jonnekin jo nyt, jos kiinnostaa katsella.

Tämä taitaa jäädä historiaan ensimmäisenä putkapostina, johon ei tule heti ensimmäisten päivien aikana kokonaista rypästä optimaalisia ratkaisuja.

Hassua; minusta tämä on ehkä helpoin tähän mennessä.

Helppo ja helppo. Itse en ole minkään näköistä ohjelmaa keksinyt, (no se keksiminen oli vaa yhdellä illalla. Tuo vastaus mikä mul o ni o laskettu paperil. Seuraavii en enää jaksanu ;)

Minusta tämä on taas ollut vaikein ja kiinnostaisi kovasti Metabolixin ratkaisu. :) Vaan ehkä tässä vielä jokin oivallus löytyy...

Edit: taitaa olla mulla sama algoritmi kuin foobatilla, J ja L tuottivat myös ongelmia ja tuloskin on melkein sama

No mikä siinä nyt tökkii ;) Kynä ja paperi käteen ja miettimään, mitä nappulaa pitäisi painaa. Sitten kun on muutaman ratkonut käsin, niin alkaa varmaankin hahmottua, mitä tulikaan tehtyä. Olettaen tietenkin, että saa käsin ratkottua mitään. (Ei ole tietenkään pakko pitäytyä juuri noissa huoneissa, mutta kannattaa silti varmistaa, että ratkaisu on olemassa.)

Metabolix, lisätehtävänä voit kokeilla, kuinka suurista syötteistä ratkaisusi selviää esim. alle kymmenessä sekunnissa (huomioiden lamppujen lukumäärän ja vaikutusvälin).

Omien tesisyötteiden valmistaminen käy kätevästi vaikkapa ohjelmalla, joka aloittaa sammutetusta lamppurivistä ja painelee satunnaisesti katkaisimia riittävän monta kertaa.

VilleP: Ensimmäinen testi, koko miljoona ja vaikutusmatka 53 suuntaansa. Tuolla on siis tehtävä. Vastaukseksi tuli käsittääkseni 432334 naksautusta. Time sanoi 20,5s ilman optimointia ja 9,9s optimoinnilla -O2. Hassusti -O3 taas pudottaa ajan takaisin 17s:iin.

Yksi optimointi varmaankin olisi tallentaa yhteen muuttujaan (vaikka 64-bittiseen) joka bittiin yhden lampun tila, jos jaksaisi laskea niissä, millaiset maskit tarvitaan ja missä menee yli jne, jolloin lamppujen naksauttelu sujuisi ainakin isoilla vaikutusmatkoilla nopeammin.

Metabolix, vastaus näyttäisi olevan oikein, mutta vieläkään sen enempää paljastamatta kerrottakoon, että ajassa/tehokkuudessa on vielä perin huomattavasti parantamisen varaa.

Sain saman vastauksen (432334) epäoptimaalisella algoritmilla ajassa 0,625 s.
Vaihtoehtoja ei tainnut olla kovin montaa...

Tosiaan, tietyillä rajoituksilla vaihtoehtoja taitaa itse asiassa olla tässä tapauksessa tasan yksi.

Metabolix, miten olisi vaikutusväli tasan 312 (molempiin suuntiin), koko tasan 1000000?

Pitäisiköhän muuttaa randomiakin? Tulee nimittäin täsmälleen saman vastauksen vaativa tehtävä :) Mutta tämä sen sijaan ratkesi puolessatoista sekuntissa. Linkki, jos ette jaksa itse generoida.

Erona on, että ensimmäisestä ratkaistessaan algoritmini painaa kytkintä 26882936 kertaa, jälkimmäistä taas 491496. Pitäisi siis vielä hieman optimoida nähöjään. Edellisessä muuten oli tuo 53 juuri sitä varten, ettei tulisi yhteisiä tekijöitä (n):lle ja (2*m+1):lle (n = koko, m = vaikutus).

Edit. Törttöilin linkin kanssa. Nyt toimii.

Edit2. Ja jos samaa vastausta etsitään syötteestä, jonka vaikutusmatka on 2345, niin aikaa näyttäisi kuluvan kiitettävän pitkään :) Eli näköjään isoja huoneita kannattaa yleensäkin sammutella hieman eri suunnasta. Tarkemmin ajatellen tämä algoritmi on yhä tietynlainen brute-force.

Edit3. Tein pienen muutoksen, ja nyt ensimmäinen testisyöte vie noin 2,5s ja toinen lähemmäs 7s.

Ajan vertailu ei ole välttämättä helppoa, sillä eri ihmisillä voi olla erinopeuksiset koneet.

Jep, teinpä nyt algoritmini eri tavalla, eikä tarvinnut kuin muutama tunti pähkäillä. Enää ei tarvita mitään naksuttelufunktiota :)

Käännetty -O2:lla, tehomyllynä 2,0GHz AMD Athlon. Keskimäärin nuo molemmat testisyötteet menevät nyt suunnilleen 0,75s:ssä. Ensimmäinen yleensä hieman jälkimmäistä hitaammin, mutta hajontaa eri ajokerroilla tulee muutenkin viiden sadasosan verran ellei enemmänkin, eli ei ole turhan tarkkaa tuo ajanotto jostain syystä. Varmaankin natiivissa Linuxissa ottaisi tarkemmin.

Itselleni tämä tehtävä taitaa olla vaikein tähänastisista. Monta erilaista ideaa on ollut, mutta viimeinen huone on vielä kokonaan ratkaisematta.

Luulisin, että voisin ratkoa jopa viimeisen huoneen ihan paperille tällä uusimmalla algoritmilla. Vaikka kyllä siinä mukavasti hetki vierähtäisi, ehkä tunnin verran ainakin, jos ajatukset eivät takkuaisi :)

Noniin. Olipa typerä virhe sotkemassa algoritmia.
Nyt menee Metabolixin testisyöte (naksautuksia 432334) ajassa 0,484s, (2,16 GHz AMD Athlon XP).
Aikakompleksisuus on selvästi kertaluokkaa O(n), huoneen koon suhteen.

Tämä on eka tehtävä, jossa olen päässyt näinkin pitkälle. J:n ja L:n kanssa tulee raja vastaan. G:täkään minun ohjelmani ei ratkaissut ilman pitkää arvailusessiota.

Voisinko kysyä sen verran, että analysoiko teidän ohjelmat tarkemminkin tilannetta (esim onko tietyn matkan päässä lamppuja päällä/kiinni ja entäs niiden vieressä tai siitä vaikutusmatkan päähän toiseen suuntaan...) vai pystyykö tuommoisen ratkaisemaan jotenkin kaavamaisemmin?

Minulla ja setä:llä on luultavasti sama tyyli ratkaista, koska meillä oli jossain vaiheessa sama vastaus.

EDIT: Se tais olla sittenkin Samin kanssa samanlainen...

Kuten os sanoi, aikakompleksisuus on O(n). Tämä siis tarkoittaa sitä, että käytetty aika on (teoriassa) suoraan verrannollinen huoneen kokoon, mistä taas voi päätellä, että jokaiselle lampulle suoritetaan jokseenkin sama toimenpide (keskimäärin, jos sellaista sanaa voi tähän soveltaa). Tämä tarkempi selostus toiminnasta voisi olla jo liian tarkka. Mutta toistan vielä, että paperi ja kynä ja kaikessa rauhassa suunnittelu. Hyvin kaavamainen lopputulos siitä väkisin tahtoo syntyä, kuten O(n)-ajoaika kertoo.

Niin ne taidot kehittyvät :) Ja kun on tämän ratkaissut, niin on taas vähän taitavampi.