PALMA junior
Úloha o motivácii

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 47 / 66 = 71 %

• Úspešnosť riešenia: 3,85 / 6 = 64 %

Riešenie tejto úlohy nie je ťažké. Máme dva reťazce (pomenujme ich slogan a znaky) a našou úlohou je rozhodnúť, či reťazec slogan je možné vytvoriť len využitím znakov reťazca znaky.

Napr.

Reťazec "programovanie" je možné vytvoriť zo znakov reťazca "prgrmvnoaoaie".

Reťazec "programovanie" už ale nie je možné vytvoriť zo znakov reťazca "prgrmvnoaaie", pretože nám chýba jeden znak "o".

Pri hľadaní riešenia si stačí uvedomiť postup, ktorý by sme zvolili, ak by sme úlohu riešili bez počítača. Aj pri takomto prístupe je možné použiť viacero postupov. Pozrime sa na ne postupne.

Riešenie 1:

Postupne budeme prechádzať znakmi sloganu, ktorý chceme vyskladať. Pri každom nie bielom znaku sa spýtame, koľko takýchto znakov potrebujeme a koľko ich máme k dispozícii.

Ak potrebujeme viac takýchto znakov než ako ich máme k dispozícii, text sa nedá vyskladať a ďalej nemá zmysel pokračovať.

Ak máme takýchto znakov dostatok, pokračujeme ďalším znakom sloganu.

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

# Python
def da_sa_vyskladat1(slogan, znaky):
    for znak in slogan:
        if not znak.isspace():
            if slogan.count(znak) > znaky.count(znak):
                return False
    return True

Riešenie je správne, ale nie je veľmi efektívne. Ak by text sloganu obsahoval veľa rovnakých znakov, budeme ich počty zisťovať opakovane. A to nielen v samotnom slogane ale aj v texte znakov.

Riešenie 2:

Skúsme použiť iný prístup. Prechádzajme postupne znakmi sloganu. Pre každý nie biely znak sloganu zistime, či sa nachádza medzi dostupnými znakmi. Ak áno, odstráňme ho z dostupných znakov. Ak nie, slogan sa vyskladať nedá.

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

# Python
def da_sa_vyskladat2(slogan, znaky):
    for znak in slogan:
        if not znak.isspace():
            if znak in znaky:
                znaky = znaky.replace(znak, '', 1)
            else:
                return False
    return True

Toto riešenie je už lepšie, lebo spočítavanie rovnakých znakov už nerobíme opakovane. Znaky zo sloganu nie je potrebné odstraňovať. Každý znak spracovávame len raz.

Riešenie 3:

Ak by sa v slogane nachádzali rovnaké znaky, budeme opakovane zisťovať ich prítomnosť medzi dostupnými znakmi a opakovane ich budeme z dostupných znakov odstraňovať. Navrhnime ešte lepšie riešenie, v ktorom to pre každý unikátny znak sloganu spravíme len raz. 

# Python
def da_sa_vyskladat3(slogan, znaky):
    while slogan != '':
        znak = slogan[0]
        if znak.isspace():
            slogan = slogan.replace(znak, '')
        elif slogan.count(znak) <= znaky.count(znak):
            slogan = slogan.replace(znak, '')
            znaky = znaky.replace(znak, '')
        else:
            return False
    return True

V tomto riešení opäť prechádzame znakmi sloganu.

Ak narazíme na biely znak, všetky jeho výskyty v slogane odstránime.

Inak sa pýtame, koľko takýchto znakov potrebujeme a koľko ich máme k dispozícii.

Ak máme takýchto znakov dostatok, vymažeme všetky výskyty znaku zo sloganu aj z dostupných znakov. Tým zabezpečíme, že k tomuto znaku sa už nikdy nevrátime a reťazec dostupných znakov postupne skracujeme, takže sa s ním pracuje rýchlejšie.

Ak potrebujeme viac takýchto znakov než ako ich máme k dispozícii, text sa nedá vyskladať a ďalej nemá zmysel pokračovať. 

Zatiaľ sme naše vylepšenia zdôvodňovali len intuitívne na základe toho, čo a ako často sa pri realizácii vykonáva. Trochu lepšiu predstavu o vylepšeniach nám poskytne ich vzájomné časové porovnanie.

Zrealizovali sme jednoduchý test, v ktorom sme opakovane jednotlivé funkcie spúšťali pre rôzne dlhé slogany (50 .. 10000 znakov), rôzne dlhé texty znakov (dĺžka sloganu +- 30). V texte sme použili znaky, ktoré by sme v sloganoch aj očakávali (znaky abecedy, číslice, interpunkčné znamienka a pod.). Každú z funkcií sme spustili 5x pre 1000 rôznych sloganov a textov znakov. Relatívny čas behu jednotlivých funkcií je nasledovný:

• da_sa_vyskladat1() - 56 časových jednotiek,

• da_sa_vyskladat2() - 5 časových jednotiek,

• da_sa_vyskladat3() - 1 časová jednotka.

Ukázali sme, že našimi postupnými úvahami sme riešenie skutočne vylepšovali. 

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

Takmer všetky riešenia implementovali úvahu, že je potrebné nejakým spôsobom prechádzať oboma reťazcami. Či už priamo (napr. cyklom) alebo nepriamo (napr. funkciou count). Problém vám robilo rozpoznanie situácie, keď v krabici boli znaky potrebné na vyskladanie sloganu, ale nebol ich dostatok. Ďalším nedostatkom riešení bol neefektívny návrh algoritmu.

V niektorých riešeniach sa objavili pokusy o použitie množín alebo slovníkov. Použiť slovník, kde pre každý znak máme uložený počet jeho výskytov, je celkom rozumný nápad. Pri množinách vieme uchovať informáciu o tom, aké znaky potrebujeme, ale strácame informáciu o ich potrebnom počte. Z toho pohľadu je použitie množín v tomto prípade problematické.