PALMA junior
Úloha o kvalite prenosu

Autorské riešenie
[stiahni imp : py]

• Počet riešiteľov: 11 / 13 = 85 %

• Úspešnosť riešenia: 5,22 / 6 =  87%

Úlohou je vyhodnotiť kvalitu prenosu správy. Podľa zadania, správa ostane zrozumiteľná, ak nastane práve jedna z možnosí:

• správa sa nezmení,

• zmení sa jeden znak,

• jeden znak sa vynechá,

• jeden znak sa pridá. 

V ďalších prípadoch správa už nevyhovuje požadovanej kvalite a nebude zrozumiteľná.

Úlohu si môžeme rozdeliť na prípady, ak výsledná správa má rovnakú dĺžku ako pôvodná alebo jej dĺžka sa zmenila.

Ak sú počty znakov v obidvoch správach rovnaké môžeme predpokladať, že žiadna zmena nenastala alebo sa nejaké znaky zmenili. Ak by sa nejaký znak pridal/vynechal, musel by sa nejaký znak aj vynechať/pridať a to by znamenalo, že prijatá správa už nie je zrozumiteľná.

Budeme postupne porovnávať znaky na rovnakých pozíciách v oboch správach či sú zhodné. Sledujeme počet zmien medzi oboma správami. Ak počet zmien prekročí 1, vieme že prijatá správa nebude zrozumiteľná.

Prvý podprogram môže vyzerať nasledovne:

; Imagine Logo
viem rovnake_dlzky_su_podobne :sprava1 :sprava2
  urobTu "zmeny 0
  urobTu "index 1

  kym [:index <= pocet :sprava1][
    ak prvok :index :sprava1 <> prvok :index :sprava2 [
      zvys "zmeny
      ak :zmeny > 1[
        vysledok "nie
      ]
    ]
    zvys "index
  ]
  vysledok "ano 
koniec 

Ak sú počty znakov v obidvoch správach rôzne, môžeme predpokladať, že sa nejaký znak pridal alebo vynechal. Ak by sa nejaký znak zmenil, musel by sa ešte nejaký znak pridať alebo vynechať  a to by znamenalo, že prijatá správa už nie je zrozumiteľná.

Budeme postupne porovnávať znaky na rovnakých pozíciách v oboch správach či sú zhodné. Ak nájdeme nezhodu, posunieme sa v dlhšej správe a zvýšime počet zmien. Ak počet zmien prekročí 1, vieme že prijatá správa nebude zrozumiteľná.

Druhý podprogram môže vyzerať nasledovne:

;Imagine Logo
viem rozne_dlzky_su_podobne :kratka :dlha
  urobTu "zmeny 0
  urobTu "index_kratka 1
  urobTu "index_dlha 1

  kym [:index_dlha <= pocet :dlha][
    ak2 prvok :index_kratka :kratka = prvok :index_dlha :dlha [
      zvys "index_kratka
      zvys "index_dlha
    ][
      zvys "index_dlha
      zvys "zmeny
      ak :zmeny > 1 [
        vysledok "nie
      ]
    ]
  ]
  vysledok "ano
koniec

Všimnime si, že je nám jedno, či prijatá správa je dlhšia alebo kratšia. Porovnávame dve správy, jednu kratšiu a jednu dlhšiu a to bez ohľadu na to, ktorá z nich je prijatá a ktorá odoslaná.

V hlavnej procedúre zabezpečíme, aby sme otestovali všetky možné prípady: prvá správa je kratšia alebo prvá správa je dlhšia alebo správy sú rovnako dlhé.

Hlavná procedúra môže vyzerať nasledovne:

;Imagine Logo
viem kvalita_prenosu :sprava1 :sprava2
  ak pocet :sprava1 > pocet :sprava2 [
    vysledok rozne_dlzky_su_podobne :sprava2 :sprava1
  ]

  ak pocet :sprava1 < pocet :sprava2 [
    vysledok rozne_dlzky_su_podobne :sprava1 :sprava2
  ]

  vysledok rovnake_dlzky_su_podobne :sprava1 :sprava2
koniec

Základná myšlienka riešenia použitá v prostredí Image Logo je aplikovateľná aj v jazyku Python. Problém nastáva pri podprograme, ktorý bude porovnávať dve rôzne dlhé správy, aj to len v špecifickom prípade - ak sa k správe pridali nejaké znaky na koniec alebo sa zo správy nejaké posledné znaky stratili. Dôvod vzniku tohto problému súvisí so skutočnosťou, že ak sa odkazujeme na index, ktorý v reťazci nie je, Python vyhodí chybu.

Túto situáciu vyriešime dvoma krokmi: Zabezpečíme, aby pri porovnávaní správ oba indexy (krátkej aj dlhej správy) boli menšie ako dĺžky príslušných správ. Pred samotné porovnanie vložiť ešte test, ktorý odchytí situáciu, keď je dĺžka dlhej správy väčšia o viac ako jeden znak oproti kratšej správe. Výsledný program môže vyzerať nasledovne:

