Testi

Testi: testi-filmski-igralci.py

Naloga

Ta domača naloga se ocenjuje in vam ne sme manjkati.

Za določeno oceno morate rešiti tudi vse naloge, potrebne za nižjo oceno. Za, na primer, oceno 7, morate rešiti tudi naloge za oceno 6 in tako naprej.

Ocena 6

Imamo seznam parov imen igralcev in filmov, v kateri so igrali, na primer

[("Ana", "Od Čateža do Litije"),
 ("Berta", "Od Čateža do Litije"),
 ("Ana", "Harry Potter 4"),
 ("Cilka", "Harry Potter 4"),
 ("Berta", "Star Trek DS-9"),
 ("Dani", "Harry Potter 4"),
 ("Ema", "Star Trek DS-9"),
]

Če igralec igra v več filmih, se pojavi večkrat; tako je Ana igrala v Od Čateža do Litije in v Harry Potter 4.

Napiši naslednje funkcije

  • igralci(povezave) prejme seznam, kot je gornji, in vrne množico imen igralcev,
  • filmi(povezave) vrne množico imen filmov,
  • filmi_igralca(igralec, povezave) vrne množico imen filmov, v katerih je igral podani igralec,
  • igralci_filma(film, povezave) vrne množico imen igralcev, ki so nastopali v podanem filmu,
  • po_igralcih(povezave) vrne slovar, katerega ključi so imena igralcev, pripadajoče vrednosti pa množice imen filmov, v katerih so igrali ti igralci, na primer python {"Ana": {"Od Čateža do Litije", "Harry Potter 4"}, "Berta": {"Od Čateža do Litije", "Star Trek DS-9"}, "Cilka": {"Harry Potter 4"}, "Dani": {"Harry Potter 4"}, "Ema": {"Star Trek DS-9"} }
  • po_filmih(povezave) vrne slovar, katerega ključi so filmi, pripadajoče vrednosti pa množice imen igralcev.

Rešitev

Napisali bomo le rešitve v eni vrstici. Iz ene vrstice v več gre po preprostem vzorcu: return {izraz for spremenljivke in nekaj} zamenjamo z

r = set()
for spremenljivke in nekaj:
    r.add(izraz)
return r

če gre za slovar, pa je zgodba praktično enaka. (Seveda gre enako preprosto tudi v drugo smer, če je funkcija napisana v primerni obliki.)

def igralci(povezave):
    return {igralec for igralec, _ in povezave}

def filmi(povezave):
    return {film for _, film in povezave}

def filmi_igralca(igralec, povezave):
    return {film for igralec2, film in povezave if igralec2 == igralec}

def igralci_filma(film, povezave):
    return {igralec for igralec, film2 in povezave if film2 == film}

def po_igralcih(povezave):
    return {igralec: filmi_igralca(igralec, povezave) for igralec in igralci(povezave)}

def po_filmih(povezave):
    return {film: igralci_filma(film, povezave) for film in filmi(povezave)}

Vseeno je tu na mestu nekaj komentarjev. - Tole ne gre - ali pa je zelo zapleteno -, če vaše funkcije ne kličejo funkcijo, ki ste jih napisali predtem. Konkretno, funkcij filmi_igralca in igralci_filma, v kasnejših nalogah za višje ocene pa še drugih. - Prav tako je tole veliko bolj zapleteno, če niste ubogali in ne pišete zank for tako, da v njih razpakirate terke. Se pravi, če ste navajeni namesto for igralec, film in povezave pisati for i in range(len(povezave)) in potem kakšne klobase v slogu povezave[i][0], se boste hitro izgubili. - Končno, to ne gre, če pišete stvari kot if pogoj: pass else: <naredi nekaj> in podobno. Za oceno 8 ste se morali torej naučiti predvsem programirati tako lepo, kot se učimo in na samo dovolj dobro, da deluje. :)

Še ena stvar, na katero moram opozoriti, je, da zelo radi sestavljate sezname, ob katerih se počutite lagodneje, in iz njih šele na koncu naredite množico. To še bolj velja za tiste, ki niste poskušali napisati funkcije v eni vrstici. Ni treba. Tako kot imajo seznami append, imajo množice add.

