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

;Imagine Logo

viem vysledny_smer :smer_start :start :ciel
  ak alebo (zaroven (:smer_start = 0) (prvok 2 :start <> prvok 2 :ciel))
           (zaroven (:smer_start = 1) (prvok 1 :start<> prvok 1 :ciel))[
    ak2 :smer_start = 0[
      urobTu "smer_start 1
    ][
      urobTu "smer_start 0
    ]
  ]
  vy :smer_start
koniec


viem pocet_prikazov :smer_start :start :ciel
  urobTu "pocet_prikazov 0
  ak alebo (zaroven (:smer_start = 0) (prvok 2 :start <> prvok 2 :ciel))
           (zaroven (:smer_start = 1) (prvok 1 :start <> prvok 1 :ciel))[
    urobTu "pocet_prikazov :pocet_prikazov + 1
  ]
  urobTu "pocet_prikazov abs((prvok 1 :start) - (prvok 1 :ciel)) +
                       abs((prvok 2 :start) - (prvok 2 :ciel))
  vy :pocet_prikazov
koniec 

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

;Imagine Logo

viem pocet_prikazov_trasy :smer_start :start :bod1 :bod2 :bod3
  urobTu "pocet pocet_prikazov :smer_start :start :bod1
  urobTu "smer_start vysledny_smer :smer_start :start :bod1
  urobTu "pocet :pocet + pocet_prikazov :smer_start :bod1 :bod2
  urobTu "smer_start vysledny_smer :smer_start :bod1 :bod2
  urobTu "pocet :pocet + pocet_prikazov :smer_start :bod2 :bod3

  vy :pocet
koniec

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

;Imagine Logo

viem trasa :smer_start :start :zas1 :zas2 :zas3
  urobTu "min_prikazov pocet_prikazov_trasy :smer_start :start :zas1 :zas2 :zas3
  urobTu "poradie (zoznam :zas1 :zas2 :zas3)


  urobTu "pocet_prikazov pocet_prikazov_trasy :smer_start :start :zas1 :zas3 :zas2
  ak :pocet_prikazov < :min_prikazov [
    urobTu "min_prikazov :pocet_prikazov
    urobTu "poradie (zoznam :zas1 :zas3 :zas2)
  ]

  urobTu "pocet_prikazov pocet_prikazov_trasy :smer_start :start :zas2 :zas1 :zas3
  ak :pocet_prikazov < :min_prikazov [
    urobTu "min_prikazov :pocet_prikazov
    urobTu "poradie (zoznam :zas2 :zas1 :zas3)
  ]

  urobTu "pocet_prikazov pocet_prikazov_trasy :smer_start :start :zas2 :zas3 :zas1
  ak :pocet_prikazov < :min_prikazov [
    urobTu "min_prikazov :pocet_prikazov
    urobTu "poradie (zoznam :zas2 :zas3 :zas1)
  ]


  urobTu "pocet_prikazov pocet_prikazov_trasy :smer_start :start :zas3 :zas1 :zas2
  ak :pocet_prikazov < :min_prikazov [
    urobTu "min_prikazov :pocet_prikazov
    urobTu "poradie (zoznam :zas3 :zas1 :zas2)
  ]

  urobTu "pocet_prikazov pocet_prikazov_trasy :smer_start :start :zas3 :zas2 :zas1
  ak :pocet_prikazov < :min_prikazov [
    urobTu "min_prikazov :pocet_prikazov
    urobTu "poradie (zoznam :zas3 :zas2 :zas1)
  ]

  vysledok :poradie
koniec

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.