PALMA junior
Úloha o robotickom roznášačovi pizze

Autorské riešenie
[stiahni [imp][py]]

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

• Úspešnosť riešenia:  5.15 / 7 = 73.6 %

Hlavná stratégia riešenia úlohy je nasledovná:

• Postupným čítaním jednotlivých príkazov budeme meniť pozíciu a natočenie robota, pričom budeme zisťovať či jeho pozícia je prvkom zoznamu obsahujúcim pozície všetkých domácností (odteraz cieľov). Ak aktuálna pozícia robota je v zozname, tak danú hodnotu zo zoznamu vymažeme.

• Na konci vypíšeme či je prázdny zoznam s pozíciami cieľov, čo znamená, že každý z cieľov bol navštívený robotom. Ak zoznam nie je prázdny, tak robot neprešiel všetkými cieľmi a v tomto zozname sú súradnice ešte nenavštívených cieľov.

Najprv navrhnime údajové štruktúry, ktoré použijeme v riešení tejto úlohy:

• Príkazy pre robota uložíme do reťazcovej premennej prikazy, ktorej znaky sú prvky množiny {K, O}, napr. 'KKKOKK' (tymíto príkazmi sa dostane robot zo svojej počiatočnej pozície do cieľa D1 na ilustračnom obrázku)

• Pozíciu robota uložíme do trojprvkového zoznamu pozicia, kde prvé dva prvky zoznamu predstavujú x-ovú a y-ovú súradnicu robota. Tretí prvok zoznamu predstavuje natočenie robota, ktoré môžme kódovať nasledovne: 0 (robot natočený na sever),  1 (robot natočený na východ),  2 (robot natočený na juh),  3 (robot natočený na západ). Napr. pozícia robota na obrázku je [0, 0, 0]. Ak by sa tento robot dostal do cieľa D1 a bol natočený na východ, tak jeho pozícia by bola [2, 3, 1]. 

• Pozície všetkých cieľov uložíme do zoznamu súradníc cieľov (dvojprvkových zoznamov) ciele. Napr. ciele na obrázku by boli uložené v zozname [ [2 3] [3 1] [2 -2] [-3 1] ].

Poďme najpr vyriešiť čiastkovú úlohu - výpočet novej pozície (súradníc a natočenia) robota po vykonaní zadaného príkazu, ktorú využijeme pri zostavení riešenia celej úlohy.

Vytvorme funkciu nova_pozicia, ktorá pre zadanú pozíciu robota a zadaný príkaz, vráti novú pozíciu robota. Napr. nova_pozicia([0, 0, 0], 'O') --> [0, 0, 1] alebo  nova_pozicia([0, 0, 0], 'K') --> [0, 1, 0].

Najprv vyriešíme situáciu, ak bol zadaný príkaz 'O'. V tomto prípade sa mení o 1 len posledný prvok zoznamu - pozicia[2]. Potom vyriešíme situáciu, ak bol zadaný príkaz 'K. Tu máme 4 situácie podľa natočenia robota, kde zvyšujeme resp. znižujeme o 1 x-ovú resp. y-ovú súradnicu robota, t.j. 1. resp 2. prvok zoznamu - pozicia[0] resp. pozicia[1].

#Python
def nova_pozicia(pozicia, prikaz):
    ''' Načíta pozíciu robota [x, y, natočenie] a príkaz z {K, O} a
    vráti novú pozíciu robota
    :param pozicia: aktuálna pozícia robota
    :type pozicia: list
    :param prikaz: aktuálny príkaz pre robota
    :type prikaz: str
    :return: nová aktuálna pozícia robota
    :rtype: list
    '''
    if prikaz == 'O':
        # vykonal sa prikaz 'O' - otoč sa o 90 stupňov vpravo
        pozicia[2] = (pozicia[2] + 1) % 4
    else:
        # vykonal sa prikaz 'K' - krok dopredu
        if pozicia[2] == 0:
            # robot sa pozerá na sever, pozicia[0] (x-súradnica) sa nemeni
            pozicia[1] = pozicia[1] + 1
        elif pozicia[2] == 1:
            # robot sa pozerá na východ, pozicia[1] (y-súradnica) sa nemeni
            pozicia[0] = pozicia[0] + 1
        elif pozicia[2] == 2:
            # robot sa pozerá na juh, pozicia[0] (x-súradnica) sa nemeni
            pozicia[1] = pozicia[1] - 1
        elif pozicia[2] == 3:
            # robot sa pozerá na západ, pozicia[1] (y-súradnica) sa nemeni
            pozicia[0] = pozicia[0] - 1
    return pozicia

