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

	PALMA junior

Úloha o rozpoznávaní cifier

Autorské riešenie
[stiahni py]

Počet riešiteľov: 8 / 8 = 100,00 %
Úspešnosť riešenia: 5,56 / 7 = 79,46 %

Pri riešení úlohy postupne porovnáme znaky zosnímanej vzorky so znakmi každej z cifier 0 až 9. Vzorka bude rozpoznaná ako niektorá z cifier, ak sa bude líšiť od zistenej cifry o nanajvýš 2 znaky. Pre riešiteľnosť úlohy je rovnako dôležité, aby pre zadanú vzorku bola vyhovujúca len jedna cifra, ktorá má najmenej odlišných pixelov od vzorky.

Pre zistenie počtu odlišných znakov dvoch porovnávaných reťazcov použijeme funkciu pocet_odlisnych_znakov s dvomi parametrami. Výstupom funkcie je počet odlišných znakov. V prípade viac ako dvoch odlišných znakov funkcia vráti hodnotu 3.

def pocet_odlisnych_znakov(retazec1, retazec2):
    pocet = 0
    idx = 0
    while idx < len(retazec1) and pocet <= 2:
        if retazec1[idx] != retazec2[idx]:
            pocet += 1
        idx += 1
    return pocet

Pomocou funkcie miery_nezhody sa pre zadanú vzorku vytvorí 10-prvkový zoznam s počtami odlišných znakov tejto vzorky od cifier 0 až 9. Tu využijeme zoznam kódovania cifier 0 až 9 zo zadania úlohy.

def miery_nezhody(vzorka):
    cifry = [
        '0111010001100011000101110',
        '0010001100101000010011111',
        '1111000001011101000011111',
        '1111100001001101000101110',
        '0011001010100101111100010',
        '1111110000111100000111110',
        '0001000100011101000101110',
        '1111100010001000100010000',
        '0111010001011101000101110',
        '0111010001011100010001000'
    ]
    vysledok = []
    for cifra in cifry:
        vysledok.append(pocet_odlisnych_znakov(vzorka, cifra))
    return vysledok

Využitím predchádajúcich dvoch pomocných funkcií napokon vytvoríme funkciu rozpoznaj, ktorá určí niektorú z cifier 0 až 9, na ktorú sa najviac podobá zadaná vzorka. Vo výpočte použijeme minimálnu hodnotu z 10-prvkového zoznamu s hodnotami nezhôd zadanej vzorky s ciframi 0 až 9. Táto minimálna hodnota musí byť rovná nanajvýš 2 a musí byť jedinečná. V ostatných prípadoch úloha nemá riešenie. Aby sme zabezpečili odolnosť funkcie voči chybným vstupom doplnil sme na jej začiatok dve podmienky s generovaním výnimiek.

def rozpoznaj(vzorka):
    if len(vzorka) != 25:
        raise ValueError('Chybný vstup - vzorka nemá 25 znakov.')
    if vzorka.count('0') + vzorka.count('1') != 25:
        raise ValueError('Chybný vstup - vzorka obsahuje aj iné znaky ako {0, 1}.')
    zoznam = miery_nezhody(vzorka)
    hodnota_kandidata = min(zoznam)
    if hodnota_kandidata > 2:
        raise ValueError('Úloha nemá riešenie - vzorka sa líši od cifier 0 až 9 vo \
                          viac ako 2 znakoch.')
    if zoznam.count(hodnota_kandidata) != 1:
        raise ValueError('Úloha nemá jednoznačné riešenie - vyhovujú viacerí \
                          kandidáti.')
    kandidat = zoznam.index(hodnota_kandidata)
    return kandidat

Výsledný programový kód riešenia tejto úlohy môže vyzerať nasledovne:

def pocet_odlisnych_znakov(retazec1, retazec2):
    pocet = 0
    idx = 0
    while idx < len(retazec1) and pocet <= 2:
        if retazec1[idx] != retazec2[idx]:
            pocet += 1
        idx += 1
    return pocet


