PALMA junior
Úloha o ozdobných stromčekoch

Autorské riešenie
[stiahni py] 

• Počet riešiteľov: 11/17 = 65 %

• Úspešnosť riešenia: 3,39 / 5 = 67,73 %

Pri tejto doskovej hre si môžeme hracie políčka očíslovať celými číslami od 0 do 99. Prvý robot je na pozícii 0 a druhý robot na pozícii 99.

Pri pohybe niektorého robota nahor sa jeho pozícia zvýši o 10, nadol o -10, vpravo o 1 a vľavo o -1.

Funkcia tah, ktorá pre zadaný príkaz a zadanú pozíciu robota vráti jeho novú pozíciu, môže vyzerať nasledovne:

def tah(prikaz, pozicia):
    ''' Vráti novú pozíciu robota podľa zadaného príkazu a zadanej pozície '''
    if prikaz == 'H':
        pozicia = pozicia + 10
    elif prikaz == 'D':
        pozicia = pozicia - 10
    elif prikaz == 'L':
        pozicia = pozicia - 1
    elif prikaz == 'P':
        pozicia = pozicia + 1
    return pozicia

Vzdialenosť medzi dvomi pozíciami vypočítame ako súčet dĺžok vodorovného a zvislého úseku medzi nimi. Funkcia vzdialenost môže vyzerať nasledovne:

