PALMA junior
Úloha o zásobovacom robotovi

Autorské riešenie
[stiahni py imp]                                        

• Počet riešiteľov: 12 / 22 = 55 %

• Úspešnosť riešenia: 3,08 / 7= 44 %

Riešenie tejto úlohy:

Zásobovací robot stojí na pozícii [0,0], je otočený na východ. Robot pozná iba 3 príkazy: vpred o 1, dozadu o 1, otoč vpravo o 90 stupňov. Našou úlohu bolo určiť také poradie návštevy zásobníkov, aby robot na ich návštevu potreboval vykonať čo najkratšiu postupnosť príkazov.

Riešenie problému môžeme rozdeliť na tri podproblémy.

1. Najmenej koľko príkazov potrebuje robot na to, aby z aktuálnej pozície a z aktuálneho smeru prišiel k zadanému zásobníku.

2. Najmenej koľko príkazov potrebuje robot, aby z aktuálnej pozície navštívil zásobníky v určenom poradí.

3. Pre ktoré poradie zásobníkov potrebuje robot vykonať najmenej príkazov tak, aby ich z aktuálnej pozície postupne všetky navštívil.

Keďže robot pozná príkazy dopredu a dozadu, tak počet krokov z aktuálnej pozície do cielovej pozície určíme ako súčet absolútnych hodnôt rozdielu x-ových a y-ových súradníc. Ak cielová pozícia nie je v smere pred alebo smere za robotom, potrebuje robot ešte jeden príkaz na otočenie. Keďže pre výpočet počtu krokov je dôležitý aj smer, musíme si pamätať aj to, v akom smere bude robot otočený, ak sa presunie z aktuálnej pozície do cieľovej.

Vytvorme si dve funkcie. Jedna vypočíta počet príkazov potrebných na presun zo štartovacej pozície a štarovacieho smeru do zadaného bodu a druha nám vráti výsledný smer po tomto presune.

#Python
def vysledny_smer(smer_start, start, ciel):
    if (smer_start == 0 and start[1] != ciel[1]) or \
            (smer_start == 1 and start[0] != ciel[0]):
        if smer_start == 0:
            return 1
        else:
            return 0
    return smer_start


def pocet_prikazov(smer_start, start, ciel):
    pocet_prikazov = 0
    if (smer_start == 0 and start[1] != ciel[1]) or \
            (smer_start == 1 and start[0] != ciel[0]):
        pocet_prikazov += 1
    pocet_prikazov += abs(start[0] - ciel[0]) + abs(start[1] - ciel[1])
    return pocet_prikazov

Keď už vieme, koľko najmenej príkazov robot potrebuje, aby sa presunul z jedného bodu do druhého zistime, koľko príkazov bude potrebovať na to, aby navštívil body trasy v zadanom poradí.

#Python
def pocet_prikazov_trasy(smer_start, start, bod1, bod2, bod3):
    pocet = pocet_prikazov(smer_start, start, bod1)
    smer_start = vysledny_smer(smer_start, start, bod1)
    pocet += pocet_prikazov(smer_start, bod1, bod2)
    smer_start = vysledny_smer(smer_start, bod1, bod2)
    pocet += pocet_prikazov(smer_start, bod2, bod3)
    return pocet

Nakoniec musíme zistiť, pre ktoré poradie zásobníkov bude pre prejdenie trasy potrebných najmenej príkazov. Keďže máme tri zásobníky, existuje celkom šesť rôznych poradí ako ich navštíviť. Otestujeme všetky a to poradie, pri ktorom bude počet príkazov najmenší je to najlepšie. 

#Python
def trasa(smer_start, start, zas1, zas2, zas3):
    min_prikazov = pocet_prikazov_trasy(smer_start, start, zas1, zas2, zas3)
    poradie = [zas1, zas2, zas3]

    pocet_prikazov = pocet_prikazov_trasy(smer_start, start, zas1, zas3, zas2)
    if pocet_prikazov < min_prikazov:
        min_prikazov = pocet_prikazov
        poradie = [zas1, zas3, zas2]

    pocet_prikazov = pocet_prikazov_trasy(smer_start, start, zas2, zas1, zas3)
    if pocet_prikazov < min_prikazov:
        min_prikazov = pocet_prikazov
        poradie = [zas2, zas1, zas3]

    pocet_prikazov = pocet_prikazov_trasy(smer_start, start, zas2, zas3, zas1)
    if pocet_prikazov < min_prikazov:
        min_prikazov = pocet_prikazov
        poradie = [zas2, zas3, zas1]

    pocet_prikazov = pocet_prikazov_trasy(smer_start, start, zas3, zas1, zas2)
    if pocet_prikazov < min_prikazov:
        min_prikazov = pocet_prikazov
        poradie = [zas3, zas1, zas2]

    pocet_prikazov = pocet_prikazov_trasy(smer_start, start, zas3, zas2, zas1)
    if pocet_prikazov < min_prikazov:
        min_prikazov = pocet_prikazov
        poradie = [zas3, zas2, zas1]

    return poradie

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

Zaujímavé riešenie odovzdal tím acmigtui. Na vytvorenie všetkých preusporiadaní v akom možno zásobnníky navštíviť, použil modul intertools.

Častou chybou bolo, že ste si neuvedomili, že stačí počítať rozdiel medzi jednotlivými súradnicami jednotlivých zásobníkov a potom k zásobníkom prejsť daný počet krokov buď dopredu alebo cúvaním.