PALMA junior
Úloha o symetriách

Autorské riešenie
[stiahni symetrie1.py, symetrie2.py, symetrie3.py]

• Počet riešiteľov: 35 / 46 = 76 %

• Úspešnosť riešenia: 4,24 / 6 = 71 %

Riešenie tejto úlohy spočíva vo vykresľovaní symetrických obrázkov. Obrázky sú definované návodom na ich vykreslenie. Podľa zadania: "návod môže obsahovať inštrukcie na zafarbenie celého obrázka, vybraného riadku, stĺpca alebo konkrétneho políčka". Ak sa pozrieme na ilustratívny príklad zo zadania, tak podľa návodu:

[['*', '*', 'yellow'], ['*', 3, 'green'], [7, '*', 'blue'], [9, 5, 'red'] ]

by sa mal vykresliť nasledovný obrázok:

Ak porovnáme návod s obrázkom rýchlo zistíme, ako od seba odlíšiť jednotlivé typy inštrukcií:

• každá inštrukcia je trojprvkový zoznam,

• prvé dva prvky definujú čo sa má vyfarbiť, tretí prvok určuje farbu,

  • *, * znamená, že vyfarbíme celý obrázok,

  • *, číslo znamená, že vyfarbujeme celý riadok číslo, pričom riadky číslujeme od 0,

  • číslo, * znamená že vyfarbujeme celý stĺpec číslo, pričom stĺpce číslujeme od 0,

  • číslo1, číslo2 znamená že vyfarbujeme políčko v stĺpci číslo1 a v riadku číslo2,

• pri farbení farbíme nie len zadanú časť, ale aj políčka symetrické podľa zvislej a vodorovnej osi súmernosti.

Všimnime si jednu zaujímavú vec. Vďaka symetrii je úplne jedno, či číslujeme stĺpce zľava alebo sprava alebo či číslujeme riadky zhora alebo zdola. Ak máme vyfarbiť riadok číslo R, k nemu symetrický riadok má číslo 9-R. Rovnako aj pre stĺpec S je symetrickým stĺpcom stĺpec 9-S.

Časť problému je už vyriešená. Máme k dispozícii funkciu na vykreslenie mriežky (kresli_mriezku()) a funkciu na vyfarbenie jedného políčka (vyfarbi_policko(stlpec, riadok, farba)), aj keď zatiaľ bez symetrie.

Pozrime sa bližšie na to, čo potrebujeme vyriešiť. Požadovaná funkcia vytvor_symetriu() by zrejme mala dostať návod na kreslenie. Podľa jednotlivých inštrukcií v návode by mala zabezpečiť vykreslenie jednotlivých častí obrázka. Kreslenie celého obrázka si môžeme rozdeliť na štyri prípady (farbenie celého obrázka, vybraného riadku, stĺpca alebo políčka) a pre každý z prípadov si vytvorme samostatnú funkciu. Funkcie by sme mohli navrhnúť tak, že okrem farbenia požadovanej časti vyfarbia aj symetrické časti. Schéma celého programu (volanie jednotlivých funkcií) by teda mohla vyzerať nasledovne:

Program môže vyzerať nasledovne:

#symetrie1.py
import turtle

def je_korektna_suradnica(suradnica):
    ...


def vyfarbi_policko(stlpec, riadok, farba):
    ...

    
def kresli_mriezku():
    ...


def vyfarbi_vsetko(farba):
    for riadok in range(10):
        for stlpec in range(10):
            vyfarbi_policko(stlpec, riadok, farba)


def vyfarbi_symetricky_stlpec(stlpec, farba):
    for riadok in range(10):
        vyfarbi_policko(stlpec, riadok, farba)
        vyfarbi_policko(9-stlpec, riadok, farba)


def vyfarbi_symetricky_riadok(riadok, farba):
    for stlpec in range(10):
        vyfarbi_policko(stlpec, riadok, farba)
        vyfarbi_policko(stlpec, 9-riadok, farba)


