Testi

Testi: testi-objekti-v-orbiti.py

Obvezna naloga

Sorry, moral sem. Ker gre dobro k naslovu.

V tej nalogi bomo počeli nekaj podobnega kot v prejšnji. Imeli bomo razred Luna, ki bo poznal imena lun, ki krožijo okrog njega.

Sprogramirati bo potrebno dva razreda. Preden se lotiš prvega, preberi tudi navodila za drugega, da ti ne bo potrebno potem spreminjati.

Napiši razred Luna z naslednjimi metodami:

  • konstruktor - napiši ga, če se ti zdi potrebno. Ne sprejema argumentov, stori pa naj, kar se ti zdi pametno.
  • pripni(ime) si zabeleži, da okrog te lune kroži (tudi) luna z imenom ime. Metoda ne vrne ničesar.
  • lune() vrne množico vseh lun, ki krožijo okrog podane lune.
  • ima_luno(ime) vrne True, če je med lunami, ki krožijo okrog te lune, tudi luna s podanim imenom, in False, če ne.
  • stevilo_lun() vrne število lun, ki krožijo okrog podane lune.

Tule je primer klicanja teh metod.

>>> a = Luna()
>>> a.pripni("b")
>>> a.pripni("c")
>>> a.lune()
{'b', 'c'}
>>> a.stevilo_lun()
2
>>> a.ima_luno("foo")
False
>>> a.pripni("foo")
>>> a.lune()
{'foo', 'b', 'c'}
>>> a.stevilo_lun()
3
>>> a.ima_luno("foo")
True

Poleg tega sprogramiraj razred EkskluzivnaLuna, okrog katere lahko krožijo največ tri lune. Če dodamo četrto, odstrani prvo. Če dodamo še eno, odstrani drugo... Skratka, odstranjuje jih v takšnem vrstnem redu, v kakršnem smo jih dodajali; vedno obdrži zadnje tri.

Razred EkskluzivnaLuna naj bo izpeljan iz razreda Luna in naj spremeni samo metodo pripni. Tudi dodati ne sme nobene metode.

>>> b = EkskluzivnaLuna()
>>> b.pripni("Cilka")
>>> b.pripni("Ana")
>>> b.pripni("Ema")
>>> b.lune()
{'Ana', 'Ema', 'Cilka'}
>>> b.pripni("Berta")  # pri tem odstrani Cilko, ki je prišla prva
>>> b.lune()
{'Berta', 'Ema', 'Ana'}
>>> b.pripni("Dani")  # in tu odide Ana, ker je druga najstarejša
>>> b.lune()
{'Berta', 'Ema', 'Dani'}

Kot je očitno iz gornjega primera, se ob pripenjanju četrte lune ne odstrani "prva luna iz množice", saj množice nimajo vrstnega reda. Očitno bo moral razred Lune shranjevati lune na tak način, da bo vedel, v kakšnem vrstnem redu jih je dodajal. Spomni se na naloge iz vaj.

Rešitev

Razred Luna ni čisto nič posebnega: Luna mora vedeti le, katere lune krožijo okrog nje.

Prva past: človek bi poimenoval atribut, v katerem bodo shranjene lune, lune. Vendar naloga zahteva metodo s tem imenom. Če napišemo

class Luna:
    def __init__(self):
        self.lune = set()

    def lune(self):
        return lune

in potem ustvarimo objekt luna = Luna(), bo luna.lune prazna množica in ne metoda. Ime luna smo v __init__-u pač povozili, da se ne nanaša več na metodo temveč na neko množico. (Če bi kdo pripomnil, da ni prav, da Python to dopušča, bi mu rekli, da so Pythonovi razredi v resnici narejeni zelo preprosto in mu zagotovili, da bi se mu ta lastnost, če bi boljše poznal Pyhonove razrede, v bistvu zdela imenitna. Poleg tega pa nam pride zelo prav pri testiranju resnične kode v praksi.)

