PALMA junior
Úloha o maľovaní farebným pravidelným štvorstenom

Autorské riešenie
[stiahni py, py2]

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

• Úspešnosť riešenia: 4,08 / 7 = 58,33 %

Najprv sa pozrime na konkrétnu situáciu prevaľovania štvorstena uvedenú v zadaní úlohy. Na nasledovnom obrázku je štvorsten zobrazený postupne v 6 stavoch:

pričom po použití zoznamu operátorov prevalenia ['vpravo hore', 'vpravo dole', 'dole', 'vpravo dole', 'vpravo hore'] štvorsten zanechal na ploche nasledovné odtlačky:

ktoré vieme zapísať do zoznamu [‘červená’, ’žltá’, ’modrá’, ’červená’, ’zelená’, ’modrá’]

Pri riešení úlohy nám pomôže pomocný obrázok s odtlačkami štvorstena pri jeho prevaľovaní do rôznych smerov,

Pri prevaľovaní štvorstena môžeme zistiť, že sa striedavo mení orientácia jeho odtlačku - raz je natočený hranou k nám (hranou dole, čo môžeme vyjadriť hodnotou premennej orientacia = 0) a raz je natočený vrcholom k nám (hranou hore, čo môžeme vyjadriť hodnotou premennej orientacia = 1). Pri každej z uvedených orientácii štvorstena môžeme pri prevaľovaní použiť inú trojicu operátorov, a to:

• pre orientácia = 0 sa dá použiť niektorý operátor zo zoznamu ['lh', 'ph', 'd']

