PALMA junior
Úloha o palindrómoch

Autorské riešenie
[stiahni palindromy.py]  

• Počet riešiteľov: 6 / 10 = 60 %

• Úspešnosť riešenia: 3,4 / 8 = 42,5 %                 

Úloha o palindrómoch je zameraná na prácu s reťazcami, vyhľadávanie vzorov a optimalizáciu. Zo zadania vieme, že na vstup dostaneme reťazec pozostávajúci z medzier a malých písmen anglickej abecedy, teda bez diakritiky. Úlohou je v reťazci spočítať všetky palindromické podreťazce. Palindromický podreťazec je taký úsek reťazca, ktorý sa číta rovnako zľava doprava aj sprava doľava. Z definície je teda aj každý jednopísmenkový podreťazec triviálny palindróm. Úlohu je možné riešiť viacerými spôsobmi.

Riešenie hrubou silou

Riešenie hrubou silou skúma všetky možnosti. To znamená, že program prejde každý možný podreťazec vstupného reťazca a kontroluje, či je palindróm. Takéto riešenie pozostáva z 3 vnorených cyklov:

• vonkajší cyklus - pre každý možný začiatok podreťazca
• vnútorný cyklus - pre každý možný koniec podreťazca
• skrytý cyklus - pre porovnanie podreťazca s jeho reverznou verziou

Kvôli vnoreným cyklom rastie s dĺžkou reťazca zložitosť tohto algoritmu veľmi rýchlo. Ak by sme zväčšili dĺžku reťazca 10-krát, počet operácií by vzrástol až 1000-násobne. Pre dlhšie vstupy by teda program bežal pridlho.

Riešenie rozširovaním okolu stredu

Toto riešenie vychádza z pozorovania, že každý palindróm má svoj stred. Pri nepárnej dĺžke palindrómu je stred jeden znak (napr. aba) a pri párnej dĺžke sú stredom dva znaky (napr. abba). Teda, každý znak reťazca na vstupe a každú dvojicu susediacich znakov môžeme považovať za potenciálny stred.

Následne skúšame, ako ďaleko vieme aktuálny podreťazec symetricky rozšíriť doľava a doprava tak, že sa nové znaky zhodujú. Od každého stredu rozširujeme maximálne po okraje reťazca. Každé úspešné rozšírenie zvýši počet palindrómov o 1. Nezabúdame započítať aj triviálne palidrómy pozostávajúce z jedného znaku.

Riešenie môžeme rozdeliť do dvoch funkcií. Hlavná funkcia pocet_palindromov dostane na vstup reťazec, z ktorého odstráni medzery, a tým ho pripraví na analýzu. Následne prechádza celým reťazcom a každý znak skúsi použiť ako stred palindrómu nepárnej dĺžky, ale spolu s nasledujúcim znakom aj ako stred palindrómu párnej dĺžky.

Funkcia spocitaj spočíta počet palindrómov, ktorý dosiahneme pre aktuálny znak (alebo dvojicu znakov), ak ho uvažujeme ako triviálny palindróm, a ak ho skúsime rozšíriť.

def pocet_palindromov(retazec):
    retazec = retazec.replace(" ", "")
    pocet = 0
    for stred_idx in range(len(retazec)):
        pocet += spocitaj(retazec, stred_idx, stred_idx)
        pocet += spocitaj(retazec, stred_idx, stred_idx + 1)
    return pocet

def spocitaj(retazec, lavy_idx, pravy_idx):
    pocet = 0
    while lavy_idx >= 0 and pravy_idx < len(retazec) and 
          retazec[lavy_idx] == retazec[pravy_idx]:
        pocet += 1
        lavy_idx -= 1
        pravy_idx += 1
    return pocet

Môžeme si všimnúť, že oproti riešeniu hrubou silou má riešenie rozširovaním okolo stredu o jeden vnorený cyklus menej. Prakticky, ak by sme zväčšili dĺžku reťazca 10-krát, počet operácií by vzrástol len 100-násobne. Preto je tento prístup výrazne efektívnejší a rýchlejší.

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

Efektívne riešenie rozširovaním okolo stredu odovzdal len jeden tím. Niekoľko tímov odovzdalo správne riešenie hrubou silou, ktoré však nespĺňa požiadavku na rýchlosť zo zadania, a preto týmto riešeniam nebol udelený plný počet bodov. Jeden tím zabudol na odstránenie medzier zo vstupného reťazca, takéto riešenie nefunguje správne pre palindrómy s medzerami, napr. "v elipse spi lev".