Uusi putkapostitehtävä liittyy säännöllisiin lausekkeisiin:
https://www.ohjelmointiputka.net/postit/tehtava.
Tämän tehtävän ratkaistuaan voi todella sanoa hallitsevansa säännölliset lausekkeet.
Mikä tässä on yhden säännöllisen lausekkeen maksimipituus merkkeinä?
Mitään erityistä rajaa ei ole, en ihan tarkkaan tiedä, kuinka pitkistä säännöllisistä lausekkeista PHP:n ereg-funktio selviytyy. Tarkistus tosin hidastuu lausekkeen pituuden kasvaessa. Olisi hyvä pyrkiä saamaan joka kohtaan alle miljoonan merkin pituinen lauseke.
Voisiko tuota "Lähetä vastaus"-sivua muuttaa niin että vastauksen voi lähettää myös tiedostona? (eli <input type="file" ...>)
Minulla Copy-Paste alkaa olla turhan hidas jo 60000 merkin pituisilla riveillä.
Selaimena on Firefox 2.0.0.6 (Linux)
Kuinkas isoilla luvuilla noita regexpejä tarkistellaan? Tässä tehtävässähän ei taida noille 4 luvulle olla täydellistä ratkaisua ja niille voi vain tehdä ratkaisuja, jotka ovat täydellisiä vain tiettyyn pituuteen asti. Tarkastin lienee virheellinen, jos joku saa enemmän kuin 5 oikeaa vastausta :)
Kyllä minä omasta mielestäni ratkaisin 3:n ja 6:n ihan puhtaasti. Ja olen lähes varma, että myös 7 ja 9 ovat mahdollisia.
FooBat kirjoitti:
Kuinkas isoilla luvuilla noita regexpejä tarkistellaan? Tässä tehtävässähän ei taida noille 4 luvulle olla täydellistä ratkaisua ja niille voi vain tehdä ratkaisuja, jotka ovat täydellisiä vain tiettyyn pituuteen asti. Tarkastin lienee virheellinen, jos joku saa enemmän kuin 5 oikeaa vastausta :)
Minäkin arvelin aluksi ettei tehtävä ole mahdollinen luvuille 3,6,7,9, mutta nyt näyttää siltä että olin väärässä.
Luvuille 3 ja 6 sain sen verran yksinkertaisen ratkaisun että uskallan sanoa sen olevan täydellinen (eli toimii ihan miten pitkillä luvuilla tahansa.)
Arvelisin myös luvun 9 ratkaisun olevan täydellinen, mutta en ole siitä 100% varma. Ainakin se hyväksyttiin.
Luvulle 7 en ole vielä saanut ratkaisua, mutta sekin alkaa jo vaikuttaa mahdolliselta.
Juu, voin olla väärässä. Nuo vaan näyttää näin aluksi katsottuna aika patologisilta regexp-lauseilta, jotka vaatisivat rekursiota tai muuttujija.
malaire kirjoitti:
Voisiko tuota "Lähetä vastaus"-sivua muuttaa niin että vastauksen voi lähettää myös tiedostona?
Hyvä ajatus, pitkien vastausten lähetys on tosiaan hankalaa lomakkeen kautta. Toteutan pyytämäsi ominaisuuden lähiaikoina.
FooBat kirjoitti:
Tässä tehtävässähän ei taida noille 4 luvulle olla täydellistä ratkaisua - -
Kaikki tehtävän osat on mahdollista ratkaista täydellisesti rajoittamatta lukujen pituutta. Tai näin ainakin uskon, ennen kuin joku todistaa toisin. :)
FooBat kirjoitti:
Tarkastin lienee virheellinen, jos joku saa - -
Tarkastin ei valitettavasti ole aivan luotettava, sillä se kokeilee säännöllistä lauseketta vain rajallisella määrällä lukuja. Mutta sanoisin, että on helpompaa laatia oikein toimiva säännöllinen lauseke kuin säännöllinen lauseke, joka ei toimi aina oikein mutta onnistuu kuitenkin huijaamaan tarkastinta.
Täytyy kehaista tätä tehtävää. Jo hyvin vähäisellä regexp-osaamisella saa yhden oikein saman tien, mutta onnistuminen kaikissa vaatii jo paneutumista. Lisäksi joku saattaa tutustua hyödyllisiin regexpeihin tämän tehtävän myötä.
Tiedostolähetystä voi nyt kokeilla vastaussivulla.
Jos ilmenee ongelmia, niin kertokaa niistä. Muuten tämä lähetyssivu korvaa pian vanhan lähetyssivun. (Muoks. nyt tiedostolähetys on varsinaisella lähetyssivulla.)
Antti Laaksonen kirjoitti:
Tarkastin ei valitettavasti ole aivan luotettava, sillä se kokeilee säännöllistä lauseketta vain rajallisella määrällä lukuja. Mutta sanoisin, että on helpompaa laatia oikein toimiva säännöllinen lauseke kuin säännöllinen lauseke, joka ei toimi aina oikein mutta onnistuu kuitenkin huijaamaan tarkastinta.
Minä ainakin onnistuin tuossa (ei kyllä ollut tarkoitus huijata). Tein tänään perl-ohjelman joka testaa säännöllisiä lausekkeita ja huomasin että lähettämäni vastaukset luvuille 3,6,9 olivat väärin, eli eivät toimineet kaikissa tapauksissa.
Sain korjattua lukujen 3,6 vastaukset, mutta luvulle 9 en ole vielä keksinyt täydellistä vastausta, vaikka aikaisempi vastaukseni hyväksyttiinkin.
Antti Laaksonen kirjoitti:
Kaikki tehtävän osat on mahdollista ratkaista täydellisesti rajoittamatta lukujen pituutta. Tai näin ainakin uskon, ennen kuin joku todistaa toisin. :)
Oletko muuten itse saanut luvut 7,9 ratkaistua alle miljoonalla merkillä, vai oletatko vain että se on mahdollista? Uskon kyllä että tehtävä on periaatteessa mahdollinen. Kysymys onkin kuinka pitkiä vastauksista tulee.
Antti Laaksonen kirjoitti:
Tiedostolähetystä voi nyt kokeilla vastaussivulla.
Jos ilmenee ongelmia, niin kertokaa niistä. Muuten tämä lähetyssivu korvaa pian vanhan lähetyssivun.
Jos tiedoston viimeisen rivin lopussa on rivinvaihto (\n), niin saan virheilmoituksen "Virhe lähetyksessä: Virheellinen tai toistuva jakaja:".
malaire kirjoitti:
Tein tänään perl-ohjelman joka testaa säännöllisiä lausekkeita ja huomasin että lähettämäni vastaukset luvuille 3,6,9 olivat väärin - -
Tarkastin on sittenkin epäluotettavampi kuin kuvittelin. Korjaus on tulossa tämän päivän aikana, mutta sitä ennen tarkastin voi hyväksyä lausekkeita, jotka eivät toimikaan aina oikein. Ongelma taitaa koskea erityisesti juuri lukuja 3, 6 ja 9.
malaire kirjoitti:
Oletko muuten itse saanut luvut 7,9 ratkaistua alle miljoonalla merkillä, vai oletatko vain että se on mahdollista?
Minulla on noihin lukuihin ratkaisut, jotka ovat selvästi alle miljoonan merkin pituisia.
malaire kirjoitti:
Jos tiedoston viimeisen rivin lopussa on rivinvaihto (\n), niin saan virheilmoituksen "Virhe lähetyksessä: Virheellinen tai toistuva jakaja:".
Nyt tämä ongelma on korjattu, tarkastin ei enää välitä tyhjistä riveistä.
Paransin nyt tarkastinta niin, että se kokeilee säännöllisiä lausekkeita suuremmalla joukolla pidempiä lukuja. Jos tarkastin vielä hyväksyy virheellisiä lausekkeita (tai hylkää virheettömiä lausekkeita), ilmoittakaa siitä minulle. Täydellistä tämän tehtävän tarkastimesta ei tule koskaan, mutta nyt virheellisten lausekkeiden pääseminen läpi pitäisi olla huomattavasti hankalampaa.
Muuten on helppo, mutta sulutus on hankala saada oikein. Pitänee tehdä ylisulutettuja ratkaisuja, koska kyllähän se tietokone niitä ymmärtää. [kehno lisp-vitsi poistettu]
EDIT: (korjasin vielä tätä selitystä)
Minulla on nyt ratkaisu, josta kelpasi kaikki, paitsi viimeisenä oleva tapaus 9. Se jäi oudosti roikkumaan, eikä antanut virhettäkään. Muissa olivat ne #-merkit ja ok näkyvissä. Onkohan mahdollisesti syynä tiedoston koko, koska ratkaisuni ei ole erityisen tehokas pituudeltaan. Tarjoan vain, mitä ohjelmani rykäisi ulos eka kerralla.
Koko tiedoston (2-10) koko on näin hurja.
19.08.2007 10:36 1 529 840 tulos.txt
Sopiiko tuota koetella uudestaan, vai joko teen DoS-hyökkäystä, jos alan värkätä tällaista? No, tässä päivällä katson uudemmas asiaa. Jospa vaikka voisin optimoida tuon hurja-regexpin alle miljoonaan merkkiin :-)
Voit kokeilla lähettää uudestaan, tietysti voisi auttaa, jos saat vastausta jollain konstilla lyhyemmäksi. Mitään erityisiä rajoituksia tarkastimessa ei ole, mutta ongelma voi johtua jonkin aikarajan ylityksestä tai muistin loppumisesta palvelimella. Jos tarkastin ei millään hyväksy vastausta, voit lähettää sen myös minulle sähköpostilla, niin tarkastan sen itse.
Laitoin sen pisimmmän, eli kohdan 9, ekaksi, ja tämä oli ainoa, mitä näin:
lainaus:
Tarkastetaan jaollisuutta luvulla 9...
Joku resurssi loppui kesken (ja selain muuten sanoi sivusta, että Valmis), koska mitään virhettäkään ei näkynyt. No, jätin tämän pois ja sain 8 pistettä muilla. Ysi jää optimointiharjoitukseksi.
Eli voi #%:n @&!, joudun vielä kirjoittamana regexpejä, jotka käsittelevät regexpejä, ja optimoivat niitä! ... Ei vaiskaan, tämä on hauska harjoitus.
Tehtävä on oikein hyvä. Siitä oli suuri apu, että tiesin aiheeseen liittyvää matemaattista teoriaa ja pääsin heti oikeille jäljille sen ansiosta.
MUOKS: On se kumma, että SciTE:en ei voi pastata edes vähän yli miljoonan merkin mittaista riviä ilman, että se juuttuu. Mihin käyttöön tämmöinen editori oikein on tehty, kysyn vaan??? :-)
MUOKS2: Lähetin Antille sen ruman viritelmän, että hän voi katsoa mikä mättää, vaikka se ei nyt niin tärkeää ole. Jotain ratkaisun laadusta kertoo se, että kyseinen tekstitiedosto pakkautui noin 20 kiloon...
No niin, tulihan se sieltä, tiedoston (2-10) koko n. 220 kt. Olikin jo korkea aika opetella säännölliset lausekkeet ja niitä vastaava teoria, hyvä tehtävä siinä mielessä.
Kopeekalle, huomasin saman hitausongelman usealla editorilla, notepad2 tuntuu toimivan melko sujuvasti.
Hyvä tehtävä tosiaan. Minäkään en ollut regexpejä ennen juurikaan käyttänyt ja vielä vähemmän miettinyt miten noita voi muodostaa vähän vaikeammissa tapauksissa. Lopullinen tiedoston pituus mullakin oli noin 220kt.
Olin tosiaan aluksi aivan väärässä. Regexpeillä pystyy näköjään sittenkin toteuttamaan kaikkien lukujen jaollisuus tarkistukset täydellisesti. Regexp lauseen pituus vaan tuntuu kasvavan luokassa O(n!). Olin vähän pettynyt, että 7 ja 9 tehtäviin ei oikein voinut kirjoittaa ratkaisua käsin :). 3 tehtäväänkin ohjelma löysi käsinkirjoitettua paremman ratkaisun.
Se minun ylipitkä 9:ni oli kuulemma oikein (Antti testasi), mutta kaiketi vei muistia liikaa serverillä, joten testaus katkesi tuolta lomakkeesta lähetettynä. Enpä ole kerennyt optimoidakaan sen kokoa, kun ilmaantui muut kiinnostavaa tekemistä. Selvästi siitä kyllä näkee ihan ihmissilmälläkin, että parantamisen aihetta olisi.
Aihe on jo aika vanha, joten et voi enää vastata siihen.