Premoženje Novakovih

Pri tokratni nalogi je mogoče "goljufati" tako, da pri, recimo, funkciji premozenje(oseba, denar), pokličeš (rekurzivno) funkcijo, ki vrne imena vseh članov rodbine posamezne osebe, potem pa preprosto, brez rekurzije, sešteješ, koliko denarja imajo. To bo preživelo teste in bo priznano kot pravilna rešitev. Ali je to pametno, presodi sam(a).

Obvezna naloga

V (globalnem) slovarju otroci je podan rodovnik Novakovih (kot na predavanjih). Funkcije kot argument prejmejo ime osebe (oseba) in slovar denar, ki pove, koliko denarja ima katera oseba.

Napiši funkcijo premozenje(oseba, denar), ki pove, kolikor denarja imajo (skupaj) člani rodbine podane oseb.

Napiši funkcijo najbogatejsa(oseba, denar), ki vrne terko z imenom najbogatejše osebe in količino njenega denarja.

Rešitev

Premoženje rodbine določene osebe dobimo tako, da k njenemu denarju prištejemo premoženje rodbin njenih otrok.

def premozenje(oseba, denar):
    return denar[oseba] + sum(premozenje(otrok, denar) for otrok in otroci[oseba])

Najbogatejšo v rodbini določene osebe dobimo tako, da najprej predpostavimo, da je najbogatejša oseba kar ta oseba. Nato gremo čez vse otroke in vrašamo po najbogatejši osebi v njihovih rodbinah. Če je kdo od njih bogatejši od najbogatejše osebe doslej, si to zapomnimo. Na koncu vrnemo ime najbogatejše najdene osebe in njeno količino denarja.

def najbogatejsi(oseba, denar):
    naj_oseba, naj_denar = oseba, denar[oseba]
    for otrok in otroci[oseba]:
        ta_naj, ta_denar = najbogatejsi(otrok, denar)
        if ta_denar > naj_denar:
            naj_oseba, naj_denar = ta_naj, ta_denar
    return naj_oseba, naj_denar

Dodatna naloga

Rodbina določene osebe je uravnotežena, če imajo rodbine vseh njenih otrok enako denarja in so tudi same uravnotežene.

Napiši funkcijo uravnotezeni(oseba, denar), ki vrne True, če je rodbina podane osebe uravnotežena.

Napiši funkcijo neuravnotezeni(oseba, denar), ki vrne ime tiste osebe znotraj rodbine podane osebe, ki ima neuravnoteženo rodbino, ker rodbine njenih otrok niso enako premožne. Predpostaviš lahko, da je takšna kvečjemu ena oseba. Če je ni, naj funkcija vrne None.

Rešitev

Tidve funkciji sta (lahko) malo bolj zoprni.

Rodbina določene osebe je uravnotežena, če se uravnotežene rodbine vseh otrok in če imajo rodbine vseh otrok enako denarja. Drugi pogoj preverimo tako, da premoženja rodbin otrok zložimo v množico in preverimo, ali ima ta množica manj kot dva elementa, len({premozenje(otrok, denar) for otrok in otroci[oseba]}) < 2.

Tako dobimo

def uravnotezeni(oseba, denar):
    return all(uravnotezeni(otrok, denar) for otrok in otroci[oseba]) \
        and len({premozenje(otrok, denar) for otrok in otroci[oseba]}) < 2

To ni posebej dobra rešitev, saj zelo velikokrat pokliče funkcijo premozenje: za vsako osebo jo pokliče tolikokrat, koliko prednikov ima, in potem še enkrat. Je pa relativno preprosta. Bolj kot tale:

def uravnotezeni(oseba, denar):
    koliko_vsak = None
    for otrok in otroci[oseba]:
        denar_rodbine = uravnotezeni(otrok, denar)
        if denar_rodbine is False:
            return False
        if koliko_vsak is None:
            koliko_vsak = denar_rodbine
        elif koliko_vsak != denar_rodbine:
            return False
    return (koliko_vsak or 0) * len(otroci[oseba]) + denar[oseba]

Najprej: ta funkcija malo goljufa. Če je rodbina uravnotežena, vrne njeno premoženje, sicer pa vrne False. To deluje ob predpostavki, da ima vsaka testirana rodbina vsaj nekaj denarja.