Napokon vytvoríme hlavnú funkciu over_misiu, ktorá pre zadanú počiatočnú pozíciu robota, zadané príkazy a zadané ciele zistí či boli navštívené všetky tieto ciele.

Aby sme zohľadnili situáciu, že počiatočná pozícia robota môže byť v zozname súradníc cieľov, musíme sa na to opýtať už na začiatku funkcie. V pozitívnom prípade prvok s počiatočnými súradnicami robota (t.j. pozicia[0:2] resp. pozicia[:2]) odstránime zo zoznamu súradníc cieľov.  

Následne v cykle prechádzame všetkými príkazmi (z reťazca prikazy) a pre zadaný príkaz a zadanú aktuálnu pozíciu robota vypočítame novú aktuálnu pozíciu robota. Ak tieto aktuálne súradnice robota sú v zozname súradníc cieľov, tak ich odstránime zo zoznamu súradníc cieľov.

Výsledkom tejto funkcie bude informácia či boli navštívené všetky ciele, t.j. či zoznam so súradnicami cieľov je prázdny, resp. jeho počet prvkov je 0.  

#Python
def over_misiu(pozicia, prikazy, ciele):
    ''' Pre zadanú počiatočnú pozíciu a postupnosť príkazov vráti informáciu
    o návštevnosti zadaných cieľov
    :param pozicia: počiatočná pozícia robota
    :type pozicia: list
    :param prikazy: reťazec obsahujúci všetky príkazy pre robota
    :type prikazy: str
    :param ciele: zoznam súradníc všetkých cieľov, ktoré má robot navštiviť
    :type ciele: list
    :return: tvrdenie či boli navštívené všetky ciele z počiatočnej pozície
    po vykonaní všetkých príkazov
    :rtype: bool
    '''
    if pozicia[:2] in ciele:
        # ak sa poč. súradnice robota nachádzajú v zozname cieľov, tak sa z neho zmažú
        ciele.remove(pozicia[:2])
    for prikaz in prikazy:
        # postupná zmena pozície robota po vykonaní jednotlivých príkazov
        pozicia = nova_pozicia(pozicia, prikaz)
        if pozicia[:2] in ciele:
            # ak sa súradnice robota nachádzajú v zozname cieľov, tak sa z neho zmažú
            ciele.remove(pozicia[:2])
    return len(ciele) == 0  # boli navštívené všetky ciele?

Výsledné riešenie celej úlohy zapísané v jazyku Python môže vyzerať nasledovne:  

#Python
def nova_pozicia(pozicia, prikaz):
    ''' Načíta pozíciu robota [x, y, natočenie] a príkaz z {K, O} a
    vráti novú pozíciu robota
    :param pozicia: aktuálna pozícia robota
    :type pozicia: list
    :param prikaz: aktuálny príkaz pre robota
    :type prikaz: str
    :return: nová aktuálna pozícia robota
    :rtype: list
    '''
    if prikaz == 'O':
        # vykonal sa prikaz 'O' - otoč sa o 90 stupňov vpravo
        pozicia[2] = (pozicia[2] + 1) % 4
    else:
        # vykonal sa prikaz 'K' - krok dopredu
        if pozicia[2] == 0:
            # robot sa pozerá na sever, pozicia[0] (x-súradnica) sa nemeni
            pozicia[1] = pozicia[1] + 1
        elif pozicia[2] == 1:
            # robot sa pozerá na východ, pozicia[1] (y-súradnica) sa nemeni
            pozicia[0] = pozicia[0] + 1
        elif pozicia[2] == 2:
            # robot sa pozerá na juh, pozicia[0] (x-súradnica) sa nemeni
            pozicia[1] = pozicia[1] - 1
        elif pozicia[2] == 3:
            # robot sa pozerá na západ, pozicia[1] (y-súradnica) sa nemeni
            pozicia[0] = pozicia[0] - 1
    return pozicia


def over_misiu(pozicia, prikazy, ciele):
    ''' Pre zadanú počiatočnú pozíciu a postupnosť príkazov vráti informáciu
    o návštevnosti zadaných cieľov
    :param pozicia: počiatočná pozícia robota
    :type pozicia: list
    :param prikazy: reťazec obsahujúci všetky príkazy pre robota
    :type prikazy: str
    :param ciele: zoznam súradníc všetkých cieľov, ktoré má robot navštiviť
    :type ciele: list
    :return: tvrdenie či boli navštívené všetky ciele z počiatočnej pozície
    po vykonaní všetkých príkazov
    :rtype: bool
    '''
    if pozicia[:2] in ciele:
        # ak sa poč. súradnice robota nachádzajú v zozname cieľov, tak sa z neho zmažú
        ciele.remove(pozicia[:2])
    for prikaz in prikazy:
        # postupná zmena pozície robota po vykonaní jednotlivých príkazov
        pozicia = nova_pozicia(pozicia, prikaz)
        if pozicia[:2] in ciele:
            # ak sa súradnice robota nachádzajú v zozname cieľov, tak sa z neho zmažú
            ciele.remove(pozicia[:2])
    return len(ciele) == 0  # boli navštívené všetky ciele?


