- Time limit: N/A
- Memory limit: N/A
Aineisto
Tehtävän aineistona on kaksi sanalistaa:
- Lista A: suomen kielen sanoja kirjoitettuna oikein päin
- Lista B: samat sanat kirjoitettuna väärin päin
ohjelmointi
ja listassa B vastaavasti itniomlejho
. Huomaa, että listoissa on päällekkäisyyksiä: esimerkiksi molemmissa listoissa on sanat aatto
ja ottaa
.Listat on tallennettu UTF-8-muodossa, millä on vaikutusta ääkkösten ja muiden erikoismerkkien käsittelyssä.
Aineisto perustuu Kotimaisten kielten keskuksen nykysuomen sanalistaan, joka on julkaistu EUPL-lisenssillä. Listaa on muokattu tähän tehtävään sopivaksi mm. poistamalla sanat, joissa on tiettyjä erikoismerkkejä.
Tehtävä
Laadi säännöllinen lauseke $S$, joka täsmää mahdollisimman moneen listan A sanaan ja mahdollisimman harvaan listan B sanaan.
Molemmissa listoissa on $n = 93855$ sanaa. Olkoot $a$ niiden listan A sanojen määrä, joihin $S$ täsmää, ja $b$ niiden listan B sanojen määrä, joihin $S$ täsmää. Tällöin osumatarkkuus on $$r = \frac{a + n - b}{2n}.$$ Tavoitteesi on päästä mahdollisimman korkeaan osumatarkkuuteen.
Esimerkkejä:
- Säännöllinen lauseke
.*rv.*
täsmää $a = 1453$ sanaan listassa A ja $b = 2$ sanaan listassa B, joten osumatarkkuus on $r \approx 0.508$.
- Säännöllinen lauseke
xyzzy
ei täsmää mihinkään sanaan listoissa A ja B, ja osumatarkkuus on $r = 0.5$.
- Säännöllinen lauseke
.*
täsmää kaikkiin sanoihin listoissa A ja B, ja osumatarkkuus on $r = 0.5$.
Jos laatimasi lauseke on kelvollinen (ks. alla täsmälliset säännöt), saat pisteitä osumatarkkuudesta $r$ riippuen kaavalla $$\min \bigl( 100, \max \bigl(0, \lfloor 250 \cdot (r - 0.55) \rfloor \bigr) \bigr).$$ Esimerkiksi osumatarkkuus $0.55$ antaa $0$ pistettä, osumatarkkuus $0.75$ antaa $50$ pistettä ja osumatarkkuus $0.95$ antaa $100$ pistettä, mikä on tehtävän maksimipistemäärä.
Säännölliset lausekkeet
Säännöllinen lauseke on merkkijono, joka täsmää yhteen tai useampaan merkkijonoon. Tässä tehtävässä voit käyttää lausekkeessa kaikkia aineistossa esiintyviä merkkejä, vaihtoehtoa (
|
), toistoa (*
), sulkuja sekä yleismerkkiä (.
).Vaihtoehdon avulla voit antaa useamman kelpaavan merkkijonon. Esimerkiksi lauseke
apina|banaani|cembalo
täsmää merkkijonoihin apina
, banaani
ja cembalo
.Toisto tarkoittaa, että sitä edeltävä lausekkeen osa voi toistua miten tahansa monta kertaa. Esimerkiksi lauseke
(aa)*
vaatii, että merkkijonon jokainen merkki on a
ja sen pituus on parillinen (myös tyhjä merkkijono on sallittu).Yleismerkki
.
täsmää mihin tahansa yksittäiseen merkkiin. Esimerkiksi lauseke .*abc.*
täsmää mihin tahansa merkkijonoon, jossa on jossain kohtaa merkkijono abc
, koska alussa ja lopussa voi olla mitä tahansa.Esimerkki mutkikkaammasta lausekkeesta on
api(la|na)|.*s
. Tämä lauseke täsmää sanoihin apila
, apina
sekä mihin tahansa sanaan, jossa viimeinen kirjain on s
, kuten sanoihin ilmoitus
ja ratas
.Palautusohje
Palauta UTF-8-muotoinen tekstitiedosto, jossa on laatimasi säännöllinen lauseke. Lausekkeen pituus saa olla enintään 500 merkkiä.
Voit käyttää halutessasi lausekkeessa välilyöntejä ja rivinvaihtoja. Tarkastaja jättää nämä huomiotta, eikä niitä lasketa lausekkeen pituuteen.
Esimerkiksi
.*rv.*
on kelvollinen ratkaisu, jonka pituus on 6 merkkiä. Tämän lausekkeen osumatarkkuus on $0.508$, joten sillä ei saa vielä tehtävästä pisteitä.