Kiitos SL-haasteen tehtävien laatijoille ja toteuttajille! Minulla oli hauskaa sen parissa.
Tiedoksi saatettakoon, että olen vienyt jokusen tähden ja pari kruunuakin pois edellisiltä omistajilta huhtikuun 2011 aikana. Koska, tuota noin, tehtävistä tuli pieni pakkomielle :)
Metabolix kirjoitti parhaista ratkaisuista aiemmassa ketjussa, mutta siihen ei voi enää lisätä uusia viestejä. Kysyisin siis: Vieläköhän mahtaa jossakin tehtävässä olla tunnettua parantamisen varaa?
Onnittelut hienosta saavutuksesta!
Ainakin tehtävissä 5.1, 5.2, 5.3, 5.5 ja 5.8 ennätystä voi vielä parantaa.
Monessa muussakin tehtävässä saattaa olla parantamisen varaa, koska on hyvin vaikeaa tietää varmasti, milloin ratkaisu on optimaalinen.
Oijoi, oijoijoi! Noin monessa tehtävässä olisi vielä miettimistä. Toivoin jo päihittäneeni kaikki.
En tietenkään voi vastustaa kiusausta pohtia näitä parannettavia tuloksia, mutta pidän kuitenkin pienen tauon ennen kuin palaan aiheeseen. Joku rajaa pitää säännöllisten lauseiden pohdinnallekin laittaa. Tässä on nyt siis jollakulla ahkeralla ja osaavalla tilaisuus napata minulta jokunen tähti pois ainakin toistaiseksi.
Ja tosiaan, aivan varmoinahan kaikkia ennätyksiä ei voi pitää vaikeammissa tehtävissä. Sekin tuo oman jännityksensä asiaan.
Mainittakoon vielä, että ainakin tehtävässä 5.5 nykyinen ennätys on hyvin kaukana optimaalisesta.
Minusta myös tehtävät 2.9 ja 5.6 ovat erityisen kiinnostavia, koska lausekkeen voi rakentaa niin monella tavalla. Samoin tehtävissä 5.1 ja 5.2 saattaa odottaa vielä todellinen läpimurto.
Toisaaltahan noihin saattaisi saada parempia vastauksia, jos kaikkia säännöllisten lausekkeiden ominaisuuksia, kuten takaisinviittausta, saisi käyttää.
Itse olisin varmasti surkea noissa SL:ssä. En edes äkkiseltään keksi, miten 5.5 kohtaan voisi tehdä toimivan lausekkeen.
Grez kirjoitti:
Toisaaltahan noihin saattaisi saada parempia vastauksia, jos kaikkia säännöllisten lausekkeiden ominaisuuksia, kuten takaisinviittausta, saisi käyttää.
Totta, on lähinnä mielivaltainen valinta, mitkä säännöllisten lausekkeiden merkinnät ovat käytössä. Takaisinviittaus puuttuu kuitenkin myös siitä syystä, että se estäisi nykyisen kaltaisen täydellisen tarkistajan tekemisen.
Grez kirjoitti:
En edes äkkiseltään keksi, miten 5.5 kohtaan voisi tehdä toimivan lausekkeen.
Itse tein sen siten, että piirsin paperille tilakoneen, missä jokainen numero on yksi tila. Sitten piirsin näille sallitut tilasiirtymät. Sitten lähdin pala kerrallaan sieventämään tilakonetta sl-lauseeksi. Lopulta kun tilakoneen jokainen reitti oli käyty läpi ja yksi hervottoman pitkä sl löytynyt, lähdin sieventämään lauseketta yhdistämällä ja järjestelemällä toistuvia kohtia.
Ratkaisin aika usean vaikeammista tehtävistä kuten Torgokin. Joskus onnistuin käyttämään enemmän intuitiota ja 5.5 on yksi vaikeammista tehtävistä, jossa tämä onnistui ja vain satuin keksimään hyvän idean. Kyllä se olikin tovin hakusessa, mutta sitten vain loksahti. Tehtävän vaatimuksen voi esittää sanallisestikin ihan eri tavalla, mikä sitten johti minut ratkaisuun.
Paransin muuten juuri 5.5:n tulosta 81:stä 63:een, koska se aiempi hyvä idea ei ollutkaan toteutunut aivan tehokkaasti ensi kerralla. Vieläkö on varaa parantaa? :)
Tosiaan kaikki tehtävät voi ratkaista automaattien avulla, mutta esimerkiksi tehtävässä 5.5 paljon parempaan tulokseen pääsee suunnittelemalla lausekkeen rakenteen "puhtaalta pöydältä".
Yksi automaattien rajoitus on, että niistä suoraan muodostetut lausekkeet tuottavat jokaisen merkkijonon tasan yhdellä tavalla. Usein kuitenkin lausekkeen saa lyhyemmäksi sallimalla, että se voi tuottaa jonkin merkkijonon monella eri tavalla.
Kapteeni kirjoitti:
Paransin muuten juuri 5.5:n tulosta 81:stä 63:een,
Hyvä alku, mutta tästäkin voi parantaa vielä reilusti...
Äh, olin onnistunut jättämään pariinkin ratkaisuun ylimääräisiä sulkumerkkejä.
Jos tuossa 5.5:ssä olisi vain 3 merkkiä, niin saisin sen tehtyä 74 merkillä, mutta saman systeemin toteuttaminen 4 merkille veisi moninkertaisesti kokoa. Onhan tuokin selkeästi lyhyempi kuin jos automaatista generoin lausekkeet, mutta selkeästi en vielä ole keksinyt "the ideaa" kun 4 merkille löytyy minun 3 merkin ratkaisua lyhyempiä.
Onhan tämäkin vaihtelua kun on algoritmeihin liittyvä asia josta ei tajua abot mitään. :D
Ehkä pitäisi tutustua teoriaan, esimerkiksi miten lausekkeen komplementti muodostetaan, niin saattaisi syntyä ahaa-elämyksiä. Tosin en ymmärrä edes tuosta ohjeesta kohtaa jossa sanotaan että:
1(0|1)+ komplementti on lauseke 0(0|1)*|1?
Minusta kumpikaan noista ei mätsää vaikka merkkijonoa "Grez", joten en ymmärrä miten nuo on toistensa komplementit. Tosin luultavasti tuossa tarkoitetaan että pysytään kahden merkin avaruudessa. Toisaalta tuostahan saisi kai toimivankin tehtyä helposti:
1(0|1)+ komplementti on lauseke 0(0|1)*|1?|[01]*([^01]+[01]*)*
(saattoi mennä oikein tai sitten ei)
Torgo vei kruunujani ja provosoi minut parantamaan paria tulosta. Ei tätä turhaan haasteeksi ole nimetty :)
Grez kirjoitti:
Minusta kumpikaan noista ei mätsää vaikka merkkijonoa "Grez", joten en ymmärrä miten nuo on toistensa komplementit. Tosin luultavasti tuossa tarkoitetaan että pysytään kahden merkin avaruudessa.
Olet oikeassa, että tuo kohta pitäisi muotoilla paremmin. Nyt lisäsin mukaan tuon oletuksen, että ainoat merkit ovat 0 ja 1.
Pitipä minun sitten pakkomielteisesti parantaa tulosta jokaisessa tehtävässä, jotka Antti yllä mainitsi. Nyt en tohdikaan kysyä, että vieläkö ne paranevat -- kun on vappukin tulossa ja muuta mielessä kuin säännölliset lauseet. Hauskaa vappua kaikille putkalaisille!
Niin, nämä tehtävät vain ovat erinomaisen hauskoja. Kiitos siis vielä kerran SL-haasteesta!
Päätimme nyt Metabolixin kanssa julkaista myös omat tuloksemme SL-haasteen tehtävissä. SL-haasteen alkaessa emme halunneet julkaista tuloksiamme, koska olimme saaneet miettiä tehtäviä etukäteen, mutta nyt on sopiva hetki julkaista tulokset.
Nyt tuloslistalla ovat siis kaikissa tehtävissä parhaat tällä hetkellä tunnetut tulokset.
Onnistuinpa itsekin saamaan eilen yhden kruunun parantamalla tehtävän 2.9 tulosta reilusti. :)
Toi on muuten hassu toi tuloslista. Miten sekä Antilla että Laurilla voi olla kummallakin 2 parasta tulosta ja lisäksi 43 jaettua parasta tulosta. Tuossahan on yhteensä 4 parasta tulosta ja jäljelle jää van 41 tehtävää. Vai onko tuolla pari piilotettua tehtävää tms?
Tuloslistassa oli tosiaan epäloogisuus, siinä oli ajateltu tähden tarkoittavan mitä tahansa ennätystä. Nyt luvut vastaavat kuvauksia.
Aika hankala olis tommonen vaikee ratkasta. Ite en lausekkeita yleensä käytä (joskus joutuu käyttämään).
Innostuin näitä SL-tehtäviä väsäämään. Jumi tuli kohdassa 5.1. Onkohan ratkaisuun asetettu jokin aikaraja, jonka kuluessa tarkistuksen pitäisi tapahtua? Nyt raksuttelee jonkin aikaa ja sitten pysähtyy, eikä ruudulle tule palautetta, missä menee vikaan :-(
On tiedossa, että eräät (onneksi harvat) syötteet aiheuttavat tarkistimessa aika- tai muistirajan ylittymisen. Luultavasti ratkaisukin on silloin väärä tai ainakin epäoptimaalinen. Kannattaa yrittää jotain muuta lähestymistapaa. Toinen vaihtoehto on toki hoputtaa Anttia toteuttamaan tarkistimeen tehokkaampi (mutta selvästi mutkikkaampi) minimointialgoritmi.
Haaste on nimensä veroinen! Kiitokset laatijoille mielenkiintoisista tehtävistä! En saanut kaikkia ratkottua, mutta taas tuli uusia ahaa-elämyksiä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.