Ocena 7

Napiši funkcije

  • soigralci(igralci_filmi), ki prejme takšen slovar, kot ga vrača funkcija po_igralcih, kot rezultat pa vrne množico parov igralcev, ki so se kdaj srečali v kakem filmu. Vsak par naj bo urejen po abecedi. Za gornji slovar bi funkcija vrnila {("Ana", "Berta"), ("Ana", "Cilka"), ("Ana", "Dani"), ("Berta", "Ema"), ("Cilka", "Dani")}. Tako, je, na primer, ("Berta" "Ema") v množici zato, ker sta Berta in Ema skupaj nastopali v "Star Trek DS-9".

  • n_soigralcev(igralec, pari) prejme ime igralca in seznam parov, kakršnega vrača prejšnja funkcija. Vrne število vseh igralcev, s katerimi je kdaj sodeloval podani igralec. Klic n_soigralcev("Dani", pari) (kjer so pari gornji seznam parov), vrne 2, saj je Dani igrala skupaj z Ano in Cilko.

  • soigralci_igralca(igralec, pari) dobi enake argumente kot prejšnja funkcija, kot rezultat pa vrne množico igralcev, s katerimi je sodeloval podani igralec. soigralci_igralca("Dani", pari) vrne {"Ana", "Cilka"}.

Rešitev

Te so že bolj zanimive. :)

def soigralci(igralci_filmi):
    return {(igralec1, igralec2)
            for igralec1, filmi1 in igralci_filmi.items()
            for igralec2, filmi2 in igralci_filmi.items()
            if igralec1 < igralec2 and filmi1 & filmi2}

Pri tej ste imeli dva velika problema. Prvi je, seveda, ugotavljanje, ali sta dva igralca sodelovala pri kakem filmu. Tu ste mnogi napisali eno ali dve dodatni zanki znotraj zank. Na predavanjih sem rekel, da vam bodo prišle množice zelo prav, če se boste spomnili nanje. Tu vam jih naloga vsiljuje! Imamo množici filmov, v katerih sta igrala igralca in zanima nas pač, ali je njun presek neprazen.

Nekateri ste to preverjali z filmi1 & filmi2 != set() ali len(filmi1 & filmi2) == 0. Vendar to kompliciranje ni potrebno: prazna množica je neresnična in neprazna resnična.

Naslednji kamen spotike je, kako urediti terko, saj naloga zahteva, naj bodo urejene po abecedi. To je bilo še bolj zanimivo opazovati. Napisali ste igralec1 != igralec2, nato sestavili terko in jo poskušali urediti, kar se vam ni posrečilo na različne načine. V resnici pa se rešimo preprosto tako, da zahtevamo igralec1 < igralec2. Če je večji, ju bomo že še srečali v zamenjanem vrstnem redu.

def n_soigralcev(igralec, pari):
    return sum(igralec in par for par in pari)

Tu bi lahko seveda sestavili množico in prešteli njene elemente ali, še preprosteje, poklicali naslednjo funkcijo. A smo rešili na malo bolj zabaven način. Gremo čez vse pare in se za vsak par vprašamo, ali vsebuje podanega igralca, se pravi igralec in par. Rezultat tega je True ali False, kar je toliko kot 1 in 0. To seštejemo, pa bomo izvedeli, koliko je bilo enk, se pravi, kolikokrat se je igralec pojavil.

def soigralci_igralca(igralec, pari):
    return {igralec1 for igralec1, igralec2 in pari if igralec2 == igralec} | \
           {igralec2 for igralec1, igralec2 in pari if igralec1 == igralec}

Tale pa vam je dala še malo več vetra. :) Sestavimo lahko množico tistih, s katerimi je podani igralec v paru kot drugi element, in množico tistih, pri katerih je prvi. Vrnemo unijo obeh.

Če nočemo sestavljati dveh množic, moramo uporabiti if-else v neki drugi vlogi, v kateri ju nismo spoznali. Za tiste, ki jih zanima:

