PALMA junior
Úloha o mriežkovom behu pre žiakov

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 4 / 4 = 100 %

• Úspešnosť riešenia: 4.5 / 6 = 75 %

V tejto úlohe je našim cieľom prepísať trasu zadanú pomocou súradníc do postupností otočení v bodoch trasy. Keďže medzi dvoma susednými bodmi trasy je vždy vzdialenosť 1 m, nemusíme ju uvádzať. Po každom otočení v mriežkovom bode trasy spravíme krok dĺžky 1 m.

Všimnime si, že už zo zadania úlohy vieme zistiť pravidlá, ako sa trasa prepisuje:

Bodová trasa: [[0, 0], [0, 1], [1, 1], [1, 2], [0, 2], [-1, 2]

Trasa na mape:

Uhlová trasa: [90, 270, 90, 90, 0]

• Prvý bod trasy je začiatok, štart behu.

• Hneď na začiatku sme sa otočili. To znamená, že štartovací smer nie je smerom na sever. Vidíme uhol 90°, zatiaľ však nevieme, či vpravo alebo vľavo.

• Po príchode do bodu [0, 1], sme otočení smerom na sever. Ak chceme pokračovať do bodu [1, 1] otáčame sa o uhol 270°. Teraz už vieme, že smer otáčania je vľavo. Na začiatku sme teda boli v pozícii, ktorá smeruje na východ (otočenie o 90° vľavo nás natočí smerom na sever, smerom k nasledujúcemu bodu [0, 1]).

• Podobne vieme dekódovať aj význam ďalších uhlov. Zároveň si vieme overiť, že všetky otáčania sú smerom vľavo.

• Všimnime si uhol 0° v uhlovom zápise. Je to uhol, o ktorý sa otáčame v bode [0, 2], aby sme pokračovali do posledného bodu trasy [-1, 2]. Keďže pokračujeme rovnakým smerom akým sme prišli, otáčať sa nepotrebujeme.

• Keďže uhlová trasa obsahuje len zoznam uhlov, musíme predpokladať, že korytnačky začnú v  správnom štartovacom bode.

Zhrňme si to:

• na začiatku je korytnačka na štarte a je otočená smerom na východ,

• všetky otáčania sú otáčania smerom vľavo,

• po príchode do nejakého bodu sa korytnačka musí otočiť o nejaký uhol vľavo tak, aby smerovala k ďalšiemu bodu trasy.

Trochu sa nám miešajú absolútne smery (východ, sever, západ a juh) s relatívnymi otáčaniami v jednotlivých bodoch. Ak si budeme pamätať, ktorým smerom je korytnačka otočená pri príchode do aktuálneho bodu a vieme, ktorým smerom je trasa z aktuálneho bodu do bodu nasledujúceho, vieme poľahky vypočítať, o aký uhol sa musí korytnačka otočiť.

Výsledný program môže vyzerať nasledovne:

def zisti_smer(od, do):
    if od[0] < do[0]:
        return 0
    if od[0] > do[0]:
        return 180
    if od[1] < do[1]:
        return 90
    return 270

def prepis_trasu(trasa):
    aktualny_smer = 0
    uhlova_trasa = []
    for idx in range(len(trasa) - 1):
        smer = zisti_smer(trasa[idx], trasa[idx + 1])
        uhlova_trasa.append((smer - aktualny_smer) % 360)
        aktualny_smer = smer
    return uhlova_trasa

Všimnime si niekoľko detailov.

Na začiatku sme aktuálny smer (východ) nastavili na 0. Ostatné smery: sever, západ a juh majú hodnoty 90, 180 a 270 (v zmysle otáčania smerom vľavo).

Pre zistenie, akým smerom je umiestnený nasledujúci bod, sme si vytvorili pomocnú funkciu zisti_smer. Porovnaním jednotlivých súradníc bodov vieme zistiť smer z jedného bodu do druhého. Zo zadania vyplýva, že z každého bodu trasy je možné pokračovať len štyrmi možnými smermi.

Pre výpočet jednotlivých otočení nám stačí vypočítať rozdiel smeru kam chceme ísť a aktuálneho natočenia. Aby sme sa vyhli záporným uhlom, tento rozdiel nahradíme zvyškom po delení číslom 360. Vypočítaný uhol vložíme na koniec uhlovej trasy a zároveň aktualizujeme hodnotu pre aktuálny smer (podľa smeru k nasledujúcemu bodu).

Tento postup realizujeme pre každú susednú dvojicu bodov trasy. Všimnime si, že počet dvojíc je o 1 menší než počet bodov trasy. Preto range(len(trasa) - 1).

Vaše zaujímavé riešenia a najčastejšie chyby

Dva tímy neošetrili situáciu, keď na vstupe je prázdny alebo jednoprvkový zoznam. Aj toto je technicky správny zoznam adries. Úplne správne riešenie mal tím "raketak" a má našu pochvalu.