Keskustelu: Ohjelmointiputka: SL-haaste alkaa!

Ohjelmointiputkassa alkaa tänään SL-haaste:

https://www.ohjelmointiputka.net/slh/

SL-haaste sisältää joukon tehtäviä, joissa on tarkoituksena suunnitella säännöllisiä lausekkeita.

Jokaisessa tehtävässä on kaksi haastetta: ensimmäinen haaste on luoda toimiva lauseke, toinen haaste on luoda mahdollisimman lyhyt lauseke. SL-haaste sisältää automaattisen säännöllisen lausekkeen tarkistajan.

SL-haasteen tehtävät vaikeutuvat pikku hiljaa. Ensimmäiset tehtävät käsittelevät säännöllisten lausekkeiden perusasioita, kun taas viimeiset tehtävät tarjoavat pohdittavaa kenelle tahansa.

Tervetuloa mukaan!

Tehtävässä 2.8

"Alkuluku on kokonaisluku, joka on suurempi kuin 1 ja jaollinen vain 1:llä ja itsellään."

Pitäisi sanoa, että alkuluvun ainoat positiiviset tekijät ovat 1 ja luku itse. Esimerkiksi 2 on alkuluku vaikka on jaollinen luvulla -2.

Kiitos tarkennuksesta, korjasin tehtävänantoa.

5.9: Jaollisuus 3 kirjoitti:

Lauseke hyväksyy merkkijonon 0, vaikka sen pitäisi hylätä se.

Taitaa yleisten jaollisuussääntöjen perusteella 0 olla jaollinen kaikilla nollasta poikeavilla luvuilla.

edit: taisi tehtävässä olla lisämaininta positiivisista luvuista.

Putkapostikansiosta löytyi DFA->regex -muuntaja, jonka avulla vaikeimpiinkin tehtäviin sai helposti muodostettua toimivan lausekkeen. Useimmissa on vielä rutkasti optimoitavaa.

Tämä haastehan on ihan mukavaa puuhastelua, ainakin mitä noita olen pohtinut ja ratkonut. Alkupään tehtävissä ainakin helposti pääsi samoihin ennätyksiin muiden kanssa, tulipa pariin jopa uusi ennätyskin tehtyä (jotka nopeasti rikottiin tai ainakin päästiin samaan näin yöaikaankin). Saa nähdä kuinka paljon noita loppupään monimutkaisempia (ja oletettavasti pidempiä) lausekkeita jaksaa miettiä.

Ainakin jaollisuuslausekkeita onkin tullut aiemmin mietittyä hieman putkapostin muodossa, näissä ratkaisussa on kuitenkin vielä kovasti parantamisen varaa pituuden suhteen.

Miksiköhän tuo systeemi ei hyväksy merkkiä . ? Olisi kätevä noissa tehtävissä, joissa tarvitsee pohtia vain pituutta. Ensimmäisen tehtävänkin saisi ratkaistua 5 merkillä, kun nykyisellään tuosta omituisuudesta johtuen tarvitsee 10 merkkiä.

Myöskään \ merkkiä ei nähtävästi hyväksytä, eli ilmeisesti takaisinviittausta ei voi käyttää, vaikka siitä on puhetta ohjeissa?

Itse asiassa ihmetyttää, miksei sallittuja merkkejä kerrota suoraan ohjeissa? (Vai olenko sokea?) JS:stähän ne kyllä löytyy
// Sallitut merkit kaikkineen: 0-9 [-] {,} () | *+?

Miksi tehtävässä 2.4 lausekkeen on hylättävä jono 11111? Esiintyväthän siinä parit 01 ja 10 yhtä monta (0) kertaa, samoin kuin tyhjässä jonossa, joka tarkistimen mukaan on hyväksyttävä.

Kiitos mielenkiintoisesta haasteesta.
Itse asiassa niin mielenkiintoisesta, että tuli lopultakin luotua tunnus tänne putkaan.

Grez kirjoitti:

Miksiköhän tuo systeemi ei hyväksy merkkiä . ? Olisi kätevä noissa tehtävissä, joissa tarvitsee pohtia vain pituutta.

Lausekkeista päätettiin jättää pois merkinnät, joiden tulkinta riippuu merkistöstä ja jotka voisivat aiheuttaa epäselvyyksiä. Käytännössä nämä ovat mainitsemasi . sekä hakasuluissa ^.

Grez kirjoitti:

Myöskään \ merkkiä ei nähtävästi hyväksytä, eli ilmeisesti takaisinviittausta ei voi käyttää, vaikka siitä on puhetta ohjeissa?

Ohjeissa mainitaan, että SL-haasteen säännölliset lausekkeet ovat perinteisiä, kun taas takaisinviittaus kuuluu laajennettujen säännöllisten lausekkeiden ominaisuuksiin. Takaisinviittauksen salliminen estäisi nykyisen kaltaisen tarkistajan toteuttamisen.

Jotkut ovat jopa sitä mieltä, että jos lausekkeessa on takaisinviittaus, on väärin nimittää sitä säännölliseksi lausekkeeksi.

Grez kirjoitti:

Itse asiassa ihmetyttää, miksei sallittuja merkkejä kerrota suoraan ohjeissa?

Kaikki sallitut merkinnät esiintyvät kohdassa "Merkinnät", mutta selvennän vielä tätä kohtaa ohjeissa.

hunajavohveli kirjoitti:

Miksi tehtävässä 2.4 lausekkeen on hylättävä jono 11111?

Tehtävänannossa oli tosiaan virhe, jonka korjasin.

Varmasti tosi mielenkiintoinen haaste, kun haluaa oppia säännöllisiä lausekkeita. Yritän varmasti jossain vaiheessa!