def vyfarbi_symetricky_policko(stlpec, riadok, farba):
    vyfarbi_policko(stlpec, riadok, farba)
    vyfarbi_policko(9-stlpec, riadok, farba)
    vyfarbi_policko(stlpec, 9-riadok, farba)
    vyfarbi_policko(9-stlpec, 9-riadok, farba)


def vytvor_symetriu(navod):
    for instrukcia in navod:
        stlpec = instrukcia[0]
        riadok = instrukcia[1]
        farba = instrukcia[2]
        if stlpec == '*':
            if riadok == '*':
                vyfarbi_vsetko(farba)
            else:
                vyfarbi_symetricky_riadok(riadok, farba)
        else:
            if riadok == '*':
                vyfarbi_symetricky_stlpec(stlpec, farba)
            else:
                vyfarbi_symetricky_policko(stlpec, riadok, farba)


pero = turtle.Turtle()
pero.speed(0)
pero.hideturtle()
plocha = turtle.Screen()
plocha.delay(2)

navod = [['*', '*', 'yellow'],
         ['*', 3, 'green'],
         [2, '*', 'blue'],
         [9, 5, 'red']
         ]

kresli_mriezku()
vytvor_symetriu(navod)

plocha.mainloop()

Všimnime si, ako náš program obrázok vykresľuje. Niektoré políčka obrázka sa prekresľujú opakovane, až kým sa dosiahne ich konečná farba. Ak by bol návod veľmi komplikovaný, vykresľovanie obrázka by mohlo trvať veľmi dlho. A to aj napriek tomu, že sme kreslenie urýchlili:

• urýchlili sme samotný pohyb kresliaceho pera - pero.speed(0),

• urýchlili sme aktualizáciu kresliacej plochy  - plocha.delay(0).

Aby sme políčka opakovane nevykresľovali, výhodnejšie  bude, vytvoriť si nejaký model obrázka a postupne ho upravovať podľa návodu. Keď bude hotový model výsledného obrázka, výsledný obrázok podľa neho vykreslíme. Takto si zabezpečíme, že každé políčko obrázka vykreslíme len raz.

Navrhnime nejaký model obrázka. Keďže obrázok je dvojrozmerný, aj model by sme mohli reprezentovať v nejakej dvojrozmernej dátovej štruktúre. Celkom prirodzene môžeme využiť zoznamy zoznamov. Každý vnútorný zoznam bude reprezentovať jeden riadok obrázka a jeho prvky stĺpce v danom riadku. Prvky zoznamov majú svoje poradie. To môžeme využiť a poradie vnútorných zoznamov a ich prvkov môže zodpovedať poradiu riadkov a stĺpcov v obrázku. Upravme schému programu nasledovne:

Ak implementujeme jednotlivé funkcie, ďalšia verzia programu môže vyzerať nasledovne: 

#symetrie2.py
import turtle


def je_korektna_suradnica(suradnica):
    ...


def vyfarbi_policko(stlpec, riadok, farba):
    ...

    
def kresli_mriezku():
    ...


def registruj_farbu_vsetko(farba, model_obrazka):
    model_obrazka[:] = [[farba] * 10 for i in range(10)]


def registruj_farbu_stlpec(stlpec, farba, model_obrazka):
    for riadok in range(10):
        model_obrazka[riadok][stlpec] = farba
        model_obrazka[riadok][9-stlpec] = farba


def registruj_farbu_riadok(riadok, farba, model_obrazka):
    model_obrazka[riadok] = [farba] * 10
    model_obrazka[9-riadok] = [farba] * 10


def registruj_farbu_policko(stlpec, riadok, farba, model_obrazka):
    model_obrazka[riadok][stlpec] = farba
    model_obrazka[riadok][9-stlpec] = farba
    model_obrazka[9-riadok][stlpec] = farba
    model_obrazka[9-riadok][9-stlpec] = farba


def vyfarbi_obrazok(model_obrazka):
    for riadok in range(10):
        for stlpec in range(10):
            farba = model_obrazka[riadok][stlpec]
            if not farba is None:
                vyfarbi_policko(stlpec, riadok, farba)


