PALMA junior
Úloha o dvojsmerovke

Autorské riešenie
[stiahni py]                                       

• Počet riešiteľov: 7/8 = 87,50 %

• Úspešnosť riešenia: 6,21 / 7 = 88,78 %

Ak by sa v dvojsmerovke neprekrývali slová, tak v našom riešení by sme mohli použiť metódu replace pre každé zadané slovo a jeho prevrátenú podobu nasledovne:

def lusti_dvojsmerovku(slova, dvojsmerovka):
    for slovo in slova:
        dvojsmerovka = dvojsmerovka.replace(slovo,'')
        dvojsmerovka = dvojsmerovka.replace(slovo[::-1],'')
    return dvojsmerovka

print(lusti_dvojsmerovku(['jar', 'osa', 'lov'], 'LjarEosaTvolO'))
# výsledok LETO

Vo všeobecnosti sa však v dvojsmerovke môžu prekrývať slová ako je to uvedené na obrázku, kde sa prekrýva slovo "osa" a prevrátené slovo "jas".

V tejto situácii by vyššie uvedené riešenie v jazyku Python nedávalo správne výsledky.

V našom riešení použijeme pomocný zoznam indexy, ktorý bude mať rovnaký počet prvkov ako dĺžka dvojsmerovky. Na začiatku hodnoty zoznamu nastavíme na True.

Potom budeme postupne pre každé zadané slovo zo zoznamu zadaných slov vyškrtávať v zozname indexy jeho pozície v dvojsmerovke, t. j. nastavíme tieto hodnoty na False.

Napokon po vyškrtaní všetkých výskytov slov v dvojsmerovke zozbierame z dvojsmerovky nevyškrtané znaky (ktoré majú na rovnakých pozíciách hodnotu True v zozname indexy).

Pri programovej realizácii pre každé zadané slovo najprv zistíme súčet jeho výskytov a výskytov jeho prevrátenej podoby (použijeme metódu count). Ak sa slovo ani jeho prevrátená podoba nevyskytujú v dvojsmerovke alebo sa vyskytujú viac ako jedenkrát, program vygeneruje výnimku  - chybovú správu o nekorektne zadaných vstupoch. V ďalšom postupe vieme, že sú vstupy korektné, t. j. že sa slovo alebo jeho obrátená podoba vyskytujú práve raz v dvojsmerovke.

Pri hľadaní výskytu slov v dvojsmerovke použijeme metódu find, pričom rozlíšime obidve situácie - pre výskyt slova a výskyt jeho prevrátenej podoby, pre ktoré na zistených pozíciách v zozname indexy nastavíme hodnoty False.

Napokon pomocou generátorovej notácie zozbierame do nového zoznamu vysledok len tie hodnoty pomocného zoznamu indexy, ktoré majú hodnotu True. Na konci funkcie ešte premeníme zoznam na reťazec pomocou metódy join.

V hlavnom programe ošetríme chybovú situáciu pomocou konštrukcie try-except.

def lusti_dvojsmerovku(slova, dvojsmerovka):
    ''' Funkcia vráti výsledok vyškrtania slov z dvojsmerovky '''
    # vytvoríme pomocný zoznam indexy s rovnakým počtom prvkov ako dĺžka dvojsmerovky
    indexy = [True] * len(dvojsmerovka)
    for slovo in slova:
        # ak sa zadané slovo a jeho prevrátená podoba nevyskytujú v dvojsmerovke 
        #alebo vyskytujú 2-krát a viac, vygeneruje sa chyba
        if dvojsmerovka.count(slovo) + dvojsmerovka.count(slovo[::-1]) != 1:
            raise ValueError('Nekorektne zadané vstupy')
        index = dvojsmerovka.find(slovo)
        if index >= 0: # zistíme pozíciu slova v dvojsmerovke a vyškrtáme v pomocnom 
                       # zozname jeho pozície (nastavíme hodnoty na True)
            indexy[index:index + len(slovo)] = [False] * len(slovo)
        else: # zistíme pozíciu prevráteného slova v dvojsmerovke a vyškrtáme 
              # v pomocnom zozname jeho pozície (nastavíme hodnoty na True)
            index = dvojsmerovka.find(slovo[::-1])
            indexy[index:index + len(slovo)] = [False] * len(slovo)
    # vytvoríme zoznam nevyškrtaných prvkov dvojsmerovky (ich hodnota je True) 
    # a premeníme ho na reťazec
    vysledok = [dvojsmerovka[i] for i in range(len(dvojsmerovka)) if indexy[i]]
    vysledok = ''.join(vysledok)
    return vysledok

try:
    print(lusti_dvojsmerovku(['jar', 'osa', 'jas', 'lov'], 'LjarEosajTvolO'))
    # výsledok LETO

    # print(lusti_dvojsmerovku(['jar', 'osa', 'jas', 'lov', 'zima'], 'LjarEosajTvolO'))
    # výsledok 'Nekorektne zadane vstupy'

    # print(lusti_dvojsmerovku(['jar', 'osa', 'jas', 'lov'], 'LjarEosajTvolOraj')) 
    # výsledok 'Nekorektne zadane vstupy'
except ValueError as chyba:
    print(chyba)

Táto úloha je zameraná na použitie dekompozície ako stratégie riešenia problému, na precvičenie príkazov cyklu, vetvenia, funkcie s parametrami a výstupom, práce s údajovými typmi reťazec (metóda find, count, join) a zoznam (výrezy), zachytávanie a generovanie výnimiek.

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

Do riešenia tejto úlohy sa zapojilo 7 tímov z  kategórie GURU.  Plný počet bodov dosiahli 3 tímy (Šedá eminencia dodekedrónov, seesharp a srobarkaMJ, ktorým gratulujeme. Veľmi oceňujeme riešenie tímu Šedá eminencia dodekedrónov, kde autor okrem bonusového grafického výstupu dôsledne okomentoval zdrojový kód svojho programu.

Len dva tímy použili na vyškrtávanie slov pomocné reťazce, ostatných 5 tímov použili pomocné zoznamy, len v 2 tímy použili v zoznamoch logické hodnoty.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému, tvorby menej efektívneho riešenia či z pretrvávajúcich programátorských zlozvykov:

• neošetrenie chybových situácii (slovo sa nevyskytuje v osmesmerovke, resp. sa dá vyškrtnúť rôznymi spôsobmi),

• nezohľadnenie prípadu rôznych veľkosti znakov (zbytočné a nevhodné použitie metódy upper),

•  použitie cyklov, kde sa dali použiť výrezy,

• zbytočné použitie globálnej premennej vo funkcii,

• použitie zloženej podmienky, kde sa dala použiť jednoduchá podmienka,

• použitie hodnoty None namiesto [] na otestovanie prázdneho zoznamu,

• menej prehľadný programový kód s vnorenými cyklami a vetveniami  vďaka neznalosti niektorých metód (find, count).