Druga past: v razredu EkskluzivnaLuna bo potrebno poznati vrstni red dodajanja lun. Množicam za vrstni red ni mar, torej bomo morali lune shranjevati v seznam. Ker mora metoda luna vrniti množico, bomo seznam kar sproti pretvorili.

class Luna:
    def __init__(self):
        self.pripete = []

    def pripni(self, ime):
        self.pripete.append(ime)

    def lune(self):
        return set(self.pripete)

    def ima_luno(self, ime):
        return ime in self.pripete

    def stevilo_lun(self):
        return len(self.pripete)

Razred EkskluzivnaLuna dopolni metodo pripni tako, da pokliče podedovano metodo, nato pa obdrži le prve tri elemente (ali manj, če jih je manj).

class EkskluzivnaLuna(Luna):
    def pripni(self, ime):
        super().pripni(ime)
        self.pripete = self.pripete[-3:]

Dodatna naloga

Pazi to: z metodo pripni lahko na Luno pripneš tudi drugo Luno, ne le njenega imena.

com = Luna()
b = Luna()
g = Luna()
h = Luna()
c = Luna()
d = Luna()
e = Luna()
i = Luna()

com.pripni(b)
b.pripni(g)
g.pripni(h)
b.pripni(c)
c.pripni(d)
d.pripni(e)
d.pripni(i)

Pozor: ne piše b.pripni("g") temveč b.pripni(g). Luna b v svojem seznamu nima niza "g" temveč kar Luno, ki je shranjena v spremenljivki g. Objekt vsebuje objekt, ker ... zakaj ne.

To, kar je napisano zgoraj, deluje samo od sebe, če si pravilno sprogramiral(a) obvezno nalogo.

Pač pa razredu Luna zdaj dodaj še metode:

  • ima_odvisnika(x) vrne True, če je med odvisniki lune (tudi) luna x

    >>> b.ima_odvisnika(g)
    True
    >>> d.ima_odvisnika(g)
    False
    
  • n_odvisnikov() vrne število odvisnikov te lune

    >>> b.n_odvisnikov()
    6
    

    (primer velja za gornje lune, ki ne predstavljajo celotne slike iz prejšnje domače naloge)

    Nasvet: tule ti ne bo potrebno obračati slovarja, tako kot smo ga v prejšnji domači nalogi. Vse, kar potrebuješ, že imaš.

  • sirina_orbite(n) vrne širino orbite na n-tem nivoju

    >>> com.sirina_orbite(2)
    2
    >>> c.sirina_orbite(2)
    2
    

    Funkcijo sirina_orbite lahko, če želiš, skopiraš iz svoje ali celo iz moje rešitve prejšnje naloge, in jo seveda ustrezno prirediš, saj je šlo tam za funkcijo, tu pa za metodo.

Te tri metode nimajo argumenta orbite, kot smo ga imeli v prejšnji domači nalogi. To ni napaka.

Rešitev

Lotimo se najprej n_odvisnikov. Zaradi primerjave s prejšnjo domačo nalogo. Tam je bila ena od možnih rešitev takšna.

def n_odvisnikov(luna, orbite):
    pripete = lune(orbite)[luna]
    odvisnikov = len(pripete)
    for luna in pripete:
        odvisnikov += n_odvisnikov(luna, orbite)
    return odvisnikov

Funkcija je prejela dva argumeta: luno, katere odvisniki nas zanimajo, in slovar, v katerem je za vsako luno zapisano, kdo kroži okrog nje.

Tu je metoda videti tako:

    def n_odvisnikov(self):
        odvisnikov = len(self.pripete)
        for luna in self.pripete:
            odvisnikov += luna.n_odvisnikov()
        return odvisnikov

Funkcija še vedno dobi kot argument luno, katere odvisniki nas zanimajo, le da se ta argument zdaj ne imenuje luna, temveč, po splošnem dogovoru v Pythonu, self. Pomembno pa je, da ne dobi več argumenta orbite. V prejšnji domači nalogi so bili podatki o tem, kaj kroži okrog te lune, shranjeni v ločenem slovarju (za nekaj dodatnega šikaniranja študentov pa je bilo potrebno ta slovar še obračati, tako da smo do lun prišli z lune(orbite)[luna]). Tu pa luna sama zase ve, kdo kroži okrog nje; podatek o tem je shranjen v self.pripete.

