Tässä tulee uusi putkaposti:
https://www.ohjelmointiputka.net/postit/tehtava.
Tehtävä muodostuu kahdesta osasta, joista jälkimmäinen (sanaketjun etsintä) on selvästi haastavampi. Ainakaan tällä hetkellä ei ole tiedossa täydellistä ratkaisua tehtävään, mutta on kiinnostavaa nähdä, kuinka pitkiä ketjuja onnistutte muodostamaan.
Rivinvaihtojen muunto Windows-muotoisiksi on mennyt pieleen tuossa sanalistassa. Siellä on \r\n:n paikalla \r\r\n.
Eikö ohjelmoinnin kannalta olisi helpointa jättää kuitenkin pelkkä \n?
EDIT: muita ongelmia: vastausohje-esimerkissä lukee alussa 2, anagrammiryhmiä on kuitenkin ilmeisesti 3. Lisäksi vastauksentarkistaja ei hyväksy annettua ryhmää "sulka sula alus alas jalas", valittaen "sula"-sanasta.
lainaus:
EDIT: muita ongelmia: vastausohje-esimerkissä lukee alussa 2, anagrammiryhmiä on kuitenkin ilmeisesti 3
Esimerkissä on kaksi anagrammiryhmää. Kolmas tekstirivi on sanaketju.
Joo, vastauksentarkistaja ei kelpuuta vastausta, se yrittää laskea sanajonorivinkin anagrammiryhmäksi. Ilman tuota sanajonoa vastaus kelpasi.
Ilmeisesti myös yhden sanan ryhmät kelpaavat vastauksessa, tästä olisi ehkä mukava mainita erikseen. Kaikki eivät välttämättä automaattisesti ajattele matemaattisesti "oikein", että tyhjä tai yhden jäsenen joukko on joukko.
Anagrammipuoli oli kaiketi helppo (vai teinköhän sitten väärin). Seuraavaksi pitäisi siirtyä sanaryhmien pariin, mutta ensiksi taitaa olla kuitenkin aika lukea hieman biologiaa kokeeseen. ;)
Tällä kertaa en pyydä ratkaisujen kuvauksia postitse, koska tehtävä eli omaa elämäänsä sen jälkeen, kun alunperin ehdotin sitä Antille. Omakin lopullinen versio on vielä tekemättä. Jos haluatte muunlaista palautetta antaa, saa toki minullekin. Osa tehtävän ideoista on kyllä Antilta peräisin.
(Näin kuitenkin tehtävän pari päivää ennen muita, joten en lähetä mitään vielä tarkastimen kautta. Eipä tarvitse kenenkään pahoittaa mieltään lopullisen järjestyksen takia, vaikka eihän tämä mikään kisa ole.)
Minäkin havaitsin yhden ylimääräisen rivivaihdon sanaston joka rivillä ohjelmani sisällä, mutta ajattelin, että se johtuu käyttämäni kielen tavasta lukea tiedostoja ja korjasin sen poistamalla whitespacen erikseen.
Ja tosiaan, kuten tkarkkainen jo totesi, vastauksessa on viimeinen rivi, joka ei ole anagrammiryhmä ollenkaan.
Nyt tiedoston rivinvaihdot ovat kunnossa. Jos huomaatte vielä muita virheitä tiedostossa, niin ilmoittakaa niistä, koska tiedostolle on varmaan käyttöä tämän tehtävän ulkopuolellakin. (Tiedostossa oli alun perin moni muukin asia hullusti, mutta onneksi Pekka havaitsi viat ennen tehtävän julkaisua.)
Metabolix kirjoitti:
Kaikki eivät välttämättä automaattisesti ajattele matemaattisesti "oikein", että tyhjä tai yhden jäsenen joukko on joukko.
Minäkään en ajatellut, mutta näköjään olen kuitenkin sen verran taitava ohjelmoija, että tarkastaja ottaa tämän huomioon. Ovathan kelvolliset yhden sanan "anagrammiryhmät" siinä mielessä kiinnostavia, että niissä olevan sanan täytyy olla poikkeuksellisen pitkä, joten jääköön tämä porsaanreikä tehtävään ylimääräiseksi älykkyystestiksi.
Antti Laaksonen kirjoitti:
Metabolix kirjoitti:
Kaikki eivät välttämättä automaattisesti ajattele matemaattisesti "oikein", että tyhjä tai yhden jäsenen joukko on joukko.
Minäkään en ajatellut, mutta näköjään olen kuitenkin sen verran taitava ohjelmoija, että tarkastaja ottaa tämän huomioon.
Minä lähinnä ajattelin niin, että "anagrammi" tarkoittaa sanakirjan mukaisesti sanaa (tässä tapauksessa ei tietenkään lausetta tai virkettä), joka on muodostettu järjestämällä toisen sanan kirjaimet uudelleen.
Miten tämä pisteytys muuten menee. Ilmeisesti anagrammisanoista (tehtävän määrittelyn mukaisista) saa kustakin 1 ja niitä on se 1200 yhteensä. Saako sitten sanaketjusta yhden pisteen jokaisesta ketjun sanasta vai jokaisesta merkistä? Eli haetaanko pisintä ketjua vai monisanaisinta ketjua?
Ja täytyy muuten sanoa että aika tylsiä anagrammeja yleisesti kun suurin osa tuntuu olevan kahden osasanan muodostamia yhdyssanoja, jossa vaan osien paikka vaihtuu.
Jokaisesta sanasta (anagrammiryhmässä tai sanaketjussa) saa yhden pisteen. Eli tässä tehtävässä ketjun pituus on siinä olevien sanojen lukumäärä.
On noiden kaksisanaisten anagrammien joukossa onneksi monta todella hauskaakin, joita tuskin koskaan huomaisi ilman tietokonetta.
Joo, lukeehan se pisteiden määräytymismalli siellä tulosluettelon alussakin. Oon varmaan vaan sokea. Täytyy sanoa että tällä hetkellä tuloksissa oleva 44 sanan ketju on jo aika massiivinen.
Varsin mielenkiintoinen tehtävä. En ole koskaan ennen ajatellutkaan miten pitkiä sanajonoja suomenkielessä on. Varsinkaan yli tuhannen sana jonoja en odottanut löytyvän. Saa nähdä menevätkö yli kymmenen tuhannen :)
Hehe, ja minä kun luulin että 44 olisi pitkä :D
Joo, tosiaan lähes 4400 sadan ketju tuli muutamassa sekunnissa kun olin tuon etsintäsoftan saanut koodattua. Ongelma vaan on se, että tuossa menee ikä ja terveys että se löytää sen absoluuttisesti parhaan brute forcella :D
Onko kukaan saanut mielestään varmaa "parasta" vastausta kohtuullisessa ajassa?
Tämä tehtävä poikkeaa siinä Putkapostin perinteistä, että kukaan ei oikein tiedä, voiko tehtävää edes ratkaista kokonaan. Olen kuitenkin toistaiseksi aika toiveikas, että pisimmän sanaketjun löytäminen on mahdollista tai ainakin voi päästä todella lähelle parasta ratkaisua.
Jos laskuni täsmäävät, yksi yläraja ketjun pituudelle on 9239 sanaa. Tällä hetkellä minulla on koossa 5999 sanan ketju, mutta sen muodostava ohjelma ei tee juuri mitään älykästä. Tutkimalla tarkemmin sanaverkon rakennetta tulos varmasti parantuu, jos on parantuakseen.
Antti Laaksonen kirjoitti:
Tämä tehtävä poikkeaa siinä Putkapostin perinteistä, että kukaan ei oikein tiedä, voiko tehtävää edes ratkaista kokonaan.
Mäpäs tiedän! Voi ratkaista kokonaan. Mahdollisia tarkastettavia tapauksia on äärellisen monta, kaikki tapaukset voidaan tarkastaa koneella (tai käsin) äärellisessä ajassa ja siten maksimaalisen ketjun pituus voidaan selvittää.
Mitäs luokka tuo äärellinen määrä on? Meinaan jos se on luokkaa 9239! (tai luokkaa 2.3^9300 kuten itse nopeasti arvioin) niin on aika vähän merkitystä sillä että määrä on äärellinen.
Nyt laskin uuden, tiukemman ylärajan: 7755 sanaa. Eli tämän pidempiä ketjuja ei pitäisi pystyä muodostamaan mitenkään. Mielessäni mutta vielä toteuttamatta on parempi etsintäohjelma, joka toivon mukaan löytää aiempaa pidempiä ketjuja.
Pah, bruteforcettajassani oli bugi, ja korjattuani sen ohjelma alkoi syödä luvattomasti muistia ja aikaa entiseen verrattuna. Uusi löytää takuuvarmasti kaikki ketjut, mutta vanha löytää kohtuullisen isoja nopeasti. Ajan nyt vanhaa siihen asti, että se löytää parhaan löytämänsä (pällinä tuhosin logit ja kadotin sen), muistaakseni 4675 pituudeltaan, ja jätän sitten syvyyshaut sikseen.
Jo löytyi, tosiaan 4675. Kuusi ja puoli tuntia meni. Edellinen ajo oli pyörinyt kaiken kaikkiaan päälle 13 tuntia löytämättä pidempää. Korjattu ohjelma taas täyttää RAM-muistin puolen tunnin sisään: seuraa julmettu swappaus, ja etsintä hidastuu jo ensimmäisessä pidempiketjuisessa sanassa sellaiseksi, ettei sitä kannata edes ajaa pidempään, noin 3900 sanan pituisen ketjun kohdalla.
Tyhjät rivit voisi poistaa vastauksen lopusta ennen tarkistusta, ihmettelin vähän saadessani valitusta väärästä anagrammiryhmien määrästä.
Meni 6000 rikki (6005). Omakaan ohejelmani ei tällä hetkellä tee mitään kovin fiksua, vaan toimii pääsääntöisesti satunnaislukugeneraattorin voimalla.
Tämä pisimmän reitin ongelma on mukavaa vaihtelua ainaisiin lyhympien reittien hakuun. Taitaa ongelma myös olla paria luokkaa hankalampi laskennallisesti.
Pitäisi melkein tutkia tuota verkkoa jonkin visualisoijan avulla niin tietäisi mitä kohtia pitäisi hakea tarkemmin.
Edit: näköjään tuo tulos tuossa parani kun vähän säädin haun parametreja, 6172. Katsotaan löytääkö tuo kone parempaa, jos jätän sen yöksi jauhamaan.
FooBat kirjoitti:
Pitäisi melkein tutkia tuota verkkoa jonkin visualisoijan avulla niin tietäisi mitä kohtia pitäisi hakea tarkemmin.
En ole itse kokeillut, mutta Himmeli voisi sopia tuohon tarkoitukseen.
Tässä on Himmelin näkemys (muuten oletusasetuksilla, mutta kahden minuutin laskenta-ajalla) verkosta, jossa on 7541 sanaa ja 18000 kaksisuuntaista yhteyttä. Verkosta on poistettu joukko umpikujia, joihin menemällä on mahdotonta palata takaisin.
https://www.ohjelmointiputka.net/tiedostot/
Kuvassa ä:t on korvattu A:illa ja ö:t on korvattu O:illa. Verkon reuna-alueista saa ihan hyvin selvää, mutta keskiosa on näin pienessä kuvassa aika sotkuinen. Yhdestä sanasta lähtee keskimäärin 4,77 yhteyttä, 617 sanasta lähtee ainakin 10 yhteyttä ja 11 sanasta lähtee ainakin 20 yhteyttä.
Kun kaksi pisintä umpikujaa ovat 10 sanan ketjuja, uusi yläraja sanaketjun pituudelle on 7561 sanaa. Tämän saavuttamiseksi verkko pitäisi koluta läpikotaisin sekä pystyä valitsemaan aluksi ja lopuksi pisin umpikuja. Todellinen paras tulos (FooBatin 6223?) ja yläraja lähestyvät pikku hiljaa toisiaan.
(Näissä laskuissa saattaa olla virheitä, koska ohjelmat eivät ole ihan yksinkertaisia!)
Mielenkiintoinen kuva :) Noilla yhteysmäärillä siitä ei taida saada mitenkään kovin nättiä.
Tossapäivänä vierailin sivuilla ja ihan mielenkiintoiselta tehtävältä vaikutti. Anagrammit tein tuossa toki ensin ja parissa tunnissa oli ohjelma siihen valmis. (myönnetään, en hyväksynyt 1 sanan anagrammeja ennenkuin nyt kun luin tätä ketjua)
Sitten aloin jo miettiä tätä sanaketjupuolta ja aika nopeasti huomasin, että ongelma on "löydä pisin reitti" jota ei ilmeisesti ihan äkkiä ratkaistakkaan. (NP-hard) Mutta jospa tuohon nyt jonkinlaisen "hakuammunan" sais aikaan.
Aihe on jo aika vanha, joten et voi enää vastata siihen.
