Logická úloha na zítřek (pátek), ale můžete řešit už dnes :-).

[Pavel Troller]

Zdravím,

Tuto úlohu mi dal dnes syn, brali ji ve škole (chodí na robotiku). Měli na
správné řešení 15 minut. Dal to a já taky :-). Tak schválně, kolik členů
této konfery to dá :-)...

  Mějme jednorozměrné hrací pole v podobě nekonečné, nezasmyčkované pásky,
rozdělené na políčka.
  V počátečním stavu hry vygeneruje hrací systém na dvou náhodně určených
políčkách hráče - roboty.
  Systém hry generuje "tahy". Robot si určí, co se má do příštího tahu stát
a systém pak "táhne" oběma roboty naráz.
  Robot je vybaven tímto souborem elementárních instrukcí:
  - Jdi o jedno políčko "dopředu" (oba roboti jsou iniciování stejným
směrem, takže tato instrukce způsobí, že se pohnou stejným směrem na pásce).
  - Jdi o jedno políčko "dozadu".
  - Nehni se (v tomto tahu stůj).
  - Podmíněný skok v programu. Testovat lze jedinou podmínku - že robot stojí
na startovacím políčku (bylo takto uvedeno, požádal jsem o upřesnění, ano,
test zabere jak na "moje", tak na "kolegovic" startovací políčko).
  - V podstatě nepodmíněný cyklus (ale těsně po začátku nebo před koncem cyklu
lze dát podmíněný skok, takže lze emulovat cyklus podmíněný).
  Logických instrukcí (skok, cyklus) lze provést během tahu více, tahy vlastně
synchronizují jen pohybové instrukce (vpřed, vzad, stůj), tj. rozhodovací
logika proběhne vždy mezi dvěma tahy.
  Nejsou k dispozici proměnné, ani jiná paměť stavu. Jediným stavem je hodnota
"čítače programu", tj. jaký kus algoritmu právě běží.
  Oba roboti mají algoritmus vždy identický.
  Cílem hry je, aby se oba roboti "potkali", tj. stáli v jednom tahu na tom
samém políčku. Tento stav nemusí testovat (ani nemají jak), ale zjistí ho
systém a hru v tento okamžik ukončí.


  Samozřejmě, cílem je vymyslet algoritmus, který zaručeně v konečném a co
možnám minimálním čase vede ke splnění úlohy.

Až na něco přijdete, nedávejte sem hned výsledek, ať si ostatní ještě mohou
popřemýšlet :-). Rozluštění třeba zítra večer :-).

Zdraví Pavel