def vzdialenost(pozicia_1, pozicia_2):
    ''' Vráti pravoúhlu vzdialenosť dvoch bodov '''
    vysledok = abs(pozicia_1 // 10 - pozicia_2 // 10) + \
               abs(pozicia_1 % 10 - pozicia_2 % 10)
    return vysledok			  

Po definovaní predchádzajúcich dvoch pomocných funkcii môžeme definovať hlavnú funkciu vyhodnot_suboj. V tejto funkcii postupne s každým príkazom pre jedného a druhého robota meníme ich pozície a testujeme, či sa ich pozície nerovnajú, t.j. či daný robot nevykopol toho druhého. Ak sa tak stalo, vrátime poradové číslo víťazného robota (1 alebo 2). Ak sa tak nestalo, spočítame vzdialenosť oboch robotov od ich cieľových pozícií. Ak sú rovnako vzdialení, vrátime výsledok 0 (remízu), alebo poradové číslo víťazného robota, ktorý je bližšie k svojej cieľovej pozícii (1 alebo 2). 

def vyhodnot_suboj(prikazy1, prikazy2):
    ''' Vráti výsledok súboja zadaného reťazcami príkazov pre oboch robotov.
    Ak vyhrá 1. hráč, výsledok je 1. Ak vyhrá 2. hráč, výsledok je 2.
    V prípade remízy výsledok je 0. '''
    pozicia_r1 = 0
    pozicia_r2 = 99

    for poradie in range(len(prikazy1)):
        prikaz1 = prikazy1[poradie]
        prikaz2 = prikazy2[poradie]
        pozicia_r1 = tah(prikaz1, pozicia_r1)
        if pozicia_r1 == pozicia_r2:
            return 1
        pozicia_r2 = tah(prikaz2, pozicia_r2)
        if pozicia_r1 == pozicia_r2:
            return 2

    vzdialenost1 = vzdialenost(pozicia_r1, 99)
    vzdialenost2 = vzdialenost(pozicia_r2, 0)
    if vzdialenost1 == vzdialenost2:
        return 0
    elif vzdialenost1 < vzdialenost2:
        return 1
    else:
        return 2


def tah(prikaz, pozicia):
    ''' Vráti novú pozíciu robota podľa zadaného príkazu a zadanej pozície '''
    if prikaz == 'H':
        pozicia = pozicia + 10
    elif prikaz == 'D':
        pozicia = pozicia - 10
    elif prikaz == 'L':
        pozicia = pozicia - 1
    elif prikaz == 'P':
        pozicia = pozicia + 1
    return pozicia


def vzdialenost(pozicia_1, pozicia_2):
    ''' Vráti pravoúhlu vzdialenosť dvoch bodov '''
    vysledok = abs(pozicia_1 // 10 - pozicia_2 // 10) + \
               abs(pozicia_1 % 10 - pozicia_2 % 10)
    return vysledok


print(vyhodnot_suboj('HHHHHHHH', 'LLLLLLLL'))
print(vyhodnot_suboj('HHHHHHHH', 'LLLLLLPL'))
print(vyhodnot_suboj('HPHPHPHPHPHPHPHPHP', 'LDLDLDLDLDLDLDLDLD'))

V zadaní úlohy sme predpokladali rovnako dlhé reťazce s príkazmi. Rovnako pri opravovaní súťažných riešení aj vo vyššie uvedenom autorskom riešení sme predpokladali korektne zadané vstupy v reťazcoch obsahujúcich len 4 znaky{H, D, L, P} a tiež, že počas výpočtu nevybehne žiaden z robotov mimo hraciu plochu.

Ak by sme chceli ošetriť korektnosť vstupov, tak by sme vo funkcii vyhodnot_suboj na jej začiatok doplnili nasledovné dva príkazy vyhadzujúce výnimky:

if prikazy1.count('H') + \
   prikazy1.count('D') + \
   prikazy1.count('L') + \
   prikazy1.count('P') != len(prikazy1):
    raise ValueError('Chybný 1. reťazec. Obsahuje znaky rôzne od {H, D, L, P}.')
if prikazy2.count('H') + \
   prikazy2.count('D') + \
   prikazy2.count('L') + \
   prikazy2.count('P') != len(prikazy2):
    raise ValueError('Chybný 2. reťazec. Obsahuje znaky rôzne od {H, D, L, P}.')

Ak by sme chceli ošetriť situácie, že žiaden z robotov nevybehne z hracej plochy, tak by sme vo funkcii tah upravili jej programové kódy tak, aby vyhadzovali výnimky:

def tah(prikaz, pozicia):
    ''' Vráti novú pozíciu robota podľa zadaného príkazu a zadanej pozície '''
    if prikaz == 'H':
        if pozicia >= 90:
            raise ValueError('Chybná pozícia mimo hrací plán')
        pozicia = pozicia + 10
    elif prikaz == 'D':
        if pozicia <= 9:
            raise ValueError('Chybná pozícia mimo hrací plán')
        pozicia = pozicia - 10
    elif prikaz == 'L':
        if pozicia % 10 == 0:
            raise ValueError('Chybná pozícia mimo hrací plán')
        pozicia = pozicia - 1
    elif prikaz == 'P':
        if pozicia % 10 == 9:
            raise ValueError('Chybná pozícia mimo hrací plán')
        pozicia = pozicia + 1
    return pozicia

Kompletné riešenie úlohy s ošetrením vstupov a priebežných pozícii počas hry je uložené v súbore 2_riesenie2.py.

Táto úloha je zameraná na: 

• použitie viacerých stratégii riešenia problémov (dekompozície problému na podproblémy, abstrakcie pri zakódovaní dvojice súradníc do jedného celého čísla),

• precvičenie príkazov opakovania, vetvenia, volania funkcií s parametrami a návratovou hodnotou, práce s dátovým typom reťazec (str).

• použitie matematických výpočtov s celými číslami (celočíselné delenie, zvyšky pri delení).

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

Do riešenia tejto úlohy sa zapojilo 11 tímov z  kategórie EXPERT.  Plný počet bodov dosiahlo 5 tímov (Doma, File-Open, HFD, Master a Oliver Seman), ktorým gratulujeme. Len 3 tímy použili vo svojich riešeniach komentáre (File-Open, GLŠTN masters a HFD), za čo ich chválime.

Žiaden z tímov neriešil úlohu spôsobom, aký je uvedený v autorskom riešení. 9 tímov použilo na prácu s pozíciou robotov zoznamy a 2 tímy slovníky a n-tice.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému, tvorby menej efektívneho riešenia či z pretrvávajúcich programátorských zlozvykov:

• nepresnosti pri výpočtoch súradníc či vzdialeností robotov od cieľov (odčítanie namiesto sčítania, násobenie namiesto sčétania, nesprávna podmienka na rovnosť pozícii robotov, index mimo rozsahu),

• zúženie riešenia len na prípad nastatia kolízie,

• zbytočné ošetrovanie dĺžky vstupov, keď v zadaní bolo uvedené, že sú rovnako dlhé,

• namiesto použitia funkcií s parametrami použitie globálnych premenných s príkazom input a funkciami bez parametrov,

• namiesto plnovýznamových identifikátorov premenných použitie málohovoriacich jednopísmenových identifikátorov.