Golfový turnaj

Návod

Zahrajeme si programátorský golf. Místo nejmenšího počtu úderů holí se ale budeme snažit o nejmenší počet instrukcí v programu, který řeší danou úlohu.

Náš programovací jazyk počítá s celými čísly. Jediná paměť, kterou má k dispozici, je zásobník. Ten si můžete představit jako posloupnost čísel uspořádanou shora dolů. Nová čísla přidáváme na vrchol zásobníku, odebíráme opět z vrcholu.

Například chceme-li sečíst 1+2, napíšeme 12a. To je program o třech instrukcích: Instrukce 1 uloží na vrchol zásobníku číslo 1. Podobně instrukce 2 uloží 2. Poslední instrukce a (add) odebere dvě čísla z vrcholu zásobníku, sečte je a výsledek opět uloží na zásobník. Na konci výpočtu tedy bude zásobník obsahovat jediné číslo 3.

Každá instrukce je tvořena jedním znakem. Velká a malá písmena nerozlišujeme. Mezery mezi instrukcemi jsou ignorovány. Některé instrukce používají kulaté závorky pro vymezení bloku programu.

Omezení: Program smí obsahovat nejvýše 1000 instrukcí. Po spuštění musí doběhnout do 1 milionu kroků (jeden krok odpovídá vyhodnocení jedné instrukce nebo kulaté závorky). Na zásobníku může být současně maximálně 1000 čísel. Čísla jsou 32-bitová se znaménkem, přetečení způsobí běhovou chybu.

Instrukce

Tabulka uvádí: jméno instrukce, obsah zásobníku před provedením instrukce a po něm, popis instrukce.

0
(const)
0uloží na zásobník konstantu 0 (podobně 1–9)
a
(add)
x yx+ysečte dvě čísla
c
(copy)
nxzkopíruje n-tou hodnotu od vrcholu zásobníku, přičemž nultá je ta těsně pod n (9870c zkopíruje 7, 9872c zkopíruje 9)
d
(dup)
xx xduplikuje hodnotu na vrcholu zásobníku
e
(equal)
x yx=yuloží 1, pokud x=y, jinak 0
g
(grtr)
x yx>yuloží 1, pokud x>y, jinak 0
i
(if)
podmpodmínka: (instrukce)i přečte hodnotu ze zásobníku a pokud je nenulová, provede instrukce
k
(count)
nspočítá, kolik čísel bylo na zásobníku před provedením instrukce
l
(less)
x yx<yuloží 1, pokud x<y, jinak 0
m
(mul)
x yx*yvynásobí dvě čísla
o
(over)
n xpřepíše n-tou hodnotu od vrcholu zásobníku číslem x (98723o změní 9 na 3, takže na zásobníku zbude 3 8 7)
p
(pop)
xsmaže číslo z vrcholu zásobníku
q
(quot)
x yx/yspočítá podíl čísel x a y
r
(rem)
x yx%yspočítá zbytek po dělení čísla x číslem y
s
(sub)
x yx-yodečte dvě čísla
t
(trace)
vypíše aktuální stav programu
w
(while)
cyklus: (podmínka)(tělo)w provede posloupnost instrukcí podmínka, pak odebere jedno číslo ze zásobníku, a pokud je nenulové, provede posloupnost instrukcí tělo a znovu vyhodnocuje podmínku
x
(xchg)
x yy xprohodí dvě čísla na vrcholu zásobníku

Příklady

Klikněte pro simulaci vypočtu.