Reilu vuosi sitten Putkapostissa esiteltiin Uolevi, joka halusi hävittää kaikki luvut maan päältä. Nyt Uolevi on hieman rauhoittunut ja oppinut hyväksymään joitakin lukuja.
https://www.ohjelmointiputka.net/postit/tehtava.
Hmm, jos tällainen on sopivaa, niin minulla on ratkojille pieni pyyntö.
Ongelman laatijana minua tietenkin kiinnostaa nähdä ratkaisuja. Jos lähetät ratkaisusi Antille, niin voit mielelläsi lähettää sen myös minulle saman tien. Osoitteeni on profiilissa. Tai voit sanoa Antille, että hän saa lähettää ratkaisun eteenpäin minulle ennen julkaisua. Olisihan se mukava nähdä, miten muut lähestyvät ongelmaa.
Ongelmalla ei ole suoraa esikuvaa missään, mistä minä tietäisin. Viihteellisessä lukuteoriassa on paljon lukujen muotoon liittyviä ongelmia ja ne inspiroivat tämänkin.
Jos jollakulla on intoa, voi hän kertoa tutkimustuloksia tehtävän ainestoa isommista luvuista ja niiden tasaajista. Olisi myös kiva kuulla käytetyistä kielistä ja ohjelmien suoritusajoista. Tiedän yhden tehokkaan menettelyn tehtävän ratkaisuun, jonka tietenkin kerroin Antille. Niitä voi olla toisiakin.
Olipa helppo! Kerrotaan kaikki nollalla, jolloin aika moni luku tasoittuu.
Kopeekka kirjoitti:
Viihteellisessä lukuteoriassa.
Kiva termi. Täytyypi alkamaan opiskelemaan sitä, kunhan ensiksi oppisi algebrallista ja aritmeettista lukuteoriaa. :)
Eh niin joo kyllä teknisesti ottaen olet oikeassa suunnassa ajatuksinesi kyllä oikeastaan :-)
Joku editoi pois sanat positiivinen kokonaisluku. Mahdollisesti minä jo ennen kuin esitin ongelman Antille. Onkohan tuo tarpeellista korjata?
Muokkaus: Kyllä se viihteellinen lukuteoria aina ulkoalukuteorian voittaa ;-)
Lisäsin tehtävänantoon sanan "positiivinen", tuskinpa täsmennys ainakaan haittaa.
Vaikuttaa hyvältä tehtävältä. Aloitin puhtaalla bruteforcella nähdäkseni miten hyvin sillä pärjää. Kohtalaisesti: 136/162. Sitten runsaasti turhaa laskentaa karsiva algoritmi: 153/162.
Yhdeksän suurinta lukua piileskelevät vielä ja vaativat paremman algoritmin.
Taisi olla onnekas löytö vaikeusasteen puolesta. Jotain tarttee tehrä, ellei ole määrättömästi konetehoa saatavilla :-)
Tutkin jonkin verran 5-numeroisia lukuja tehtäväalueen yläpuolelta ja siellä eräässä paikassa nämä yhdeksän suurinta tasaajalukua vaativat nelinumeroiset luvut tekivät oudon comebackin. Antti ehkä huomasi sen lähettämästäni aineistosta. Tällä tiedolla tuskin on merkitystä, mutta oli tosi outo juttu, että ne putkahtivat sielläkin esiin. Eikä minulla ole aavistustakaan, miksi.
Onneksi näitä kaikkia vaikeita syvyyksiä ei tarvitse koluta, että Uolevi-polo saa itselleen rauhan.
Toimiikos toi tarkastin kunnolla isoilla luvuilla?
Keksin yhden ratkaisutavan, jolla tämä tehtävä taitaa ratketa. Ensimmäisessä testiajossa luvulle 1089 löytyi 61 merkkinen kerroin (ei välttämättä pienin) ja 64 merkkinen tasattu luku. Tarkastin kuitenkin valittaa, että kerroin on virheellinen luku.
Luvun pituuden rajaksi oli jäänyt 50 numeroa, mutta nyt muutin rajaksi 1000 numeroa. Toimiiko tarkastus nyt?
Näyttää toimivan.
Nyt on ilmaantunut ainakin yksi 1620-pisteinen oikea vastaus. Ihanaa leijonat ihanaa!
Jos nyt annoin yllä sen kuvan, että tehtävässä on joku outo niksi, niin ei asia niin huonolla mallilla ole. Voi sen ratkaista monella tavalla. Yksi tuntemani tapa on kyllä muita selvästi kätevämpi.
(Tarkoitus ei ole mitenkään kehuskella millään. Onhan minulla kuukauden etumatka ongelman kanssa.)
Chiman kirjoitti:
runsaasti turhaa laskentaa karsiva algoritmi: 153/162.
Antin paljastus 50 numeron rajasta rohkaisi minut jättämään juuri tuon algoritmin jauhamaan tunneiksi, ja sillähän ne loputkin luvut sitten löytyivät. Ratkaisuni ei paljon tyylipisteitä ansaitse, mutta algoritmissa riitti vääntöä juuri ja juuri tarpeeksi.
en tajua. Taaskin periaate toimii aivan oikein mutta bruteforcetus ei tuota tulosta. Aivan liian hidas.
Paljonkos näihin on yleensä vastausaikaa? Nyt ei taida saada kunnon vastausta aikaseksi, erittäin yksinkertaisella tavalla saa tuon n. 150/162 selvitettyä, tai ehkä hyvällä tuurilla kaikki. Ei jaksa miettiä parempaa algoritmia.
Yleisesti ottaen brute force on hidas. Miettikää nopeampi vaihtoehto; sellainen on olemassa.
Yleensä tehtävä näkyy sivupalkissa noin kuukauden, mutta myös vanhoihin tehtäviin saa lähettää vastauksen, jos niihin ei ole vielä julkaistu malliratkaisua. Mainittakoon, että tämän tehtävän voi ratkaista nykyaikaisella tietokoneella kokonaisuudessaan alle sekunnissa.
Jonkinlaisen malliratkaisun suoritusajan voisi kaiketi laittaa aina kunkin tehtävän yhteydessä näkyville, jotta olisi jokin vertailukohta oman ratkaisun tehokkuudelle. Tietenkin on mahdollista, että joku keksii ratkaisuja kynällä ja paperilla (kuten nyt vaikkapa tehtävässä Kuninkaan hevoset), mutta ohjelmointia vaativissa tehtävissä tieto tehokkaamman tavan olemassaolosta voi lisätä motivaatiota sen etsimiseen, vaikka olisi jo sen hitaamman tehnyt ja vastaukset lähettänyt.
Tosiaan tehtäviin voisi lisätä merkinnän, viekö paras ratkaisu aikaa pari millisekuntia, pari sekuntia vai pari minuuttia. Jos vastauksen saamiseksi piti jättää kone yöksi laskemaan, voi olla varma, että parempi tapa on olemassa.
Metabolix kirjoitti:
Jonkinlaisen malliratkaisun suoritusajan voisi kaiketi laittaa aina kunkin tehtävän yhteydessä näkyville, jotta olisi jokin vertailukohta oman ratkaisun tehokkuudelle.
Miten tuota voi mitata? Eri koneiden laskutehot vaihtelevat. Minä esimerkiksi ratkaisin tämän tehtävän paljon nopeammin omalla koneellani kuin jääkukan, jossa käytin kynää, paperia ja kännykkäni laskinta.
Jaska kirjoitti:
Metabolix kirjoitti:
Jonkinlaisen malliratkaisun suoritusajan voisi kaiketi laittaa aina kunkin tehtävän yhteydessä näkyville, jotta olisi jokin vertailukohta oman ratkaisun tehokkuudelle.
Miten tuota voi mitata? Eri koneiden laskutehot vaihtelevat.
Niinhän ne vaihtelevat, mutta kyllä siitä silti yleensä näkee, onko se nykykoneella lähempänä sekuntia, minuuttia vai tuhannesosasekuntia, vaikka useinhan se näissä tapaa hieman alle sekunnin olla.
Aihe on jo aika vanha, joten et voi enää vastata siihen.