Tudi rekurzivni klic zdaj ni več n_odvisnikov(luna, orbite) temveč luna.n_odvisnikov(). Lahko si predstavljamo (in ta predstava bi tudi kar ustrezala resnici), da funkcija ne kliče več rekurzivno same sebe, temveč metoda ene lune kliče metodo druge lune. (Tehnično pa gre še vedno za isto funkcijo, le z drugim self-om.)

Na podoben način se poenostavi funkcija sirina_orbite.

    def sirina_orbite(self, n):
        if n == 0:
            return 1
        sirina = 0
        for luna in self.pripete:
            sirina += luna.sirina_orbite(n - 1)
        return sirina

Nekoliko pa so me užalostila vprašanja glede metode ima_odvisnika. Pravilna rešitev je

    def ima_odvisnika(self, koga):
        if koga in self.pripete:
            return True
        for luna in self.pripete:
            if luna.ima_odvisnika(koga):
                return True
        return False

Če ima self med pripetimi lunami tudi iskano, vrnemo True. Sicer gremo prek vseh pripetih lun, vsako vprašamo, če ima tega odvisnika in če odgovori, da ga ima, vrnemo True. Sicer vrtimo zanko naprej in ko se izteče, vrnemo False. Kar nekaj študentov pa je napisalo tole:

    # Ta metoda ne deluje pravilno!
    def ima_odvisnika(self, koga):
        if koga in self.pripete:
            return True
        for luna in self.pripete:
            return luna.ima_odvisnika(koga):
        return False

Ta zanka se izvede le enkrat (ali nikoli, če luna nima podlun). Torej je to isto, kot če bi napisali

    # Ta metoda ne deluje pravilno!
    def ima_odvisnika(self, koga):
        if koga in self.pripete:
            return True
        if self.pripete:
            return self.pripete[0].ima_odvisnika(koga)
        return False

To preveri le prvo luno. To je žalostno zato, ker je isto, kot če bi pisali funkcijo, ki preveri, ali je v seznamu kakšno sodo število in jo zavozili takole:

def obstaja_sodo(s):
    for x in s:
        return x % 2 == 0

kar je seveda isto kot

def obstaja_sodo(s):
    return s[0] % 2 == 0

Zoprno je, da pri tem ne gre za težave z rekurzijo temveč že z veliko zgodnejšo snovjo, namreč zankami in pogoji.

Vse tri metode se da napisati tudi veliko krajše. Celoten razred Luna je lahko tak:

class Luna:
    def __init__(self):
        self.pripete = []

    def pripni(self, ime):
        self.pripete.append(ime)

    def lune(self):
        return set(self.pripete)

    def ima_luno(self, ime):
        return ime in self.pripete

    def stevilo_lun(self):
        return len(self.pripete)

    # Dodatna
    def ima_odvisnika(self, koga):
        return koga in self.pripete \
               or any(luna.ima_odvisnika(koga) for luna in self.pripete)

    def n_odvisnikov(self):
        return len(self.pripete) \
               + sum(luna.n_odvisnikov() for luna in self.pripete)

    def sirina_orbite(self, n):
        return n == 0 or sum(luna.sirina_orbite(n - 1) for luna in self.pripete)

Lastnost modernih jezikov je, da so jedrnati, ne da bi bili nepregledni. S pomočjo funkcijskega sloga programiranja je možno veliko funkcij napisati z enim samim izrazom (po domače: v eni vrstici).

(Hack je samo v zadnji funkciji. Če je n == 0 enak True, funkcija vrne True, kar je isto kot 1. Če je False, pa vrne tisto, kar sledi or-u.)

Za κῦδος

Problem: pozabil sem, kaj sem vam hotel zastaviti kot nalogo za κῦδος. Pozabljiv star profesor pač. Vse, kar mi je ostalo, so testi - te sem na srečo že napisal. No, pa začetek definicije nekega razreda. Očitno je bila vaša naloga, da napišete takšen razred.

