Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointiputka: Putkaposti 29: Käänteislauseke

Sivun loppuun

Antti Laaksonen [06.03.2009 20:42:47]

#

Uusin putkaposti liittyy säännöllisiin lausekkeisiin:

https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=kala

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.

FooBat [07.03.2009 03:24:39]

#

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.

Antti Laaksonen [07.03.2009 11:02:44]

#

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.

Jaqqo [07.03.2009 16:10:34]

#

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ä?

Antti Laaksonen [07.03.2009 16:28:04]

#

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ä.

JTS [07.03.2009 19:00:09]

#

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.

Metabolix [08.03.2009 13:48:03]

#

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ä?

Metabolix [08.03.2009 22:07:06]

#

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. ;)

Antti Laaksonen [08.03.2009 22:38:08]

#

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ä?

Metabolix [08.03.2009 22:54:00]

#

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.

Antti Laaksonen [08.03.2009 23:05:04]

#

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.

FooBat [09.03.2009 00:24:42]

#

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.

Metabolix [09.03.2009 01:17:41]

#

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.

Antti Laaksonen [09.03.2009 12:21:13]

#

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]*.

FooBat [09.03.2009 23:09:07]

#

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;
	}

Päärynämies [11.03.2009 20:14:39]

#

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.

Jaska [21.03.2009 18:45:52]

#

Itse en muista, mitä nuo operaatiot tarkoittavat. Taidan jättää väliin.


Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta