PALMA junior
Úloha o guľôčkovom hlavolame

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 18 / 19 = 95 %

• Úspešnosť riešenia: 4,83 / 7 = 69 %

Našou úlohou je simulovať otáčanie kružníc z guľôčok. Pri otočení jednou z kružníc sa udejú dve veci:

1. Časť guľôčok otáčanej kružnice sa presunie zo začiatku na jej koniec, resp. naopak podľa toho, ktorým smerom otáčame (ale to je v podstate to isté). Začiatkom v tomto prípade myslíme miesto horného prieniku obidvoch kružníc.

2. Dve guľôčky v druhej kružnici sa zmenia.

Vyriešme postupne obidva problémy. Pomôžme si náčrtom, v ktorom si znázorníme jednotlivé pozície guľôčok v kružniciach tak, ako ich reprezentujeme v zoznamoch.  

Pozrime sa najskôr na to, čo sa stane, ak niektorú z kružníc pootočíme o kladný počet pozícií guľôčok, napr. o 5. Kružnica sa pootočí v protismere hodinových ručičiek. Guľôčky na pozíciách 0 .. 4 sa dostanú na koniec a guľôčka, ktorá bola na pozícii 5 sa dostane na pozíciu 0. Vo všeobecnosti, ak uvažujeme posun o hodnotu n, môžeme zmenu zoznamu pozícií pre toto otočenie vyjadriť nasledovne:

kruznica = kruznica[n:] + kruznica[:n]

Keďže Python pozná aj záporné indexy, ak by číslo n bolo záporné, výraz pre zmenu zoznamu bude rovnaký.

Vyriešime teraz, ako sa zmení zoznam jednej kružnice, ak otočíme druhou. Tu si stačí uvedomiť, že hodnoty v kružniciach na pozíciách 0 a 0 a súčasne hodnoty v kružniciach na pozíciách 6 a 18 (resp. -6) musia byť rovnaké. Po otočení jednou kružnicou, stačí skopírovať hodnoty na zodpovedajúcich indexov do druhej kružnice. Výsledný kód môže vyzerať nasledovne:

# Python
def simuluj_tahy(kruznica1, kruznica2, tahy):
    kruznica1 = kruznica1.copy()
    kruznica2 = kruznica2.copy()

    for idx in range(len(tahy)):
        tah = tahy[idx] % len(kruznica1)
        if idx % 2 == 0:
            kruznica1 = kruznica1[tah:] + kruznica1[:tah]
            kruznica2[0], kruznica2[-6] = kruznica1[0], kruznica1[6]
        else:
            kruznica2 = kruznica2[tah:] + kruznica2[:tah]
            kruznica1[0], kruznica1[6] = kruznica2[0], kruznica2[-6]
    return kruznica1, kruznica2

Všimnime si ešte niekoľko detailov:

• Aby sme nezmenili zoznamy kružníc v hlavnom programe, vo funkcii pracujeme s kópiami.

• V cykle for postupne prechádzame jednotlivými ťahmi. Vieme, že ťah na párnej pozícii platí pre prvú kružnici a ťah na nepárnej pozícii pre druhú kružnicu.

• Každé celé otočenie kružnice nezmení pozície guľôčok. Zaujímajú nás preto len tie pohyby, ktoré sú nad celé otočenie. Preto každý pohyb nahradíme zvyškom po delení celkovým počtom guľôčok.

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

S touto úlohou ste si poradili celkom dobre. Niektorým robilo problém správne upraviť zoznamy guľôčok po ich otočení. Niektorí ste predpokladali, párny počet ťahov prípadne ste neuvažovali ťahy o viac ako jedno otočenie kružnice.

Zaujímavé riešenie použili tímy Bobaľky SK a Master. Využili modul collections a triedu deque, vďaka čomu si uľahčili rotovanie guľôčok pri otáčaní kružníc.