PALMA junior
Úloha o písmenkovom kruhu

Autorské riešenie
[stiahni py]                                       

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

• Úspešnosť riešenia:  4.84 / 6 = 81 %                   

Riešenie úlohy o písmenkovom kruhu je založené na práci s dvoma reťazcami:

• kruhový text (reťazec) - postupnosť znakov, ktoré sú umiestnené po obvode kruhu,
• hľadaný text (reťazec) - postupnosť znakov, pre ktorý potrebujeme overiť, či sa nachádza na kruhu priamo alebo v opačnom poradí.

Jednoduchým testom na úvod môžeme zistiť, či je dĺžka hľadaného a kruhového reťazca rovnaká. Ak sme zistili, že dĺžka hľadaného a kruhového reťazca:

• nie je rovnaká, tak ďalej už úlohu riešiť nemusíme, lebo sme dostali odpoveď, že reťazce budú určite rôzne;
• je rovnaká, tak nás čaká náročnejšia úloha. V takom prípade je potrebné otestovať všetky možnosti, ktorým môže reťazec z kruhového textu začínať a navyše uvažovať aj smer spájania písmen.

Skúsenejší programátori rýchlo zistia, že hľadaný text si vieme veľmi rýchlo napísať aj odzadu s využitím výrezov v jazyku Python a to pomocou príkazu hladany_text_odzadu = hladany_text[::-1]. Potom nám už stačí preskúmať, či od zadaného indexu na kruhovom reťazci sa hľadaný text nachádza na kruhu buď priamo alebo v tvare tohto hľadaného textu odzadu. Hneď pri prvom nájdení zhody môžeme vrátiť hodnotu True, a teda v prípade kladnej odpovede už ďalšie indexy skúmať nemusíme.

Nasleduje možný zdrojový kód v jazyku Python

# Python
def over(hladany_text, kruhovy_text):
    if len(hladany_text) != len(kruhovy_text):
        return False
 
    hladany_text_odzadu = hladany_text[::-1]
 
    for index in range(len(kruhovy_text)):
        spojenie = kruhovy_text[index:] + kruhovy_text[:index]
        if spojenie == hladany_text:
            return True
        if spojenie == hladany_text_odzadu:
            return True
 
    return False

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

Úlohu riešilo všetkých 25 tímov. Väčšina riešení bola správna a používala prehľadanie všetkých možných indexov začiatku hľadaného reťazca na kruhu. Niektorí, aj keď to zadanie nevyžadovalo, do riešení doplnili aj prípadné vymazanie medzier v hľadanom texte alebo v texte na písmenkovom kruhu.

Každého tímu sa podarilo aspoň načítať hľadaný text a kruhový text. Súťažiacim, ktorí získali menší počet bodov, chýbalo napríklad vyriešenie úlohy aj opačným smerom. Niektorý namiesto postupného prechodu všetkých pozícií na kruhu použili funkciu na náhodné generovanie indexu, čo neviedlo v niektorých prípadoch k správnemu výsledku.