# Domača naloga: Družabno omrežje dražbe

## Seznami

1. Napiši funkcijo `unikati(s)`, ki prejme seznam in vrne seznam, ki vsebuje iste elemente kot `s`, v enakem vrstnem redu, vendar brez ponovitev. Funkcija ne sme spreminjati podanega seznama, temveč mora vrniti novega.

   Klic `unikati(["Ana", "Ana", "Berta", "Cilka", "Ana", "Berta", "Berta", "Berta", "Ema", "Dani", "Cilka"])` vrne `["Ana", "Berta", "Cilka", "Ema", "Dani"]`.

2. Napiši funkcijo `skupnih(s, t)`, ki prejme dva seznama in vrne število skupnih elementov. Morebitne ponovljene elemente mora ignorirati.

   Klic `skupnih(["Ana", "Berta", "Ana", "Ana", "Cilka"], ["Cilka", "Dani", "Ana", "Ana"])` vrne 2, ker imate seznama dva skupna elementa (Ano in Cilko). To, da se Ana ponovi večkrat, ga ne zmede.

3. Napiši funkcijo `vseh(s, t)`, ki vrne število vseh elementov, ki se pojavijo v `s` ali `t` (ali v obeh).

   Klic `skupnih(["Ana", "Berta", "Ana", "Ana", "Cilka"], ["Cilka", "Dani", "Ana", "Ana"])` vrne 4, ker se v podanih seznamih pojavljajo 4 različna imena.

### Rešitev

Za `unikate` bomo najprej sestavili prazen seznam in vanj prepisovali elemente iz podanega seznama, vendar za vsakega poprej preverili, da ni morda že tam.

    def unikati(s):
        t = []
        for x in s:
            if x not in t:
                t.append(x)
        return t

Ker gre za čisto generične zadeve, bosta `s` in `t` primerni imeni za seznama.

Število `skupnih` elementov ugotovimo tako, da enega od seznamov pustimo čez unikati. Nato za vsakega od teh, unikatnih elementov, preverimo, ali se pojavi tudi v drugem seznamu.

    def skupnih(s, t):
        sk = 0
        for x in unikati(s):
            if x in t:
                sk += 1
        return sk

Drugega seznama ni treba "unificirati". Enega pa moramo, sicer bi ponovljene elemente šteli večkrat.

Vseh je toliko, kolikor je unikatnih v obeh skupaj.

    def vseh(s, t):
        return len(unikati(s + t))

Če že poznamo množice, sta zadnji dve funkciji (še) veliko preprostejši.

    def vseh(s, t):
        return len(unikati(s + t))

    def vseh(s, t):
        return len(set(s) | set(t))

Tudi prvo bi nas lahko zamikalo rešiti z množicami: seznam pretvorimo v množico, da se znebimo duplikatov

## Procesiranje seznamov

1. Napiši funkcijo `preberi_datoteko(ime_dat, locilo)`, ki prejme ime datoteke, podobne tem, s kakršnimi smo delali doslej. Razlika je le v tem, da ločilo med stolpci ni nujno vejica, zato je ločilo podano z drugim argumentom. Funkcija mora vrniti seznam seznamov. Vsak element vrnjenega seznama je vrstica, ki vsebuje podatke iz vrstice.

   Recimo, da imamo datoteko `kolesa.txt` s takšno vsebino:

       Cube-5031-159-Janez-2017
       Stevens-3819-1284-Ana-2012
       Focus-3823-1921-Benjamin-2019

   Klic `preberi_datoteko("kolesa.txt", "-")` mora vrniti seznam

       [['Cube', '5031', '159', 'Janez', '2017\n'],
        ['Stevens', '3819', '1284', 'Ana', '2012\n'],
        ['Focus', '3823', '1921', 'Benjamin', '2019\n']]

   (Ne vznemirjaj se zaradi `\n` v zadnjih elementih.)

   Nasvet: funkcija je zelo preprosta. V seznam trpaj, kar ti vrača `split`.

