PALMA junior
Úloha o krásnych a nádherných slovách

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 26 / 28 = 93 %

• Úspešnosť riešenia: 4/6 = 66.6%

Najprv sa zamyslime, čo sú to nádherné a krásne slová. Zjavne, nádherné slová sú polindrómy - slová, ktoré sa čítajú rovnako spredu aj zozadu. V pythone môžeme jednoducho overiť, či je slovo palindrómom pomocou rezu reťazcov. Tretí argument rezu je krok, ktorý ak je záporný, python číta reťazec odzadu. Následovný kód teda vráti "nadherne" práve vtedy, keď sa vstupný reťazec rovná samému sebe prečítanému odzadu.

def ohodnot_slovo(slovo):
    if slovo == slovo[::-1]:
        return "nadherne"
    return "ani jedno"

Ak sa necítime komfortne pracovať s rezmi, alebo jednoducho chceme mechanickejší a teda zjavnejší spôsob ako overiť, či je vstupné slovo nádherné, môžeme vo for-cykle overiť, či je prvé písmeno rôzne do posledného, druhé od predposledného a tak ďalej... Akonáhle nájdeme jednu rôznu dvojcu, slovo nie je nádherné. Ak nenájdeme žiadnu, slovo nádherným je. Všimnime si, že pri slovách s nepárnym počtom písmen nás stredné písmeno nezaujíma, keďže pri čítaní slova od zadu je toto písmeno stále určite v strede. Tento postup je aplikovateľný aj pre iné programovacie jazyky a v Pythone by mohol vyzerať nasledovne.

def ohodnot_slovo(slovo):
    dlzka_slova = len(slovo)
    for znak in range(dlzka_slova // 2):
        if slovo[znak] != slovo[dlzka_slova - znak - 1]:
            return "ani jedno"
    return "nadherne"

Po zvyšok riešenia budeme používať prvý spôsob identifikácie nádherného slova. Teraz sa pozrime na náročnejšiu časť úlohy. Všimnime si, že korytnačky považovali za krásne slová ako aktivita, zoo, klik alebo osol. Tieto slová majú vlastnosť, že ak do nich pridáme alebo odoberieme písmeno, vzniknú z nich nádherné slová. Napríklad ativita / aktivitka, oo / zooz, kik / klilk alebo oso / losol.

Uvedomme si, že akonáhle platí, že do slova vieme pridať písmeno aby vzniklo nádherné slovo, platí, aj že z neho vieme jedno odobrať. Krásne slová sa totiž skladajú z niekoľkých párov zrkadlovo rovnakých písmen a jedného, ktorý pár nemá. Tomuto písmeno môžeme buď pár vyrobiť pridaním písmena na správne miesto, alebo odobraním tohto problémového písmena.

Prvou našou myšlienkou by mohlo byť skúsiť na všetky miesta v slove pridať písmeno z tohto slova. Ak po hociktorom z týchto pridaní sa slovo stane nádherným, vieme, že je krásne. Aby sme neskúšali niektoré písmena pridať viackrát, najprv spravíme z písmen v slove množinu. Takýto kód by mohol vyzerať nasledovne.

#Python
def ohodnot_slovo(slovo):
    if slovo == slovo[::-1]:
        return "nadherne"
    pismena_v_slove = set(slovo)
    dlzka_slova = len(slovo)
    for pismeno in pismena_v_slove:
        for pozicia in range(dlzka_slova):
            nove_slovo = slovo[:pozicia] + pismeno + slovo[pozicia:]
            if nove_slovo == nove_slovo[::-1]:
                return "krasne"
    return "ani jedno"

Toto riešenie samozrejme funguje, no môžeme si všimnúť, že sa v ňom nachádza for-cyklus vnorený do druhého for-cyklu, v ktorom ešte aj je rezanie reťazca, čo je samo o sebe operácia lineárnej náročnosti, keďže program musí prejsť cez všetky písmená reťazca. Tento program je teda až kubickej časovej náročnosti. Určite to teda zvládneme spraviť lepšie.

Stačí nám nájsť spomínané problémové písmeno, ktoré nemá v slove pár a odstrániť ho. Ak po jeho odstránení dostaneme nádherné slovo, vstupné slovo je krásne. Ak sa tak nestane, v slove bolo viacej písmen bez páru a teda nie je krásne. To môžeme robiť podobne, ako v druhom riešení pre identifikáciu nádherných slov, teda postupne porovnávať zrkadlové dvojice písmen.

V momente, kedy narazíme na dvojicu ktorá sa nerovná, ešte nevieme, ktoré z týchto dvoch písmen je hľadaným problémovým. Skúsime teda obe odstrániť a overiť, či výsledné slovo je nádherné. Znova platí, že nám nezáleží na strednom písmene, teda dĺžku slova môžeme celočíselne deliť dvomi. Kód by mohol vyzerať nasledovne.

#Python
def ohodnot_slovo(slovo):
    if slovo == slovo[::-1]:
        return "nadherne"
    dlzka_slova = len(slovo)
    for pozicia in range(dlzka_slova // 2):
        if slovo[pozicia] != slovo[dlzka_slova - pozicia - 1]:
            nove_slovo_1 = slovo[:pozicia] + slovo[pozicia + 1:]
            nove_slovo_2 = slovo[:dlzka_slova - pozicia - 1] + slovo[dlzka_slova - pozicia:]
            if nove_slovo_1 == nove_slovo_1[::-1]:
                return "krasne"
            elif nove_slovo_2 == nove_slovo_2[::-1]:
                return "krasne" 
            else:
                return "ani jedno"

Toto riešenie obsahuje iba jeden for-cyklus, v ktorom sa ešte v jednom konkrétnom prípade spustia nanajvýš dva procesy s lineárnou časovou náročnosťou. Riešenie je teda celé lineárnej časovej náročnosti, čiže je omnoho efektívnejšie ako predošlé. Tým sme korytnačkám pomohli pre akékoľvek slovo vyhodnotiť, či je nádherné, krásne, alebo ani jedno.

Vaše najčastejšie chyby

Mnohí ste za dostatočnú podmienku pre to, aby slovo bolo krásne považovali, že existuje nanajvýš jedna dvojica písmen, ktorá sa nezhoduje. To je správna myšlienka, no nie je dotiahnutá do konca. Prítomnosť problémového písmena totižto rozhodí pozície dvojíc, ktoré by inak boli po jeho odstránení zhodné.

Napríklad slovo aktivita je krásne, no ak iba porovnávame znaky z oboch strán, rýchlo narátame nezhodné dvojice k != t, t != i a i != v a nesprávne vyhodnotíme, že nie je krásne. Tento postup prináša aj opačný problém, napríklad slovo zoom krásne nie je, no pri počítaní nezhodných dvojíc natrafíme iba na jednu a teda o ňom prehlásime, že je krásne.

Jedinou ďalšou častou chybou bolo vracanie hodnôt v nesprávnom formáte, prípadne vypisovanie výsledných hodnôt namiesto ich vracania. K tomu nemáme čo viac odporučiť, než si nabudúce prečítať zadanie poriadnejšie, aby ste vedeli, čo sa očakáva, že funkcia vracia.