PALMA junior, Programovanie, ALgoritmy, MAtematika, súťaž pre mladých programátorov v Imagine

	PALMA junior

Úloha o záhone

Autorské riešenie
[stiahni imp : py]

Počet riešiteľov: 2 / 2 = 100%
Úspešnosť riešenia: 4,25 / 7 = 60,71%

K tejto úlohe sa dalo pristupovať mnohými spôsobmi. Bolo možné vygenerovať všetky možné rozmiestnenia druhov v záhone a overovať, či dané rozmiestnenie je vhodné. Takisto sa dala využiť teória grafov, keď by sme predpokladali, že naše druhy sú vrcholy grafu a medzi nimi sa nachádza hrana iba ak dané druhy môžu byť v rozmiestnení vedľa seba. Potom by sa použil algoritmus pre prehľadávanie grafu do hĺbky začatý v každom vrchole grafu. Pre vzorové riešenie ukážeme riešenie "backtrackingom", teda preverovanie všetkých možností.

;Imagine logo
viem jeVZozname :a :zoznam
  urobTu "poc 1
  urobTu "jeVZ 0
  opakuj (počet :zoznam)[
    ak (:a=(prvok :poc :zoznam))[urobTu "jeVZ 1]
   ]
  výsledok :jeVZ
koniec

viem mozuBytSpolu :r1 :r2 :mozniSusedia
  výsledok (zároveň ((jeVZozname :r1 (prvok :r2 :mozniSusedia))=1) ((jeVZozname :r2 (prvok :r1 :mozniSusedia))=1))
koniec

viem vytvorZáhon :plan :pozicia :mozniSusedia
  ak :pozicia-1 = (počet :mozniSusedia)[
    píš :plan
    ukonči
    ]
  urobTu "rastlina 1
  opakuj (počet :mozniSusedia)[
    píš :rastlina
    urobTu "prvokPlanu prvok (:pozicia-1) :plan
    ak (alebo (:pozicia=1) (zároveň ((jeVZozname :rastlina :plan)=0) (mozuBytSpolu :rastlina :prvokPlanu :mozniSusedia)))[
      urobTu "plan vložPo :rastlina :plan
      vytvorZáhon :plan (:pozicia+1) :mozniSusedia
      urobTu "plan bezPosledného :plan
    ]
    urobTu "rastlina :rastlina+1
  ]
koniec

Python

def mozuBytSpolu(r1, r2, mozniSusedia):
    """
    Overí, či rasliny r1 a r2 možu byť susedia
    :param r1: prvá rastlina
    :param r2: druhá rastlina
    :param mozniSusedia: zoznam, ktorý obsahuje možných susedov 
     pre jednotlivé druhy
    :return: True ak môžu byť susedia, False ak nemôžu
    """
    return r1 in mozniSusedia[r2] and r2 in mozniSusedia[r1]

def vytvorZahon(plan, pozicia, mozniSusedia):
    """
    Rekurzívna funkcia, ktorá vygeneruje všetky možné rozmiestnenia
    a overí, či dané rozmiestnenie vyhovuje požiadavkam
    :param plan: momentálne vygenerovaný zoznam druhov
    :param pozicia: pozícia, na ktorú momentálne vkladáme
    :param mozniSusedia: zoznam, ktorý obsahuje možných susedov pre jednotlivé druhy
    """

    if pozicia == len(mozniSusedia):
        print(plan)
    for rastlina in range(len(mozniSusedia)):
        if (pozicia == 0) or (rastlina not in plan and 
            mozuBytSpolu(rastlina, plan[pozicia-1], mozniSusedia)):
            plan.append(rastlina)
            vytvorZahon(plan, pozicia+1, mozniSusedia)
            plan.pop()


mozniSusedia = [[3],[2,3],[1],[0,1]]
vytvorZahon([], 0, mozniSusedia)

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

Odovzdané boli 2 riešenia. Jedno však, bohužiaľ, nebolo dokončené. Druhé bolo riešené spomínaným algoritmom na prehľadávanie grafu do hĺbky, čo som nepredpokladal, že niekto zo žiakov využije. V tomto riešení však nebol správny výstup pre triviálny prípad, a to ak by sme chceli vysadiť iba jeden druh rastliny.

PALMA junior

Úloha o záhone