Levelezős csapatverseny – 2. feladatsor

II. feladat – 16 pont

Jancsi bekapcsolta az új számítógépet és egy remek játékot talált.

A feladat egy robot irányítása egy labirintusban. A cél a labirintus bejárása. A labirintus falai f-fel vannak jelölve, az o-val, x-szel és ponttal(.) jelölt mezőkön tudunk mozogni. Minden o-val jelölt mezőre rá kell lépni, azonban az x-szel jelölt mezőket el kell kerülni.

A robotot az alábbi parancsokkal irányíthatjuk:
s – menj 1-et előre
r – fordulj jobbra
l – fordulj balra

Továbbá megadhatunk végrehajtható függvényeket az alábbi formákban:
F=sssrsssrsssrsssr – F függvény meghívására egy 3 oldalhosszú négyzetet jár körbe a robot
G(S)=SSs – a G függvény az S sorozat lépéseit hajtja végre kétszer, majd előre lép egyet
H(N)=sH(N-1) – az N egész számmal paraméterezett H függvény akkor hajtja végre az utasításait, ha N > 0. Jelen esetben pontosan N-szer hajtja végre s-t, vagyis N-et előre lép.

Ha a robot fallal szemben áll, és azt a parancsot kapja, hogy menjen előre, akkor helyben marad. A robot útja akkor számít sikeresnek, ha minden o-val jelölt mezőn járt, egyetlen x-szel jelöltre sem lépett rá, és programja végére ért, megállt.

Példa1:
Az ábrán látható labirintusban a > -jellel ábrázolt robot a bal alsó sarokban áll, és jobbra néz:
fffffff
fxfofxf
fooo.of
fo.oo.f
f>.ofxf
fffffff

A robot a labirintust bejárja a következő programmal:
sslslssrsrsslsllslssrsrs

Szintén jó megoldás a következő:
F=lslssrsrs (itt csak definiáljuk F-et)
ssFslslF (itt hajtatjuk végre)

Példa2:
ffffffffffffffffffffffffffffffffff
f>..............................of
ffffffffffffffffffffffffffffffffff

Megoldás:
F(S)=SS
F(F(F(F(F(s)))))

Másik megoldás:
F(N)=sF(N-1)
F(30)

II. Készítsetek minél kevesebb karakterből álló programot a következő labirintusokhoz: (^ a felfelé néző robotot jelöli)

II. a)
fffffffffffffffffffffffffff
fx.......x.......x.......xf
f.........................f
f.........................f
f.........................f
f....o.......o.......o....f
f.........................f
f.........................f
f.........................f
fx.......x.......x.......xf
f.........................f
f.........................f
f.........................f
f....o.......^.......o....f
f.........................f
f.........................f
f.........................f
fx.......x.......x.......xf
f.........................f
f.........................f
f.........................f
f....o.......o.......o....f
f.........................f
f.........................f
f.........................f
fx.......x.......x.......xf
fffffffffffffffffffffffffff

II. b)
fffffffffffffffffffffffffff
fo.......................of
f.fffffffffffffffffffffx..f
fo.....................ox.f
f.fffffffffffffffffffx..f.f
fo...................ox.f.f
f.fffffffffffffffffx..f.f.f
fo.................ox.f.f.f
f.fffffffffffffffx..f.f.f.f
fo...............ox.f.f.f.f
f.fffffffffffffx..f.f.f.f.f
fo.............ox.f.f.f.f.f
f.fffffffffffx..f.f.f.f.f.f
fo...........ox.f.f.f.f.f.f
f.fffffffffx..f.f.f.f.f.f.f
fo.........ox.f.f.f.f.f.f.f
f.fffffffx..f.f.f.f.f.f.f.f
fo.......ox.f.f.f.f.f.f.f.f
f.fffffx..f.f.f.f.f.f.f.f.f
fo.....ox.f.f.f.f.f.f.f.f.f
f.fffx..f.f.f.f.f.f.f.f.f.f
fo...ox.f.f.f.f.f.f.f.f.f.f
f.fx..f.f.f.f.f.f.f.f.f.f.f
fo.ox.f.f.f.f.f.f.f.f.f.f.f
f.....f.f.f.f.f.f.f.f.f.f.f
f^.o.o.o.o.o.o.o.o.o.o.o.of
fffffffffffffffffffffffffff

Pontozás: mindkét labirintusnál a legkevesebb karakterből álló működő megoldás 8 pontot, a 2-5. helyezettek rendre 6, 4, 3, 2 pontot, minden további működő megoldás 1 pontot ér.

A feladat forrása, és remek terep kísérletezésre:
http://herbert.tealang.info/problem.php?id=4
http://herbert.tealang.info/problem.php?id=6
(vigyázat, a szabályok eltérnek a honlapon találhatóktól!)

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.