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

	PALMA junior

Úloha o šifrovacej mriežke

Autorské riešenie
[stiahni py]

Počet riešiteľov: 5 / 10 = 50 %
Úspešnosť riešenia: 3,2 / 7 = 46 %

Namiesto písania dlhých kódov nám na začiatku riešenia pomôže dôkladná analýza zadania. Indexy políčok, ktoré sme v riadkoch vyrezali, sa nachádzajú v riadkoch dvojrozmernej matice. Je zrejmé, že pri otáčaní sa zmenia indexy každého otvoru. Je teda dôležité zistiť, aký vplyv má otáčanie na zmenu týchto indexov.

Predpokladajme, že veľkosť štvorčekovanej mriežky je n. Potom zmeny indexov pri otáčaní môžu vyzerať nasledovne:

otacanie indexov

Ostáva nám už len zistiť, či sa pri otáčaní niektorý otvor dostane na index poľa, v ktorom sa už otvor nachádzal. V takom prípade funkcia vráti False. Funkcia vráti True iba v prípade, že po overení všetkých otvorov takáto situácia nenastane.

Nasleduje možné riešenie v jazyku Python.

#python

# overi, ci dana mriezka je navrhnuta tak, ze kazde policko sa po otoceniach pouzije najviac jedenkrat

def over(pole):
   '''
   :param pole: dvojrozmerne pole s otvormi na mriezke
   :type: two-dimensional array
   :return vrati, ci je pole navrhnute korektne (respektuju sa otacania)
   :rtype bool
   '''

   n = len(pole)
   #prejdem vsetky policka
   for riadok in range(n):
   for prvok in range(len(pole[riadok])):
     i = riadok
     j = pole[riadok][prvok]
     #otestujem otocenie vpravo
     if (n-i-1) in pole[j]:
       return False
     #otestujem otocenie nadol
     if (n-j-1) in pole[n-i-1]:
       return False
     #otestujem otocenie vlavo
     if (i) in pole[n-j-1]:
       return False
   return True
#over( [[2, 4, 6], [5], [3], [2, 5], [], [4], []])
if (over( [[1], [], [], [], [], [], []])):
   print( 'Dana mriezka JE navrhnuta tak, aby kazde policko bolo pouzite nanajvys raz')
else:
   print( 'Dana mriezka NIE JE navrhnuta tak, aby kazde policko bolo pouzite nanajvys raz')

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

Úlohu riešilo 5 tímov, dva z nich vyriešilo úlohu správnu. Jeden tím si pomohol knižnicou numpy a príkazom rot90, ktorý hodnoty dvojrozmerného poľa otočí. Následne tím kontroloval počet výskytov otvorov na jednotlivých políčkach. Druhému správnemu riešeniu (bez knižnice numpy) chýbali komentáre k riešeniu, ktoré by sprehľadnili zdrojový kód. Ďalšie riešenie bolo založené na vytvorení pomocného dvojrozmerného poľa, v ktorom ste si chceli pamätať otočenie. Na záver však tím vypísal iba vytvorené pole, funkcia však mala vrátiť hodnotu True alebo False. Ďalšie tímy zlyhali už pri základnej práci s dvojrozmerným poľom.

PALMA junior

Úloha o šifrovacej mriežke