PALMA junior
Úloha o sade písmenkových kartičiek

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

• Počet riešiteľov: 27 / 29 =  93 %

• Úspešnosť riešenia: 4,87 / 5 = 81 %

Podľa zadania úlohy máme pre zadané písmená (ďalej znaky) vygenerovať kartičky so sadou dvojíc znakov na každej kartičke. Počet kartičiek je rovnaký ako zadaný počet znakov. Na každej kartičke je počet dvojíc o jedna menší ako zadaný počet znakov. Ľubovoľné dve kartičky majú rovnakú práve jednu dvojicu znakov.

Pre lepšiu názornosť zostavme sadu kartičiek pre konkrétny textový reťazec, napr. 'AEIOU'. Pozrime sa na všetky možné dvojice znakov vytvorené z reťazca 'AEIOU'. Tie sa dajú zobraziť ako hrany v úplnom grafe s piatimi vrcholmi.

Z každého z piatich vrcholov grafu vychádzajú štyri hrany, konkrétne:

Z obrázku je zrejmé, že ak si zoberieme ľubovoľné dva vrcholy, tak tie majú spoločnú práve jednu hranu. Ostatné hrany vychádzajúce z jedného a z druhého vrchola sú rôzne. Riešenie úlohy môže vyzerať tak, že sadu kartičiek budú reprezentovať vrcholy úplného grafu a dvojice znakov na kartičke budú reprezentovať hrany vychádzajúce z daného vrcholu.

Medzi vrcholmi X a Y je rovnaká hrana ako medzi vrcholmi Y a X. Potom na vrcholoch (=kartičkách) X a Y sa bude nachádzať hrana (=dvojica) XY (kde znak X predchádza znaku Y v zadanom reťazci, resp. X je v abecede pred Y):

Takto navrhnutú sadu kartičiek môžeme zjednodušene bez označenia kartičiek reprezentovať ako zoznam zoznamov dvojznakových reťazcov. Hlavnou myšlienkou algoritmu je, že pre každý znak v zadanom reťazci vytvoríme kartičku s dvojicami znakov tvorených zadaným znakom postupne zlúčeným s ostatnými znákmi textového reťazca. O poradí znakov v každej dvojici rozhoduje ich abecedné poradie.

Výsledná funkcia vytvor_karticky s jedným parametrom znaky môže vyzerať napr. nasledovne:

def vytvor_karticky(znaky):
    if len(znaky) < 2:
        raise ValueError("Na vytvorenie kartičiek potrebujeme aspoň 2 znaky.")
    zoznam_karticiek = []
    for znak1 in znaky:
        karticka = []
        for znak2 in znaky:
            if znak1 != znak2:
                karticka.append(min(znak1, znak2) + max(znak1, znak2))
        zoznam_karticiek.append(karticka)
    return zoznam_karticiek

Iným riešením je prechádzať všetkými možnými dvojicami znakov a každú dvojicu znakov priradiť do dvoch zoznamov. O poradí znakov v každej dvojici rozhoduje ich poradie v zadanom reťazci.  Pre tento algoritmický prístup funkcia vytvor_karticky s jedným parametrom znaky môže vyzerať napr. nasledovne:

def vytvor_karticky(znaky):
    n = len(znaky)
    if n < 2:
        raise ValueError("Na vytvorenie kartičiek potrebujeme aspoň 2 znaky.")
    karticky = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            dvojica = znaky[i] + znaky[j]
            karticky[i].append(dvojica)
            karticky[j].append(dvojica)
    return karticky

Uvedené riešenie vieme zostručniť, ak pre vytvorenie všetkých možných dvojíc použijeme metódu combinations z modulu itertools. Zostručnená funkcia vytvor_karticky s jedným parametrom znaky môže vyzerať napr. nasledovne:

import itertools

def vytvor_karticky(znaky):
    if len(znaky) < 2:
        raise ValueError("Na vytvorenie kartičiek potrebujeme aspoň 2 znaky.")
    zoznam_karticiek = []
    for znak in znaky:
        zoznam_karticiek.append([''.join(dvojica) for dvojica in itertools.\
                                combinations(znaky, 2) if znak in dvojica])
    return zoznam_karticiek

Táto úloha je zameraná na:

• použitie stratégie riešenia problémov - dekompozíciu problému na podproblémy a hľadanie vzorov.

• precvičenie príkazov volania funkcií s parametrom a návratovou hodnotou, vnorených cyklov for, príkazu vetvenia, metód s reťazcami a zoznamami.

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

Do riešenia úlohy sa zapojilo 27 tímov z kategórie GURU. Plný počet bodov za svoje riešenie získalo až 18 tímov, ktorým srdečne gratulujeme.

Vo väčšine riešení súťažiaci použili na reprezentciu dvojice reťazce, ostatní použili zoznamy, či n-tice. Tím netuším použil vo svojom riešení OOP prístup. Iný tím bonusovo vykresľoval kartičky do grafického plátna. V piatich riešeniach súťažiaci použili modul itertools s metódou combinations.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému:

• nedôsledná analýza problému spôsobujúca, že riešenie úlohy nebolo správne vôbec, alebo len pre určité dĺžky reťazcov,

• nesprávne zredukovanie riešenia problému len na dve dvojice na každej kartičke,

• zbytočné načítanie počtu znakov textového reťazca, ktoré sa dá vypočítať zo zadaného reťazcapomocou funkcie len,

• nedotiahnutie riešenia do konca, v ktorom boli namiesto jednej dvojice XY uvedené dvojice XY aj YX, 

• vo funkcií namiesto vrátenia hodnoty bol výsledok vytlačený.