Tässä on uusi putkapostitehtävä:
https://www.ohjelmointiputka.net/postit/tehtava.
Alkukukka on täysin toisenlainen kasvi kuin aiempi jääkukka.
Sorruin ratkaisemaan tehtävän pitkästä aikaa Rubylla, jolloin vastaan tuli muistin määrä: 93:n kohdalla ainakin koko RAM, 2 Gt, oli täynnä ja kone takkusi niin, etten meinannut saada ohjelmaa suljettua. Pythonille käännettynä ohjelma toimi sen verran nopeammin, että oli varaa laskea joitakin asioita useampaan kertaan. Luultavasti tähän muistinkäytön optimointiin olisi ollut jokin muukin tapa.
Tyhmästä syystä jäi kisa voittamatta. ;)
Xlfrrffä ba gllcvyyvara qlannzvfra buwryzbvaava grugäiä, engxnvfhshaxgvb ibvqnna rfvggää urycbfgv erxhefvba nihyyn.
Hassua jos muisti loppuu, kun oma softa syö noin kilotavun työmuistia.
Jos ensin käyttämäni ohjelmointikielen 32-bit kokonaisluvut olisi riittäneet, niin olisin saanut toimivan softan ekalla yrityksellä :D
Vaihdoin modernimpaan versioon (VB.Net 2008), jossa on 64-bit kokonaisluvut ja softa pyörähti 0,05 sekunnissa.
Aluksi en saanut lähetettyä vastausta kun olin laittanut kukan päivien ja eri kasvatustapojen väliin tabulaattorin ja tuo vastaanottosysteemi halusi välilyönnin.
Metabolix: Ra xrxfv bvxrnfgnna zvgääa fllgä erxhefvba xälggööa.
Jos nyt kisan "voittamisesta" puhutaan, niin mulla jäi vielä tyhmemmästä syystä voittamatta. Eli huomasin koko tehtävän vasta kun 3 oli jo lähettänyt vastauksen.
Äh, ei keksi optimointeja enää tänä iltana. Koodia on niin vähän mutta lasku kestää...
.. wn xlyyä, ynfxra nyxhyhihg gnhyhxxbba raara fhbevghfgn.
Ei itsellänikään ole kuin 45 riviä mukaan lukien (turhan hieno) alkulukujen laskurutiini, kommentit ja tyhjät rivit.
User137: Xnaanggnvfvxb ynvggnn wbgnva zhhgnxva gnhyhxxbba?
Eiväthän nämä nopeuskilpailuja ole ellei postien julkaisuaikaa aleta julkaisemaan Project Eulermaisesti etukäteen ;). Oma ratkaisuni Haskellilla kirjoitettuna, idea sama kuin Metabolixin, mutta Haskellissa tuon idean toteuttamiseen ja pohtimiseen menee (ainakin minulla) enemmän aikaa kuin esim. C++:lla. Riveissä sitten voittaakin ainakin VB.netin, 27 riviä ja huonosti sekä ilmavasti kirjoitettuna ;).
Itse käytin ratkaisemiseen haskellia, jota kului yhteensä 13 riviä pois lukien tyhjät rivit.
Niin, viittaisinkin tuohon Metabolixin kommenttiin kisan "voittamisesta", kun oletin että hän tarkoittaa sitä ettei ole päässyt listalle ensimmäiseksi.
Juuh, vajaa vartti meni ratkaisemiseen tehtävänannon lukemisen aloittamisesta. Minäkin käytin Haskellia, koodia on suunnilleen 8-16 riviä laskutavasta riippuen.
Esim. Project Eulerin #77 on vähän samantapainen.
Xälgva gbqryyn lxfvaxregnvfgn erxhefvvivfgn shaxgvbgn, wbxn cnynhggnn xnvxxv revynvfrg gning fnnqn unyhggh fhzzn; rfvzrexvffä avvgä ba xbyzr: [[(7,1)],[(2,1),(5,1)],[(2,2),(3,1)]]. Ghbfgn fnn gevivnnyvfgv ynfxrgghn xnvxxvra xnfihgncbwra zääeäa.
Grez: Erxhefvb ba ybbtvara gncn xhingn engxnvfhn, wbaxn crehfgnan ba gvrgglwra gevivnnyvra gncnhfgra (cvghhf nyyr arywä) ghagrzvara wn zhvqra gncnhfgra wnxnzvara gäzäa crehfgrryyn cvrarzcvva batryzvva (ryv wbxb nyxhyhxh bgrgnna zhxnna, wbyybva cvghhf cvrararr, gnv fvggra fvveelgääa xäfvggryrzääa cvrarzcää nyxhyhxhn).
Liian hienoista ratkaisuista sakotetaan: Gnhyhxbva gbfvnna abvgn gälqryyvfvä ghybxfvn, xhgra shaxgvb lyyä rfvggv. Gäzäa gnxvn zhvfgvnxva xhyhv avva wäexlggäiäfgv, wn fhbevghf zlöf xrfgv zryxb cvgxääa (xlzzravä frxhagrwn). Xbfxn grugäiäffä rv xhvgraxnna gneivgn gvrgbn vgfr gnibvfgn inna inva avvqra zääeäfgä, grugäiäa ibv engxnvfgn uliva lxfvaxregnvfryyn vgrenngvbyyn, wbyybva fhbevghfnvxn ynfxrgnna zvyyvfrxhaarvffn rvxä zhvfgvnxnna xhyh xhva avzrxfv (nyxhyhxhgnhyhxxb, rqryyvfgra cvghhxfvra fhzzng, lugrrafä fvvf urycbfgv nyyr xvybgnih zngnynzzna gnfba xvryvyyä).
Seuraava haaste onkin ratkaista tämä Brainfuckilla. :)
Metabolix: Ehkä olisi pitänyt tarkentaa että tässä tapauksessa turhaa. Byvfv VZB wbxfrraxva gheunn gruqä erxhefvbshaxgvb ynfxrznna fryynvfgn, wbxn zrvyyä wb 100% inezhhqryyn ba gnhyhxbffn.
Grez: Wbf shaxgvb ba erxhefvvivara, fvgä ibv fhbenna xhgfhn zvyyä gnunafn cnenzrgevyyn, xha gnnf vgrengvvivfrffn engxnvfhffn gälgll vgfr uhbyrugvn, rggä gnhyhxbffn ba xnvxxv fr, zvgä cvgääxva. Rrxhefvvivaraxva shaxgvb ibv cnynhggnn neiba gnhyhxbfgn, wbf fr ba wb nvrzzva ynfxrggh.
Nvan rv xhvgraxnna byr ynvaxnna fryiää, zvgxä gvynagrrg ba gnecrra ynfxrn rghxägrra, wn gncnhxfrfgn evvcchh, zvaxä ireena vgrenngvb grxrr lyvzääeävfgä glögä fhugrrffn erxhefvbyyr gllcvyyvfrra enfxnhgrra. Reääa xreena grva grugäiäa, wbffn lyv chbyrg neibvfgn byv gheuvn, ääevgncnhxfvffn wbcn 90%. Erxhefvba nihyyn aäzä wääiäg ynfxrznggn, zhggn vgrenngvb ghyv ghbffnxva gncnhxfrffn gnecrrfrra (gheunfgn ynfxraanfgn uhbyvznggn) lxfvaxregnvfrfgv whhev ghba urycbzzna zhvfgvafäägrylafä nafvbfgn; xbxb chha fvwnna evvggv fävylggää cnev rqryyvfgä evivä (ieg. svobanppv: xnvxxv yhihg gnv inva xbyzr zhhgghwnn).
Kaikenlaisille menetelmille on omat paikkansa, ja myönnän kyllä, että tässä tapauksessa oma tapani oli huonompi, kirjoitin itsekin nyt myöhemmin tuon toisen algoritmin. Se kuitenkin oli ensimmäinen mieleen tuleva tapa (kuten aika usein tällaisissa tehtävissä).
Eiköhän tämä kysymys nyt tullut puitua aika tehokkaasti. :)
Ensimmäisenä mieleen tullut ratkaisumenetelmä riitti: Pythonilla suoritusaika 25 s. Mukava tehtävä.
Siis, onko 2 todella alkuluku? Sehän on ykkösen lisäksi jaollinen vain itsellään, kakkosella..
Tietenkin 2 on alkuluku. Onko tästä muka jotain epäselvyyttä?
Juhko kirjoitti:
Siis, onko 2 todella alkuluku? Sehän on ykkösen lisäksi jaollinen vain itsellään, kakkosella..
Millä muulla sen pitäisi mielestäsi olla jaollinen, että kelpuuttaisit sen alkuluvuksi?
Anteeksi, ajatusvirhe. :)
funktio kirjoitti:
Juuh, vajaa vartti meni ratkaisemiseen tehtävänannon lukemisen aloittamisesta. Minäkin käytin Haskellia, koodia on suunnilleen 8-16 riviä laskutavasta riippuen.
Esim. Project Eulerin #77 on vähän samantapainen.
En periaatteesta mene rekisteröitymään ko. sivustolle yhtä ongelmaa varten.
funktio kirjoitti:
Xälgva gbqryyn lxfvaxregnvfgn erxhefvvivfgn shaxgvbgn, wbxn cnynhggnn xnvxxv revynvfrg gning fnnqn unyhggh fhzzn; rfvzrexvffä avvgä ba xbyzr: [[(7,1)],[(2,1),(5,1)],[(2,2),(3,1)]]. Ghbfgn fnn gevivnnyvfgv ynfxrgghn xnvxxvra xnfihgncbwra zääeäa.
Tuossa kommentissa on kenties jotain lähimmäs ratkaisua menevää vihjettä mutta ei ihan vielä auennut :p Miten estän rekursiota havaitsemasta tapauksen [(5,1),(2,1)] ilman että laitan kaiken muistiin ja vertaan edellisiin, pitäen samalla huolen siitä että tehokkuus säilyy. (EDIT: keksinkin jo miten...) Meinaan ettei tämä ole ihan triviaali tehtävä missään kohtaa ongelmaa. Pitää olla jonkin verran matematiikan lahjoja ennen kuin noista lukupareista edes osaa laskea ratkaisut. Ehkä vaan ajattelen turhan syvällisesti tjtn...
2a+2b+3 = 7
2b+2a+3 = 7 myös, vaikkakin molemmat ovat yhteensä vain 1 tapaus. Otappa sekin vielä huomioon laskuissa >.<
No riippuu siitä että miten tottunut on rekursioon. Eipähän tuossa montaa minuuttia mene jos on usein joutunut toteuttamaan esim. syvyyshakuja tai backtracking-algoritmeja.
No sanotaan että rekursio toimii nyt. Törmäsin ongelmaan jossa haetaan funktiota joka pätee näissä kaikissa:
EDIT: eikä tämäkään funktio vielä tule riittämään kun dimensioita tulee mahdollisesti useampia...
f(1,1)=2
f(2,1)=3
f(2,2)=6
f(3,2)=12
f(x,y)=???
Havainnollistaen f(2,2)
xxOO
xOOx
xOxO
OxxO
OxOx
OOxx (= 6 eri tapausta)
User137: Nyt en kyllä ollenkaan käsitä, mitä tuossa laskeskelet.
No voi pahus, keksin mielestäni järkevän ratkaisun melkein heti, mutta sitten minultakin loppui lukujen tarkkuus aivan loppumetreillä. Kaipa tuo 97 riittää täksi illaksi, jos vaikka huomenna jaksaisin portata pythonille ja puristaa pari viimeistä lukua irti. :) En ole muiden ratkaisuja lukenut, mutta omani on O(n2) sekä aika- että tilavaativuudeltaan, hurahtaa 800MHz:n koneella 20000 kertaa sekunnissa.
Edit: Korjaan, tilavaativuus on O(n).
User137 kirjoitti:
funktio kirjoitti:
Esim. Project Eulerin #77 on vähän samantapainen.
En periaatteesta mene rekisteröitymään ko. sivustolle yhtä ongelmaa varten.
Sieltä löytyy tällä hetkellä 208 ongelmaa, ja lisää tulee koko ajan. Eli jos tämän tyyppisten yksinkertaisten mutta silti minuutista parin tuntiin pohdintaa aiheuttavien ohjelmointipähkinöiden tekeminen kiinnostaa niin kannattaa rekisteröityä. Luulen kuitenkin että funktio oli suunnannut kommentin niille, jotka tekevät sekä näitä putkaposteja että PE:n tehtäviä.
Taisi olla taas tehtävä johon on joku paljon yksinkertaisempi tapa kuin ensimmäisenä itseni toteuttama. Luultavasti ratkaisuidea on jotakuinkin sama kuin Funktiolla, mutta hänen triviaaliksi sanoma osa tuotti enemmän vaikeuksia. Olen varmaan unohtanut jonkun kombinatoriikan peruskikan, kun piti toteuttaa toi dynaamisella ohjelmoinnilla.
Foobat:
Oletettavasti se "triviaali" osa on a! / (a1! * a2! * ... * an!)
Ryv fvvf gncbwra zääeä, xhvaxn n xnccnyrggn nyxbvgn ibvqnna wäewrfgää, xha nyxvbgn N1 ba n1 xnccnyrggn, nyxvbgn N2 ba n2 xnccnyrggn, ... wn nyxvbgn Na ba na xnccnyrggn. Yvfäxfv nyxvbvqra Nv xrfxvaävfryyä wäewrfglxfryyä rv byr iäyvä.
Rfvzrexvxfv yhihg 2, 2, 2, 3 wn 4 ibvqnna wäewrfgää 5! / (3! * 1! * 1!) = 20 rev gninyyn.
Pakko sanoa että kylläpä te tunnutte tätä tehtävää ratkaisevan hankalasti. Siis ainakin nyt Samin ja User137:n kommenteista tulee fiilis, että asiaa lähestytään turhan monimutkaisesti.
Ei sen puoleen, itse taisin edellistä putkapostia ratkaista kohtuuttoman hankalasti. (vai puhuitteko jo muusta tehtävästä, kuin alkukukasta)
Ilmeisesti moni muukin menee samaan ansaan kuin minä aluksi. Onhan se aina mukava, ettei tarvitse yksin mokailla. ;) Eli kannattaa tosiaan keskittyä siihen, mitä kysytään ja mitä ei, ja tehdä ohjelma, joka laskee vain ensimmäisen näistä.
Siis kyllähän tuosta brute-force ratkaisun keksi muutamassa minuutissa mutta ongelma on kuinka optimoida sitä, tai ottaa ihan toinen ratkaisumalli.
No joo, Metabolix tuolla näköjään jo ihmetteli aikaisemminkin mitä oikein lasket. Mutta siis oletko tekemässä systeemiä, jolla saisi esim. miljoonan päivän kukan laskettua nopeasti? Noilla 2-100 päiväisillä kun brutellakaan ei mene kuin se muutama sekunnin sadasosa, niin tuntuu ettei siinä paljon tarvitse optimoida.
Näissä Putkaposteissa olisi käyttöä samanlaiselle kommentointisysteemille kuin Project Eulerin tehtävissä, eli ratkaisemalla ongelman pääsisi viestiketjuun, jossa ratkaisijat esittelevät koodejaan.
Tässä tehtävässä en keksinyt kohtuullisella miettimisellä hyvää algoritmia, joten 25 sekunnin bruteforce sai kelvata. Käytin mm. kaavaa, jonka Sami mainitsi yllä.
Joo, se olis kyllä kiva. Tosin itsellä menee niissä threadeissa siellä project eulerissa aika hyvin yli hilseen usein se jutustelu (ainakin 200+ tehtävissä) :D Ja kateellisena tulee katseltua joidenkin ohjelmointikielten näppäriä ratkaisuja.
Laitoin mailia, laita vastaus jos kiinnostaa.
Bruteforce hidastuu eksponentiaalisesti joka kierroksella. Näytän nyt aluksi käyttämäni rekursion rottina, ei siitä ratkaisijoille paljon iloa ole kun niin hidas on:
// nyz = nyxhyhxhwra xbxbanvfzääeä, ny[] = nyxhgnhyh, znxfvzv ba xnfinghfcävivra zääeä
cebprqher GSbez1.Ynfxh(pbafg a: olgr);
ine v,a2: olgr;
ortva
sbe v:=1 gb nyz-1 qb ortva
a2:=a+ny[v];
vs a2>znxfvzv gura rkvg
ryfr vs a2=znxfvzv gura ortva
vap(ghybf); rkvg;
raq ryfr vs a2<znxfvzv-1 gura Ynfxh(a2);
raq;
raq;Tuon nopeudesta sen verran, että ensimmäiset 40 päivää se laskee kaikki yhteensä alle sekunnissa, siitä eteenpäin hidastuu 50 tienoilla niin paljon että kestää arviolta useista minuuteista lähtien ilmeisesti useisiin tunteihin.
lainaus:
Bruteforce hidastuu eksponentiaalisesti joka kierroksella
Tarkoitat kai, että sinun bruteforce-toteutuksesi.
Oma bruteforce saa laskettua 1800 asti saa laskettua ilman biginttejä jos likiarvo kelpaa ( 1,81976360087128E+304 ), jolloin menee 0,2 sekuntia. 10000 asti saisi laskettua ilman biginttejä 3 sekunnissa, mutta liukuluvusta tulee "INF" :D Veikkaan että biginttien kanssa tulee joku 6 sekuntia.
Mielenkiintoinen havainto: 10000:een asti laskeminen kestää (kokonaisluvuilla) 13 sekuntia, tulosten tulostaminen lisää tähän vielä 7 sekuntia. Tässä korostuu yhteenlaskun ja jakolaskun nopeusero. Kieli on Python.
Kyllähän tuo kieltämättä alkaa hidastua mitä isompiin mennään. Itsellä alkukukat 2-4000 vei aikaa 1,5 sekuntia mutta 2 - 10000 jo 14 sekuntia.
Arvionikin 6 sekunnista meni pahasti pieleen, mutta syy on tuossa, että prossu joutuu jo peruslaskutehtävissä rouskuttelemaan ihan eri tahtiin kun luvut alkavat olla luokkaa 10^1700.
Tästähän voi vaikka Metabolix tarkistaa onko hänellä sama tulos..
10000 208978022059268917120913434181137975923025669056
649377704679087998198446732811535356963789027040
548006499420718140292432861686628018302307461377
994503775836673133150446829852799129861026072577
354931728692184181553054502173799361867222093641
803909161610299917674974032106155307966840165158
074241667228383965048332377222465409619474680280
674893920449609273068928836282801645604039498955
149357197688741521582580330291608127533272758346
744617483368562368142535158021494872596300473489
561549051406226212315910967618439834259638489440
205344598731022264538173404301112475274325469147
362705342704408698643523247659355996630059989338
729635858239397967006379354024135371321130903174
811924622631806682363437228540039680612967371102
543066497955383768892779483140157967553047791737
759549406970481921331156044595362602560429829523
462869328566014063901523054316592171365330574358
563109382848364612424275198612965045629095967627
045789167744340935564826499217931837127773072589
307745604562766963789088706784161894027231718643
337871878579062940
Tehokkaan ratkaisun keksimistä voi helpottaa, jos käy läpi muutaman ensimmäisen tapauksen kynällä ja paperilla ja miettii, miten seuraavan tapauksen voisi laskea kätevästi niiden avulla.
Tein huvin vuoksi omasta ohjelmastani QBasic-version. 33 MHz:n 486:lla koko tehtävän laskenta-aika on 0,05 sekuntia.
Kokeilinpas nopeustestejä myös omalla koodillani ja näköjään arvojen 2-10000 laskeminen ilman tulostusta hoituu suunnilleen ajassa 1,5s 1,86GHz:n Pentium M -koneella (ja tuli sama tulos 10000:n tapaukseen kuin Grezillä).
Jos mukaan otetaan vastausten tulostaminen /dev/nulliin niin aikaa menee noin 2,25s (ja ilman devnulliin ohjausta 5,9s, mutta tämä ei varmaan kerro enää paljoa itse ohjelman tehokkuudesta).
Käytin ohjelmassa isojen lukujen hoitoon GMP-kirjaston C++-wrapperia, jonka voimin on tullut myös monet project eulerit ratkaistua.
Oma Haskell-toteutukseni laski alkukukat 2-10000 seuraavasti:
:!time ./alkukukka > /dev/null real 0m5.089s user 0m5.040s sys 0m0.036s
Tämä ajettuna Intel(R) Xeon(R) CPU E5405 @ 2.00GHz :lla.
Oletanko oikein, että nuo teidänkin ratkaisut on periaatteesa brute force, eli nopeuserot riippuvat lähinnä kielen tehokkuudesta. Itse käyttämäni biginteger luokka ei tuntunut mitenkään erinomaiselta, eikä kielikään (nyt C#) ehkä ole se paras mahdollinen. Vai onko teillä jokin älkykäs kaava, joka laskee suoraan?
Luokittelet ilmeisesti minkä tahansa ratkaisun bruteforceksi, vai mikä sinusta olisi jotain muuta (edes jossain muussa tehtävässä)? :D Minusta tässä bruteforce on sellainen, joka ei osaa tallentaa mitään sopivia välituloksia vaan oikeasti käy läpi kaikki mahdolliset järjestykset alusta loppuun (mielekäs noin 40:een asti, aikavaatimus suhteessa tulokseen) tai jopa kokeilee kaikkia PPVV-jonoja ja valitsee ne, joissa määrät ovat alkulukuja (toimii kohtuullisesti ehkä 20:een asti, jos toteutetaan hyvin; aikavaatimus O(n 2n)).
Edit. Kaava? Eli muut kuin O(1)-ratkaisut ovat brute-forceja? :) Suureen osaan mahdollisista tehtävistä ei ole olemassa edes O(n)-aikaista ratkaisua, tämähän on nyt kai O(n*m), missä m on n:ää pienempien alkulukujen määrä.
Metabolix kirjoitti:
Luokittelet ilmeisesti minkä tahansa ratkaisun bruteforceksi, vai mikä sinusta olisi jotain muuta (edes jossain muussa tehtävässä)?
No yleensä ottaen lasken brute forceksi algoritmin, jolla ei ole mitään "älyä", eli joka käy vaan läpi kaikki vaihtoehdot. Muuna pidän jotain mikä käyttää mitä tahansa matemaattista mallia jolla päästään nopeampaan suoritustapaan tai muuta älykkäämpää algoritmia kuin kaikkien vaihtoehtojen läpikäyntiä.
Sanotaanko esimerkiksi että jos pitäisi laskea lottorivien määrä, niin en pidä bruteforcena käyttää kertomaa tyyliin 39! / 32! / 7!.
Jo laskettujen tulosten tallettamista/kakuttamista en pitäisi varsinaisesti eri alogritmina, vaan ainoastaan optimointina. Jokin sopiva ohjelmointikielihän voisi tehdä jopa ko. optimoinnin käyttäjän puolesta.
Puhdas bruteforce olisi tässä tosiaan sellainen, joka kävisi kaikki mahdolliset yhdistelmät läpi ilman etukäteiskarsintaa ja laskisi niistä ehdot täyttävien määrät. Esim. 42 päivää kasvavalla kukalla yhdistelmiä tutkittaisiin 2^42 = 4398046511104 kpl.
Oma "bruteforceni" toimii siten, että se ... xbxbnn nyxhyhihvfgn fvaäafä grubxxnnyyn flillfunhyyn xnvxxv znuqbyyvfrg wbhxbg, wbvffn nyxvbvqra fhzznxfv ghyrr rgfvggl xnfihcävivra zääeä. Rev wäewrfglxfvä rv xälqä yäcv, inna wbhxba wäfravfgä ynfxrgnna lxfvaxregnvfryyn xnninyyn znuqbyyvfgra wäewrfglfgra zääeä.
Edit: Täsmennän vielä, etten oikeasti pidä algoritmiani bruteforce-kategoriaan kuuluvana, mutta se nojaa monia muita enemmän laskentatehoon.
Grez kirjoitti:
Jo laskettujen tulosten tallettamista/kakuttamista en pitäisi varsinaisesti eri alogritmina, vaan ainoastaan optimointina. Jokin sopiva ohjelmointikielihän voisi tehdä jopa ko. optimoinnin käyttäjän puolesta.
Viestisi perusteella pidät lähes kaikkia dynaamisen ohjelmoinnin algoritmeja brute-forcena, mikä eroaa hyvin paljon termin normaalista käytöstä.
Wikipedia antaa termille "brute-force search" hyvinkin tiukan määritelmän, jonka mukaan suunnilleen ainoa oikeasti brute-forceksi kelpaava vastaus olisi tuo että generoidaan kaikki mahdolliset PPVV-jonot ja testataan mitkä niistä kelpaavat, mutta vaikka termiä laajennettaisiin sisältämään myös ne merkitykset joissa sitä normaalisti käytetään, ollaan vielä kaukana tehokkaista dynaamisen ohjelmoinnin algoritmeista.
Suosittelen siis että harkitset käyttämäsi terminologian muuttamista tässä asiassa mikäli toivot pystyväsi keskustelemaan näistä asioista aiheuttamatta hämmennystä kanssaihmisissä.
Chiman kirjoitti:
Oma "bruteforceni" toimii siten, että se ... xbxbnn nyxhyhihvfgn fvaäafä grubxxnnyyn flillfunhyyn xnvxxv znuqbyyvfrg wbhxbg, wbvffn nyxvbvqra fhzznxfv ghyrr rgfvggl xnfihcävivra zääeä. Rev wäewrfglxfvä rv xälqä yäcv, inna wbhxba wäfravfgä ynfxrgnna lxfvaxregnvfryyn xnninyyn znuqbyyvfgra wäewrfglfgra zääeä.
Tuo on täsmälleen se kaava mitä hain vähän ylempänä, en vaan ymmärrä miten sen laskee. Joukot mulla on kyllä tiedossa ja niiden laskemista kokeilleena se kyllä hakee kaikki 99 nopeasti. Ei vaan löydy mitään logiikkaa...
Toisekseen, tehtäväsivulla on lukenut jo useita putkaposteja sitten: "Erilaisia ratkaisuja tulee näkyville myöhemmin.". Milloinkas näitä ratkaisuja tulee? :p
Olen ilmeisesti sitten käyttäny termiä väärin.
Ehkäpä muotoilen kysymyksen (sisuaskille ja laitiselle) uudelleen:
Oletanko oikein, että nuo teidänkin ratkaisut on periaatteesa sellaisia että ne vaan muodostavat eri mahdolliset vaihtoehdot ja laskee niiden määrän (mahdollisesti välituloksia kakuttaen), eli nopeuserot riippuvat lähinnä kielen tehokkuudesta. Itse käyttämäni biginteger luokka ei tuntunut mitenkään erinomaiselta, eikä kielikään (nyt C#) ehkä ole se paras mahdollinen.
Vai onko teillä jokin älykäs kaava, joka laskee suoraan?
lainaus:
Tuo on täsmälleen se kaava mitä hain vähän ylempänä, en vaan ymmärrä miten sen laskee.
Yleisesti ottaen joukon järjestymisen voi laskea käyttäen kertomaa. Eli n!, jossa n on alkioiden määrä. Esim. 5! = 1*2*3*4*5. Tässä tulee vaan ongelmaksi se, että joukossa voi olla sama luku moneen kertaan, jolloin tässä tehtävässä siltä osin kaikkia eri järjestyksiä ei hyväksytä eri tapauksiksi. Eli joukosta täytyy vielä etsiä sellaiset osajoukot, joiden kaikki jäsenet on samoja ja jakaa tulos näiden joukkojen kertomilla.
Eli esimerkiksi jos otettaisiin yksi kukan 19 joukoista:
2 2 2 2 3 3 5
Niin tälle joukolle löytyy 7! / 4! / 2! = 105 vaihtoehtoista järjestystä.
En kuitenkaan ratkaisisi tätä tällä tavalla, koska minusta yksinkertaisempi menetelmä on nopeampi. Tuossa menee minusta turhaa aikaa sellaisen tiedon muodostamiseen, jota emme tarvitse. Voisi sanoa, että meitä kiinnostaa vain tietyn pituisen jakson muodostavien summavaihtoehtojen määrä, ei se, mitkä ne summavaihtoehdot ovat. Eli heti kun määrä on saatu laskettua, voidaan unohtaa kaikki muu.
Toki kaikenlaisessa pyörittelyssä voi olla ideaa ongelman analysoimiseksi esimerkiksi matemaattisen mallin löytämiseksi.
Luultavasti erot johtuvat ohjelmointikielten tehokkuuseroista tai toteutusten nyansseista. Programming language shootoutin mukaan C# olisi noin 50% Haskellia hitaampi, joka selittänee osan ongelmasta, vaikka itse olen ollut huomaavinani, että Haskell ei omissa ohjelmissani useinkaan pysty juuri tähän lähes C++-nopeuksiseen suoritukseen.
Edit. Huomioi, että ajoin oman ohjelmani tehokkaalla tietokoneella.
Grez kirjoitti:
Oletanko oikein, että nuo teidänkin ratkaisut on periaatteesa sellaisia että ne vaan muodostavat eri mahdolliset vaihtoehdot ja laskee niiden määrän (mahdollisesti välituloksia kakuttaen), eli nopeuserot riippuvat lähinnä kielen tehokkuudesta. Itse käyttämäni biginteger luokka ei tuntunut mitenkään erinomaiselta, eikä kielikään (nyt C#) ehkä ole se paras mahdollinen.
Suunnilleen näin menee. Veikkaisin, että oman koodini tehokkuus suhteessa muihin johtuu pääasiassa tuon GMP-kirjaston (joka on muistaakseni osittain kirjoitettu assemblyllä) tehokkuudesta.
Ohjelmassani lähes kaikki aika vaikuttaa kuluvan pienessä silmukassa jossa suoritetaan vain isojen lukujen yhteenlaskua, eli sen nopeus on ehdottomasti dominoiva tekijä ohjelman nopeuden kannalta.
Periaatteessahan GMP:lle voisi tehdä wrapperin suunnilleen mille tahansa kielelle, eli sinänsä tässä ei ole kyse niinkään edes kielen nopeudesta vaan lähinnä saatavilla olevista kirjastoista.
Grez kirjoitti:
Sanotaanko esimerkiksi että jos pitäisi laskea lottorivien määrä, niin en pidä bruteforcena käyttää kertomaa tyyliin 39! / 32! / 7!.
Lähemmin tarkasteltuna tämäkin algoritmi on O(n)-aikainen, koska kertoman n! laskemiseen tarvitaan n-2 kertolaskua. Ja voisihan jokin ohjelmointikieli sisältää myös valmiin taulukon alkukukkien kasvatustavoista. ;)
Itse tosiaan käytin Pythonia. Rubylla sama algoritmi vaati puolet enemmän aikaa (eli (1+½) * t, missä t on Python-version aika; tästä puolikkaasta on usein epäselvyyttä).
Metabolix kirjoitti:
Lähemmin tarkasteltuna tämäkin algoritmi on O(n)-aikainen, koska kertoman n! laskemiseen tarvitaan n-2 kertolaskua. Ja voisihan jokin ohjelmointikieli sisältää myös valmiin taulukon alkukukkien kasvatustavoista. ;)
Niin, tuohan oli vastauksena kysymykseesi esimerkki, jota en pidä brute forcena. Itse epäilit, että pidän mitä tahansa ei O(1) ratkaisua bruteforcena. Tuo on joka tapauksessa huomattavasti fiksumpi ja nopeampi tapa kuin käydä kaikki vaihtoehdot läpi.
Tulipa C-ratkaisun lisäksi tehtyä jonkinlainen Brainfuck-sähellyskin:
http://paste.dy.fi/?VAG
Tulostaa ekalle riville kahden päivän alkukukan kasvatustapojen määrän, tokalle kolmannen etc.
Ei sillä tätä tehtävää käytännössä kuitenkaan ratkasta, on (yllättäen) tosi hidas :)
Loysinpa mielenkiintoisen sivuston, toteutin todella ruman bruteforce-version, ja nyt kommentteja lukiessa huomaan, etta parantamisen varaa on, ja paljon, aikavaatimus tuotoksessa luokkaa O(n^n^n^n^n...)taytynee ottaa 'neuvoista' jotain irti.
kamilla kirjoitti:
aikavaatimus tuotoksessa luokkaa O(n^n^n^n^n...)taytynee ottaa 'neuvoista' jotain irti.
Tuskin nyt kuitenkaan, eiköhän O(n^6) ole jo raskaudessa aika kova saavutus tähän tehtävään. Tällöin 100 päivän kukan laskemiseen menisi luokkaa 10^12 operaatiota. Tuo O(n^n^n^n^n) tarkoittaisi käytännössä että ohjelma ei saisi ikinä ratkaistua edes 4 päivän kukkaa (luokkaa 10^154 operaatiota)
Joo, eikohan se tarkemmin ole O(n^2), taidan jo tana iltana saada aikaa version ilman tuota kakkosta, kunhan kiireiltani ehdin.
Ei taida ilman kakkosta olevaa versiota olla olemassa muuten kuin muodossa O(n m), vai kuinkahan tuo pitäisi kirjoittaa... Kertokaa toki, jos sellaisen keksitte.
Metabolix kirjoitti:
Ei taida ilman kakkosta olevaa versiota olla olemassa muuten kuin muodossa O(n m), vai kuinkahan tuo pitäisi kirjoittaa... Kertokaa toki, jos sellaisen keksitte.
Tekee taulukon, jossa on tieto aina edellisen kukan ja sitä seuraavan kukan kasvatusmäärien erosta ja sitten loopissa laskee pyydetyn kukan kasvatusmäärät.. :D
Aihe on jo aika vanha, joten et voi enää vastata siihen.