Levelezős csapatverseny – 1. feladatsor – megoldások

V. feladat

Pontozás: 10 pont

Irányítsd a szondákat! El tudod-e vezényelni a leszállóegységeket a kifutópályáikra?

Hiába mesélted el az álmod, a kapitány nem engedte, hogy vezessétek az űrhajót. Azt mondták még túl kicsik vagytok ehhez, és sokat kell még gyakorolnotok. Mivel nagyon érdeklődők voltatok, a gyakorláshoz kaptatok tőlük egy számítógépes játékot, amit rögtön ki is próbáltatok.

A szimulációban néhány bolygóra kifutópályát építettetek és felderítő egységeket telepítettetek. Az egységek feladata, hogy felderítő repüléseket végezzenek. Feladatod az egységek felszállás előtti, kifutópályán történő navigálását végző program elkészítése. A pályára felfestett csíkok jelzik a felszállásra alkalmas helyet, az egységek a csíkokat érzékelni képes szenzorokkal rendelkeznek, a navigáló programnak pedig ezen érzékelők adatai alapján kell vezérelnie az egyes egységeket. Leszálláskor az egységek biztosan a pályán érnek földet, de megállásuk pontos helye ismeretlen, ezért az általad készítendő programnak képesnek kell lennie arra, hogy a pálya bármely pontjáról eljuttassa az adott egységet egy felszállásra alkalmas helyre.

A kifutópálya négyzetekre van osztva egy képzeletbeli négyzetrács mentén. Az egység mindig egy ilyen négyzet közepén tartózkodik és a négyzet valamelyik oldala felé néz. Képes egy négyzetnyit előre haladni, illetve jobbra és balra 90°-kal elfordulni. A pályára felfestett csíkok a négyzeteket szegélyezik. Az egység 3 érzékelővel rendelkezik, meg tudja állapítani, hogy az őt tartalmazó négyzet első, jobb és bal szegélyére van-e csík festve, és ha igen, az milyen színű.

A pálya méretei és színezése az ábrán látható: alapvetően fekete színű, a szélét sárga csík jelzi, belsejében fehér csíkok találhatóak.

Felszálláskor az egységnek – a hagyományos repülőgépekhez hasonlóan – megfelelő sebességre kell gyorsulnia. Ez a pálya közepén lévő 8 négyzet hosszú, kétoldalt fehér szegéllyel határolt útvonalon tehető meg optimálisan, ezen útvonal két végpontját tekintjük felszállásra alkalmas helyeknek. A programnak e két pont valamelyikére kell navigálnia és a megfelelő irányba kell állítania az egységet, hogy megkezdhesse felszállását. Ügyelni kell rá, hogy a mozgatás során az egység nem hagyhatja el a pályát, mert az a pályát körülvevő sziklás terepen irányíthatatlanná válik.

A programnyelv megadása

Az egységek egy egyszerű nyelv segítségével programozhatóak. A nyelv főbb ismertetői:

Memória: Az egységek processzora 4 db 1 bites regisztert tartalmaz (a, b, c, d). A regiszterek a 0 és 1 értékeket vehetik fel, a program indításakor értékük 0.
Érzékelők: Az egység három érzékelővel rendelkezik (elso, jobb, bal), az érzékelők a fekete, feher, sarga színek valamelyikét képesek felismerni.

A program utasítások sorozata. Az utasítások lehetnek mozgató, értékadó, ismétlő (ciklus) és feltételes (elágazás) utasítások. A ciklusok, elágazások törzsei szintén tetszőleges utasítássorozatok lehetnek, vagyis a ciklusok és elágazások tetszőleges mélységben egymásba ágyazhatóak. Az egyes utasítások leírása:

Mozgató: Lehetőségünk van az egység egy négyzetnyivel történő léptetésére a menj kulcsszóval, jobbra fordítására a fordulj jobbra, balra fordítására a fordulj balra parancsokkal. Forgatáskor az egység nem mozdul el a helyéről, csak az iránya változik.
Értékadó: A regiszterek értéke módosítható a := kifejezés segítségével.
Ismétlő: Az amig kulcsszóval bevezetett ciklus elöltesztelős, ciklusfeltételként valamelyik regiszter értékére vonatkozó feltételt lehet megadni az = operátor használatával, végét a vege kulcsszó jelzi.
Feltételes: A ha kulcsszóval bevezetett elágazás feltételeként a regiszterekre vonatkozó feltétel mellett valamelyik érzékelőre vonatkozó feltételt is meg lehet adni. Az elágazásnak megadható alternatív ág a kulonben kulcsszó segítségével, végét a vege kulcsszó jelzi.

<utasítássorozat> ::= <utasítás> | <utasítássorozat><utasítás>
<utasítás> ::=
    menj | fordulj jobbra | fordulj balra |
    <értékadás> |
    amig <változófeltétel> <utasítások> vege |
    ha <feltétel> <utasítássorozat> vege |
    ha <feltétel> <utasítássorozat> kulonben <utasítássorozat> vege
<értékadás> ::= <változó> := <bit>
<változófeltétel> ::= <változó> = <bit>
<érzékelőfeltétel> ::= <érzékelő> = <szín>
<feltétel> ::= <változófeltétel> | <érzékelőfeltétel>
<változó> ::= a | b | c | d
<érzékelő> ::= elso | jobb | bal
<bit> ::= 0 | 1
<szín> ::= fekete | feher | sarga

A szóközöknek, tabulátoroknak, sortöréseknek nincs szerepük a kód kiértékelésekor, ennek ellenére jól átlátható, tagolt kód elkészítését kérjük. A kód a fent ismertetett kulcsszavakon és kifejezéseken, illetve fehérszóközökön kívül mást nem tartalmazhat.

Pontozás

Beküldendő a feladatot megoldó kód, szövegfájl formájában. A beküldött kód nagysága legfeljebb 10 KB lehet.
A feladatra összesen 10 pont szerezhető. 8 pontot ér, ha a program szintaktikailag helyes (futtatható), tetszőleges kezdőpontból tetszőleges irányban indítva mindig a pályán marad, és egy felszállásra alkalmas helyen terminál. További 1-1 pontot kap a leggyorsabb megoldást és legrövidebb programot adó csapat.
A program futásidejét a mozgató utasításokban mérjük: a menj, fordulj jobbra és fordulj balra utasítások 1-1 időegységnek számítanak. A programhosszt nem karakterszámban, hanem az utasítások számában mérjük: 1 utasításnak számít egy mozgatás, egy értékadás, egy ciklus illetve egy elágazás feltételének kiértékelése.

Megoldás

A feladatra több lehetséges megoldás elfogadható, a pontozásnál a fentieknek megfelelően a kód helyességét és a futás helyességét vettük figyelembe.
Az alábbi egy lehetséges megoldó algoritmus, 36 utasítással.

ha elso = sarga a := 1 vege
amig a = 0
    menj
    ha elso = sarga a := 1 vege
vege
fordulj balra
ha elso = sarga a := 0 vege
amig a = 1
    menj
    ha elso = sarga a := 0 vege
vege
fordulj balra

menj menj
ha elso = feher
    menj menj fordulj balra menj
kulonben
    fordulj balra menj
    ha bal = feher
        fordulj jobbra menj fordulj balra menj
    kulonben
        ha jobb = feher
            fordulj balra menj fordulj jobbra menj
        vege
        menj menj fordulj jobbra
    vege
vege

A verseny kereteit a TÁMOP - 4.2.2/B-10/1-2010-0030
„Önálló lépések a tudomány területén” pályázat biztosította.