def miery_nezhody(vzorka):
    cifry = [
        '0111010001100011000101110',
        '0010001100101000010011111',
        '1111000001011101000011111',
        '1111100001001101000101110',
        '0011001010100101111100010',
        '1111110000111100000111110',
        '0001000100011101000101110',
        '1111100010001000100010000',
        '0111010001011101000101110',
        '0111010001011100010001000'
    ]
    vysledok = []
    for cifra in cifry:
        vysledok.append(pocet_odlisnych_znakov(vzorka, cifra))
    return vysledok


def rozpoznaj(vzorka):
    if len(vzorka) != 25:
        raise ValueError('Chybný vstup - vzorka nemá 25 znakov.')
    if vzorka.count('0') + vzorka.count('1') != 25:
        raise ValueError('Chybný vstup - vzorka obsahuje aj iné znaky ako {0, 1}.')
    zoznam = miery_nezhody(vzorka)
    hodnota_kandidata = min(zoznam)
    if hodnota_kandidata > 2:
        raise ValueError('Úloha nemá riešenie - vzorka sa líši od cifier 0 až 9 vo \
                          viac ako 2 znakoch.')
    if zoznam.count(hodnota_kandidata) != 1:
        raise ValueError('Úloha nemá jednoznačné riešenie - vyhovujú viacerí \
                          kandidáti.')
    kandidat = zoznam.index(hodnota_kandidata)
    return kandidat


try:
    # presná zhoda:
    # print(rozpoznaj('1111100001001101000101110'))

    # približná zhoda s maximálne 2 nezhodami znakov:
    print(rozpoznaj('1111000000001101000101110'))

    # nemá riešenie, ak je viac ako 2 nezhodných znakov:
    # print(rozpoznaj('0000000000000000000000000'))

    # nemá riešenie, ak je viac kandidátov (napr. cifry 3 a 8):
    # print(rozpoznaj('0111000001001101000101110'))

    # ošetrenie situácie, ak vzorka nemá 25 znakov:
    # print(rozpoznaj('01110000010011010001011101'))

    # ošetrenie situácie, ak vzorka obsahuje aj iné znaky ako {0, 1}:
    # print(rozpoznaj('0111000001001101000101112'))


except ValueError as chyba:
    print(chyba)

Táto úloha je zameraná na:

dôslednú analýzu úlohy a použitie stratégie riešenia problémov - dekompozície problému na podproblémy,
precvičenie príkazov opakovania, vetvenia, volania funkcií s parametrami, metód na prácu s reťazcami, prácu s vnoreným dátovým typom zoznam, zachytávania a generovania výnimiek.

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

Do riešenia tejto úlohy sa zapojilo 8 tímov z kategórie EXPERT. Plný počet bodov nedosiahol žiaden tím.

V riešeniach sme zaregistrovali nasledovné nedostatky, vychádzajúce najčastejšie z nedôslednej analýzy problému, tvorby menej efektívneho riešenia či z pretrvávajúcich programátorských zlozvykov:

nezohľadnenie prípadu, ak pre zadanú vzorku vyhovujú viaceré cifry, napr. vzorke '0111000001001101000101110' vyhovuje cifra 3 a zároveň 8, čím nedostaneme potrebný jednoznačný výsledok,
nezohľadnenie tolerancie maximálne dvoch znakov pri porovnávaní vzorky s jednotlivými ciframi,
namiesto zoznamu reťazcov zo zadania úlohy bolo použítýchy zbytočne 10 premenných, čo spôsobilo dlhší a menj prehľadný kód,
výstupom úlohy mala byť cifra, nie 10 textových výpisov,
namiesto plnovýznamových identifikátorov premenných použitie málohovoriacich jednopísmenových identifikátorov.

PALMA junior

Úloha o rozpoznávaní cifier