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 y → x+ysečte dvě čísla
c
(copy) 		n → xzkopí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) 		x → x xduplikuje hodnotu na vrcholu zásobníku
e
(equal) 		x y → x=yuloží 1, pokud x=y, jinak 0
g
(grtr) 		x y → x>yuloží 1, pokud x>y, jinak 0
i
(if) 		podm → podmí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 y → x<yuloží 1, pokud x<y, jinak 0
m
(mul) 		x y → x*yvynásobí dvě čísla
o
(over) 		n x → př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) 		x → smaže číslo z vrcholu zásobníku
q
(quot) 		x y → x/yspočítá podíl čísel x a y
r
(rem) 		x y → x%yspočítá zbytek po dělení čísla x číslem y
s
(sub) 		x y → x-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 y → y xprohodí dvě čísla na vrcholu zásobníku

Příklady

Klikněte pro simulaci vypočtu.