# pozitívne prípady - z poč. bodu [0, 0] aj z iných bodov;
# poč. bod može byť jedným z cieľov
print(f'{over_misiu( [0, 0, 0], "K", [[0, 1]])}')
print(f'{over_misiu( [0, 0, 0], "K", [[0, 0], [0, 1]])}')
print(f'{over_misiu( [0, 1, 2], "K", [[0, 0]] )}')
print(f'{over_misiu( [-1, -1, 3], "OKOKOOOK", [[-1, -1], [-1, 0], [0, 0], [0, 1]] )}')
print(f'{over_misiu( [0, 0, 0], "KK", [[0, 0]])}')
# negatívne prípady
print(f'{over_misiu( [0, 0, 0], "K", [[1, 0]])}')
print(f'{over_misiu( [-1, -1, 3], "OKOKOOO", [[-1, -1], [-1, 0], [0, 0], [0, 1]] )}')

Riešenie úlohy v jazyku Imagine Logo bude v podstate rovnaké ako v Pythone až na niekoľko implementačných detailov, ktoré súvisia so spracovaním zoznamov v Imagine Logu a v Pythone:

•  Zvýšenie druhého prvku zoznamu o 1

  • v Pythone: pozicia[1] = pozicia[1] + 1  

  • v Imagine Logu: urobTu "pozicia nahraď 2 :pozicia (prvok 2 :pozicia) + 1

• Podmienka, či je číslo x v zozname 

  • v Pythone: x in ciele  

  • v Imagine Logu: prvok? x :ciele

• Vynechanie prvku x zo zoznamu 

  • v Pythone (vynechá zo zoznamu len jednu inštanciu prvku x): ciele.remove(x)  

  • v Imagine Logu (vynechá zo zoznamu všetky inštancie prvku x): urobTu "ciele bezVýskytov :x :ciele

Výsledné riešenie celej úlohy zapísané v jazyku Imagine Logo môže potom vyzerať nasledovne:

Uvedené riešenie vieme vylepšiť či doplniť tak, že ošetríme správnosť vstupov, napr. či príkazy pre robota sú len prvky z množiny {K, O}, doplníme výpisy resp. vykreslenie aktuálnych pozícií a natočenia robota, atď.

Táto súťažná úloha je zameraná na použitie stratégie rozdelenia problému do podproblémov, na precvičenie použitia jednoduchých a dvojúrovňových zoznamov pri výpočtoch, funkcii s parametrami a výstupmi.

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

Do riešenia tejto úlohy sa zapojili 4 tímy kategórie EXPERT a 6 tímov kategórie GURU. Plný počet bodov získali 3 tímy, k čomu im gratulujeme. Obzvlášť chválime tímy Šedá eminencia dodekahedrónov a Bojovnik_Macek (obidva z kategórie EXPERT!) za ich vzorové riešenie obsahujúce komentáre a popisné názvy premenných. Rovnako chválime tím DemBoiz za dôsledné riešenie, v ktorom pomocou výnimiek ošetrili vstupné údaje. Je zaujímavé, že z 10 tímov, 9 riešilo úlohu v jazyku Python a len 1 tím v Imagine Logo, navyše neúspešne.

Riešenia boli veľmi rôznorodé. Jedno riešenie bolo naprogramované objektovo. Okrem zoznamov sme v riešeniach zaregistrovali aj n-tice a množiny. Smer robota niektoré tímy označovali číslami 0, 1, 2, 3, iné hodnotami uhlov 0, 90, 180, 270 iné písmenami 'N', 'E', 'S', 'W' či slovami 'sever','vychod', 'juh', 'zapad'.

V riešeniach sme zaregistrovali nasledovné chyby:

• vyriešenie úlohy len z počiatočnej pozície [0, 0], nie z ľubovoľnej pozície s celočíselnými súradnicami,

• opomenutie prípadu, keď počiatočná pozícia robota je zároveň jednou z hodnôt zo zoznamu pozícií cieľov,

• nesprávna úvaha, že počet navštívených miest musí byť rovnaký ako počet cieľov,

• neefektívne viacnásobné použitie IF príkazov namiesto konštrukcie.IF ELIF, či IF ELSE,

• namiesto funkcie all použitie funkcie any,

• prehodenie súradníc x a y.