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

[Pavel Troller]

Zdravím,
  tak jakpak vám chodí roboti po pásce ? Máte ? Vím alespoň o jednom
úspěšném řešiteli, sice s dvěma konzultacemi, ale ono to skutečně
nemusí být na první čtení jasné :-).
  Pavel

> 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
>