PALMA junior
Úloha o dejepise

Autorské riešenie
[stiahni py]

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

• Úspešnosť riešenia: 5,3 / 7 = 76 %

Pri riešení tejto úlohy je potrebné zamiešať dvojice znakov v zadanom slove za súčasného splnenia týchto podmienok:

• dvojice znakov sú zamiešané náhodne,

• nové slovo musí byť rôzne od pôvodného slova,

• nové slová s nepárnym počtom znakov majú posledný znak nezmenený.

Nové slovo podľa týchto pravidiel nie je možné vytvoriť, ak platí aspoň jedna z nasledujúcich možností:

• dĺžka slova je menšia ako štyri (lebo máme iba jednu dvojicu znakov a tú nevieme zamiešať tak, aby vzniklo iné slovo),

• ak všetky dvojice znakov v slove sú rovnaké, napr. "ANANAN" (lebo každým zamiešaním vznikne rovnaké slovo),

• ak aspoň dve dvojice znakov v slove sú rovnaké a náhodným zamiešaním sa vymenia iba tieto rovnaké dvojice, napr. "PANANAS" (lebo výmenou rovnakých dvojíc vznikne rovnaké slovo),

• ak žiadna dvojica znakov v slove nie je rovnaká a náhodným zamiešaním sa nevymení žiadna dvojica (lebo vznikne rovnaké slovo),

Aby sme dosiahli správne riešenie, je potrebné vyriešiť všetky tieto štyri prípady.

Ak je dĺžka slova menšia ako štyri, postačí vypísať oznam, že dané slovo sa nedá vytvoriť. V opačnom prípade otestujeme, či slovo má nepárny počet znakov. Ak áno, posledný znak si odložíme a ďalej pracujeme len z párnym počtom znakov. Z takto upraveného vstupného slova si vieme vytvoriť zoznam všetkých dvojíc slova a náhodne určiť pozíciu, na ktorej nastane zmena. Následne vytvoríme zoznam použiteľných dvojíc znakov pre dané miesto v reťazci. Ak je vytvorený zoznam použiteľných dvojíc prázdny, dané slovo nie je možné vytvoriť, a teda vypíšeme oznam o neexistencii riešenia. Ak vytvorený zoznam použiteľných dvojíc nie je prázdny, náhodne vyberieme jednu z týchto dvojíc (víťaza) a odstránime ju zo zoznamu všetkých dvojíc slova. Zvyšné dvojice slova zamiešame a vytvoríme z nich nové slovo. Následne vložíme víťaza na určené miesto a pripojíme posledný znak, ak malo slovo nepárny počet znakov.

Schéma tvorby nového slova je znázornená na nasledujúcom obrázku.

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

# Python
import random
def generuj_slovo(slovo):
    #ak je dlzka slova menej ako 4, nove slovo sa neda vytvorit
    if len(slovo) < 4:
        raise ValueError('Nove slovo sa neda vytvorit')

    #ak ma slovo neparnu dlzku, posledny znak si odlozime a slovo upravime
    if len(slovo) % 2 == 0:
        posledny_znak = ''
    else:
        posledny_znak = slovo[-1]
        slovo = slovo[:-1]

    #vytvorime zoznam vsetkych dvojic slova
    dvojice = [slovo[index:index+2] for index in range(0, len(slovo), 2)]

    #nahodne urcime poziciu, kde bude zmena
    index_zmeny = random.choice(range(0,len(slovo),2))

    #vyberieme tie dvojice, ktore na mieste zmeny mozeme pouzit
    ine_dvojice = [dvojica
                   for dvojica in dvojice
                   if dvojica != slovo[index_zmeny:index_zmeny+2]]

    #ak taka dvojica neexistuje, nove slovo sa neda vytvorit
    if len(ine_dvojice) == 0:
        raise ValueError('Nove slovo sa neda vytvorit')

    #nahodne vyberieme jednu z dvojic na poziciu, kde bude zmena
    dvojica = random.choice(ine_dvojice)

    #odstranime ju zo zoznamu vsetkych dvojic, aby sme ju nepouzili opakovane
    dvojice.remove(dvojica)

    #zamiesame zoznam vsetkych zvysnych dvojic
    random.shuffle(dvojice)

    #vsetky dvojice spojime
    nove_slovo = ''.join(dvojice)

    #vlozime na urcenu poziciu dvojicu, ktora zaruci zmenu a posledny znak
    nove_slovo = nove_slovo[:index_zmeny] + \
                 dvojica + \
                 nove_slovo[index_zmeny:] + \
                 posledny_znak

    return nove_slovo

print(generuj_slovo('napanas'))

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

Úlohu riešilo 10 tímov. Tímy pracovali s reťazcami rôznymi spôsobmi. Niektorí vytvárali zoznam dvojíc, iné to skúšali iba pomocou indexov reťazca. Najčastejšou chybou bolo neošetrenie tretej a štvrtej podmienky, teda takých slov, u ktorých existuje riešenie, ale po náhodnom premiešaní môžu ostať nezmenené. Dva tímy neošetrili prípad, ak slovo má všetky dvojice znakov rovnaké.