Autorské riešenie
[stiahni imp : py]

  • Počet riešiteľov: 7 / 8 = 88 %

  • Úspešnosť riešenia: 4,36 / 7 = 62 %

Na trojuholníkovú mriežku sa môžeme pozrieť ako na súradnicový systém. Každému bodu mriežky môžeme priradiť nejakú súradnicu.

Na obrázku sú zvýraznené nami zvolené súradnicové osi x a y. Štartovacej miestnosti priradíme súradnice [0, 0], miestnosť s východom bude mať súradnice [2, 3].

suradnicovy system

 

 Stred súradnicovej sústavy nemusí byť v štartovacej miestnosti. Táto voľba nám však zjednoduší riešenie. Podobne aj pre osi x a y sme si mohli zvoliť ľubovoľnú dvojicu smerov.

Najprv zistíme súradnice hráča (súradnice miestnosti, v ktorej stlačil bezpečnostné tlačidlo). Využijeme to, že hráč začal svoj pohyb v bludisku na pozícii [0, 0] a tieto súradnice budeme postupne meniť na základe postupnosti smerov uložených v premennej zaznam_pohybu. Tento prepočet realizujeme v procedúre/funkcii suradnice_hraca jednoduchým testovaním, pričom využívame kódy možných smerov pohybu. Pre každý smer vieme povedať, ako sa zmenia súradnice hráča.

zmena suradnic

Získané súradnice aktuálnej polohy hráča (miestnosť, v ktorej hráč stlačil bezpečnostné tlačidlo) použijeme na vytvorenie zoznamu smerov, ktorými sa hráč dostane do miestnosti s východom.

Zoznam s kódmi smerov, pomocou ktorého sa hráč dostane najkratšou cestou do miestnosti s východom, vráti procedúra/funkcia vychod. Samozrejme, nie je to vždy jediná možná najkratšia cesta - poradie smerov sa môže líšiť podľa postupnosti zápisu jednotlivých podmienok. Teda, ak uvažujeme o situácii na obrázku zo zadania úlohy, možnými výsledkami sú zoznamy [1, 1, 1, 1, 2], [2, 1, 1, 1, 1]...

uakzka situacie

Pri riešení úlohy budeme hľadať zoznam pohybov hráča do miestnosti s východom. Poznáme súradnice miestnosti, kde hráč stlačil tlačidlo a súradnice miestnosti s východom. Hľadáme teda takú najkratšiu postupnosť smerov, aby sa súradnice hráča zmenili na súradnice miestnosti s východom.

Súradnicovú sústavu (trojuholníkovú sieť) pomyselne rozdelíme (vzhľadom na pozíciu miestnosti s východom) na štyri oblasti (tzv. kvadranty) a podľa toho, v ktorej z týchto štyroch častí sa hráč v simulácii nachádza, vytvoríme zoznam smerov, ktorý dovedie hráča do miestnosti s východom.

kvadranty

Z rozdielu súradníc miestnosti s východom a súradníc hráča, vieme zistiť v ktorom kvadrante sa hráč nachádza a ktoré zo smerov môžeme použiť na prechod do miestnosti s východom. V niektorých kvadrantoch vieme dvojicu smerov nahradiť - zložiť do jedného smeru.

zmena_x zmena_y kvadrant smery k východu skladanie smerov
záporná záporná 1. 4, 5  
nezáporná záporná 2. 1, 5, 6 1 + 5 = 6
nezáporná nezáporná 3. 1, 2  
záporná nezáporná 4. 2, 3, 4 2 + 4 = 3

Ak sa hráč nachádza v kvadrantoch 1. alebo 3. cesta k východu je jednoduchá. Použijeme len dva zo smerov. Použitie každého z nich zmení hráčovi buď x-ovú alebo y-ovú súradnicu.

Ak sa hráč nachádza v kvadrantoch 2. alebo 4. riešenie bude trochu náročnejšie. Tu by sme mali prednosti používať smery, ktoré menia aj x-ovú aj y-ovú súradnicu hráča súčasne. Namiesto dvoch krokov môžeme teda spraviť len jeden. Chceme totiž minimalizovať počet krokov k východu.

Riešenie úlohy môže vyzerať nasledovne:

;Imagine logo