def vytvor_symetriu(navod):
    model_obrazka = [[None] * 10 for i in range(10)]

    for instrukcia in navod:
        stlpec = instrukcia[0]
        riadok = instrukcia[1]
        farba = instrukcia[2]
        if stlpec == '*':
            if riadok == '*':
                registruj_farbu_vsetko(farba, model_obrazka)
            else:
                registruj_farbu_riadok(riadok, farba, model_obrazka)
        else:
            if riadok == '*':
                registruj_farbu_stlpec(stlpec, farba, model_obrazka)
            else:
                registruj_farbu_policko(stlpec, riadok, farba, model_obrazka)
    vyfarbi_obrazok(model_obrazka)


pero = turtle.Turtle()
pero.speed(0)
pero.hideturtle()
plocha = turtle.Screen()
plocha.delay(0)

navod = [['*', '*', 'yellow'],
         ['*', 3, 'green'],
         [2, '*', 'blue'],
         [9, 5, 'red']
         ]

kresli_mriezku()
vytvor_symetriu(navod)

plocha.mainloop() 

Všimnime si vytvorenie modelu "prázdneho" obrázka vo funkcii vytvor_symetriu(navod). Keďže nevieme, akú výslednú farbu budú políčka obrázka mať, nastavíme im zatiaľ hodnotu na None (alebo nejakú inú, vopred dohodnutú hodnotu). Model prázdneho obrázka je teda 10-prvkový zoznam zoznamov, pričom každý vnútorný zoznam obsahuje 10 hodnôt None.

Vo funkcii vytvor_symetriu() následne prechádzame zoznamom inštrukcií a podľa typu inštrukcie voláme príslušnú funkciu na úpravu modelu. Jednotlivé funkcie pre zmenu modelu (registruj_...) sú už relatívne jednoduché. Každá z nich navyše upravuje aj hodnoty symetrických políčok v modeli.

Za povšimnutie stojí aj skutočnosť, že žiadna z funkcií na úpravu modelu nevracia upravený model (return model_obrazka). Zoznam je meniteľná štruktúra a funkcie dostávajú v parametri odkaz na zoznam model_obrazka. Zmeny zoznamu vykonané v jednotlivých funkciách sa tak automaticky prejavia aj vo funkcii vytvor_symetriu().  Preto nie je potrebné výsledný zmenený zoznam vracať.

Posledným krokom je skutočné vyfarbenie obrázka podľa vytvoreného modelu. Funkcia vyfarbi_obrazok(model_obrazka) postupne prechádza jednotlivými prvkami zoznamu model_obrazka a realizuje farbenie len tých políčok, ktoré majú nastavenú reálnu farbu (hodnota je rôzna od None). 

S týmto výsledkom by sme mohli byť spokojní, ale ...

Všimnime si ešte jednu zaujímavú poznámku zo zadania úlohy: "Uvedomili si, že ak chcú nakresliť osovo súmerný obrázok, stačí vymyslieť len polovicu z neho. Druhú polovicu za nich „vytvorí“ osová súmernosť." Toto by sme mohli v programe využiť aj my. Nemusíme mať a upravovať model celého obrázka. Stačí nám pracovať len s modelom časti obrázka. Celý obrázok potom vykreslíme symetricky, podľa tejto časti. Keďže máme dve osi súmernosti, vieme dopočítať pravú časť obrázka a zároveň aj jeho hornú časť. Stačí nám preto vytvoriť model len pre ľavú spodnú časť obrázka. Nový model bude mať len štvrtinovú veľkosť pôvodného modelu. Výsledná verzia programu môže vyzerať nasledovne: 

#symetrie3.py
import turtle


def je_korektna_suradnica(suradnica):
    ...


def vyfarbi_policko(stlpec, riadok, farba):
    ...

    
def kresli_mriezku():
    ...


def symetricka_suradnica(suradnica):
    if suradnica < 5:
        return suradnica
    return 9 - suradnica