class BiLuna:
    def __repr__(self):
        return f'BiLuna("{self.ime}")'

    __str__ = __repr__

    def __init__(self, ime, center):
        self.ime = ime

Tisti __repr__ in __str__ nista preveč pomembna, napisal sem ju, da bi lažje razumeli, kar javljajo testi. Pustite ju pri miru.

Nadaljevanje konstruktorja očitno še manjka, poleg tega pa manjka še par metod, ki jih zahtevajo testi. Naloga za κῦδος: poglej teste in napiši manjkajoče metode.

Spomnim se še nečesa: vsi podatki naj bi bili shranjeni v BiLuna. Nobenih ekstra slovarjev, nobenih globalnih spremenljivk, ničesar. Vse je shranjeno v objektih BiLuna.

Ponovno se opravičujem za to blamažo, ampak saj se boste znašli. :)

Rešitev

Iz testov je bilo možno razbrati, da ima BiLuna tudi metodo zamenjaj_center, za katero ste z malo trudi lahko ugotovili, da zamenja luno, okrog katere kroži luna self.

Pravi razmislek je bil v tem: ker luna ve, katere lune krožijo okrog nje, mora luna, ki se odloči krožiti kje drugje, obvestiti luno, okrog katere je krožila doslej, da ne kroži več okrog nje. Za to pa mora luna vedeti, okrog katere lune kroži. Povezave so zdaj torej dvosmerne: luna ima atribut pripete s pripetimi lunami in _center z luno, okrog katere kroži. Podčrtaj na začetku je potreben, da se ime atributa ne stepe z imenom zahtevane metode, center.

class BiLuna:
    def __repr__(self):
        return f'BiLuna("{self.ime}")'

    __str__ = __repr__

    def __init__(self, ime, center):
        self.ime = ime
        self.pripete = set()
        self._center = None
        self.zamenjaj_center(center)

    def pripni(self, luna):
        self.pripete.add(luna)

    def odpni(self, luna):
        self.pripete.remove(luna)

    def center(self):
        return self._center

    def lune(self):
        return self.pripete

    def zamenjaj_center(self, center):
        if self._center:
            self._center.odpni(self)
        self._center = center
        if self._center:
            self._center.pripni(self)

V __init__-u nastavimo _center na None in takoj pokličemo zamenjaj_center, da ga ustrezno nastavi. Ker iz tega razreda ne bomo izpeljevali razreda EkskluzivnaLuna, je pripete lahko kar množica.

Glavna reč tu pa je zamenjaj_center. Ta mora najprej preveriti, ali luna kroži okrog katere lune in jo v tem primeru odpeti. Nato si zapiše novi center. Če ta, novi center ni None, ga obvesti, da se je luna pripela nanj.

Poleg tega so testi zahtevali še metodo dosegljivo, ki pove, ali obstaja pot med to luno in neko drugo, podano luno. To je podobno nalogi pot_med iz prejšnje domače naloge, zato jo tudi rešimo podobno: zapeljimo se do korena drevesa, torej vso pot nazaj po centrih. Potem naberimo vse lune, ki so v tem poddrevesu in preverimo, ali je podana luna med njimi.

Metodi, ki poiščeta koren in vrneta poddrevo, bomo napisali ločeno.

    def koren(self):
        luna = self
        while luna._center:
            luna = luna._center
        return luna

    def poddrevo(self):
        pod = {self}
        for luna in self.pripete:
            pod |= luna.poddrevo()
        return pod

    def dosegljivo(self, luna):
        return luna in self.koren().poddrevo()

Z nekaj spretnosti se z rekurzijo in ščepcem funkcijskega programiranja znebimo zank.

    def poddrevo(self):
        from functools import reduce
        return {self} | reduce(set.union, (luna.poddrevo() for luna 
        in self.pripete), set())

    def koren(self):
        return self if self._center is None else self._center.koren()

    def dosegljivo(self, luna):
        return luna in zacetek.poddrevo()
Zadnja sprememba: četrtek, 25. marec 2021, 21.25