Uusi putkaposti on viimein ilmestynyt:
https://www.ohjelmointiputka.net/postit/tehtava.
Tällä kertaa tehtäviä on kaksi, jotka liittyvät samaan aiheeseen, mutta jotka voi ratkaista erikseen.
Palkissa oleva linkki osoittaa vieläkin lukut-Putkapostiin.
Nyt virhe on korjattu, kiitos ilmoituksesta.
Ilmeisesti sanojen lukumäärä on saatava oikein, jotta vastaus kelpaisi? Tähänkin olisi ehkä kannustava sellainen vaihtoehto, että pisteitä saisi lukumäärän mukaan...
Jos kielen sanojen lukumäärän yleensä ilmoittaa, sen täytyy olla oikein. Pelkkä kielen lyhin sana riittää kuitenkin vastauksessa, jos sanojen määrää ei ole saanut vielä selville.
Brute forcella saa 59 ainakin pistettä :-)
Varmaankin saan kuitenkin koodattua paremman ratkaisun, ennen kuin tuo ajo neljännelle kielelle pysähtyy. Mietintämyssy päähän. Hyvä ongelma.
Lyhimpiä sanoja saa kyllä melko helposti muodostettua käsinkin varsin yksinkertaisella menetelmällä.
Syötetiedostossa on muuten välissä nollatavuja, jotka haittaavat hiukkasen sen lukemista. Ensimmäinen tällainen näyttäisi esiintyvän 62906-merkkisessä syötteessä. Edit. Tarkemmin siis, noiden nollatavujen paikalle ilmeisesti kuuluisi aina jokin merkki.
Onkohan vika nyt ratkaisussani vai vastausten tarkistuksessa, kun mielestäni tein toimivan ratkaisun mutta kuitenkin tuo 41 merkin vastaus ja isommat ovat väärin? En oikein itse hahmota, miksi siinä kohti menisi jokin eri tavalla kuin pienemmissä syötteissä, jotka ratkeavat oikein.
Tiedostoon on tosiaan eksynyt nollatavuja, niiden kohdalle kuuluu kirjain A. Nyt palvelimella on korjattu tiedosto, joka kannattaa ladata vanhan tilalle (tai muuttaa ohjelmassa nollatavut A-kirjaimiksi).
Voisitko lähettää ohjelmasi ja ratkaisusi minulle, niin tutkin niitä huomenna aamupuhteeksi? Ei olisi suurikaan yllätys, jos vika olisi minun ohjelmassani, joka tosin myös ratkaisee nuo pienet tapaukset samalla tavalla.
Antti, saat minultakin postia. En nyt tiedä onko vika sittenkin koodissani. Saatpa kuitenkin verrata sitä väärää tulostani muihin arvauksiin.
Sori tyly Haskell-tyylini. Olisihan sitä voinut ihmisen tavalla kirjoittaa, jos olisi tiennyt, että muille pitää näyttää. ;-)
Nyt tähän mennessä ilmenneet viat on korjattu Metabolixin ja Kopeekan avustuksella. Jos tarkistaja ei aiemmin kelpuuttanut vastauksia, nyt kannattaa kokeilla lähettää uudestaan.
No, nyt on puolet tehty. Pitää vielä kirjoitella se osa, joka hakee puuttuvia sanoja. Idea on tiedossa jo - ja toivottavasti se on tarpeeksi tehokas.
Tarkastaja on muuten aika tarkka välilyöntien suhteen. Tarjosin ensin versiota, jossa M-kirjaimen ympärillä oli kaksi välilyöntiä kumpaankin suuntaan, eikä se kelvannut. No, helppohan se oli muuttaa, että ohjelma tulosti vain yhden, kuten tarkoituskin oli.
Esimerkki seuraa. Tässä X korvaa oikean lukuarvon ja _ välilyönnin.
Tarjosin ilman lainausmerkkejä "4__M__X". Oli virhe. Sen sijaan "4_M_X" kelpasi.
(En nyt tiedä pitääkö tuota ominaisuutta edes korjata. Tiedoksi halusin antaa.)
Nyt välilyöntejä voi käyttää vapaammin vastauksen lähetyksessä.
Melko kookkaita tulee puuttuvista sanoista. Lisäksi oli taas erimielisyys siitä, mikä kelpaa ja mikä ei. Taidan tällä kertaa kuitenkin tehdä jotain väärin ihan vain ja ainoastaan itse.
Pitää vielä miettiä ratkaisua. Ehkä se toinen tapa on sittenkin parempi.
EDIT: Eikun pahus, se oli cut & paste -virhe. En antanut koko sanaa, joten eihän se tietnekään kelvannut. Ei siitä siis huolta.
EDIT THE 2nd: Ja nyt on se virallinen ja oikea vastaus sisässä. Pidän hyvin mahdollisena, että se ei ole optimaalinen. Sen etsivä ohjelma ei ainakaan ole :-)
Tosiaan, eipä tullut mieleenikään palauttaa luvuista vain sitä kahdeksaa numeroa... Käytin pitkiin lukuihin GMP-kirjastoa, ohjelma laskeskeli noin 80 sekuntia tuota koko pakettia. Vain viimeisten numeroiden kanssa ratkaisu pyörähtää läpi 0,05 sekuntissa lukemisine kaikkineen.
Mukava tehtävä, heti luettuani ajattelin, että tässä on oltava nyt dynaamista ohjelmointia... Ja sitähän se tavallaan oli.
Minulla ainakin vastausten lähettäminen kestää aivan järjettömän kauan, mistähän moinen?
Hmmm... Lähetyslomake näyttää jumittuneen (jo yli 7 min mennyt), mutta näen jo oman nimeni ilmestyneen vastaukset osioon. Mikä tuossa lähetystilanteessa oikein kestää, jos kerran pisteenikin on jo laskettu?
EDIT. Tunti mennyt, mutta vieläkin lataa sivua. No, ihan sama mihin se on jumittunut, kunhan pisteet tulevat listaan.
Se oli hidas minullakin.
Vastauksen tarkistus vie oman aikansa, koska satojen tuhansien merkkien merkkijonojen käsittely PHP:llä ei ole kovin nopeaa. Kantasana täytyy nimittäin tutkia alusta loppuun, jotta voidaan tarkistaa, että annettu sana ei ole sen osana. Näköjään olette kuitenkin onnistuneet saamaan vastauksia läpi, eli nykyinen tarkistus taitaa jotenkuten riittää. Jos sivun lataus kestää ja kestää, mutta tulos on ilmestynyt näkyviin, latauksen voi kyllä keskeyttää.
On muuten kohtalaisen iso toi viimeinen luku 10220000 etenkin kun sen suhteuttaa esimerkiksi universumissa olevien atomien lukumäärään (noin 1080).
Ehkä tuo viimeinen ongelma oli vähän turhankin iso ottaen huomioon, että tähän tehtävään ei taida oikein olla puoliksikaan järkevää brute force ratkaisua. Eipä tässä taida mitkään nopeusvertailutkaan olla kovin järkeviä, kun suurin nopeusero tulee käytettävästä matematiikkakirjastosta eikä niinkään itse ohjelmoidusta algoritmista.
Mitenkäs tuo tarkastin on muka noin hidas? Eihän se tarvitse edes tehdä mitään merkkijonon muodostuksia tai muuta muistinkäsittelyä mikä veisi tuhottomasti aikaa. Eikös siinä pitäisi pärjätä noin yhdellä taulokkoviittauksella ja if:llä jokaista kantasanan merkkiä kohden? Nyt tuntui jokatapauksessa vievän lähemmäs tunnin toi tarkastaminen (tosin kun ensin lähetin vain lyhimmät luvut, ne menivät läpi alle 10 minuutissa, kummallista ottaen huomioon, että lukumäärän tarkastaminen pitäisi olla nopeaa, kun siinä on vain yksi oikea arvo). Viekö toi PHP:lla tosiaan noin kauan?
Aika pitkältä tuo tarkistusaika tuntuu. Tarkistuksenhan voi tehdä siten, että ensiksi verrataan vain merkkijonon tietyssä positissa olevaa merkkiä. Jos ei täsmää, hypätään seuraavaan positioon. Jos täsmää, tutkitaan seuraavaa merkkiä jne. Näin tarkistusaika on suoraan verrannollinen merkkijonon pituuteen.
Ymmärsinkö nyt tehtävän oikein?
Eli kantasanasta EYUIA saa seuraavat sanat:
E Y U I A EY EU EI EA YU YI YA UI UA IA EYU EYI EYA EUI EUA EIA YUI YUA YIA UIA EYUI EYUA EYIA EUIA
Jos tarkistus kestää minuutteja (tai tunnin), jossain täytyy olla vikaa. Sanojen määrän voi tosiaan tarkistaa suoraan, ja lyhimmän sanan tarkistuksessa kantasana käydään vain kerran läpi. Tutkin asiaa vielä tarkemmin, olisi aika yllättävää, jos pitkien merkkijonojen käsittely olisi noin hidasta PHP:llä.
Lahha: Olet varmaan ymmärtänyt oikein, mutta listaltasi puuttuu kaksi sanaa (YUIA ja EYUIA).
Jos lähetän vastauksen 4 L AAAAA, tarkastin sanoo, että virhe: tyhjä vastaus. Tyhmä ehkä, mutta ei tyhmä.
Kokeilin, voiko saada negatiivisia pisteitä ;-)
Tämä on vaikein Putkaposti minulle tähän mennessä. Junaradat-ongelma vaati ahkeraa tuhertelua kynällä ja paperilla, mutta löysin sentään toimivan tavan. Tässä en nyt vain hoksaa parasta menettelyä...
Täytyy laittaa syrjään toistaiseksi, että saan jotain oikeaakin tehtyä.
FooBat kirjoitti:
Eipä tässä taida mitkään nopeusvertailutkaan olla kovin järkeviä, kun suurin nopeusero tulee käytettävästä matematiikkakirjastosta eikä niinkään itse ohjelmoidusta algoritmista.
Kahdeksan viimeistä numeroa kulkevat varsin näppärästi tavallisessa 32-bittisessä kokonaislukumuuttujassa, sellaista varmaankin osaa valtaosa kielistä käsitellä jokseenkin samalla tavalla. Pitemmät luvut olivat tarpeen vain, jotta sai tarkistettua, että tuo kahdeksan numeron laskenta toimii oikein, ja tässäkin tarkistuksessa 64-bittinen luku riittäisi mainiosti.
Tässä kahdeksan numeron kuljettamisessa hommassa voi auttaa jakojäännöksen ymmärtäminen.
Metabolix kirjoitti:
FooBat kirjoitti:
Eipä tässä taida mitkään nopeusvertailutkaan olla kovin järkeviä, kun suurin nopeusero tulee käytettävästä matematiikkakirjastosta eikä niinkään itse ohjelmoidusta algoritmista.
Kahdeksan viimeistä numeroa kulkevat varsin näppärästi tavallisessa 32-bittisessä kokonaislukumuuttujassa, sellaista varmaankin osaa valtaosa kielistä käsitellä jokseenkin samalla tavalla.
Asiaa varmaan olisi auttanut, jos olisi lukenut tehtävänannon loppuun asti ja huomannut, että kahdeksan viimeistä numeroa riittää :) No hyvinhän toi Java noilla BigIntegereillä laskeskeli. Tuo tosiaan nopeutuu merkittävästi, jos laskut suoritetaan perustietotyypeillä ja moduloaritmetiikalla.
vähän vaikea tajuta tätä...
tehtävä kirjoitti:
kantasanan ollessa OAEYUIEEOAOYEIUU lyhin sana on kolmen kirjaimen pituinen, esimerkiksi UAA tai UYO.
miksi se on kolmen kirjaimen pituinen?
DrDeath kirjoitti:
miksi se on kolmen kirjaimen pituinen?
Koska minkä tahansa yhden tai kahden kirjaimen mittaisen sanan saa tuosta kantasanasta erotettua mutta noita kyseisia kolmen kirjaimen sanoja ei. Siis toisin sanoen siksi, että kolme on pienempi kuin vaikkapa neljä.
Niin, siis tuossahan saa sitä enemmän pisteitä mitä lyhyemmän kieleen kuulumattoman sanan keksii. Joten jos 1 tai 2 merkin pituisia ehdot täyttäviä sanoja ei ole, niin sitten eniten pisteitä saa 3 merkkisellä sanalla.
Hieman hiljaista tuntuu olevan tämän tehtävän suhteen. Mistäköhän johtuu? Lyhin kieleen kuulumaton sana on yksinkertaisen algoritmin takana ja sen keksimisen pitäisi sujua valtaosalta aiempia Putkaposteja ratkoneista.
Erilaisten sanojen määrä voi olla eri asia. Siihen en ole vielä saanut tehtyä mitään bruteforcea parempaa.
Ehkä syy hiljaisuuteen on se, että tehtävä on aluksi vähän pelottavan näköinen (sanojen määrä eksponentiaalinen pituuteen nähden) eikä mikään brute force ole edes lähellekään riittävä ratkaisu. Niinpä tämä tehtävä on vähän on/off tyyppinen eli joko keksii kunnon ratkaisun tai sitten ei keksi ratkaisua ollenkaan. Ratkaisun löytäminen vaatinee hiukan kynää ja paperia ja yksinkertaisimpien tapauksien läpikäyntiä.
Lyhyimpien sanojen löytäminen on tehtävän helpompi osa, mutta siinäkin pitää oivaltaa oikean tyyppinen lähestymistapa. Toki tuohon on helppo keksiä epäoptimaalisia ratkaisuja (esim. tarpeeksi monta A-kirjainta peräkkäin). Optimaalisen ratkaisun löytää varmaan helpoiten, kun miettiin miten tarkistetaan nopeasti kuuluuko sana kieleen ja sitten keksii sanan, jota tuo tarkistin ei hyväksy.
Minusta sanojen määrän laskeminen oli helpompi ongelma. Katsoin vain vähän, mitä arvoja brute force antoi lyhyille kielille, ja päättelin siitä säännön. Sen esitys vei muutaman rivin Haskell-koodia.
Katselin myös tovin, mitä brute force antaa puuttuviksi sanoiksi, mutta en löytänyt sääntöä. Kaipa se olisi helppo keksiä, jos miettisi ihan aikuisten oikeasti :-)
Löysin kyllä lyhyen epäoptimaalisen ratkaisun Pythonilla värkkäämällä. Sen suoritusaika oli noin puoli tuntia, josta lähes kaikki meni viimeisen kielen parissa. Kirjoitushetkellä minulta siis uupuu vajaat 6000 pistettä optimista.
No, vaati se Junaradat-ongelmakin aikanaan kynää, paperia & pohdintaa. Pitäisi kai tähän jossakin välissä palata. Tein lämmittelynä taas pari Project Eulerin ongelmaa tässä päästäisenä.
No tuo lyhyen sanan löytäminen on sikäli helpompi, että siinä voi saada melko hyviä pisteitä vaikkei löytäisikään sitä absoluuttisesti lyhintä sanaa. Itse asiassa on melko helppokin kehittää yksinkertaisia algoritmeja jotka löytävät hyvin lyhyitä sanoja, joskaan eivät välttämättä lyhintä.
Itse asiassa on melko helppokin kehittää yksinkertainen algoritmi, jolla saa ihan oikeasti sen lyhimmän sanan, ja aika samoista lähtökohdista pääsin kiinni sanojen lukumääräänkin.
No sinänsä jos oletetaan että tehtävän tällä hetkellä neljä parasta tulosta ovat oikeasti parhaita mahdollisia, niin sitten tuo minunkin käyttämäni menetelmä tuottaa lyhimmät mahdolliset sanat. Jotenkin vaan tuntuu siltä että voisi löytyä parempikin ratkaisu. Eli sanotaanko, että tuon lyhyimmän sanan "todistaminen" parhaaksi ratkaisuksi tuntuu haastavammalta kuin tuon määrän. Tosin itse kokeilin samaa menetelmää kahteen suuntaan ja molemmilla tuli saman pituiset joskin erilaiset sanat.
Siinä mielessä täytyy myöntää että itsellenikin tuo lyhimmän sanan laskeminen oli huomattavasti helpompaa kun menetelmän keksimiseen kului minuutti (ja keksin sen ennen tuota määrän laskemista) kun taas määrän pähkäilyyn upposi hyvinkin 15-30 minuuttia sen jälkeen kun olin tehnyt yksinkertaisen bruteforce-sovelluksen jolla pääsin testaamaan eri yhdistelmiä.
Itselläni ei kyllä ollut mitään yhteistä tuolla sanojen määrän laskemisella ja lyhimmän epäsanan etsimisellä.
(Siltä varalta että jotakuta kiinnostaa, niin nysväilin nämä nyt VB6:lla ja aloitin pähkäilyn tuossa sen jälkeen kun olin kirjoittanut edellisen viestini. Eli joku 90 minuuttia taisi kaikkineen mennä. Sovelluksen kokonaispituus 1200 merkkiä. Se lukee voksaa.txt tiedoston ja tuottaa tulos.txt tiedoston. Koko hommaan menee 9,4 sekuntia. Pienellä optimoinnilla tuon saisi tippumaan varmaan alle sekunnin jos jaksaisi vääntää)
Edit: 16:19
Ok, sain vihdoin vakuutettua itseni siitä, että käyttämäni menetelmä tuottaa optimaalisen lyhyimmän sanan.
Minusta tuo lyhimmän sanan algoritmi oli jopa niin triviaali, etten vaivannut päätäni sen todistelulla. ^^ Ja vaikkei sanojen määrän laskennalla sinänsä ole mitään yhteistä tuon lyhimmän sanan kanssa, niin samoista piirroksista senkin näki.
Grez kirjoitti:
Koko hommaan menee 9,4 sekuntia.
Merkillistä. Onko kyseessä vain jokin VB:n kummallisuus vai mikä, kun tosiaan tuo minun ratkaisuni näytti kovasti toimivan alle sadasosasekuntissa (koko syötepaketti, luku ja tulostus), ellen ole aivan väärin time-komennon turinoita lukenut.
Itse en piirrellyt mitään, joten en nähnyt sellaisista mitään :D
No VB6 tosiaan soveltuu erittäin huonosti tuollaiseen hommaan. Mystistä, ajoin uudestaan saman ja nyt kesti vain 6,8 sekuntia. Käännettynä meni 4,7 sekuntia. Mutta tosiaan tiedän kyllä miten tuon saisi optimoitua koska nyt se käyttää muutamia todella hitaita operaatioita.
Joo, optimoitu VB6 versio käännettynä hoiti homman 0,25 sekunnissa.
Esimerkiksi C:llä tuo toimisi varmasti hyvin paljon nopeammin. Alle sadasosasekunti tuntuu silti kohtuullisen hyvältä suoritukselta. (Tosin aikaiksemmassa postauksessa sanoit että meni 0,05 sek, mutta ehkä se oli arvaus) Pitäisiköhän kokeilla C:llä nysvätä sama.
Jaa, oliko se siellä aiemmassa jo... En ole kotona nyt, niin en voi tuota tarkistella omalla koneella ja oikealla versiolla koodista. Sinne päin kuitenkin, vähänpä sillä enää on tuossa merkitystä, kokoluokka on kuitenkin kunnon koneella sadasosia eikä kymmenyksiä.
Tämä 333 MHz prosessorilla varustettu loistava kannettava näyttäisi suoriutuvan 0,22 sekunnissa koko paketista. Kielenä C++, kääntäjänä g++ 4.1.2 ja optimointina pelkkä -O. Koodi sinänsä on äärimmäisen optimoimaton, kirjoitin tässä vain uusiksi muistin mukaan... Ja mitäpä noin nopeaa enää optimoimaan. Kokoa kooditiedostolla näyttäisi olevan 907 tavua, koodi on täysin selkeää (eli en ole kokoa pienentänyt obfuskoinnilla). Käytin STL:stä virtoja, stringiä ja reverse-funktiota, kun satuin kokoamaan väärään suuntaan tuon lyhimmän sanan.
Joo, en epäile etteikö tosiaan hommaan paremmin sopivalla kielellä hyvinkin pyörähdä vaikka siinä sadasosasekunnissa.
Tuo omakaan optimointi sinänsä ei ollut mitään obfuskointia, lähinnä vaan korvasin stringin bytetaulukolla. VB:ssä kun stringiä ei voi käsitellä suoraan taulukkona vaan jos haluaa yksittäisen merkin sieltä saada niin täytyy käyttää esim Mid -funktiota, jolloin lopputulos on luonnollisesti merkittävästi hitaampi kuin byte-taulukkoa käytettäessä.
Yllättäen jakojäännös näyttää olevan VB6:ssa kohtuuttoman hidas operaatio. Muutin koodia niin ettei jakojäännöksiä enää käytetä, niin koodi nopeutui 66% ja pyörähtää nyt 0,15 sekunnissa.
Monen tunnin ähellyksen jälkeen sain pisteet lyhimpien puuttuvien sanojen perusteella. VB5:llä tähän kului 7,5 sekuntia. tarkistus vie huomattavasti pidemmän ajan. Näköjään lähes puolet pisteistä kertyy lyhimmillä sanoilla.
Tuo tarkistus-PHP on tosiaan käsittämättömän hidas. Pitäisköhän kokeilla huvikseen värkätä nopeampi tarkistus-PHP. :D VB6 vääntää tuon tulkattuna 0,36 sekunnissa, joten vaikea kuvitella että PHP olisi hirveästi hitaampi.
C-kääntäjät on kirjoitettu niin että ne optimoivat parhaansa mukaan huonostikin kirjoitettua koodia, eli käytännössä ei tapahdukaan kaikkea sitä mitä koodin mukaan pitäisi tapahtua. VB:n kääntäjä taas on niin vanha, että siinä ei ole yhtä paljon ja laajasti moisia optimointeja. Mutta mielenkiintoisena faktana, VB:nkin konekielikääntäjä on ollut alkujaan C-kääntäjä.
Tosin tässä tapauksessa kyllä uskon että algoritmillä on paljon tekemistä vauhdin kanssa. Jos käsiteltäviä merkkejä on vain kuusi, niin voi lähteä siitä että ne käsitteleekin kuutena numerona, joiden käsittelyyn riittää kolme bittiä, jolloin yksi Long riittää kymmenen merkin käsittelyyn ja erittäin nopeaan vertailuun taulukosta sen suhteen, onko samanlaista merkkijonoa jo olemassa. Longin käsitteleminen kun on kaikkein nopeinta 32-bittisellä koneella. Konekielelle kääntämättömänä se voi kuitenkin olla hidasta, koska P-koodi on hidas käsittelemään taulukkomuuttujia ja matematiikkaa: kääntää advanced optimizationit päällä niin saa vauhtia.
Minulla ei sitten itse kilpailuun riitä aikaa.
Merri kirjoitti:
Jos käsiteltäviä merkkejä on vain kuusi, niin voi lähteä siitä että ne käsitteleekin kuutena numerona, joiden käsittelyyn riittää kolme bittiä, jolloin yksi Long riittää kymmenen merkin käsittelyyn
Ja luultavasti tekstin muunnos tuollaiseen muotoon veisi melkeinpä yhtä kauan kuin itse algoritmi ilman tuollaista optimointia.
Käänsin systeemin vielä aidolle oikealle C:llekin. Nyt nopeus tuolla samaisella kannettavalla (333 MHz PII) on -O-lipulla käännettynä 0,13 sekuntia ja ilman optimointia 0,24 sekuntia. (C++:lla optimoimaton aika on paljon suurempi, kun ilman optimointia esimerkiksi merkin luku string-oliosta taitaa päätyä funktiokutsuksi inlinen sijaan.)
Tuo 7,5 sekuntia meni siis lyhyimpien puuttuvien sanojen hakuun VB5:llä käyttämällä merkkijonoa ja InStr-funktiota ( ~1,5 GHz prossu) tiedostokäsittelyineen. Pelkästään merkkijonojen muuttaminen Byte-taulukoiksi (3 merkkiä per Byte) vie noin pari sekuntia. En tajua kuinka Grez saa koko homman VB6:lla noin pikaisesti. Onkohan muitakin kuin vain VB:n omia funktioita mukana? Nuo nopeudet vaan kiinnostaa vaikkei tehtävässä olekkaan tarkoitus nopeuksilla kilpailla.
Ei ole mitään muita kuin VB6:n omia funktioita mukana. Itse asiassa niitäkin on nyt todella vähän tuossa uusimmassa joka hakee sanojen määrän ja lyhimmät sanat 0,15 sekunnissa käännettynä. Eli itsekin käytin instr:ää silloin kun vielä käytin Stringiä, mutta luovuin siitä kun siirryin byte-taulukkoon. En kyllä ymmärrä miten merkkijonon muuttamisessa byte-taulukoksi voi kestää pari sekuntia. Pisimmän kantasanan muuttaminen stringistä byte-taulukoksi veisi alle sadaosasekunnin, mutta luen ne kylläkin suoraan tiedostosta byte-taulukkoon.
Käänsin tuossa nyt pelkät lyhimmät sanat hakevat ja siinä menee 0,06 sekuntia kun se lukee tiedoston, kehittelee sanat ja kirjoittaa tulostiedoston. Jos setä haluat, niin voin lähettää vaikka sähköpostilla tuon lähdekoodini. Lyhimmät sanathan löysit jo itsekin, joten poistan vaan siitä tuon koodin joka laskee sanojen määrät niin voit edelleen pähkäillä sitä itse.
Merri kirjoitti:
Tosin tässä tapauksessa kyllä uskon että algoritmillä on paljon tekemistä vauhdin kanssa. Jos käsiteltäviä merkkejä on vain kuusi, niin voi lähteä siitä että ne käsitteleekin kuutena numerona, joiden käsittelyyn riittää kolme bittiä, jolloin yksi Long riittää kymmenen merkin käsittelyyn ja erittäin nopeaan vertailuun taulukosta sen suhteen
Joo, algoritmeilla on paljon väliä, ja olennaisinta nimenomaan on että ei pakkaa niitä edellä kuvatulla tavalla, koska se hidastaisi toiminta merkittävästi ja lisäksi tulisi vielä pakkaamisesta aiheutuva lisäkustannus.
Kokeilin myös lukea tiedostosta suoraan bytetaulukkoon mutta siinäkin meni liki pari sekuntia. Luin kylläkin tavu kerrallaan ja taitaa löytyä nopsempikin tapa.
Kyllä olen kiinnostunut lähdekoodistasi Grez, oppiihan sitä vielä tässäkin iässä.
Joo, laitoin nyt koodin matkaan. Meni jonkin aikaa kun kirjoittelin sinne kommentit mukaan. Alunperinhän koodi oli täysin kommentoimatonta, niinkuin yleensä tällaisessa pienissä pikavirityksissä.
En tiedä toimisiko tuo suoraan VB5:llä, mutta idea selvinnee.
Sainpas ratkaistua sanojen määrätkin. Senkin algoritmi on yksinkertainen sinänsä, mutta kesti melko kauan ennen kuin osasin lähteä hakemaan sitä oikealla tavalla. Vaadittava laskenta-aika kasvaa sekä lyhimmässä sanassa että sanojen lukumäärässä suhteessa sanan pituuteen, eli molemmat ovat O(n).
Laskenta kesti 700 MHz -koneella ja Pythonilla 9 sekuntia.
Hyvä tehtävä, kiitokset jälleen kerran laatijalle.
Missä järjestyksessä noi tulokset muuten on. Ilmeisesti ensisijaisesti saadun pistemäärän mukaan, mutta toissijainen järjestely on ilmeisesti joko satunnainen, käyttäjän putkaan rekisteröitymisajankohdan mukainen tai sen mukainen milloin ensimmäisen (pieniin tai suuriin pisteisiin oikeuttavan) vastauksensa on lähettänyt?
Viimeisin noista. Eli tulokset listataan ensisijaisesti pisteiden mukaan, toissijaisesti ensimmäisen hyväksytyn vastauksen lähetysajankohdan mukaan.
Tasatuloksen yhteydessä kyseisen pistemäärän ensiksi lähettänyt ansaitsisi mielestäni etusijan, mutta eipä tuo iso asia ole. Mainitsin tuosta reilu vuosi sitten 4. Putkapostin yhteydessä, eikä siinä taidettu nähdä muutostarvetta. Sen jälkeen olenkin pyrkinyt lähettämään edes jonkinlaisen vastauksen nopeasti :)
(Edellinen viesti taisi kadota jonnekin matkalla koneen ja Putkan välillä.)
Tehtävä olikin helppo. Piti vain hoksata, mitä tietoa voi heittää heti pois turhana.
Haskellilla ohjelmointi oli hyvin suoraviivaista. Oma ajatteluni ei tällä kertaa niinkään.
Meikäläisen algoritmi taitaapi olla pikkuisen liian raskas. Ekan sai laskettua nopeastikin, mutta jo toisessa jumittaa koneen.
Pitää mietiskellä tai luovuttaa.
Aihe on jo aika vanha, joten et voi enää vastata siihen.