def soigralci_igralca(igralec, pari):
    return {igralec1 if igralec2 == igralec else igralec2
            for igralec1, igralec2 in pari
            if igralec in (igralec1, igralec2)}

Ocena 8

Vse funkcije za oceno 6 in 7 napiši z uporabo izpeljanih slovarjev in množic, tako da bo funkcija vsebovala samo return *nekaj*.

Rešitev

Smo že. :)

Ocena 9

Moč povezave med dvema igralcema izračunamo tako, da preverimo, v koliko skupnih filmih sta igrala. Filme bi lahko preprosto prešteli ... vendar jih ne bomo, saj filmi z manj igralci vežejo močneje od takšnih, kjer je igralcev veliko. "Moč" filma je enaka 2 / kvadrat števila igralcev.

Kako močno sta povezani Ana in Berta? Igrali sta v Od Čateža do Litije, ki ima 2 igralca, in v Harry Potter 4, ki ima (kot pove že ime) 4. Povezava med Ano in Berto je torej 2 / 2 ** 2 + 2 / 4 ** 2 = 2 / 4 + 2 / 16 = 10 / 16 = 0.625.

Napiši funkciji:

  • moc_povezave(igralec1, igralec2, povezave), ki kot argument dobi imeni dveh igralcev in seznam povezav v obliki iz naloge za oceno 6. Kot rezultat vrne moč povezave. Klic moc_povezave("Ana", "Berta", povezave) vrne 0.625;

  • utezene_povezave(povezave) prejme le povezave, kot rezultat pa vrne slovar, katerega ključi so vsi pari imen igralcev (vsak par nastopa le enkrat in je urejen po abecedi), pripadajoče vrednosti pa so moči povezav, kot jih vrača prejšnja funkcija.

Pa še nekaj: obe funkciji morata biti napisani v eni vrstici.

Rešitev

Pogledamo vse skupne filme teh dveh igralcev: filmi_igralca(igralec1, povezave) & filmi_igralca(igralec2, povezave). Za vsak skupni film (for film in filmi_igralca(igralec1, povezave) & filmi_igralca(igralec2, povezave)) pogledamo, koliko je 2 deljeno s kvadratom števila igralcev v tem filmu, 2 / len(igralci_filma(film, povezave)) ** 2. To seštejemo.

def moc_povezave(igralec1, igralec2, povezave):
    return sum(2 / len(igralci_filma(film, povezave)) ** 2
               for film in filmi_igralca(igralec1, povezave) & filmi_igralca(igralec2, povezave))

Utežene povezave so potem preproste: za vsak par igralcev (for igralec1, _ in povezave for igralec2, _ in povezave, spremenljivko z imenom _ navadno uporabimo za nekaj, česar v resnici ne potrebujemo) pogledamo moč povezave in to pridno zložimo v slovar.

def utezene_povezave(povezave):
    return {(igralec1, igralec2): moc_povezave(igralec1, igralec2, povezave)
            for igralec1, _ in povezave for igralec2, _ in povezave
            if igralec1 < igralec2}

Ocena 10