def registruj_farbu_vsetko(farba, model_obrazka):
    model_obrazka[:] = [[farba] * 5 for i in range(5)]


def registruj_farbu_stlpec(stlpec, farba, model_obrazka):
    for riadok in range(5):
        model_obrazka[riadok][stlpec] = farba


def registruj_farbu_riadok(riadok, farba, model_obrazka):
    model_obrazka[riadok] = [farba] * 5


def registruj_farbu_policko(stlpec, riadok, farba, model_obrazka):
    model_obrazka[riadok][stlpec] = farba


def vyfarbi_obrazok(model_obrazka):
    for riadok in range(5):
        for stlpec in range(5):
            farba = model_obrazka[riadok][stlpec]
            if not farba is None:
                vyfarbi_policko(stlpec, riadok, farba)
                vyfarbi_policko(9-stlpec, riadok, farba)
                vyfarbi_policko(stlpec, 9-riadok, farba)
                vyfarbi_policko(9-stlpec, 9-riadok, farba)


def vytvor_symetriu(navod):
    model_obrazka = [[None] * 5 for i in range(5)]

    for instrukcia in navod:
        stlpec = instrukcia[0]
        riadok = instrukcia[1]
        farba = instrukcia[2]
        if stlpec == '*':
            if riadok == '*':
                registruj_farbu_vsetko(farba, model_obrazka)
            else:
                riadok = symetricka_suradnica(riadok)
                registruj_farbu_riadok(riadok, farba, model_obrazka)
        else:
            if riadok == '*':
                stlpec = symetricka_suradnica(stlpec)
                registruj_farbu_stlpec(stlpec, farba, model_obrazka)
            else:
                riadok = symetricka_suradnica(riadok)
                stlpec = symetricka_suradnica(stlpec)
                registruj_farbu_policko(stlpec, riadok, farba, model_obrazka)
    vyfarbi_obrazok(model_obrazka)


pero = turtle.Turtle()
pero.speed(0)
pero.hideturtle()
plocha = turtle.Screen()
plocha.delay(0)

navod = [['*', '*', 'yellow'],
         ['*', 3, 'green'],
         [2, '*', 'blue'],
         [9, 5, 'red']
         ]

kresli_mriezku()
vytvor_symetriu(navod)

plocha.mainloop()

Všimnime si novú funkciu symetricka_suradnica(). Inštrukcie v návode na kreslenie sa môžu odkazovať na ľubovoľnú časť obrázka. Keďže mi máme model len pre jednu jeho štvrtinu, všetky zmeny musíme registrovať tu. Ak by inštrukcia odkazovala na nejaké miesto mimo našej štvrtiny, prepočítame pozície týchto častí symetricky do našej štvrtiny. To je úlohou funkcie symetricka_suradnica().

O vykreslenie celého obrázka sa postará funkcia vyfarbi_obrazok(). Okrem vyfarbenia konkrétneho políčka podľa modelu obrázku zabezpečí aj vyfarbenie jeho symetrických políčok.

Ukázali sme si niekoľko rôznych prístupov k riešeniu tejto úlohu. Prvý, asi najprirodzenejší spôsob, má tú nevýhodu, že je príliš pomalý. V druhom sme kreslenie zrýchlili, lebo priebežne upravujeme model obrázka a až jeho výslednú podobu vykreslíme. V treťom riešení sme navyše ušetrili časť pamäte, pretože model reprezentuje len štvrtinu obrázka. Zvyšok vieme pri vykresľovaní na základe symetrií dopočítať.

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

Túto úlohu vyriešila väčšina z vás správne. Načastejšou chybou bolo, že požadovaná funkcia nemala definované parametre a pracovala tak s globálnou premennou, ktorá bola definovaná v hlavnom programe. Ak by sme takúto funkciu chceli použiť v inom programe, zrejme by nefungovala.

Efektívnosť riešenia, aj napriek vyššie uvedenej analýze, sme vo vašich riešeniach nehodnotili, resp. len sme na to upozornili poznámkou v hodnotení.