PALMA junior
Úloha o počte vrcholov

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 20 / 25 = 80 %

• Úspešnosť riešenia: 4 / 7 = 57 %

Táto úloha je zameraná na analýzu postupnosti číselných hodnôt - zoznam výšok bodov prejdenej trasy. V zadanom zozname potrebujeme identifikovať vrcholy. Sú to miesta, ktoré sú lokálne najvyššie a zároveň dostatočne vysoko nad najbližšími dolinami (dolinkami, sedlami).

K hľadaniu týchto bodov môžeme pristupovať dvoma spôsobmi:

1. nájdeme lokálne maximá - t.j. hodnoty, ktoré sú väčšie ako predchádzajúce a nasledujúce hodnoty zároveň, následne overíme, či klesanie pred nimi a za nimi spĺňa podmienky:

   1. klesneme aspoň 15 metrov,

   2. počas klesania nikde nestúpneme (uvedomme si, že aj rovina je v poriadku)

2. dáta budeme analyzovať priebežne:

   1. nájdeme miesto kde začíname stúpať, poznačme si jeho výšku,

   2. ak následne niekde klesneme, zrejme začíname klesať, poznačme si výšku prípadného vrcholu,

   3. nájdeme miesto kde začíname stúpať, zrejme sme dokončili zostup, poznačme si výšku,

   4. overíme, či rozdiel výšok medzi začiatkom stúpania a prípadným vrcholom a medzi prípadným vrcholom a koncom klesania je dostatočná, ak áno, našli sme vrchol a pokračujeme ďalej od bodu 1

Ak si porovnáme obidva prístupy, v prvom prístupe prechádzame niektorými prvkami opakovane (nájdeme vrchol a vraciame sa, aby sme zistili ako prebiehala trasa pred ním). Druhý prístup je výhodnejší, lebo nám stačí jeden prechod profilom trasy. Realizujme preto druhú možnosť.

Prechádzajme postupne bodmi trasy.

1. Ak nájdeme dva susedné body, pre ktoré platí bod1 < bod2, našli sme začiatok stúpania. Výška začiatku stúpania je bod1. Odteraz stúpame na potenciálny vrchol.

2. Ak nájdeme dva susedné body, pre ktoré platí bod1 > bod2, našli sme potenciálny vrchol, ktorého výška je bod1. Odteraz klesáme.

3. Ak nájdeme dva susedné body, pre ktoré platí bod1 < bod2, dokončili sme zostup vo výške bod1. Overíme si, či môžeme uznať vrchol. Zároveň sme narazili na začiatok stúpania na ďalší potenciálny vrchol. Pokračujeme teda bodom 1.

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

# Python
def pocet_vrcholov(profil):
    profil = profil.copy()
    profil.append(profil[-1] + 1)

    pocet = 0
    stav = 'vystup'
    vyska_zaciatok = profil[0]
    vyska_vrchol = profil[0]

    for idx in range(1, len(profil) - 1):
        if profil[idx] > profil[idx + 1] and stav == 'vystup':
            vyska_vrchol = profil[idx]
            stav = 'zostup'

        elif profil[idx] < profil[idx + 1] and stav == 'zostup':
            vyska_koniec = profil[idx]
            if vyska_vrchol - vyska_zaciatok >= 15 <= vyska_vrchol - vyska_koniec:
                pocet = pocet + 1
            vyska_zaciatok = profil[idx]
            stav = 'vystup'

    return pocet

Všimnime si niektoré časti riešenia podrobnejšie.

Výlet môže skončiť pri zostupe. V našej úvahe detegujeme ukončnie zostupu začiatkom stúpania. Na koniec záznamu preto pridáme umelú hodnotu, ktorá bude predstavovať začiatok stúpania. Keďže takto modifikujeme zoznam výšok, budeme to realizovať v jeho kópii.

Na začiatku predpokladáme, že výlet začne stúpaním. Navyše, začiatok stúpania a vrchol nastavíme na  hodnotu profil[0]. To ale nemusí byť pravda. Pozrime sa na to, ako sa to prejaví neskôr. Sú dve možnosti:

Začali sme stúpaním. Začiatok stúpania má korektnú hodnotu. Ak prejdeme cez potenciálny vrchol, aktualizujeme na správnu hodnotu aj výšku vrchola. V tomto prípade chyba nenastane.

Začali sme klesaním. Hodnota vrchola má korektnú hodnotu. Ak ukončíme klesanie, tak vrchol nie je dostatočne vysoko od začiatklu stúpania (hodnoty sú rovnaké), takže ho nezapočítame. Ani v tomto prípade teda chyba nenastane.

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

Najčastejšie chyby ste robili pri vyhodnocovaní nasledujúcich situáciií:

• vrcholy tesne za sebou, akonáhle zostúpime z jedného začíname stúpať na ďalší,
• výlet má len jeden vrchol, prvá časť výletu je len stúpanie a druhá časť len klesanie,
• vrchol je tiahly, dlho mierne stúpame a následne dlho mierne klesáme,
• vyhodnotenie výletu modrého tími, ktorý už podľa zadania mal len dva vrcholy.

Niektorí z vás zabudli ošetriť extrémne prípady, kde trasa mala málo záznamov alebo sme len stúpali alebo sme len klesali. Častou chybou bolo testovanie len susedných hodnôt v zozname pre zistenie vrchola.