Prvorojenci in brez potomcev
Ogrevanje
Rešuj stare naloge na temo rodbine. V pomoč bodo.
Obvezna naloga
Napiši funkcijo brez_potomcev(oseba), ki vrne število vseh tistih oseb iz rodbine podane osebe, ki nimajo potomcev.
Klic brez_potomcev("Elizabeta") vrne 7, saj so v Elizabetini rodbini brez potomcev Ludvik, Franc, Alenka, Petra, Aleksander, Barbara in Margareta. Klic brez_potomcev("Tadeja") vrne 1, saj je v Tadejini rodbini brez potomcev en sam, namreč Tadeja sama.
Rešitev
Če oseba nima potomcev, potem je v njeni rodbini očitno natančno ena oseba brez potomcev - namreč ona sama. Če ima potomce, pa vpraša otroke in sešteva osebe brez potomcev v njihovih rodbinah. Torej
def brez_potomcev(oseba):
if not otroci[oseba]:
return 1
brez = 0
for otrok in otroci[oseba]:
brez += brez_potomcev(otrok)
return brez
Ali, če se spomnimo izpeljanih seznamov oziroma generatorjev:
def brez_potomcev(oseba):
if not otroci[oseba]:
return 1
return sum(brez_potomcev(otrok) for otrok in otroci[oseba])
Večina študentov je namesto not otroci[oseba] pisala otroci[oseba] == [] ali len(otroci[oseba]) == 0. To seveda deluje, ne šteje pa se za lepo. Prav tako ne pišemo otroci[oseba] != [] ali len(otroci[oseba]) > 0, temveč kar otroci[oseba]. Prazni seznami so neresnični, neprazni so resnični.
Dodatna naloga
Napiši funkcijo prvorojenci(oseba), ki vrne množico z vsemi prvorojenci (oz. prvorojenkami) med potomci podane osebe (brez osebe same, če je ta slučajno tudi prvorojenec).
Klic prvorojenci("Elizabeta") vrne {"Ludvik", "Franc", "Alenka", "Margareta"}.
Rešitev
Sestavimo prazno množico, v katero bomo zlagali prvorojence. Če ima oseba kaj otrok, damo v to množico prvega od njih. Nato naročimo otrokom, naj naredijo isto, in v množico prvorojencev "priunijamo" njihove rezultate.
def prvorojenci(oseba):
prvo = set()
if otroci[oseba]:
prvo.add(otroci[oseba][0])
for otrok in otroci[oseba]:
prvo |= prvorojenci(otrok)
return prvo
Večina (vsi?) je namesto prvo |= prvorojenci(otrok) pisala prvo = prvo + prvorojenci(otrok). S tem ni nič narobe, je pa isto, kot če bi namesto x += 1 pisali x = x + 1.
Začetek mi gre na živce. Naredim množico in po tem vanjo dodam prvi element, če obstaja. Tri vrstice, ki bi lahko bile ena. Raje bi pisal:
def prvorojenci(oseba):
e = {otroci[oseba][1]} # Napaka!
for otrok in otroci[oseba]:
e |= prvorojenci(otrok)
return e
Vendar to ne deluje, kadar oseba nima potomcev -- takrat bo otroci[oseba][1] vrnil napako index out of range. V takem primeru se zatečemo k triku: s[:n] vrne (največ) prvih n elementov seznama s; če je seznam krajši, jih vrne manj. Torej bo otroci[oseba][:1] vrnil največ enega otroka, lahko pa tudi nobenega. Vrnil ga bo kot seznam, zato moramo ta seznam spremeniti v množico.
def prvorojenci(oseba):
e = set(otroci[oseba][:1])
for otrok in otroci[oseba]:
e |= prvorojenci(otrok)
return e
Dodatni izziv
Tole se ne bo nikamor štelo, dajem pa za izziv takšnim, ki imajo radi izzive: obe funkciji napiši v eni vrstici. Funkcija brez_potomcev ne bi smela biti prehud izziv, posebej, če se spomnimo, da je True isto kot 1. Za drugo funkcijo pa bo potrebno from functools import reduce.
Rešitev
Rešitev v eni vrstici je lahko malo na silo
def brez_potomcev(oseba):
return sum(brez_potomcev(otrok) for otrok in otroci[oseba]) if otroci[oseba] else 1
ali pa malo elegantneje (in s trikom):
def brez_potomcev(oseba):
return not otroci[oseba] or sum(brez_potomcev(otrok) for otrok in otroci[oseba])
Če oseba nima otrok, bo not otroci[oseba] resničen in Python ne bo računal naprej. Vrnil bo True, kar je isto kot 1. Če je prvi del neresničen (to je, če oseba ima otroke), pa bo vrnil in izračunal drugi del.
Prvorojenci pa so resnejši problem. Rekurzivni klici vračajo množice, ki jih je potrebno seštevati.
V modulu functools imamo funkcijo reduce. Tule je primer, kaj zna:
>>> from functools import reduce
>>> s = [5, 2, 8]
>>> def f(x, y):
... return x + y
...
>>> reduce(f, s)
15
Kot argument ji podamo funkcijo, recimo f, in seznam, recimo [x1, x2, x3, x4]. Funkcija reduce bo poklicala f na prvih dveh elementih, recimo r = f(x1, x2). Nato bo poklicala f na rezultatu prvega klica in tretjem elementu, r = f(r, x3). Nato na četrtem, r = f(r, x4). Na koncu vrne rezultat zadnjega klica. Se pravi, reduce izračuna f(f(f(x1, x2), x3), x4). Če funkcija f v resnici sešteva, bo reduce torej vrnila (((x1 + x2) + x3) + x4).
Funkciji reduce lahko podamo tudi začetno vrednost. V tem primeru v prvem koraku ne bo "seštela" (ali karkoli že) prvih dveh elementov, temveč bo začela s podano začetno vrednostjo, ji dodala prvi element, nato drugega...
>>> reduce(f, s, 3)
18
Na ta način lahko, recimo, tudi združujemo sezname.
>>> reduce(f, [[5, 1], [7, 7, 7], [12, 3]])
[5, 1, 7, 7, 7, 12, 3]
Ker je to precej uporabno, so v modulu operator že zbrane osnovne funkcije; med njimi je add, ki počne natančno isto kot gornja f.
>>> from operator import add
>>> add(3, 6)
9
>>> reduce(add, [5, 2, 8])
15
Za naše prvorojence pa ne potrebujemo seštevanja temveč unijo. Lahko si napišemo
def unija(x, y):
return x | y
Vendar nam za to funkcijo ni potrebno niti uvažati modula operator. Prikličemo jo lahko kot set.union. (V resnici gre za drugačen način uporabe metod; če je s niz, lahko namesto s.replace(x, y) rečemo str.replace(s, x, y), vendar je to neobičajno in nezaželeno.)
Prvorojence torej naberemo takole:
from functools import reduce
def prvorojenci(oseba):
return reduce(set.union, (prvorojenci(otrok) for otrok in otroci[oseba]), set(otroci[oseba][:1]))
S set.union združujemo vse prvorojence v rodbinah otrok ((prvorojenci(otrok) for otrok in otroci[oseba])), začetna vrednost pa je množica, ki vsebuje prvega otroka, če le-ta obstaja (set(otroci[oseba][:1])).