2. Napiši funkcijo `filtriran(s, stolpec, vrednost)`, ki prejme seznam, kakršnega vrača prejšnja funkcija in vrne nov seznam, ki vsebuje samo tiste elemente, ki imajo v podanem "stolpcu" `stolpec` (se pravi: na podanem indeksu) vrstici podano `vrednost`.

   Recimo, da imamo seznam

       s = [["Ana", 5, 9, "Berta"],
            ["Cilka", 5, 12, "Berta"],
            ["Ana", 5, 9, "Cilka"],
            ["Berta", 5, 1, "Ana"]]

   Klic `filtriran(s, 0, "Ana")` vrne seznam, ki vsebuje le tiste elemente seznama `s`, ki imajo v ničtem elementu niz `"Ana"`. Rezultat klica je torej

       [["Ana", 5, 9, "Berta"],
        ["Ana", 5, 9, "Cilka"]]

   Klic `filtriran(s, 3, "Berta")` vrne

       [["Ana", 5, 9, "Berta"],
        ["Cilka", 5, 12, "Berta"]]

   Klic `filtriran(s, 1, 5)` vrne kar celoten seznam, saj imajo na prvem mestu slučajno vsi ravno `5`.

3. Napiši funkcijo `izlusci(s, stolpec)`, ki vrne vse vrednosti, ki se pojavijo v podanem "stolpcu". Vrednosti morajo nastopati v originalnem vrstnem redu.

   Če je `s` seznam iz prejšnjega primera, potem klic `izlusci(s, 0)` vrne `["Ana", "Cilka", "Ana", "Berta"]`. Klic `izlusci(s, 1)` vrne `[5, 5, 5, 5]`. Klic `izlusci(s, 3)` vrne `["Berta", "Berta", "Cilka", "Ana"]`.

### Rešitev

Datoteke smo brali že tolikokrat, da sploh ni več česa komentirati.

    def preberi_datoteko(ime_dat, locilo):
        zapisnik = []
        for vrstica in open(ime_dat):
            zapisnik.append(vrstica.split(locilo))
        return zapisnik

Tudi s filtriranjem se nimamo kaj mujati: beremo vrstice in v seznam dajemo le tiste, ki imajo v pravem stolpcu pravo vrednost.

    def filtriran(s, stolpec, vrednost):
        t = []
        for vrstica in s:
            if vrstica[stolpec] == vrednost:
                t.append(vrstica)
        return t

Tudi `izlusci` je preprosta: v seznam zlagamo vse, kar najdemo v drugem stolpcu.

    def izlusci(s, stolpec):
        t = []
        for vrstica in s:
            t.append(vrstica[stolpec])
        return t

Dodajmo le še, da so vse tri funkcije klasični primeri nečesa, kar se bomo naučili narediti v eni sami vrstici.

    def preberi_datoteko(ime_dat, locilo):
        return [vrstica.split(locilo) for vrstica in open(ime_dat)]

    def filtriran(s, stolpec, vrednost):
        return [vrstica for vrstica in s if vrstica[stolpec] == vrednost]

    def izlusci(s, stolpec):
        return [vrstica[stolpec] for vrstica in s]

## Dražba

Čestitam, prišli ste do sem, programiranja je zdaj skoraj konec. Če boste pametni, boste poslej samo klicali funkcije, ki ste jih napisali doslej.

1. Napiši funkcijo `predmeti(ime_dat, oseba)`, ki prejme ime datoteke z zapisnikom dražbe in ime neke osebe. Vrniti mora seznam vseh predmetov, za katere se je zanimala ta oseba.

2. Napiši funkcijo `osebe(ime_dat, predmet)`, ki prejme ime datoteke z zapisnikom in ime predmeta. Vrniti mora osebe, ki so se zanimale za ta predmet.

3. Napiši funkcijo `podobnost_oseb(ime_dat, oseba1, oseba2)`. Ta prejme ime datoteke z zapisnikom in imeni dveh oseb. Vrniti mora podobnost oseb. Podobnost oseb je definirana kot število predmetov, za katere sta se zanimali obe osebi, deljenemu s številom predmetov, za katere se je zanimala ena ali druga ali obe. (Glej Jaccardov index).

   Klic `podobnost_oseb("zapisnik.txt", "Cilka", "Ema")` vrne 0.5. Cilka je hotela `['pozlačen dežnik', 'kip', 'srebrn jedilni servis']`, Ema pa `['Meldrumove vaze', 'kip', 'srebrn jedilni servis']`. Skupna predmeta sta 2 (kip in servis), vseh predmetov, za katere sta se zanimali (ena ali druga ali obe), pa 4. Funkcija vrne 2 / 4, torej 0.5.

