PALMA junior
Úloha o priateľstvách

Autorské riešenie
[stiahni socialna_siet.py]

• Počet riešiteľov:26 / 26 =  100 %

• Úspešnosť riešenia: 5,65 / 7= 81 %

Pri riešení tejto úlohy potrebujeme analyzovať záznamy sociálnej siete a vyriešiť dva základné problémy:

1. Nájsť záznam používateľa, pre ktorého hľadáme obojsmerných priateľov a zapamätať si jeho všetkých jednosmerných priateľov.

2. Nájsť záznam každého z jednosmerných priateľov používateľa a zistiť, či aj on označili uvažovaného používateľa za priateľa. Ak áno, zaradíme tohto priateľa do zoznamu obojsmerných priateľov používateľa. 

Výsledné riešenie môže vyzerať nasledovne: 

def priatelia(pouzivatel, zaznamy):
    obojsmerni_priatelia = []
    jednosmerni_priatelia = []

    for zaznam in zaznamy:
        if pouzivatel == zaznam[0]:
            jednosmerni_priatelia.extend(zaznam[1:])
            break

    if jednosmerni_priatelia == []:
        return obojsmerni_priatelia

    for zaznam in zaznamy:
        if zaznam[0] in jednosmerni_priatelia:
            if pouzivatel in zaznam:
                obojsmerni_priatelia.append(zaznam[0])

    return obojsmerni_priatelia 

Keďže záznamy sociálnej siete nie sú usporiadané podľa mien používateľov, musíme záznam používateľa hľadať tak, že postupne prehľadávame všetky záznamy. Ak záznam nájdeme, zapamätáme si jednosmerných priateľov používateľa a prehľadávanie môžeme ukončiť.

Ak zoznam jednosmerných priateľov používateľa je v tomto okamžiku prázdny (buď nemá jednosmerných priateľov alebo nie je vedený ako používateľ sociálnej siete), znamená to, že nemá žiadnych obojsmerných priateľov a funkcia vráti prázdny zoznam.

V opačnom prípade, opäť prehľadávame záznamy sociálnej siete, aby sme našli záznamy jednosmerných priateľov používateľa. Ak nájdeme záznam jednosmerného priateľa tak overíme, či priateľstvo je obojsmerné. Ak áno, tento jednosmerný priateľ je zároveň obojsmerným a jeho meno si uložíme do zoznamu obojsmerných priateľov.

Posledným krokom je vrátenie zoznamu obojsmerných priateľov.

Všimnime si ešte jednu vec. Zoznam jednosmerných a zoznam obojsmerných priateľov sme na začiatku inicializovali ako prázdne hodnoty. Následný výpočet ich buď naplní hodnotami alebo nechá bez zmeny. Nemusíme ich teda priebežne vytvárať a prípadne testovať, či sú vytvorené a s akým obsahom. 

Pri hľadaní záznamu daného používateľa sme postupovali tak, že ak sme ho našli, prehľadávanie záznamov sme ukončili (príkaz break). Týmto sme si ušetrili zbytočné prehľadávanie zvyšku záznamov. Podobne môžeme postupovať aj pri hľadaní záznamov jednosmerných priateľov. Ak sme už všetky našli a vyhodnotili, prehľadávanie môžeme ukončiť. Vylepšené riešenie môže vyzerať nasledovne: 

def priatelia(pouzivatel, zaznamy):
    obojsmerni_priatelia = []
    jednosmerni_priatelia = []

    for zaznam in zaznamy:
        if pouzivatel == zaznam[0]:
            jednosmerni_priatelia.extend(zaznam[1:])
            break

    if jednosmerni_priatelia == []:
        return obojsmerni_priatelia

    for zaznam in zaznamy:
        if zaznam[0] in jednosmerni_priatelia:
            if pouzivatel in zaznam:
                obojsmerni_priatelia.append(zaznam[0])
                jednosmerni_priatelia.remove(zaznam[0])
                if len(jednosmerni_priatelia) == 0:
                    break

    return obojsmerni_priatelia

Ak nájdeme a analyzujeme záznam jednosmerného priateľa, odstránime ho zo zoznamu jednosmerných priateľov. Ak je zoznam jednosmerných priateľov už prázdny, prehľadávanie ukončíme.

Všimnime si ešte jednu vec. Pomerne často testujeme, či sa nejaká hodnota nachádza v nejakom zozname (operátor in) alebo hľadáme hodnotu v nejakom zozname. Toto sú pomerne náročné operácie. Aby ich Python dokázal vyhodnotiť, potrebuje postupne hľadanú hodnotu porovnať s každým prvkom zoznamu až kým nenájde zhodu alebo sa nedostane na koniec zoznamu.

V Pythone existujú dátové štruktúry, v ktorých sa operácia in alebo vyhľadávanie vyhodnocujú veľmi rýchlo. Sú to slovníky a množiny. Pozrime sa, ako by riešenie vyzeralo, ak tieto štruktúry a ich vlastnosti využijeme:

def priatelia(pouzivatel, zaznamy):
    jednosmerni_priatelia = {zaznam[0]: set(zaznam[1:]) for zaznam in zaznamy}
    obojsmerni_priatelia = [meno 
                            for meno in jednosmerni_priatelia[pouzivatel] 
                            if pouzivatel in jednosmerni_priatelia[meno]]
    return obojsmerni_priatelia

Najskôr sme si vytvorili slovník (jednosmerni_priatelia), kde mapujeme mená používateľov na množiny ich jednosmerných priateľov.

V druhom kroku postupne prejdeme množinou všetkých jednosmerných priateľov používateľa (for meno in jednosmerni_priatelia[pouzivatel]) a overíme či označili používateľa za svojho priateľa (if pouzivatel in jednosmerni_priatelia[meno]). Ak je táto podmienka splnená, pridáme meno do výsledného zoznamu. 

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

Pomerne častou chybou bolo neefektívne riešenie, kde ste v jednom cykle prehľadávali záznamy, aby ste našli záznam používateľa. Keď ste ho našli, tak pre každého jednosmerného priateľa ste opäť prehľadávali všetky záznamy.

Niektorí z vás využili množiny alebo slovníky. Tu si však treba dať pozor na to, aby riešenie bolo zrozumiteľné. Aj keď sa riešenie dá zapísať v jednom riadku, môže to byť na úkor čitateľnosti a porozumenia kódu.