Sanalista

• Time limit: N/A
• Memory limit: N/A

Tehtäväsi on rakentaa säännöllinen lauseke, joka pyrkii tunnistamaan, onko annettu suomen kielen sana kirjoitettu oikein vai väärin päin. Lauseke testataan aineistolla, jonka voit ladata omalle koneellesi tutkittavaksi.

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
  

Kummankin listan jokaisella rivillä on yksi sana. Listassa A on esimerkiksi sana 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$.
  

Pisteytys

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