4. Napiši funkcijo `podobnost_predmetov(ime_dat, predmet1, predmet2)`, ki prejme ime datoteke in imeni dveh predmetov. Vrniti mora podobnost predmetov. Ta je enaka številu oseb, ki so se zanimale za oba predmeta, deljenemu s številom oseb, ki so se zanimale za vsaj enega.

### Rešitev

Za `predmeti` preberemo datoteko, izfiltriramo ven tiste, ki imajo v prvem stolpcu ustrezno ime osebe, nato izluščimo vrednosti iz ničtega stolpca in poberemo ven unikate.

    def predmeti(ime_dat, oseba):
        zapisnik = preberi_datoteko(ime_dat, ",")
        z_osebo = filtriran(zapisnik, 1, oseba)
        predm = izlusci(z_osebo, 0)
        return unikati(predm)

Gre tudi v eni vrstici,

    def predmeti(ime_dat, oseba):
        return unikati(izlusci(filtriran(preberi_datoteko(ime_dat, ","), 1, oseba), 0))

Vendar se pri tem izgubimo v klicih, oklepajih in argumentih. Preglednejše je lepo sproti zlagati v spremenljivke.

Funkcija `osebe` je analogna.

    def osebe(ime_dat, predmet):
        zapisnik = preberi_datoteko(ime_dat, ",")
        s_predmetom = filtriran(zapisnik, 0, predmet)
        oseb = izlusci(s_predmetom, 1)
        return unikati(oseb)

Preden se lotimo funkcij `podobnost_oseb` in `podobnost_predmetov` si lahko samoiniciativno napišemo funkcijo `podobnost`, ki meri podobnost seznamov `s` in `t`.

    def podobnost(s, t):
        return skupnih(s, t) / vseh(s, t)

Zdaj sta funkciji `podobnost_oseb` in `podobnost_predmetov` le še

    def podobnost_oseb(ime_dat, oseba1, oseba2):
        return podobnost(predmeti(ime_dat, oseba1), predmeti(ime_dat, oseba2))

    def podobnost_predmetov(ime_dat, predmet1, predmet2):
        return podobnost(osebe(ime_dat, predmet1), osebe(ime_dat, predmet2))

## Priporočilni sistem (Dodatna, neobvezna naloga)

Neobvezno, vendar preprosto, sploh, če uporabite funkcijo `argmax`, ki smo jo napisali na predavanju. Kar skopirajte jo v datoteko s svojim programom.

1. Napiši funkcijo `priporoci_predmet(ime_dat, predmet)`, ki prejme ime datoteke in ime nekega predmeta. Vrne naj predmet, ki je najbolj podoben temu predmetu. (Seveda je vsak predmet najbolj podoben samemu sebi; vrniti mora naslednji najpodobnejši predmet.)

2. Napiši funkcijo `priporoci_prijatelja(ime_dat, oseba)`, ki prejme ime datoteke in ime osebe ter vrne najbolj podobno osebo.

    def argmax(s):
        max_k = max_v = None
        for k, v in s:
            if max_v is None or v > max_v:
                max_k = k
                max_v = v
        return max_k

    def priporoci_predmet(ime_dat, predmet):
        podobnosti = []
        for predmet2 in unikati(izlusci(preberi_datoteko(ime_dat, ","), 0)):
            if predmet2 != predmet:
                podobnosti.append((predmet2, podobnost_predmetov(ime_dat, predmet, predmet2)))
        return argmax(podobnosti)

    def priporoci_prijatelja(ime_dat, oseba):
        podobnosti = []
        for oseba2 in unikati(izlusci(preberi_datoteko(ime_dat, ","), 1)):
            if oseba2 != oseba:
                podobnosti.append((oseba2, podobnost_oseb(ime_dat, oseba, oseba2)))
        return argmax(podobnosti)