Tammikuun putkaposti kolahti juuri luukusta:
https://www.ohjelmointiputka.net/postit/tehtava.
Tällä kertaa aiheena on kombinatoriikka eli yhdistelmien muodostaminen.
ei riitä 64bittiä viimeisiin :(
Onneksi on olemassa kehittyneitä kieliä, joissa on sisäänrakennettu tuki rajattoman suurille luvuille :)
Pahinta tarkkuudenpuutetta voi yrittää lieventää oveluudella ja ulkopuolisilla laskimilla, jollaisia löytyy vaikkapa www.swox.com/gmp -sivun pohjanurkista.
Kun aluksi keksisi algoritmin, jonka voi laskimeen tunkea. Luulin jo kertaalleen tajunneeni toimivan, mutta tilanne olikin paljon monimutkaisempi kuin luulin, ja jätin homman toistaiseksi sikseen.
Sillä välin brute-force eli rekursiivinen syvyyshaku ei ole reilussa neljässä CPU-tunnissakaan löytänyt vastausta 110*110-ruudukolle...
Vihjeenä kerrottakoon, että tämän tehtävän voi ratkaista kokonaisuudessaan kynällä ja paperilla...
Sitähän tuossa käytännössä tarkoitin. Sössin vain kertaalleen joten harmistuin ja kyllästyin.
Algoritmin sain päässä hahmoteltua ja koodiin kirjoitettua melko nopeasti. On vaan aika tehoton jo 26:n jälkeen...
Niin, se on se brute-force. Itse tiedän suunnilleen, mitä pitäisi lähteä tekemään oikeaa ratkaisua varten, mutta laiskuus iski :)
Hmnjoo, tosiaankin paperilla ja kynällä voi ratkaista. ainakin tämä "yleinen kaava" kun sivu on >= 4 näyttää varsin hienolta:P
no se on nyt löydetty, vaikka vähän enemmän kokeilemalla, kuin ajattelemalla.
VB5:ssä voi käyttää desimal-tyyppiä, jolla on 29 numeron kapasiteetti, tosin mahdollisuus vain aritmeettisiin laskutoimituksiin. Tähän tehtävään riittää hyvin. Mutta kankeaa on aivotoiminta kun en tuota kuningasajatusta ole oivaltanut!:(
Kas taas mukava aivonystyröiden hieronta tehtävä. Pitäisiköhän koettaa saada tälläkertaa kaikki ratkaistuksi. :)
Löytyihän se nopea algoritmi, kun tarpeeksi kauan pähkäilin. Hyvä tehtävä tämäkin :)
Tuossa tulosten järjestämisessä on varmaan pieni bugi, sillä VilleP, phadej ja os löysivät täydellisen ratkaisun nopeammin kuin minä. Ilmeisesti olen listan kärjessä, koska lähetin jonkinlaisen ratkaisun ennen heitä, mutta parhaimman ratkaisun lähetysajankohdan pitäisi ratkaista järjestys.
Nopein kai on O(1) tässä tehtävässä, bruteforcaamalla on O(n^6), hihi, eron huomaa :P
Tämä tehtävä taitaa olla aavistuksen liian helppo. Näyttää nimittäin vahvasti siltä, että saan tehtävän kokonaan ratkaistuksi aika tyhmällä brute-force menetelmällä :). No joo, on sitä hiukan optimoitu siitä triviaalista O(n^6) ratkaisusta.
Pitäisi varmaan kokeilla etsiä sitä kaavaa, jos vaikka sen löytäisi nopeammin kuin viimeisen luvun laskentaan menee.
Ei tämä mitenkään liian helpolta minusta vaikuta. Hyvä vain, että on realistisen tasoinen tehtävä muillekin kuin teille algoritmien guruille :)
Itse en näe juurikaan järkeä ratkaista tätä edes optimoidulla brute-forcella, jos sillä kestää yli viisitoista minuuttia. Menee hyvä pähkinä silloin ohi.
Olen samalla kannalla kuin Metabolix: O(1)-algoritmin löytyminen on sen verran palkitsevaa, että sitä kannattaa yrittää. Ihan heittämällä se ei löydy, muttei tuo mielestäni ole liian vaikea kenellekään. Kynän ja ruutupaperin avulla kannattaa hakea ratkaisun logiikkaa kaikessa rauhassa.
Brute forcea jatkokehittämällä algoritmin teho saattaisi riittää tällaiseen kerran suoritettavaan ohjelmaan. Oikeastaan se voisi olla opettava välivaihe: Vaikka optimointiin esim. laskentahaarojen karsimisen muodossa panostaa paljon, tuloksena saatava algoritmi on silti auttamattoman hidas verrattuna parhaaseen mahdolliseen. Eräs kultainen sääntö kuuluukin: älä optimoi - valitse parempi algoritmi.
Minkä resurssin suhteen vaativuus saadaan luokkaan O(1)? Vastaushan riippuu sivun pituudesta, joten ainakaan asetelmien lukumäärä ei ole vakio kaiken kokoisilla laudoilla. Mielestäni ratkaisujen lukumäärä on laskujeni mukaan polynomiaalinen sivun pituuden suhteen (täytyy vielä tarkistaa laskelmat), mutta ei vakio. Olisi kiva kuulla mitä Chimanin tarkoitat O(1)-algoritmilla.
"O(1)-algoritmin" voi löytää myös ilman kombinatoriikan taitoja (tai kyllästyessään) suhteellisen helpolla ei-analyyttisellä tavalla. Riittävä kapasiteetti O(1)-sovelluksille löytyy vaikka Windowsin laskimesta.
O(1) tarkoittaa tässä tapauksessa algoritmin nopeutta - time complexity, mikä lie suomeksi. Tuo fiksu algoritmi vaatii aina saman määrän ja samantapaisia laskutoimituksia, oli ruudukon koko mikä hyvänsä.
Jaska kirjoitti:
Olisi kiva kuulla mitä Chimanin tarkoitat O(1)-algoritmilla.
Melko yksinkertaista laskukaavaa, johon sijoittamalla n:n arvo saadaan yhdistelmien määrä. Suoritukseen kuluva aika on siis jotakuinkin vakio.
OK. Aina pitää muistaa mainita minkä suhteen algoritmi on mitäkin kertaluokkaa. Harmittaa kun polynomiviritykseni ei toiminutkaan. Pitää treenata vielä kombinatoriikkaa.
Aikavaativuudeltaan O(1):ksi algoritmia et voi saada, sillä ratkaisujen lukumäärä kasvaa rajatta kun sivun pituus kasvaa rajatta ja toisaalta 3x3 tapauksessa ratkaisuja on äärellisen monta. Myöskin tilavaativuus kasvaa rajatta kun n kasvaa rajatta ja 3x3 tapauksessa vastaus mahtuu äärelliseen tilaan, mutta ratkaisujen lukumäärään tarvittavien bittien lukumäärä kasvaa rajatta kun sivun pituus kasvaa rajatta.
En siis vieläkään ymmärrä miten O(1) algoritmi on mahdollista, kun se ei ole mahdollista ainakaan tila- tai aikavaatimusten suhteen.
Ratkaisualgoritmin kompleksisuus ei olennaisesti riipu sivun pituudesta, jos ratkaisu n voidaan ilmoittaa suljetussa muodossa sivun pituuden s funktiona:
n = f(s).
Koska f on kuitenkin hyvin nopeasti kasvava funktio, tarvitaan luvun n käsittelemiseen yhä enemmän muistia ja tehoa tavallisten 32- ja 64-bittisten kokonaislukujen loppuessa kesken. Algoritmin todellinen ajan- ja muistinkulutus on siis itse asiassa kertaluokkaa O(log n)
Myönnän että O(1)-luokittelu oli turhan kevyesti annettu. Käytännössä tehtävässä annettujen sivupituuksien välillä suoritusaikojen erot ovat kuitenkin minimaaliset. Tässä esimerkkinä 113-numeroinen sivunpituus ja sitä vastaava yhdistelmien määrä:
123456789876543212345678987654321234567898765432123456789- 87654321234567898765432123456789876543212345678987654321
590117686497279411532492278190327282874461631868390111973- 944005753734852193797796717537000533122616720674543323376- 764164005265954225315370362317653187339085429280473574442- 342723946096247059440830398213768665579436396304133451604- 169626092568666109283857288331656521826472188222032054827- 690116450672991711658671032527272079719930996463447371238- 266634996391811032108111313404097001218620158387055769134- 543499605084492808782604031428606276974262923021633079491- 790740218303198793912851069525963128564469061616673474395- 149193164340194825039878311855198034110290087112178854263- 619010485698955915673833011923329973095720407537094149439- 770713148914164593237951408097977017970086052
Suoritusaika 700 MHz -koneella ja Pythonilla oli noin 1,5 ms. Alkuperäisen tehtävän kaikkien lukujen laskenta kesti hieman yli 1 ms.
Ohhoh, täytynee perehtyä Pythoniin. Sillähän onnistuu varmaan piin laskeminen 10 000 numerolla ja voin tarkistaa tuon seinällä olevan julisteen.
onnistuuhan isojen lukujen vääntö kielellä kuin kielellä, voi vaikka tehdä c++ wrapperi gmp:hen (villep:n postaama linkki) jolloin voi käyttää niitä tavallisten numeroiden tavoin.
tai sellainen on jo, en vaa löydä. (itse käytin bc:tä).
edit: katos gmp:ssa on wrapperi c++:lle mut en tiedä millainen se on.
Löytyihän se kaava sieltä kun vähän aikaa väänsin. Pakko myöntää että vähän huijasin, ilmeisesti os:n kuvailemalla tavalla sain kaavan esiin johtamatta sitä kombinatoriikan avulla.
FooBatin ratkaisusta olisi kyllä kiva kuulla lisää.
Oikeastaan tehtävä on silloin onnistunut, kun täydelliseen vastaukseen voi päästä monilla eri tavoilla. Aluksi ajattelin, että tehtävän suurin luku olisi 512. Se olisi selvästi ollut liian pieni.
Tämä lukualue oli siitä kiva, että jouduin miettimään, onko valitulla lukujonolla jokin syvällinen merkitys ratkaisussa :)
Oma ratkaisuni on siitä perus O(n^6) brute-force algoritmista johdettu noin O(n^3) algoritmi. Sisimpiä silmukoita pystyi poistamaan summakaavoilla ja jällelle jääneistä pystyi melko suuren osan laskentaa siirtämään ylemmälle tasolla. Lopullinen koodinpätkä on kyllä todella ruma ja siinä on käytetty aivan liikaa koodin kopioitia ja muita huonoja ohjelmointitapoja. Voinhan mä sen varoittavaksi esimerkiksi lähettää kunhan saan viimeisen luvun ratkaistua, kestää vielä noin 30h :).
Lukualue oli siitä huono, että se on juuri sillä rajalla, jonka kuvittelin pystyvän ratkaisemaan brute-forcella enkä siis ollut pakotettu keksimään sitä kaavaa. Jos viimeinen luku olisi ollut 50000 en olisi edes vaivaitunut optimoimaan ensimmäistä ratkaisuani, jolla hain lähinnä pienimpien lukujen malliratkaisut. Ei sinänsä että tämä olisi ollut huono asia. Algoritmien optimointi on ihan mukavaa puuhaa, vaikka usein se onkin vähän tyhmää, jos on olemassa se parempi ratkaisu.
Parantelin omaa brute-force ratkaisuani ja saisinkin varmaan laskettua useamman luvun kunhan vain jaksaisi odottaa paria minuuttia pidempään tuloksen ratkeamista.
FooBat: Täytyy sanoa, että nopeaksi olet saanut ratkaisusi. Kokeilin nimittäin omallani toiseksi viimeistä lukua (5168), jolloin arvoioin laskemiseen kuluvan noin 1000h luokkaa, kun laskukoneena on 700 MHz AMD :)
Taitaa olla omaa tyhmyyttäni, kun millään ole vielä keksinyt toimivaa kaavaa tuon laskemiseksi.
Löytyihän se kaava, kun lähti oman koneen ääressä oikeasta suunnasta hakemaan, ja Decimal-tyyppi (128-bittinen luku) löytyi onneksi myös .NET-kielistä. Miksi tuo ei olisi O(1)-algoritmi? Suora kaavahan tuo lopulta on, ja jos tyyppi on tavallinen (kuten int, tai nyt Decimal) eikä jokin erikoisempi viritelmä, niin laskutoimitukset menevät tietääkseni aina yhtä nopeasti.
Nähtävästi neljää pienemmät luvut antavat tuolla väärän vastauksen, mutta kakkonen menee päässäkin :) Yllättävää, että toimii niinkin pieniin asti. Olisin kuvitellut, että vasta 8 toimisi.
Metabolix kirjoitti:
Miksi tuo ei olisi O(1)-algoritmi? Suora kaavahan tuo lopulta on, ja jos tyyppi on tavallinen (kuten int, tai nyt Decimal) eikä jokin erikoisempi viritelmä, niin laskutoimitukset menevät tietääkseni aina yhtä nopeasti.
Prosessori ei voi suorittaa laskutoimituksia bittimääräänsä suuremmille luvuille kerralla, vaan se tarvitsee yhä useampia konekielikäskyjä luvun pituuden kasvaessa. Kehittyneemmät kielet piilottavat käytännön toteutuksen, joten ero ei näy päällepäin muuten kuin suoritusajan hitaana kasvuna. Ja nyt puhutaan siis O-luokituksesta vain suoritusajan suhteen.
O(1) algoritmin keksimiseen meni kolmisen tuntia, mutta ei riitä millään lukujen koko yli kohdan 11, missä kielissä olisi helposti mahdollisuus isoihin lukuihin kun vb ei näytä olevan yksi niistä?
Ei mitään enää. Python osasi.
Deewiant kirjoitti:
O(1) tarkoittaa tässä tapauksessa algoritmin nopeutta - time complexity, mikä lie suomeksi.
Algoritmin aikakompleksisuus.
Putkaan voisi kirjoittaa oppaan algoritmien kertaluokasta. Kaikille ei näköjään ole selvää, miksi esimerkiksi tilavaativuudeltaan O(1) tyyppisistä lauseista koostuva algoritmi ei välttämättä ole tilavaativuudeltaan enää O(1). Ja toisaalta sanonta "algoritmi on kertaluokkaa O(log n)" on huono. Voihan olla, että asymptoottinen suoritusaika on logaritminen verrattuna syötteen pituuteen, mutta tilavaativuus on vakio.
Ja aina on muistettava mainita mitä suuretta n tai muut kaavassa esiintyvät muuttujat kuvaavat!
Pitääpä itsekkin kokeilla tuota ja varmaan saan nopeammin vastaukseni jos teillä on 700MHz koneet ja itse saan perjantaina 3.2GHz koneen, joten väsään sen koodin nyt ja annan sen laskea ;)
Aihe on jo aika vanha, joten et voi enää vastata siihen.