• pre orientácia = 1 sa dá použiť niektorý operátor zo zoznamu ['ld', 'pd, 'h']

kde sme použili skrátené názvy operátorov 'lh', 'ph', 'd', 'ld', 'pd, 'h' namiesto názvov operátorov 'vľavo hore', 'vpravo hore', 'dole', 'vľavo dole', 'vpravo dole, 'hore'.

Pozrime sa na všetky možné situácie s rôznymi farbami a rôznou orientáciou odtlačkou podstavy štvorstena. Tieto situácie sú uvedené na nasledovnom obrázku:

čo vieme vyjadriť aj tabuľkou:

Na základe tejto tabuľky vieme zostaviť funkciu tah(), ktorá pre zadanú farbu podstavy a zadaný operátor vráti výslednú (novú) farbu podstavy. Prvoplánovo sa dá naprogramovať funkcia, ktorá obsahuje viaceré do seba vnorené príkazy vetvenia. Elegantnejším riešením je použiť slovníky - pre každú farbu (riadok tabuľky) jeden slovník a tiež jeden hlavný slovník, ktorého kľúčom je farba a ktorého hodnotou je slovník pre odpovedajúcu farbu.

Pomocná funkcia tah() so vstupnými parametrami farba a operátor vracajúca novú farbu podstavy môže vyzerať nasledovne:

def tah(farba, operator):
    slovnik_Cervena = {'lh': 'zelená',
                       'pd': 'zelená',
                       'ld': 'žltá',
                       'ph': 'žltá',
                       'h': 'modrá',
                       'd': 'modrá'}
    slovnik_Zelena = {'lh': 'červená',
                      'pd': 'červená',
                      'ld': 'modrá',
                      'ph': 'modrá',
                      'h': 'žltá',
                      'd': 'žltá'}
    slovnik_Zlta = {'lh': 'modrá',
                    'pd': 'modrá',
                    'ld': 'červená',
                    'ph': 'červená',
                    'h': 'zelená',
                    'd': 'zelená'}
    slovnik_Modra = {'lh': 'žltá',
                     'pd': 'žltá',
                     'ld': 'zelená',
                     'ph': 'zelená',
                     'h': 'červená',
                     'd': 'červená'}

    slovnik = {'červená': slovnik_Cervena,
               'zelená': slovnik_Zelena,
               'žltá': slovnik_Zlta,
               'modrá': slovnik_Modra}

    return slovnik[farba][operator]

Výsledná funkcia zisti_farby() so vstupnými parametrami farba, orientacia a zoznam_operatorov vracajúca výsledný zoznam s farbami odtlačkov štvorstena môže vyzerať nasledovne:

def zisti_farby(farba, orientacia, zoznam_operatorov):
    dovoleny_tah = [{'lh', 'ph', 'd'}, {'h', 'ld', 'pd'}]
    vysledok = [farba]
    for operator in zoznam_operatorov:
        if operator in dovoleny_tah[orientacia]:
            farba = tah(farba, operator)
            orientacia = 1 - orientacia
            vysledok.append(farba)
        else:
            raise ValueError('operátor sa nedá aplikovať')
    return vysledok

V uvedenej funkcii sú ošetrené dovolené ťahy so striedaním hodnôt orientácie {0,1}. Pre ilustračný príklad funkcia zisti_farby('červená', 0, ['ph', 'pd', 'd', 'pd', 'ph']) vráti zoznam farieb odtlačkov štvorstena ['červená', 'žltá', 'modrá', 'červená', 'zelená', 'modrá']

Iné alternatívne riešenie úlohy využiva zobrazenie štvorstenu zhora, v ktorom sa na označenie farieb použijú celé čísla od 0 do 3. Na nasledovnom obrázku vľavo je uvedený štvorsten orientácii s hranou dole (orientácia = 0) s farbou podstavy 0 a vpravo je uvedený štvorsten orientácii s hranou hore (orientácia = 1) s farbou podstavy 3. Obidva uvedené stavy vyjadríme zoznamom [0, 1, 2, 3].

Pri preklápaní týchto stavov nám postačia 4 operátory 'vľavo', 'vpravo', 'hore', 'dole', ktoré v programe môžeme označiť jednopísmennými skratkami 'l', 'p', 'h', 'd'.

Zo stavu [0, 1, 2, 3] sa pri hodnote orientacia = 0 dostaneme:

• po operátore 'l' do stavu [2, 3, 0, 1] s hodnotou operacia = 1

• po operátore 'p' do stavu [1, 0, 3, 2] s hodnotou operacia = 1

• po operátore 'h' do stavu [], čo je chybový stav vyhadzujúci výnimku

• po operátore 'd' do stavu [0, 1, 2, 3] s hodnotou operacia = 1

Zo stavu [0, 1, 2, 3] sa pri hodnote orientacia = 1 dostaneme:

• po operátore 'l' do stavu [1, 0, 3, 2] s hodnotou operacia = 0 

• po operátore 'p' do stavu [2, 3, 0, 1] s hodnotou operacia = 0

• po operátore 'h' do stavu [0, 1, 2, 3] s hodnotou operacia = 0

• po operátore 'd' do stavu [], čo je chybový stav vyhadzujúci výnimku

Na základe tejto analýzy môžeme vytvoriť funkciu zisti_farby() so vstupnými parametrami stav, orientacia a zoznam_operatorov, ktorá vracia výsledný zoznam s farbami odtlačkov:

def tah(stav, zmena):
    if len(zmena) == 0:
        raise ValueError('operátor sa nedá aplikovať')
    else:
        novy_stav = [stav[zmena[i]] for i in range(4)]
    return novy_stav


def zisti_farby(stav, orientacia, zoznam_operatorov):
    podstava = [stav[0], stav[3]][orientacia]
    vysledok = [podstava]
    for operator in zoznam_operatorov:
        if orientacia == 0:
            zmeny = {'l': [2, 3, 0, 1], 
                     'p': [1, 0, 3, 2], 
                     'h': [], 
                     'd': [0, 1, 2, 3]}
        else:
            zmeny = {'l': [1, 0, 3, 2], 
                     'p': [2, 3, 0, 1], 
                     'h': [0, 1, 2, 3], 
                     'd': []}
        stav = tah(stav, zmeny[operator])
        orientacia = 1 - orientacia
        podstava = [stav[0], stav[3]][orientacia]
        vysledok.append(podstava)
    return vysledok


print(zisti_farby(['červená', 'zelená', 'žltá', 'modrá'], 
                  0, 
                 ['p', 'p', 'd', 'p', 'p']))
# ['červená', 'žltá', 'modrá', 'červená', 'zelená', 'modrá']

V uvedenej funkcii sú ošetrené dovolené ťahy so striedaním hodnôt orientácie {0,1}. Pre ilustračný príklad funkcia zisti_farby(['červená', 'zelená', 'žltá', 'modrá'], 0, ['p', 'p', 'd', 'p', 'p']) vráti zoznam farieb odtlačkov štvorstena ['červená', 'žltá', 'modrá', 'červená', 'zelená', 'modrá']. Prvý parameter funkcie stav predstavuje počiatočné nastavenie farieb štvorstena.

Iným exotickým riešením úlohy je, ak použité hodnoty operátorov nebudú smery, ale priamo farby, na ktoré sa má štvorsten preklápať. Tu je potrebné ošetriť opakovanie rovnakej farby v nasledovnom preklopení.

Táto úloha je zameraná na:

• použitie stratégie riešenia problémov - dekompozícia problému na podproblémy,  hľadanie vzorov, nakresli obrázok, vytvor tabuľku.

• precvičenie príkazov volania funkcií s parametrami s výstupom, cyklu for, vetvenia, prácu so zoznamom a slovníkom.

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

Do riešenia úlohy sa zapojili 4 tímy z kategórie EXPERT a 8 tímov z kategórie GURU. Plný počet bodov za svoje riešenie dosiahlo 5 tímov: albatros, elemejou, file-open, gg_ez a oliverseman, ktorým srdečne gratulujeme.

Najčastejšie bola riešená pomocou slovníkov a zoznamov. Jeden tím si vytvoril viacero pomocných funkcií s podmienkami pre rôzne smery prevalenia.

Niektoré tímy uvažovali 4 smery prevalenia (vľavo, vpravo, hore a dole). Iné tímy uvažovali len 3 smery prevalení, pričom si neuvedomili, že trojuholníkový odtlačok štvorstena môže byť orientovaný s hranou dole alebo s hranou hore. Niektoré tímy zabudli na ošetrenie chybových stavov (nepovolených ťahov).