Putkaposti: Älykäs robotti

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:

• Osku siirtyy jossain vaiheessa labyrintin oikeaan alanurkkaan. Tämän jälkeen Osku saa hortoilla mielensä mukaan labyrintissa, eli ei ole merkitystä, mihin ruutuun Osku sattuu lopuksi päätymään.
• Labyrintissa ei ole reittiä vasemmasta ylänurkasta oikeaan alanurkkaan. Tällöin Osku saa liikkua labyrintissa haluamallaan tavalla ja pysähtyä mihin tahansa ruutuun.

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 2¹⁴ = 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.