Odzipaj priloženo datoteko s testi. Vsebuje datoteko testi.py in direktorij 0. Ta ima kup poddirektorijev. Ti direktoriji imajo poddirektorije. In ti poddirektorije. In tako naprej. Da bo zip gotovo pravilno deloval, direktoriji niso prazni: v vsakem se nahaja še datoteka foo, ki vsebuje besedo bar.

Če uvozimo modul os, dobimo funkcijo os.listdir(d), ki vrne vsebino (imena vseh direktorijev in datotek) v direktoriju d. Tako bo, recimo, os.listdir("0/986/717") vrnil seznam ["134", "602", "748", "foo"], ker direktorij 0/986/717 vsebuje 134, 602, 748 in foo (prvi trije so direktoriji, foo je datoteka).

Tule, recimo, je funkcija, ki izpiše vse vnuke podanega direktorija dir:

def izpisi_vnuke(dir):
    for otrok in os.listdir(dir):
        if otrok != "foo":
            for vnuk in os.listdir(dir + "/" + otrok):
                print(dir + "/" + otrok + "/" + vnuk)

Pokličemo jo lahko z, recimo, izpisi_vnuke("0/103").

Pazi: v vseh modernih operacijskih sistemih kot ločilo med direktoriji uporabljamo poševnico (/) in ne vzvratne poševnice (\). Tudi Microsoft, ki je kar se tega tiče naredil manjšo štalo, zdaj podpira (tudi :( ) poševnico. Ker bom domače naloge pregledoval na računalniku, ki nima Windowsov, vam bom hvalažen, če boste uporabljali /.

Obvezne naloge

1. Napiši funkcijo prestej(dir), ki ji podamo ime nekega direktorija (recimo "0" ali "0/986/717") in vrne število vseh direktorijev, poddirektorijev, podpoddirektorijev ... podanega direktorija -- vključno s podanim direktorijem, a brez datotek foo. Klic prestej("0/103/93/599") vrne 12, saj ima direktorij 0/103/93/599 dvanajst pod(podpod)direktorijev (599, 84, 137, 307, 838, 874, 463, 702, 847, 647, 722, 803). O tem se lahko prepričamo na sliki na desni, ki kaže "drevo" znotraj poddirektorija 0/103/93, 599.

  1. Napiši funkcijo koncni(dir), ki vrne število vseh poddirektorijev (podpoddirektorijev, podpodpoddirektorijev...) podanega direktorija dir, ki nimajo nobenega poddirektorija več. Tako mora koncni("0/103/93/599") vrniti 6, saj ima direktorij 0/103/93/599 šest pod(podpod)direktorijev, ki nimajo več poddirektorijev (glej sliko: to so 137, 307, 874, 463, 702 in 803).

  2. Napiši funkcijo globina(dir), ki vrne največjo globino, v katero se je možno zariti pod podani direktorij. Klic globina("0/103/93/599") vrne 5, saj je najglobji direktorij (803) pet nivojev globoko. (Najglobji je na sliki "najbolj desni" ne "najnižji", čeprav je v primeru na sliki to slučajno enako.)

Rešitev

Vse naloge so jako podobne temu, kar smo se na predavanjih šli z rodbino Novakovih. Prva naloga je v bistvu velikost rodbine. Rešimo jo tako

def prestej(dir):
    vseh = 1
    for pod in os.listdir(dir):
        if pod != "foo":
            vseh += prestej(dir + "/" + pod)
    return vseh

ali, krajše, tako

def prestej(dir):
    return 1 + sum(prestej(dir + "/" + pod) for pod in os.listdir(dir) if pod != "foo")

Druga je število oseb brez potomcev. Če se prav spomnim, na predavanjih tega ni bilo, pač pa se to najde v starih nalogah.

def koncni(dir):
    koncnih = 0
    for pod in os.listdir(dir):
        if pod != "foo":
            koncnih += koncni(dir + "/" + pod)
    if koncnih > 0:
        return koncnih
    else:
        return 1

Če dani direktorij nima poddirektorijev (ki imajo na koncu koncev končne direktorije), je ta direktorij sam končen, zato vrnemo 1. Zadnja if in else se krajše napišeta

return koncnih or 1

Krajše,

def koncni(dir): return sum(koncni(dir + "/" + pod) for pod in os.listdir(dir) if pod != "foo") or 1

Tudi zadnjo poznamo. Gre za globino rodbine, rešimo pa jo z

def globina(dir):
    naj_globina = 0
    for pod in os.listdir(dir):
        if pod != "foo":
            naj_globina = max(naj_globina, globina(dir + "/" + pod))
    return naj_globina + 1

ali

def globina(dir): return 1 + max((globina(dir + "/" + pod) for pod in os.listdir(dir) if pod != "foo"), default=0)

Vse skupaj gre še lepše, če si pripravimo funkcijo, ki vrne vse poddirektorije podanega direktorija.

To storimo tako

def poddirektoriji(dir):
    return [dir + "/" + pod for pod in os.listdir(dir) if pod != "foo"]

ali tako

def poddirektoriji(dir):
    for pod in os.listdir(dir):
        if pod != "foo":
            yield dir + "/" + pod

ali, najlepše, tako

def poddirektoriji(dir):
    return (dir + "/" + pod for pod in os.listdir(dir) if pod != "foo")

Od funkcij potem ostane le še

def poddirektoriji(dir):
    return (dir + "/" + pod for pod in os.listdir(dir) if pod != "foo")

def prestej(dir):
    return 1 + sum(prestej(pod) for pod in poddirektoriji(dir))

def koncni(dir):
    return sum(koncni(pod) for pod in poddirektoriji(dir)) or 1

Dodatna naloga

  1. Napiši funkcijo naj_pot(dir), ki vrne pot do najglobjega direktorija znotraj dir (tistega, katerega globino vrača globina(dir)). Klic naj_pot("0/103/93/599") vrne "0/103/93/599/847/647/722/803".

  2. Napiši funkcijo najvec_pod(dir), ki vrne ime tistega pod(podpodpod)direktorija znotraj dir, ki ima največ poddirektorijev. To je lahko tudi dir sam.

  3. Napiši funkcijo pot_do(x, dir), ki vrne pot do direktorija x znotraj direktorija dir. Klic pot_do("874", "0/103/93/599") vrne "0/103/93/599/84/838/874".

Rešitve

Najdaljšo pot prepoznamo po tem, da ima največ znakov /, torej (če predpostavimo, da imamo gornjo funkcijo poddirektoriji, sicer pa je v obeh primerih zraven še en if):

def naj_pot(dir):
    naj = dir
    for pod in poddirektoriji(dir):
        ta = naj_pot(pod)
        if ta.count("/") > naj.count("/"):
            naj = ta
    return naj

ali pa (krajše, a s par triki):

def naj_pot(dir):
    return max((naj_pot(pod) for pod in poddirektoriji(dir)),
               key=lambda x: x.count("/"), default=dir)

Druga je na las podobna, le na namesto znakov / štejemo poddirektorije.

def najvec_pod(dir):
    naj = dir
    for pod in poddirektoriji(dir):
        ta = najvec_pod(pod)
        if len(os.listdir(ta)) > len(os.listdir(naj)):
            naj = ta
    return naj

ali

def najvec_pod(dir):
    return max(dir,
            max((najvec_pod(pod) for pod in poddirektoriji(dir)),
                default=dir, key=lambda x:len(os.listdir(x))),
            key=lambda x: len(os.listdir(x)))

Pa še zadnja:

def pot_do(x, dir):
    dirs = os.listdir(dir)
    if x in dirs:
        return dir + "/" + x
    for pod in poddirektoriji(dir):
        kje = pot_do(x, pod)
        if kje:
            return kje

ali

def pot_do(x, dir):
    return dir + "/" + x if x in os.listdir(dir) else (
        max((pot_do(x, pod) for pod in poddirektoriji(dir)), default=""))

Čisto dodatne naloge

Tole ni za kakšne dodatne točke, temveč kar tako. Zanje tudi ni testov.

  1. Vseh šest gornjih funkcij napiši v eni vrstici, s tem, kar smo se učili prejšnji teden.

  2. Imena nekaterih direktorijev se pojavijo večkrat. Katerih?

  3. Napiši funkcijo skupni_prednik(x, dir), ki ji podamo ime direktorija x, ki se ponovi večkrat in ime "korena" dir (lahko je 0 ali kateri od poddirektorijev). Funkcija vrne ime (podpodpod)direktorija, za katerega velja, da se vse ponovitve x pojavijo znotraj njega. Klic skupni_prednik("42", "0") vrne "0/976/891", ker se direktorij 42 obakrat pojavi znotraj 0/976/891, tam pa se njuni poti ločita - ena je znotraj 0/976/891/428/... druga pa znotraj ``0/976/891/966/...`

Rešitve

Prvo smo rešili sproti.

Rešitev druge je takšna (brez komentarja; kar študirajte):

def veckrat(dir):
    def veckrat0(dir):
        spod = {dir.rsplit("/", 1)[-1]}
        veckrat = set()
        for pod in poddirektoriji(dir):
            pod_spod, pod_veckrat = veckrat0(pod)
            veckrat |= pod_veckrat | (pod_spod & spod)
            spod |= pod_spod
        return spod, veckrat
    return veckrat0(dir)[1]

Tretja je, ko se je človek loti pametno, presenetljivo kratka.

def skupni_prednik(x, dir):
    kje = [pod for pod in poddirektoriji(dir) if pot_do(x, pod)]
    if len(kje) > 1:
        return dir
    elif kje:
        return skupni_prednik(x, kje[0])
Zadnja sprememba: torek, 26 marec 2019, 17:14