PALMA junior
Úloha o vyhľadávaní v knižnici

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 19 / 26 = 73 %

• Úspešnosť riešenia: 6,11 / 7 = 87 %

Riešenie tejto úlohy nie je náročné. Potrebujeme si však dobre premyslieť, aké podmienky definujeme pre porovnávanie zodpovedajúcich dvojíc znakov v porovnávaných reťazcoch a v akom poradí ich budeme realizovať.

Postupne budeme prechádzať dvojicami znakov z oboch reťazcov a vzájomne ich budeme porovnávať.

Ak by sa znaky rovnali, ich rozdiel je 0 a celkový rozdiel porovnávaných reťazcov to nezmení. V tomto prípade teda nemusíme nič robiť. Otestujme preto ako prvé, či sú porovnávané znaky rôzne.  

# Python
def rozdiel_textov(text1, text2):
    rozdiel = 0
    for idx in range(len(text1)):
        znak1 = text1[idx]
        znak2 = text2[idx]
        if znak1 != znak2:
            ...

Teraz potrebujeme otestovať, ako sa porovnávané znaky líšia. Máme niekoľko prípadov, ktoré musíme rozpoznať:

• znaky sa líšia len veľkosťou,

• znaky líšia len v diakritickom znamienku,

• znaky líšia súčasne vo veľkosti aj v diakritickom znamienku,

• znaky líšia inak.

Zamyslime sa nad poradím, v akom budeme rozdiely testovať.

Logické bude začať podmienkami, v ktorých testujeme najmenšie rozdiely: rozdiel vo veľkosti alebo rozdiel v diakritickom znamienku.

Ak v znakoch nie je jeden z malých rozdielov otestujme, či nie je rozdiel aj vo veľkosti aj v diakritickom znamienku súčasne.

Ak nie je rozdiel aj vo veľkosti aj v diakritickom znamienku súčasne, znaky sa líšia inak.

Pozrime sa ešte na technickú stránku podmienok.

Ak chceme zistiť, či sa znaky líšia len veľkosťou, stačí porovnať ich zmenšené verzie (uvedomme si, že prvá podmienka vylúčila rovnosť znakov).

if znak1.lower() == znak2.lower():

Porovnanie, či sa znaky líšia len v diakritickom znamienku bude o niečo náročnejšie. Takúto funkciu reťazce nemajú. Príslušnú funkciu si budeme musieť vytvoriť. Samotné porovnanie môžeme potom zrealizovať nasledovne: 

elif bez_diakritiky(znak1) == bez_diakritiky(znak2): 

Otestovanie toho, či je rozdiel aj vo veľkosti aj v diakritickom znamienku súčasne, zrealizujeme nasledovne: 

elif bez_diakritiky(znak1.lower()) == bez_diakritiky(znak2.lower()): 

Výsledná funkcia môže vyzerať nasledovne: 

def rozdiel_textov(text1, text2):
    rozdiel = 0
    for idx in range(len(text1)):
        znak1 = text1[idx]
        znak2 = text2[idx]
        if znak1 != znak2:
            if znak1.lower() == znak2.lower():
                    rozdiel += 0.3
            elif bez_diakritiky(znak1) == bez_diakritiky(znak2):
                    rozdiel += 0.4
            elif bez_diakritiky(znak1.lower()) == bez_diakritiky(znak2.lower()):
                    rozdiel += 0.7
            else:
                rozdiel += 1
    return rozdiel 

Ostáva ešte definovať funkciu bez_diakritiky(). Môžeme postupovať tak, že overíme či znak obsahuje diakritické znamienko. Ak áno, nahradíme ho znakom bez znamienka. Ak nie, nemusíme nič riešiť. Funkciu môžeme definovať nasledovne: 

def bez_diakritiky(znak):
    znaky_s_diakritikou =  'áäčďéěĺľňóôöŕřšťúýžÁÄČĎÉĚĹĽŇÓÔÖŔŘŠŤÚÝŽ'
    znaky_bez_diakritiky = 'aacdeellnooorrstuyzAACDEELLNOOORRSTUYZ'
    if znak in znaky_s_diakritikou:
        poz = znaky_s_diakritikou.index(znak)
        return znaky_bez_diakritiky[poz]
    return znak

Keď sa zamyslíme nad uvedenou funkciu, realizuje "nahradzovanie". Znak s diakritickým znamienkom nahradí znakom bez znamienka. Rovnakú funkcionalitu nám ponúka aj dátová štruktúra slovník (dictionary). Ak pri riešení využijeme slovník, funkciu bez_diakritiky() nepotrebujeme.  Výsledná funkcia môže byť definovaná nasledovne:

# Python
def rozdiel_textov(text1, text2):
    znaky_s_diakritikou = 'áäčďéěĺľňóôöŕřšťúýžÁÄČĎÉĚĹĽŇÓÔÖŔŘŠŤÚÝŽ'
    znaky_bez_diakritiky = 'aacdeellnooorrstuyzAACDEELLNOOORRSTUYZ'
    # vytvorime slovnik, ktory mapuje znaky s diakritikou na znaky bez diakritiky
    # ak znak v slovniku neexistuje, funkcie slovnika get() nam vrati
    # hodnotu druheho argumentu
    bez_diakritiky = {znaky_s_diakritikou[i]: znaky_bez_diakritiky[i]
                      for i in range(len(znaky_s_diakritikou))}
    rozdiel = 0
    for idx in range(len(text1)):
        znak1 = text1[idx]
        znak2 = text2[idx]
        if znak1 != znak2:
            if znak1.lower() == znak2.lower():
                rozdiel += 0.3
            elif bez_diakritiky.get(znak1, znak1) == bez_diakritiky.get(znak2, znak2):
                rozdiel += 0.4
            elif bez_diakritiky.get(znak1.lower(), znak1.lower()) == \
                    bez_diakritiky.get(znak2.lower(), znak2.lower()):
                rozdiel += 0.7
            else:
                rozdiel += 1
    return rozdiel

Obidve uvedené riešenia sú správne. Riešenie využívajúce slovník je ale omnoho efektívnejšie.

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

Väčšina z vás riešila túto úlohu správne. Problémy sa objavili pri podmienkach, kde sa testovala zhodnosť znakov po odstránení diakritiky. Niektoré podmienky boli zapísané príliš komplikovane, čo bolo dôsledkom toho, že ste podmienky nevnárali, a tak ste opakovane testovali rovnaké veci.

Niektorí z vás na odstránenie diakritiky využili modul unicodedata, ktorý bolo potrebné inštalovať. Použili ste ho však trochu nešikovným spôsobom, keď ste skombinovali príliš veľa funkcií (čo nebolo potrebné). Šikovnejšie by bolo použiť modul unidecode a jeho funkciu unidecode.