# Python
def kvalita_prenosu(sprava1, sprava2):
    if len(sprava1) > len(sprava2):
        return rozne_dlzky_su_podobne(sprava2, sprava1)
    if len(sprava1) < len(sprava2):
        return rozne_dlzky_su_podobne(sprava1, sprava2)
    return rovnake_dlzky_su_podobne(sprava1, sprava2)


def rovnake_dlzky_su_podobne(sprava1, sprava2):
    zmeny = 0
    for i in range(len(sprava1)):
        if sprava1[i] != sprava2[i]:
            zmeny = zmeny + 1
            if zmeny > 1:
                return False
    return True


def rozne_dlzky_su_podobne(kratka, dlha):
    zmeny = 0
    index_kratka = 0
    index_dlha = 0
    if len(dlha) - len(kratka) > 1:
        return False
    while index_dlha < len(dlha) and index_kratka < len(kratka):
        if kratka[index_kratka] == dlha[index_dlha]:
            index_kratka = index_kratka + 1
            index_dlha = index_dlha + 1
        else:
            index_dlha = index_dlha + 1
            zmeny = zmeny + 1
            if zmeny > 1:
                return False
    return True 

V Pythone je možné použiť aj šikovnejšie riešenie pomocou výrezov z reťazcov. Najprv porovnávame správy znak po znaku až do okamihu, kedy nájdeme prvý znak, v ktorom sa správy líšia. Výsledok potom získame už len porovnaním zvyšných výrezov z oboch správ. Z kratšej správy zoberieme celý neporovnaný zvyšok a z dlhej zvyšok bez znaku, v ktorom sme našli rozdiel. Toto riešenie môže vyzerať nasledovne:  

# Python
def rozne_dlzky_su_podobne_alt_riesenie(kratka, dlha):
    index_kratka = 0
    index_kratka = 0
    while index_kratka < len(kratka) and index_dlha < len(dlha):
        if kratka[index_kratka] == dlha[index_dlha]:
            index_kratka = index_kratka + 1
            index_dlha = index_dlha + 1
        else:
            return kratka[index_kratka:] == dlha[index_dlha + 1:]
    return True 

Pri programovaní nie je nič nezvyčajné, ak prvé riešenie postupne vylepšujeme, zjednodušujeme,  sprehľaďnujeme alebo sa na problém pozeráme z rôznych uhlov. Aj riešenie tejto úlohy môžeme postupne vylepšovať. Na celý problém sa môžeme pozrieť aj z iného pohľadu. Vieme, že dve porovnávané správy sa môžu líšiť v maximálne jednom znaku (zmazaný, pridaný, zmenený). Nájdime teda 1. miesto, kde sa reťazce líšia a porovnajme zvyšky. Tie by už mali byť rovnaké. Ak nie, jedna zo správ nebude zrozumiteľná. 

# Python
def kvalita_prenosu1(sprava1, sprava2):
    idx = 0
    if len(sprava1) > len(sprava2):
        skok_sprava1, skok_sprava2 = 1, 0
    elif len(sprava1) < len(sprava2):
        skok_sprava1, skok_sprava2 = 0, 1
    else:
        skok_sprava1, skok_sprava2 = 1, 1

    while idx < len(sprava1) and idx < len(sprava2) and sprava1[idx] == sprava2[idx]:
            idx += 1
    return sprava1[idx + skok_sprava1:] == sprava2[idx + skok_sprava2:] 

Na začiatku sme porovnali dĺžky správ a podľa toho nastavili dĺžky skokov. Tieto skoky použijeme na preskočenie miesta, v ktorom sa správy 1. krát líšili. Ak sú správy rôzne dlhé, preskočíme pridaný znak v tej dlhšej. Ak boli rovnako dlhé, preskočíme v oboch znak, v ktorom sa líšia. Všimnime si, že v tomto riešení je úplne jedno, ktorá zo správ je odoslaná a ktorá prijatá.

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

Parametre ste používali všetci správne, ale zabudli ste na to, že aj prijatá, aj odoslaná správa môže byť tá kratšia, teda znaky sa môžu pri prenose stratiť alebo pridať.  Najviac chýb ste mali v tom, že ste netestovali prípady, ak je súčasne aj zmena dĺžky správy a zmena znakov.

Chyby pri riešeniach v Pythone súviseli práve s nedôsledným testovaním pridávania alebo uberania znakov na konci reťazca, v dôsledku čoho program skončil s chybou. Táto situácia mohla nastať aj v prípade, že správy "kvet" a "ket", príp. "kvet" a "kviet" boli programom správne vyhodnotené (znak bol vynechaný alebo pridaný vo vnútri správy), no situáciu pri porovnávaní správ "kvet" a "kvety" už program nezvládal.

Ďalšou pomerne častou chybou bolo použitie výpisu namiesto návratovej hodnoty z funkcie - zmysluplná funkcia by mala mať aj návratovú hodnotu, ktorú vráti naspäť do hlavného programu na ďalšie spracovanie, teda nemala by končiť len samotným výpisom výsledku (to môže zabezpečiť napokon hlavný program, ak to bude potrebné).