Funkcija si v spremenljivki koliko_vsak beleži, koliko denarja naj bi imela rodbina vsakega otroka. V začetku ne ve, koliko naj bi to bilo, zato si v koliko_vsak zabeleži None. Nato gre čez vse otroke. Vpraša otroka, ali je njegova rodbina uravnotežena. Če ta odgovori, da ne (odgovor mora biti False, ne samo neresničen, zato preverjamo if denar_rodbine is False, ne samo if denar_rodbine), vrnemo ne. Sicer preverimo, ali že vemo, kakšna premoženja naj bi imele rodbine otrok te osebe. Če ne vemo (if koliko_vsak is None), si zapomnimo, da toliko, kolikor smo pravkar izvedeli. Če vemo, pa preverimo, ali ima tudi ta otrok toliko; če nima, vrnemo False.

Končno, če je vse uravnoteženo, vrnemo premoženje rodbine tega otroka. To je enako koliko_vsak * len(otroci[oseba]) + denar[oseba]. Popaziti moramo le na osebe brez otrok. Če je koliko_vsak enak None, bomo število otrok (ki je sicer 0), pomnožili z 0, zato pišemo koliko_vsak or 0; če je koliko_vsak enak None, bo rezultat tega enak 0.

Ta funkcija torej hkrati računa tako premoženje rodbine kot uravnoteženost. Ni pa posebej lepa, saj namesto True vrne število (ki bi lahko bilo načelno celo 0), kar je narobe. Če smo kaj tankočutni, preimenujemo to funkcijo v uravnotezeni0 in jo pokličemo iz druge, ki se imenuje uravnotezeni in vedno vrne True ali False.

def uravnotezeni0(oseba, denar):
    koliko_vsak = None
    for otrok in otroci[oseba]:
        denar_rodbine = uravnotezeni0(otrok, denar)
        if denar_rodbine is False:
            return False
        if koliko_vsak is None:
            koliko_vsak = denar_rodbine
        elif koliko_vsak != denar_rodbine:
            return False
    return (koliko_vsak or 0) * len(otroci[oseba]) + denar[oseba]

def uravnotezeni(oseba, denar):
    if uravnotezeni0(oseba, denar) is False:
        return False
    else:
        return True

Tu še enkrat poudarimo, da je rezultat funkcije uravnotezeni0 lahko tudi 0, kar ni resnično. Zato tale čudni is False (če bi pisali == False, ne bi bilo dobro, saj je 0 == False resnično, mi pa hočemo, da ni). Vseeno pa lahko funkcijo napišemo lepše:

def uravnotezeni(oseba, denar):
    return uravnotezeni0(oseba, denar) is not False

Tudi neuravnotezeni je ena packarija. Naredimo lahko takole:

def neuravnotezeni(oseba, denar):
    for otrok in otroci[oseba]:
        u = neuravnotezeni(otrok, denar)
        if u is not None:
            return u
    if len({premozenje(otrok, denar) for otrok in otroci[oseba]}) >= 2:
        return oseba

Če rekurzivni klic za katerega od otrok ne vrne None temveč ime otroka, vrnemo ime tega otroka. Sicer pa preverimo ali so premoženja otrok različna (se pravi, ali imamo dve ali več različnih premoženj). Če je tako, vrnemo ime te osebe. Če ni, ne vrnemo ničesar, torej vrnemo None.

Grdota te funkcije je v tem, da kliče funkcijo premozenje. In to v vsakem vozlišču. In te klici gredo potem naprej dol po drevesu.

Funkcijo lahko polepšamo na podoben način kot smo to naredili zgoraj, le da je še malo bolj zoprno: vrnemo bodisi ime neuravnotežene osebe bodisi številko, ki predstavlja premoženje rodbine te osebe, saj je to podatek, ki ga potrebujemo. To zapakiramo v funkcijo neuravnotezeni0, funkcija neuravnotezeni pa pokliče neuravnotezeni0 in če ta vrne niz z imenom osebe, tudi neuravnotezeni vrne prav to, če neuravnotezeni0 vrne številko, pa neuravnotezeni ne vrne ničesar.

Manj grdo je, če napišemo funkcijo neuravnotezeni0, ki vrne par: številko s premoženjem in ime neuravnotežene osebe. Točneje, vrne eno ali drugo, takole

def neuravnotezeni0(oseba, denar):
    koliko_vsak = None
    for otrok in otroci[oseba]:
        koliko_ta, kdo_ni = neuravnotezeni0(otrok, denar)
        if kdo_ni:
            return 0, kdo_ni
        elif koliko_vsak is None:
            koliko_vsak = koliko_ta
        elif koliko_vsak != koliko_ta:
            return 0, oseba
    return (koliko_vsak or 0)* len(otroci[oseba]) + denar[oseba], None

def neuravnotezeni(oseba, denar):
    return neuravnotezeni0(oseba, denar)[1]

neuravnotezeni pa vrne le drugi element, ki je bodisi ime osebe bodisi None.