Napiši funkciji

  • povezani_z(igralec, pari), ki prejme ime igralca in seznam parov igralcev, ki so kdaj sodelovali. Kot rezultat množico imen vseh igralcev, ki so sodelovali s katerim od igralcev, ki je sodeloval s katerim od igralcev, ki je sodeloval s katerim od igralcev ... ki je sodeloval s podanim igralcem. Rezultat vključuje tudi podanega igralca samega.

    Klic povezani_z("Ana", [("Ana", "Berta"), ("Berta", "Cilka"), ("Dani", "Ema"), ("Berta", "Fanči"), ("Greta", "Helga")] vrne množico {"Ana", "Berta", "Cilka", "Fanči"}; Ana je sicer neposredno sodelovala le z Berto, vendar je ta sodelovala tudi s Cilko in Fanči.

    Klic povezani_z("Ana", [("Ana", "Berta"), ("Berta", "Cilka"), ("Dani", "Ema"), ("Berta", "Fanči"), ("Greta", "Helga"), ("Ema", "Fanči")]) vrne {"Ana", "Berta", "Cilka", "Dani", "Ema", "Fanči"}. V primerjavi s prejšnjim klicem imamo še par Ema in Fanči, ki z Ano (prek Berte in Fanči), poveče še Emo, prek Eme pa še Dani.

  • otoki(pari) vrne seznam vseh "otokov" nepovezanih igralcev. Vsak otok je predstavljen z množico. Vrstni red otokov v seznamu je poljuben.

    Klic otoki([("Ana", "Berta"), ("Berta", "Cilka"), ("Dani", "Ema"), ("Berta", "Fanči"), ("Greta", "Helga")]) vrne [{"Ana", "Berta", "Cilka", "Fanči"}, {"Dani", "Ema"}, {"Greta", "Helga"}].

    Klic otoki([("Ana", "Berta"), ("Berta", "Cilka"), ("Dani", "Ema"), ("Berta", "Fanči"), ("Greta", "Helga"), ("Ema", "Fanči")]) vrne [{"Ana", "Berta", "Cilka", "Fanči", "Dani", "Ema"}, {"Greta", "Helga"}].

Teh dveh funkcij ni potrebno napisati v eni vrstici. Pravzprav bi bilo to precej zoprno.

Rešitev

Tidve pa sta v resnici malo težji. Navsezadnje zanju dobite oceno 10. Tule objavljam elegantni rešitvi (šlo bi tudi malo hitrejše, a daljše), vendar bomo veseli tudi malo manj elegantnih.

def povezani_z(igralec, pari):
    povezani = [igralec]
    for igralec in povezani:
        for soigralec in soigralci_igralca(igralec, pari):
            if soigralec not in povezani:
                povezani.append(soigralec)
    return set(povezani)

Čeprav mora funkcija vrniti množico, bomo sestavljali seznam. (Zakaj, boste videli.) Sestavimo torej seznam povezani, ki v začetku vsebuje prvega igralca. Nato gremo prek seznama povezanih in za vsakega storimo naslednje. Pogledamo soigralce tega igralca. Za vsakega preverimo, ali je že povezan. Če še ni, ga dodamo med povezane.

In to je to. :)

Zakaj seznam? Zato, ker je zanka for pripravljena iti prek seznama, ki se spreminja. To nas je v preteklosti kdaj teplo - recimo takrat, ko smo znotraj zanke for poskušali brisati elemente seznama, zato se nam je ta "izpodmikal". Tule pa nam pride prav, saj na ta način sproti podaljšujemo seznam ljudi, ki jih je potrebno še pregledati.

def otoki(pari):
    neobiskani = {igralec1 for igralec1, _ in pari} \
        | {igralec2 for _, igralec2 in pari}
    o = []
    while neobiskani:
        otok = povezani_z(neobiskani.pop(), pari)
        o.append(otok)
        neobiskani -= otok
    return o

Najprej sestavimo množico vseh igralcev - ker se bo izkazalo, da je ta za tole bolj praktična. Dobimo jo kot unijo množice vseh, ki nastopajo kot prvi element para in vseh, ki nastopajo kot drugi. To množico imenujemo neobiskani, ker bo vsebovala vse, ki je še nismo uvrstili v nobeno otok ali, v jeziku nekega drugega predmeta, "obiskali".

Poleg tega si pripravimo seznam o, ki bo vseboval otoke.

Zdaj pa le ponavljamo: dokler je potrebno obiskati še koga, sestavimo otok iz vseh, ki so povezani z nekim naključnim še neobiskanim (dobimo ga z neobiskani.pop()). Otok damo v seznam otokov in vse njegove "prebivalce" odstranimo iz množice neobiskanih (kar je razlog, da je to množica).

Tidve nalogi sodita že malo na področje algoritmov in podatkovnih struktur. Vendar sta še dovolj preprosti za odlično oceno iz Programiranja 1. :)

Last modified: Wednesday, 24 March 2021, 3:54 PM