Tässä tulee uusi putkaposti:
https://www.ohjelmointiputka.net/postit/tehtava.
Tuli heti mieleen tarkentavia kysymyksiä?
lainaus:
Etsi mahdollisimman pitkä merkkijono, jonka voi tulkita muodostuvaksi kolmella eri tavalla suomen kielen sanoista.
Eli jos löytyy 4 tai useampia tulkintoja, niin ei kelpaa? (Arvaus: ei haittaa)
lainaus:
Sanat ovat tulkinnoissa aidosti lomittain, eli kaikki paitsi tulkintojen ensimmäiset sanat alkavat eri kohdasta merkkijonoa.
Eli seuraavat pituudet ei kelpaisi?
4+5+7+8
5+4+8+7
11+13
Entä kelpaako jos yhdyssanaan kuuluisi väliviiva, mutta toiseen versioon ei. Tässähän ei pitäisi todellisuudessa tulla tulkintaongelmaa:
...la ama... ...kela-amatööri...
Hieman repesin, kela-amatööri liek wtf:D
Grez kirjoitti:
Eli jos löytyy 4 tai useampia tulkintoja, niin ei kelpaa?
Ei haittaa, vaikka olisi enemmän tulkintoja.
Grez kirjoitti:
Eli seuraavat pituudet ei kelpaisi?
4+5+7+8
5+4+8+7
11+13
Eivät, koska kahden ensimmäisen tulkinnan kolmannet sanat alkavat samasta kohdasta merkkijonoa.
Grez kirjoitti:
Entä kelpaako jos yhdyssanaan kuuluisi väliviiva, mutta toiseen versioon ei.
Myös väliviivojen tulee täsmätä kaikissa tulkinnoissa.
Hyvä että mainitsit tästä, koska alkuperäinen tarkistaja ei hyväksynyt lainkaan väliviivoja. Nyt korjasin tämän asian.
Eihän sanalistassa ole yhtään väliviivaa, joten vastauksessakaan ei voi olla.
Metabolix kirjoitti:
Eihän sanalistassa ole yhtään väliviivaa, joten vastauksessakaan ei voi olla.
Tämä on hyvä huomio.
Metabolix kirjoitti:
Eihän sanalistassa ole yhtään väliviivaa, joten vastauksessakaan ei voi olla.
No ei tietenkään siinä ole, koska siinä ei ole yhdyssanoja. Kuitenkin jos vaikka sanat linja ja auto pistetään peräkkäin, niin väliin pitäisi tulla väliviiva, linja-auto.
Eli ymmärsinkö oikein, että vaikkapa linja ja auto eivät voi esiintyä peräkkäin tuossa järjestyksessä? Vai tarkoittaako se, että tehtävään kelpaa myös virheelliset yhdyssanat ilman tuota väliviivaa?
Tehtävässä ei käsketty muodostaa mielekästä yhdyssanaa vaan mielivaltainen merkkijono, jossa on sanoja peräkkäin. Vai onko sinusta esimerkkinä annettu "varis+taaja+alas+iloinen" jollain tavalla mielekäs yhdistelmä?
Eli "linjaauto" teoriassa kelpaa, mutta sen täytyy olla muodossa "linja+auto", koska "linjaauto" ei sisälly sanalistaan (edes toisen sanan osana).
Metabolix kirjoitti:
Tehtävässä ei käsketty muodostaa mielekästä yhdyssanaa vaan mielivaltainen merkkijono, jossa on sanoja peräkkäin.
Ok. Tehtävänannossa tosin puhuttiin tulkitsemisesta, jonka itse ymmärtäisin vaativan kielioppisääntöjen noudattamista. Mutta eiköhän tämä nyt tullut selväksi että tulkitsemissäännöt on normaaleja löysemmät.
Ja tosiaan, edellisiä kirjoittaessani en muistanut, että niihin tulee vielä ne plussatkin väliin, eli tarkistimelle ei anneta pelkkää sanaa. Eli minkäänlaista tulkitsemista ei edes tarvita.
Grez kirjoitti:
Metabolix kirjoitti:
Tehtävässä ei käsketty muodostaa mielekästä yhdyssanaa vaan mielivaltainen merkkijono, jossa on sanoja peräkkäin.
Ok. Tehtävänannossa tosin puhuttiin tulkitsemisesta, jonka itse ymmärtäisin vaativan kielioppisääntöjen noudattamista. Mutta eiköhän tämä nyt tullut selväksi että tulkitsemissäännöt on normaaleja löysemmät.
Säännöt olivat, että muodostetun merkkijonon täytyy olla kolmella eri tavalla yhdistelmä annetun listan sanoja. Puheet yhdyssanoista ovat täysin omaa keksintöäsi.
Mistähän kiikastaa, kun ei tule minkäänlaisia ratkaisuja muilta? :)
Meinasin parikin kertaa yrittää mutta väsähdin viiden minuutin kohdalla.
Metabolix kirjoitti:
Mistähän kiikastaa, kun ei tule minkäänlaisia ratkaisuja muilta? :)
Kai sitä kehtaa oman vastauksensa palauttaa, vaikka se jääkin paljon Metabolixin vastauksesta. En keksi mitä teen väärin, koska tietääkseni käyn läpi kaikki mahdolliset tapaukset... silti saan vain 65 merkkiä pitkän kolmitulkintaisen merkkijonon enkä 118 merkkistä. Jossain on siis bugi.
Itseäni jatkaen... miten pienestä se joskus onkin kiinni... (eli aina ei voi yksinkertaistaa rankasti ja saada yhä oikeaa lopputulosta).
Tuloksessa on muuten yhä parantamisen varaa.
Kas. :) Olin epähuomiossa koodannut niin, että sama sana ei saa toistua muissakaan kolmesta tulkinnasta. Nyt ratkaisun pitäisi olla kunnossa, ainakin välitulos meni läpi. Saa nähdä, kauanko kestää: edellinenkin ratkaisu hyrräsi muistaakseni kymmenen minuutin verran, ja nyt pelataan jo nelinkertaisilla pituuksilla.
Metabolix kirjoitti:
Kas. :) Olin epähuomiossa koodannut niin, että sama sana ei saa toistua muissakaan kolmesta tulkinnasta. Nyt ratkaisun pitäisi olla kunnossa, ainakin välitulos meni läpi. Saa nähdä, kauanko kestää: edellinenkin ratkaisu hyrräsi muistaakseni kymmenen minuutin verran, ja nyt pelataan jo nelinkertaisilla pituuksilla.
Oho, pitääpä korjata tuo omaan ohjelmaanikin. Tosin nyt suoritusaika saattaa räjähtää käsiin.
Eilinen virheellisillä oletuksilla toiminut python-koodi vaati noin 5 minuuttia koko aineistoon. Nykyinen versio (C++) vaikuttaisi vaativan "hyvin kauan" (ainakin tuhansia kertoja kauemman). Tuon muutos ei ainakaan paranna tätä asiaa.
Joo, jätän homman tähän 476:een. Monta tuntia meni eikä päästy enää edes ratkaisun sadatta kirjainta vaihtamaan puhumattakaan aloittamisesta eri merkillä. Nyt tarvitaan jokin parempi idea.
Miten nopeita teidän ohjelmat on? Kikkailin char* pointtereilla yms, ja nyt ohjelma yrittää noin 3300 sanaa millisekunnissa (3 threadia 3.2 GHz Core i5 quadcore prosessorilla), mutta ohjelmasta puuttuu vieläkin hyvä etsintälogiikka. Ehkä set<char*> puut voisi muuttaa oikeiksi hash mapeiksi... Harmi että visual studion code profiler bugaa jotenkin, etten saa selkeää kuvaa että mihin aika kuluu.
Koitin mm. tallentaa merkkijonojen pituudet map<char*,int> rakenteeseen, mutta se oli jopa hitaampi kuin kutsua aina strlen:iä. Ehkä nuo sanat ovat niin lyhyitä ettei tuosta ollut mitään apua.
No sanalistallahan on 91566 vähintään 4-merkkistä sanaa, eli ne voidaan laittaa 91566! eli noin 2.686 × 10^414562 järjestykseen. Ja lisäksi kaikki lyhyemmät yhdistelmät. Niitä ei siis voi "brute forcella" käydä läpi vaikka saisi 10^1000 yhdistelmää testattua sekunnissa.
Eli siis hyvä etsintälogiikka on niinsanotusti kaikki kaikessa.
Ooh, en tarkoittanut "hash mappia" vaan tietysti hash tablea.
Hakua tehdessä "branch factor" on aika ikävän suuri, etenkin jos lyhyin sana on 2 merkkiä lyhyempi kuin pisin ja 2. pisin on 1 merkin lyhyempi. Esim. "na*" alkuisia on yli 600 kpl. Ohjelmani vie muistia vain 80 mt, pitäisi jotenkin käyttää enemmän muistia hyödyksi :)
Eiköhän minun koneeni ole paljon hitaampi kuin sinun.
Tuota branch factoria pienentää melkoisesti se, että jos na-alkuiseksi sanaksi valitaan narkkari, siihen na-osan jälkeen alkavaan ketjuun pitäisi löytyä jokin rkk-alkuinen sana. Mutta ei tämä toki koko ongelmaa ratkaise.
Joo, toteutin tuon filtteröinnin toissapäivänä. Se oli helppo toteuttaa bit maskeilla, koska pisin sana on alle 32 merkkiä pitkä. Mutta siinä vaiheessa kun sana kasvaa pitkäksi, on hyvin todennäköistä että kaikki käyttökelpoiset sanat on jo käytetty.
Hmm, CUDAsta ei liene apua tällaiseen paljon haarautuvaan probleemaan.
msdos464 kirjoitti:
Koitin mm. tallentaa merkkijonojen pituudet map<char*,int> rakenteeseen, mutta se oli jopa hitaampi kuin kutsua aina strlen:iä. Ehkä nuo sanat ovat niin lyhyitä ettei tuosta ollut mitään apua.
Vieläkö tuo merkkijonojen pituuksien määrityksen hitaus on nykyisessä ratkaisussasi ongelmana? Jos on, niin voisi kannattaa kokeilla semmoista kikkaa, että tallennatkin char*:n päähän varaamasi taulukon ensimmäiseen merkkiin sanan pituuden ja laitatkin sanan alkamaan vasta toisesta merkistä. Tällöin löytäisit aina pointterin päästä vakioajassa sanan pituuden ja saisit säästettyä koko strlenin (tai vaihtoehtoisesti tuommoisen monimutkaisen map-tietorakenteen find-kutsun). Pointterin päähän allokoituun bufferiin tallettamasi data olisi siis muotoa:
Ja nyt tietysti sana löytyy ihan normaalisti char-pointterin päästä kuten ennenkin, kunhan muistat vaan laittaa offsettia yhden byten verran tallettamaasi pointteriin.
Ja disclaimer: En itse ole vielä kauhean tarkasti tutustunut varsinaiseen tehtävänannon ongelmaan. Kommentoin nyt vaan tällaista yhtä kohtaa, joka pisti silmään.
Hmm tuo olisikin ihan järkevä kikka. Itse tein toisen taulukon johon nuo pituudet tallennetaan, ja sen taulukon indeksin voi laskea char* pointterin arvosta jako- ja pluslaskulla. Ilmeisesti "new char[n]" palauttaa aina pointterin jonka ensimmäiset 4 bittiä ovat nollia. Aiemmin tallensin käytetyt sanojen aloituskohdat set<char*> rakenteeseen, mutta tämänkin pystyi helposti korvaamaan tuolla suoraan indeksoitavalla taulukolla.
Jätin työpaikan koneen käymään noita sanoja läpi, maanantaina näkee että onko sieltä löytynyt mitään 521 merkkiä pidempää.
Aihe on jo aika vanha, joten et voi enää vastata siihen.