Kirjautuminen

Haku

Tehtävät

Putkaposti: Älykäs robotti

Kirjoittaja: Antti Laaksonen

OSQ-433, tuttavallisemmin pelkkä Osku, on uuden sukupolven robotti, jossa on monia kehittyneitä ominaisuuksia. Nyt Oskua yritetään opettaa löytämään reitti ulos labyrintista. Oskua ohjelmoidaan komentosarjoilla, joiden rajoituksena on, että ne eivät voi sisältää haarautumista, vaan kaikki komennot suoritetaan aina samassa järjestyksessä. Mihin suuntaan Oskun täytyy liikkua missäkin vaiheessa, jotta se löytää ulos mistä tahansa labyrintista?

Tehtävä

Labyrintin koko on 4 x 4 ruutua, ja jokainen ruutu on joko tyhjä, jolloin Osku voi liikkua siihen, tai estetty, jolloin Osku ei voi liikkua siihen. Oskun lähtöpaikka on labyrintin vasen ylänurkka, ja robotin pitää päästä labyrintin oikeaan alanurkkaan, jos sinne on olemassa jokin mahdollinen reitti. Labyrintin vasen ylänurkka ja oikea alanurkka ovat aina tyhjiä, muut ruudut taas ovat joko tyhjiä tai estettyjä.

Oskulle annettava komentosarja muodostuu kirjaimista V, O, Y ja A, jotka tarkoittavat vastaavasti liikkumista vasemmalle, oikealle, ylös ja alas. Kun Osku käynnistetään lähtöpaikassaan, se alkaa liikkua järjestyksessä komentosarjan mukaisiin suuntiin. Kuitenkin jos jokin liikkuminen johtaisi estettyyn ruutuun tai labyrintin ulkopuolelle, Osku pysyy sen komennon ajan paikallaan.

Oskun suoritus hyväksytään kahdessa tilanteessa:

Esimerkiksi Oskun komentosarja AAAOOOY tarkoittaa, että Osku liikkuu aluksi kolme askelta alas, sitten kolme askelta oikealle ja lopuksi askeleen ylös. Seuraavissa kuvissa tapauksessa A tämä reitti käy oikeassa alanurkassa, mutta tapauksissa B ja C Osku ei pääse koskaan tavoiteruutuunsa. Tapauksissa A ja C Oskun suoritus hyväksytään, koska C:ssä mitään reittiä ei ole olemassa.

Kun labyrintin vasen ylänurkka ja oikea alanurkka ovat aina tyhjiä, erilaisia labyrintteja on kaikkiaan 214 = 16384. Oskun muistiin mahtuu korkeintaan 100 liikkumiskomentoa, mutta mitä lyhyempi komentosarja on, sen paremmaksi vastaus tulkitaan.

Vastausohje

Kirjoita vastaukseen kirjaimista V, O, Y ja A muodostuva komentosarja, jolla Osku pääsee aina labyrintin vasemmasta ylänurkasta oikeaan alanurkkaan, jos labyrintissa on yleensä jokin reitti näiden ruutujen välillä.

Vastaus voisi näyttää seuraavalta:

AAAOOOY

Tämä komentosarja ei kuitenkaan sovellu jokaiseen labyrinttiin. Tämän huomaa suoraan esimerkin B-tapauksesta, jossa reitti oikeaan alanurkkaan on kyllä olemassa (esim. OOOAAA), mutta Osku tyytyy seilaamaan labyrintin vasemmassa reunassa.

Vastaukset

28 henkilöllä on tulos. Suluissa oleva luku tarkoittaa komentosarjan pituutta.

lukujenVihaaja (29), BadHabit (29), FooBat (29), jlaire (29), Sisuaski (29), Metabolix (29), Chiman (29), Laakeri (29), Jhuunhym (29), symbols (29), Ruokauuni (29), kluopaja (29), Legu (29), isashkar (29), san9blin (30), Konvehti (33), Laitinen (33), Tilastokeskus (33), TapaniS (40), Jogge (46), öppis (49), pnj (52), a256kvk (52), os (58), siruli (58), L2-K2 (62), Dzarg (63), Pekka Karjalainen (100)

Kirjaudu sisään Ohjelmointiputkaan, niin voit lähettää vastauksen tehtävään.

Keskustelu

Katso myös Putkaposti 19: Älykäs robotti.

Tietoa sivustosta