Uusin putkaposti liittyy säännöllisiin lausekkeisiin:
https://www.ohjelmointiputka.net/postit/tehtava.
Yksi säännöllisten lausekkeiden kiehtova ominaisuus on, että mille tahansa säännölliselle lausekkeelle voi tehtävän tapaan muodostaa käänteisen vastaparin. Jos säännölliset lausekkeet ja yleisemmin laskennan teoria kiinnostavat, kertokaa minulle siitä! Aihetta voidaan mielellään käsitellä enemmänkin Ohjelmointiputkassa.
Onkohan tuossa tarkistusohjelmassa jokin vika, kun hyvinkin yksinkertainen testitapaus xxxKORONKORKOxxx epäonnistuu kaikilla ei triviaaleilla yrityksilläni. Javan regexpeillä sama testitapaus näyttäisi toimivan oikean, vaikken takuuseen menekään oman regexpini täydellisestä toiminnasta.
Voisitko lähettää minulle sähköpostitse jonkin niistä säännöllisistä lausekkeista, jotka toimivat eri tavalla tarkistimessa ja Javassa? Tarkistin käyttää muuten PHP:n funktiota ereg, joten voit myös itse testata, jos käytössäsi sattuu olemaan PHP.
Putkaposti kirjoitti:
Voit käyttää säännöllisessä lausekkeessa seuraavia merkkejä: - -
Tarkoittaako tämä, että tehtävän ratkaisussa saa käyttää vain mainittuja merkkejä?
Tarkistimessa oli todellakin virhe, joka on nyt korjattu FooBatin ansiosta. Toivottavasti kenenkään muun lausekkeita ei ole hylätty turhaan virheen vuoksi.
Säännöllinen lauseke saa sisältää vain tehtävässä mainittuja merkkejä.
No jopas, pitänee uudestaan kokeilla muutamia jotka lähetin... Tuo on hyvä tietää että tarkistus tehdään eregillä, vaikka en nyt tosipuheessa osaa sanoa kuinka paljon sillä on eroa pregiin.
Engxnvfva grugäiäa xvewbvggnznyyn lxfvaxregnvfra ääeryyvfra nhgbznngva, xbfxn fr ba urycbzcv xhva inefvanvara fääaaöyyvara ynhfrxr. Nhgbznngva zhhgva fääaaöyyvfrxfv ynhfrxxrrxfv ybchygn fxevcgvyyä, wbxn ghbggv 135 zrexva ynhfrxxrra. Gäfgä zhhafva ivryä zhhgnzna N(O|P)-xbuqna ylulrzcääa zhbgbba NO|PQ. :)
Menetelmästä johtuen uskon, että ratkaisuni on ainakin hyvin lähellä parasta mahdollista. Toisaalta aihe on sen verran tuntematon, että saatan olla aivan väärässäkin.
Edit. Luulin jo muistini pettäneen, mutta löytyihän se aihetta sivuava opas — keskeneräisten joukosta. Se pitäisi varmaankin kirjoittaa loppuun joskus, vai mitä?
Tarkistusskriptissä mahtaa muuten olla yhä jokin virhe, kun oman laskutaitoni mukaan lähettämäni ratkaisu on neljä merkkiä lyhyempi kuin sivulla lukee. Kristallipallo kertoo, että tulokseksi tulee lausekkeen ^(...)$ pituus. ;)
Metabolix kirjoitti:
Menetelmästä johtuen uskon, että ratkaisuni on ainakin hyvin lähellä parasta mahdollista. Toisaalta aihe on sen verran tuntematon, että saatan olla aivan väärässäkin.
Voisitko kertoa vielä lisää tästä esim. ROT13-salattuna?
Metabolix kirjoitti:
Edit. Luulin jo muistini pettäneen, mutta löytyihän se aihetta sivuava opas — keskeneräisten joukosta. Se pitäisi varmaankin kirjoittaa loppuun joskus, vai mitä?
Kyllä, mutta vähän eri näkökulmasta ehkä. Säännöllisten lausekkeiden "guruopas" voisi olla aika kova sana.
Metabolix kirjoitti:
Tarkistusskriptissä mahtaa muuten olla yhä jokin virhe, kun oman laskutaitoni mukaan lähettämäni ratkaisu on neljä merkkiä lyhyempi kuin sivulla lukee.
Nyt tämäkin puute on korjattu. Kertooko kristallipallosi vielä syyn alkuperäisen tarkistimen osittaiseen toimimattomuuteen, jos annan vihjeeksi, että silloin tulokset heittivät kaksi merkkiä?
Antti Laaksonen kirjoitti:
Kertooko kristallipallosi vielä syyn alkuperäisen tarkistimen osittaiseen toimimattomuuteen, jos annan vihjeeksi, että silloin tulokset heittivät kaksi merkkiä?
Ainakin alku- ja loppumerkkien puuttuminen selittäisi, miksi lauseke hyväksyy virheellisetkin syötteet: kelvollinen osuma (esimerkiksi [^K]) löytyy tekstistä joka tapauksessa.
Kaipaatko nyt tarkempaa selostusta käyttämästäni menetelmästä vai siitä, miksi oletan ratkaisun olevan lähellä optimaalista? :) Rupesin juuri viilaamaan lopullista ratkaisuani, ja ihmisaivot yllättäen saavatkin vielä monta merkkiä pois. Nyt tosin lauseke on jo niin kieroutunut muodoltaan, että sen logiikan löytäminen vaatii vähintäänkin syvempää ymmärrystä mystiikasta.
Metabolix kirjoitti:
Ainakin alku- ja loppumerkkien puuttuminen selittäisi, miksi lauseke hyväksyy virheellisetkin syötteet: kelvollinen osuma (esimerkiksi [^K]) löytyy tekstistä joka tapauksessa.
Toisin päin: alku- ja loppumerkit ymmärsin laittaa itsekin, mutta sulut unohtuivat, jolloin osan lausekkeista toiminta oli väärä.
Metabolix kirjoitti:
Kaipaatko nyt tarkempaa selostusta käyttämästäni menetelmästä vai siitä, miksi oletan ratkaisun olevan lähellä optimaalista?
Erityisesti minua kiinnostaisi tuo jälkimmäinen.
Tuo tarkistin ei muuten tarkista kovinkaan huolellisesti. Muutamat ensimmäisistä yrityksistäni oli nimittäin virheellisiä ja eivätkä hyväksyneet kaikkia sanoja, joissa ei ollut sanaa KORONKORKO. Itse käytän samaa menetelmää kuin Metabolix, mutta tuossa välivaiheessa oli pieni virhe eikä se vieläkään ole optimaalinen.
Olen hiukan yllättynyt kuinka hankala tuota regexpiä on muodostaa käsipelillä. Valitun sanan rekursiivisuudella on tietenkin osuutta asiaan, mutta silti olisin kuvitellut tuon onnistuvan. Tämä tietenkin tekee tehtävästä aika haastavan, jos ei ole entuudestaan tutustunut NFA-DFA-REGEXP -kolmiyhteyteen.
FooBat kirjoitti:
Tuo tarkistin ei muuten tarkista kovinkaan huolellisesti.
Tähän taitavat nojautua myös oman ratkaisuni viimeisimmät optimoinnit, tai ainakin omat silmäni väittävät, ettei lauseke enää voi olla yhtäpitävä alkuperäisen kanssa. :)
FooBat kirjoitti:
Itse käytän samaa menetelmää kuin Metabolix, mutta tuossa välivaiheessa oli pieni virhe eikä se vieläkään ole optimaalinen.
Eikö se ole aika helppo tehdä? :o
FooBat kirjoitti:
Tämä tietenkin tekee tehtävästä aika haastavan, jos ei ole entuudestaan tutustunut NFA-DFA-REGEXP -kolmiyhteyteen.
Tiesin ennestään vain, että REGEX ja DFA liittyvät tiiviisti toisiinsa. Tässäpä sekin yhteys tuli tarkemmin tutkittua. NFA ei tietääkseni liity tähän tehtävään. (Mikä lie käytännössä edes, en ole tutustunut.)
Nhgbznngvffnav ba nyxhgvyn, ybcchgvyn wn 10 iäyvgvynn frxä aävqra iäyvfrg, lxfvaxregnvfrg fvveglzäg. Nyxhgvynfgn rafvzzävfrra iäyvgvynna ivr ynhfrxr "^", wn infgnninfgv gäfgä ybcchha ivr "$". Gbvfva fnabra engxnvfh gnvgnn yhbggnn, rggrv grfgvflögr ybch xrfxra cbgragvnnyvfra bfhzna. ;)
Antti: Ra inefvanvfrfgv bfnn crehfgryyn byrghfgnav zhhgra xhva fvyyä, rggä nhgbznnggvav ba nvanxva cvxnvfrfgv zvrgvgglaä bcgvznnyvara, wbyybva ynhfrxxrraxva cvgävfv aäuqäxfrav byyn. Xäfva grxrzäav bcgvzbvaavg crehfghing yäuvaaä hhgrra eluzvggrylla wn fnznagncnvfgra xbugvra luqvfgrylla xlflzlfzrexxvra nihyyn. Gäyyä baxva wb xbyzvfraxlzzragä zrexxvä xnqbaahg, zhggn alg nyxning xrchyvxbafgvg ybcchn.
FooBat kirjoitti:
Tuo tarkistin ei muuten tarkista kovinkaan huolellisesti. Muutamat ensimmäisistä yrityksistäni oli nimittäin virheellisiä ja eivätkä hyväksyneet kaikkia sanoja, joissa ei ollut sanaa KORONKORKO.
Onko erityistä syötetyyppiä, jota tarkistin ei ota huomioon? "Vaikeita" syötteitä saa mielellään ehdottaa minulle, niin lisään ne tarkistimeen.
Ehkä joskus innostun tekemään PHP:llä kunnollisen kahden säännöllisen lausekkeen vertaajan, mutta toistaiseksi joudumme tyytymään vaillinaiseen tarkistukseen.
Metabolix:
Nvanxva zvaha ghagrznav gning zhhggnn ääeryyvara nhgbznnggv fääaaöyyvfrxfv ynhfrxxrrxfv ibving ghbggnn uliva zhgxvxxnna fääaaöyyvfra ynhfrxxrra, invxxn nhgbznnggv byvfv cnenf znuqbyyvara. Zvgä fnng ghybxfrxfv, wbf zhhgng nhgbznngva xääagrvfirefvba fääaaöyyvfrxfv ynhfrxxrrxfv? Gäzäa cvgävfv fvvf infgngn fääaaöyyvfgä ynhfrxrggn [N-M]*XBEBAXBEXB[N-M]*.
Antti Laaksonen kirjoitti:
FooBat kirjoitti:
Tuo tarkistin ei muuten tarkista kovinkaan huolellisesti. Muutamat ensimmäisistä yrityksistäni oli nimittäin virheellisiä ja eivätkä hyväksyneet kaikkia sanoja, joissa ei ollut sanaa KORONKORKO.
Onko erityistä syötetyyppiä, jota tarkistin ei ota huomioon? "Vaikeita" syötteitä saa mielellään ehdottaa minulle, niin lisään ne tarkistimeen.
Tässä oma javalla tehty testiohjelmani, jolla havaitsin vanhat lähetykseni virheellisiksi. Ilmeisesti se php tarkistin ei vaan käytä riittävästi KORN-kirjainten kombinaatiota testitapauksissa.
private static boolean isValid(String regexp) {
Pattern p = Pattern.compile(regexp);
StringBuilder sb = new StringBuilder();
Random rand = new Random();
for(int i = 0; i < 1000; i++) {
sb = new StringBuilder();
for (int r = 0; r < 100; r++)
sb.append("KORN".charAt(rand.nextInt(4)));
if (rand.nextBoolean())
sb.insert(rand.nextInt(sb.length()), "KORONKORKO");
String s = sb.toString();
boolean match = s.indexOf("KORONKORKO") == -1;
if (p.matcher(s).matches() != match) {
System.out.println("failed: "+s+", pm "+p.matcher(s).matches()+", ix "+s.indexOf("KORONKORKO"));
return false;
}
}
return true;
}On kyllä ilmeisesti tavallista vaikeampi tehtävä tai tiedollisesti "vaativampi", kun vasta 2 ihmistä on ratkaisun lähettänyt. Täytyy kyllä itsekin sanoa, että en oikein tiedä miten tuota lähtisi ratkaisemaan, pitäisi varmaan hankkia enemmän tietoa noista DFA:ista. Tosin noita rot13-salattuja tekstejäkään en ole vielä mennyt lukemaan.
Hyvä kuitenkin, että on erilaisia putkaposteja, jotka liittyvät erilaisiin aiheisiin. Edellinen olikin turhan helppo.
Itse en muista, mitä nuo operaatiot tarkoittavat. Taidan jättää väliin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.