viem suradnice_hraca :zaznam_pohybu
 ;pohyb zacina v startovacej miestnosti so suradnicami [0, 0]
 urobtu "x 0
 urobtu "y 0
 ;suradnice aktualnej pozicie hraca budeme menit podla hodnot v zozname zaznam_pohybu
 opakuj pocet :zaznam_pohybu[
  akJe prvok pocitadlo :zaznam_pohybu
   [1 [urobtu "x :x+1]
    2 [urobtu "y :y+1]
    3 [urobtu "x :x-1 urobtu "y :y+1]
    4 [urobtu "x :x-1]
    5 [urobtu "y :y-1]
    6 [urobtu "x :x+1 urobtu "y :y-1]]
   ]
 urobtu "suradnice []
 urobtu "suradnice vlozPo :x :suradnice
 urobtu "suradnice vlozPo :y :suradnice
 vysledok :suradnice
koniec

viem vychod :zaznam_pohybu
 urobtu "suradnice suradnice_hraca :zaznam_pohybu
 urobtu "x_hraca prvok 1 :suradnice
 urobtu "y_hraca prvok 2 :suradnice
 urobtu "x_vychod 2
 urobtu "y_vychod 3
 urobtu "zmena_x (:x_vychod - :x_hraca)
 urobtu "zmena_y (:y_vychod - :y_hraca)
 urobtu "navrat []
 ak2 :zmena_y >= 0
  [ak2 :zmena_x>=0
   [opakuj (abs :zmena_y)[urobtu "navrat vlozPo 2 :navrat]
    opakuj (abs :zmena_x)[urobtu "navrat vlozPo 1 :navrat]
   ]
   [ak2 (abs :zmena_x) < (abs :zmena_y)[urobtu "pocet_dvojkrokov abs(:zmena_x)]
                                      [urobtu "pocet_dvojkrokov abs(:zmena_y)]
    opakuj ((abs :zmena_x) - :pocet_dvojkrokov)[urobtu "navrat vlozPo 4 :navrat]
    opakuj ((abs :zmena_y) - :pocet_dvojkrokov)[urobtu "navrat vlozPo 2 :navrat]
    opakuj :pocet_dvojkrokov[urobtu "navrat vlozPo 3 :navrat]
   ]
  ]
  [ak2 :zmena_x <= 0
   [opakuj (abs :zmena_x)[urobtu "navrat vlozPo 1 :navrat]
    opakuj (abs :zmena_y)[urobtu "navrat vlozPo 5 :navrat]
   ]
  [ak2 (abs :zmena_x) < (abs :zmena_y) [urobtu "pocet_dvojkrokov (abs :zmena_x)]
                                       [urobtu "pocet_dvojkrokov (abs :zmena_y)]
   opakuj ((abs :zmena_x) - :pocet_dvojkrokov)[urobtu "navrat vlozPo 1 :navrat]
   opakuj ((abs :zmena_y) - :pocet_dvojkrokov)[urobtu "navrat vlozPo 5 :navrat]
   opakuj :pocet_dvojkrokov[urobtu "navrat vlozPo 6 :navrat]
  ]
 ]
vysledok :navrat
koniec

 

Python
def suradnice_hraca(zaznam_pohybu):
    x, y = 0, 0
    for smer in zaznam_pohybu:
        if smer == 1:
            x += 1
        elif smer == 2:
            y += 1
        elif smer == 3:
            x -= 1
            y += 1
        elif smer == 4:
            x -= 1
        elif smer == 5:
            y -= 1
        elif smer == 6:
            x += 1
            y -= 1
    return [x, y]


def vychod(zaznam_pohybu):
    x_vychod, y_vychod = 2, 3
    suradnice = suradnice_hraca(zaznam_pohybu)
    x_hraca = suradnice[0]
    y_hraca = suradnice[1]
    zmena_x = x_vychod - x_hraca
    zmena_y = y_vychod - y_hraca
    if zmena_y >= 0:
        if zmena_x >= 0:
            navrat = [1] * abs(zmena_x)
            navrat = navrat + [2] * abs(zmena_y)
        else:
            pocet_dvojkrokov = min(abs(zmena_x), abs(zmena_y))
            navrat = [4] * (abs(zmena_x) - pocet_dvojkrokov)
            navrat = navrat + [2] * (abs(zmena_y) - pocet_dvojkrokov)
            navrat = navrat + [3] * pocet_dvojkrokov
    else:
        if zmena_x >= 0:
            pocet_dvojkrokov = min(abs(zmena_x), abs(zmena_y))
            navrat = [1] * (abs(zmena_x) - pocet_dvojkrokov)
            navrat = navrat + [5] * (abs(zmena_y) - pocet_dvojkrokov)
            navrat = navrat + [6] * pocet_dvojkrokov
        else:
            navrat = [5] * abs(zmena_y)
            navrat = navrat + [4] * abs(zmena_x)
    return navrat


zaznam_pohybu = [2, 2, 1, 5, 4, 4, 5, 3]
print(vychod(zaznam_pohybu))

				  

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

Úlohu riešilo 7 tímov, 2 tímy z kategórie expert a 5 tímov z kategórie guru. Jeden tím úlohu vyriešil len pre jeden špeciálny prípad. Ostatné tímy sa s touto úlohou dobre popasovali.

Najčastejšie boli chyby len v tom, že žiaci neošetrili všetky podmienky a niektorí neošetrili ani to, či sa v zozname nachádzajú naozaj len hodnoty 1-6. Zaujímavé, avšak nie optimálne, bolo riešenie, v ktorom bolo pre hráčov odporúčané vrátiť sa na štart a zo štartu prejsť najkratšou cestou do cieľa.  Niektoré tímy na riešenie používali "klasickú" súradnicovú sústavu, v ktorej okrem celých čísel používali na  určenie miestnosti vo vrchole trojuholníka aj desatinné čísla - konkrétne polovice. V tomto prípade sa stalo, že žiaci neošetrili riešenie, kedy x-ová súradnica je síce správna, ale neexistuje krok smerom "priamo nahor", ktorý by bol optimálny, a teda riešenie sa zacyklilo.