PALMA junior
Úloha o replikácii údajov

Autorské riešenie
[stiahni py]

• Počet riešiteľov: 13 / 18 = 72 %

• Úspešnosť riešenia: 4,77 / 6 = 80 %

Cieľom úlohy bolo pracovať so vstupným parametrom reprezentovanom ako zoznam zoznamov. Vonkajší zoznam uchováva jednotlivé uzly, každý vnútorný zoznam uchováva bloky uložené na príslušnom uzle. Je potrebné si uvedomiť, že každý vnútorný zoznam môže mať rôzny počet prvkov, aj žiaden prvok. Na základe vstupného zápisu replikácie údajov bolo potrebné overiť, či sa každý blok sa nachádza práve dvakrát sumárne za všetky uzly, ale pritom na dvoch rôznych uzloch. V skutočnosti teda bolo potrebné overiť súčasné splnenie viacerých podmienok:

1. overenie číslovania blokov od nuly (bez preskočenia niektorých hodnôt),
2. overenie, či v jednom uzle nie je ten istý blok zastúpený viackrát ako raz,
3. overenie, či vo všetkých uzloch sumárne sa nachádza každý blok práve dvakrát.

Splnenie prvej podmienky vieme zabezpečiť pomocou indexov cyklu opakovania. Riešenie druhej podmienky má viacero možností. Môžeme testovať cez cyklus opakovania, či sa každý blok nachádza v danom uzle najviac jedenkrát, alebo tiež môžeme použiť funkciu set, ktorá vráti množinu prvkov (prvky sa neopakujú) zo zoznamu prvkov a testovať, či sa počet prvkov zoznamu rovná počtu prvkov množiny:

Tretiu podmienku už môžeme zabezpečiť opätovne cyklom opakovania cez všetky bloky. Alebo tiež môžeme zlúčiť všetky bloky z uzlov do jedného zoznamu, v ktorom otestujeme prítomnosť každého bloku práve dvakrát. V takom prípade tiež nesmieme zabudnúť na overenie druhej podmienky ešte pred samotným zlúčením blokov do jedného zoznamu.

Úloha teda mala viacero možných riešení, jedno z možných riešení v jazyku Python má nasledujúcu podobu:

def je_uzol_ok(uzol):
  for blok in uzol:
    if uzol.count(blok) != 1:
      return False
  return True
 
 
def over_replikaciu(pocet_blokov, kod_replikacie):
  bloky = []
  for uzol in kod_replikacie:
    if je_uzol_ok(uzol):
      bloky.extend(uzol)
    else:
      return False
  for blok in range(pocet_blokov):
    if bloky.count(blok) != 2:
      return False
  return True

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

Úlohu riešilo 12 tímov, ale iba tri tímy získali plný počet bodov. Najčastejšie riešitelia zabudli na druhú podmienku, a teda kontrolu, či sa daný blok nenachádza viackrát v tom istom uzle. Niektoré témy zlúčili všetky bloky do jedného zoznamu, a v ňom otestovali dvojnásobnú prítomnosť každého bloku. Stratili však informáciu o tom, že niektorý blok mohol byť síce dvakrát, ale v tom istom uzle. To by pri poškodení daného uzla spôsobilo stratu časti údajov. Niektorí si v poli pre každý blok pamätali, koľkokrát sa daný blok nachádza v jednotlivých uzloch. Väčšina riešení používala dvakrát cyklus opakovania, pomocou ktorého prešli všetky bloky a všetky uzly, pričom sa kontrolovalo, či sa každý blok nachádza v uzloch práve dvakrát, tiež či je uložený na dvoch rôznych uzloch.