Olisi kiva nähdä tuossa tehtävälistassa nopeasti parhaan tuloksen pituus sekä tehtävän ratkaisseiden käyttäjien määrä.

Saako tästä diplomia?

Ensimmäisen päivän päätteeksi koossa on jo lähes 800 ratkaisua!

Ape kirjoitti:

Olisi kiva nähdä tuossa tehtävälistassa nopeasti parhaan tuloksen pituus sekä tehtävän ratkaisseiden käyttäjien määrä.

Tämä on hyvä ehdotus ja toteutuu luultavasti. Muitakin uusia ominaisuuksia saa ehdottaa mielellään.

yuizy kirjoitti:

Saako tästä diplomia?

Diplomin saa laatimalla kaikkiin tehtäviin alle 200-merkkisen lausekkeen ja lähettämällä minulle sähköpostitse oman nimen ja postiosoitteen.

funktio kirjoitti:

Putkapostikansiosta löytyi DFA->regex -muuntaja, jonka avulla vaikeimpiinkin tehtäviin sai helposti muodostettua toimivan lausekkeen. Useimmissa on vielä rutkasti optimoitavaa.

Loppupään tehtäviin tuntuisi tosiaan olevan luontevampaa laatia automaatti kuin säännöllinen lauseke. Toisaalta olisi hauska yrittää pähkäillä noita puhtaasti päässä, mutta vaikea sanoa, pääseekö sillä tavalla lopulta kovin optimaalisiin tuloksiin.

Automaatin lausekkeeksi muuntava algoritmi tuottaa usein melko pitkiä lausekkeita, ja useimmissa loppupään tehtävissä päässee huomattavasti parempaan tulokseen suunnittelemalla lausekkeen itse.

Nyt tehtävälistassa näkyvät oman ratkaisun ja parhaan ratkaisun pituudet. Lisäksi jokaisella käyttäjällä on oma sivu, jossa näkyvät hänen ratkaisemansa tehtävät.

Kiitos tästä mielenkiintoisesta tehtävästä.
Koskaan en ole ensimmäistäkään säännöllistä lauseketta tehnyt, mutta pakkohan se oli nyt tutustua aiheeseen.
Parisen tuntia on asiaa ihmetelty ja reilu 20 tehtävää nyt ratkaistu. Nyt alkaakin sitten menemään aikalailla haastaviksi loput. Pitänee tutustua oikeasti vähän enemmän aiheeseen.

Tuleeko näihin jossakin vaiheessa esimerkkivastaukset?

Mun mielestä ainakin tehtävässä 3.8 on ihan epäselvä toi tehtävänanto. Voisko sitä jotenkin selventää? Siis vaikka noihin esimerkkeihin voisi selventää miksi mikäkin on hylätty ja mikä sallittu jos sanalliseen kuvaukseen ei pysty.

Lainaus omilla kommenteilla lisättynä:

Suunnittele säännöllinen lauseke, joka hyväksyy merkkijonot, joissa kahden merkin 0 välissä on pariton määrä merkkejä. Merkkijonot muodostuvat merkeistä 0 ja 1.

Esimerkiksi lausekkeen täytyy hyväksyä seuraavat merkkijonot:
Selvä: 101110
Selvä: 00011
Hieman epäselvä: 1000101 vai 1000101
Vastaavasti lausekkeen täytyy hylätä seuraavat merkkijonot:
10110 (selkeä parillinen määrä)
10011 (selkeä ei pariton määrä eli 0)
1011111 (selkeä, ei kahta 0:aa, joiden välissä voisi olla)

Mutta sitten kun kokeilee tehdä tehtävää..
"Lauseke hylkää merkkijonon 0000, vaikka sen pitäisi hyväksyä se."

Siis mitä kummaa? Mun mielestä tossa on 0:ien välissä parillinen määrä merkkejä 0000

Yritin ymmärtää tehtävän myös toisella tavalla mutta siltikin vaadittiin hyväksymään/hylkäämään epäloogisesti.

Grez: Merkkijono kelpaa, jos siitä voidaan valita sellaiset kaksi nollaa, että niiden välissä on pariton määrä merkkejä. Merkkijonon pitää siis olla muotoa X0Y0Z, missä X ja Z ovat mitä tahansa ja Y sisältää parittoman määrän merkkejä. Monissa merkkijonoissa nollat on mahdollista valita monellakin tavalla, esimerkiksi 0000 tai 0000.

Antti varmaan keksii tehtävänantoon jonkin ytimekkään selvennyksen.

makumaku kirjoitti:

Tuleeko näihin jossakin vaiheessa esimerkkivastaukset?

Haasteessa on kaksi osaa: toimivan lausekkeen muodostaminen ja lyhyimmän lausekkeen etsiminen. Siksi mallivastauksia ei oikein voi julkaista: Jos mallivastaus näytettäisiin vain lyhimmän ratkaisun löytäneille, siitä ei varmaankaan olisi mitään iloa. Jos se taas näkyisi kaikille tehtävän ratkaiseille, sen pitäisi olla todella huono, jottei siitä saisi liikaa vinkkejä lyhintä lauseketta varten.

Selvensin tehtävää 3.8: "- - joissa joidenkin kahden merkin 0 välissä on pariton määrä merkkejä".

Kaikista epäselvistä asioista kannattaa ilmoittaa, jotta tehtävänannoista saadaan mahdollisimman hyvät.

Kiitos erittäin paljon kun tälläisenkin jaksoitte tehdä. Putkaa parempaa puzzlea ei kohta olekkaan. Löytyy php-haaste, sl-haaste, putkaposti ja vielä sillon tällöin kilpailuita. Eiköhän vielä joskus tule joku uusikin haaste.