Pripovedke iz gozda

Imamo gozd. Se pravi drevesa. Na kvadratni mreži. Zaradi nekih novih norih evropskih predpisov.

Gozd na sliki opišemo s takšnimle seznamom nizov:

gozd = ["..##.......",
        "#...#...#..",
        ".#..#.#..#.",
        "..#.#...#.#",
        ".#...##..#.",
        "..#.##.....",
        ".#.#.#....#",
        ".#..#.....#",
        "#.###..#...",
        "#....#....#",
        ".#......#.#"]

V nizu se pojavljata samo znaka . in #. Vsi nizi so enako dolgi. Širina in višina nista nujno enaki. Razpored dreves sem ukradel na Advent of Code (slika pa je moja, samo zajec je iz OpenClipart). Saj mu vsako leto iz hvaležnosti nekaj nakažem. Resno.

Testi

Testi: testi-pripovedke-iz-gozda.py

Za ogrevanje

Ker tu nimaš kaj čarati, bodo testi preverili tudi, da je tvoja funkcija dolga eno samo vrstico, se pravi en sam return. Kar je več, je preveč.

Rešitev

Da bomo imeli funkcije na čem preskušati, si pripravimo gozd.

gozd = ["..##.......",
        "#...#...#..",
        ".#..#.#..#.",
        "..#.#...#.#",
        ".#...##..#.",
        "..#.##.....",
        ".#.#.#....#",
        ".#..#.....#",
        "#.###..#...",
        "#....#....#",
        ".#......#.#"]
def dimenzije(gozd):
    return len(gozd[0]), len(gozd)

dimenzije(gozd)
(11, 11)
def je_drevo(x, y, gozd):
    return gozd[y][x] == "#"
je_drevo(4, 1, gozd)
True
je_drevo(2, 1, gozd)
False

V drugi funkciji ne smemo prezreti, da elementi seznama gozd predstavljajo vrstice, znotraj teh pa imamo stolpce, zato gozd[y][x] in ne gozd[x][y].

Funkciji je bilo potrebno napisati v eni vrstici. To sem zahteval predvsem zaradi druge, da bi vas odvadil pisati

def je_drevo(x, y, gozd):
    if gozd[y][x] == "#":
        return True
    else:
        return False

Za oceno 6: Revirni gozdar

vsa_drevesa

Ena možnost je ta:

def vsa_drevesa(gozd):
    sirina, visina = dimenzije(gozd)
    drevesa = set()
    for x in range(sirina):
        for y in range(visina):
            if je_drevo(x, y, gozd):
                drevesa.add((x, y))
    return drevesa

Tole so vsa drevesa v prvih dveh vrsticah:

vsa_drevesa(gozd[:2])
{(0, 1), (2, 0), (3, 0), (4, 1), (8, 1)}

Osebno imam raje tole. Ne potrebujemo dimenzij, predvsem pa: potrebujemo vrstice (in znake) in indekse, kar je vedno lepo narediti z enumerate.

def vsa_drevesa(gozd):
    drevesa = set()
    for y, vrstica in enumerate(gozd):
        for x, c in enumerate(vrstica):
            if c == "#":
                drevesa.add((x, y))
    return drevesa

Je pa to očitno stvar okusa. Eno ali drugo lahko spremenimo v izpeljano množico: vrniti je potrebno množico koordinat, na katerih ni dreves.

def vsa_drevesa(gozd):
    return {(x, y)
            for x in range(len(gozd[0])) for y in range(len(gozd))
            if je_drevo(x, y, gozd)}

ali

def vsa_drevesa(gozd):
    return {(x, y)
            for y, vrstica in enumerate(gozd) for x, c in enumerate(vrstica)
            if c == "#"}

Mogoče je še najlepše tako,

def vsa_drevesa(gozd):
    sirina, visina = dimenzije(gozd)
    return {(x, y)
            for x in range(sirina) for y in range(visina)
            if je_drevo(x, y, gozd)}

vendar vam testi tega ne bi priznali kot eno vrstico.

stevilo_dreves

Rešitev je:

def stevilo_dreves(x0, y0, x1, y1, gozd):
    v = 0
    for x in range(x0, x1):
        for y in range(y0, y1):
            if je_drevo(x, y, gozd):
                v += 1
    return v

stevilo_dreves(2, 3, 4, 6, gozd)
2

Zanimiva čudna rešitev, ki jo je napisalo veliko študentov, je, da so spustili x in y prek celotnega gozda, potem pa upoštevali samo drevesa, ki so znotraj iskanega intervala.

def stevilo_dreves(x0, y0, x1, y1, gozd):
    sirina, visina = dimenzije(gozd)
    v = 0
    for x in range(sirina):
        for y in range(visina):
            if x0 <= x < x1 and y0 <= y < y1 and je_drevo(x, y, gozd):
                v += 1
    return v

To deluje, vendar nima smisla: če nas zanima le koordinate znotraj nekega intervala, gremo pač le prek tega intervala.

To bi bilo smiselno, če bi šli prek vseh dreves in za vsako preverili, ali je znotraj iskanih koordinat. Če že ravno imamo funkcijo vsa_drevesa.

def stevilo_dreves(x0, y0, x1, y1, gozd):
    v = 0
    for x, y in vsa_drevesa(gozd):
        if x0 <= x < x1 and y0 <= y < y1:
            v += 1
    return v

Če vemo, da je True enak 1 in False enak 0, lahko seštevamo kar te True-je in False.

def stevilo_dreves(x0, y0, x1, y1, gozd):
    v = 0
    for x, y in vsa_drevesa(gozd):
        v += x0 <= x < x1 and y0 <= y < y1
    return v

To nas vodi direktno v rešitev z generatorjem.

def stevilo_dreves(x0, y0, x1, y1, gozd):
    return sum(x0 <= x < x1 and y0 <= y < y1 for x, y in vsa_drevesa(gozd))

Podobno pa je mogoče preobrniti tudi prvo funkcijo.

def stevilo_dreves(x0, y0, x1, y1, gozd):
    return sum(je_drevo(x, y, gozd) for x in range(x0, x1) for y in range(y0, y1))

ni_dreves

Ni kaj. :)

def ni_dreves(x0, y0, x1, y1, gozd):
    return stevilo_dreves(x0, y0, x1, y1, gozd) == 0

Nekdo je vprašal, ali ta rešitev velja ali se šteje za goljufijo. Seveda velja. Tako je bilo mišljeno.

Za oceno 7: Ljubitelj dreves

dreves_na_33

Tudi to velja. Tudi to je bilo tako mišljeno.

def dreves_na_33(x, y, gozd):
    return stevilo_dreves(x, y, x + 3, y + 3, gozd)

Bistvo te funkcije je predvsem, da se zavedate, da morate k x in k y prišteti 3, ker spodnje desno oglišče ni vključeno. Na ta način pregledujemo vse med (x, y) in (vključno) (x + 2, y + 2).

naj_kvadrat

def naj_kvadrat(gozd):
    naj_dreves = 0
    sirina, visina = dimenzije(gozd)
    for x in range(sirina - 2):
        for y  in range(visina - 2):
            naj_dreves = max(naj_dreves, dreves_na_33(x, y, gozd))
    return naj_dreves

Bistvo te funkcije pa je, da se zavedamo, da moramo napisati range(sirina - 2). Tako bo največji x enak sirina - 3. Tu se namreč začne zadnji dovoljen kvadrat dimenzij 3x3 - zadnji dovoljeni x-i so sirina - 3, sirina - 2 in sirina - 1.

Namesto

            dreves = dreves_na_33(x, y, gozd)
            if dreves > naj_dreves:
                naj_dreves = dreves

smo si pomagali s funkcijo max. Za malo spremembe. :)

Različica z generatorjem je

def naj_kvadrat(gozd):
    return max(
        dreves_na_33(x, y, gozd)
        for x in range(len(gozd[0]) - 2) for y in range(len(gozd) - 2))

Gremo čez vse koordinate, za vsako izračunamo dreves_na_33(x, y, gozd) in pogledamo maksimum le-tega.

Za oceno 8: Grm, v katerem tiči zajec

lovec

Funkcija ni zapletena, lahko pa postane takšna, če se je lotimo nerodno.

def lovec(x, y, pot, gozd):
    sirina, visina = dimenzije(gozd)
    buske = 0
    for c in pot:
        dx, dy = {"^": (0, -1), "v": (0, 1), "<": (-1, 0), ">": (1, 0)}[c]
        nx, ny = x + dx, y + dy
        if not (0 <= nx < sirina and 0 <= ny < visina):
            continue
        elif je_drevo(nx, ny, gozd):
            buske += 1
        else:
            x, y = nx, ny
    return buske

Prvi trik: spremembi damo v dx in dy, s čimer se rešimo seznama zoprnih if-ov. Ta trik smo videli pred nekaj tedni, v nalogi srecanja.

Naslednji trik: namesto da bi naračunali novi koordinati naravnost v x in y, ju začasno naračunamo v nx in ny.

Nato pa:

Očitno bi lahko pisali tudi

        if 0 <= nx < sirina and 0 <= ny < visina:
            if je_drevo(nx, ny, gozd):
                buske += 1
            else:
                x, y = nx, ny

vendar mi je gornja rešitev všeč, ker program beži manj desno. Poleg tega pa mi je všeč tudi, da eksplicitno pove, da ne bo naredil ničesar, če so koordinate izven dovoljenih meja.

zajec

Za to nalogo se moram pa skoraj malo opravičiti. Sam sem jo rešil le v eni vrstici in se mi je zdela čisto preprosta. Šele ob pisanju tega besedila - ko ste nalogo že davno začeli reševati - pa sem videl, da rešitev brez izpeljanih seznamov sploh ni tako preprosta in kratka. Takšna je.

def zajec(drevesa):
    sirina = max(drevesa)[0] + 1

    naj_koord = None
    naj_dreves = 0
    for x in range(sirina):
        stolpec = []
        for x0, y0 in drevesa:
            if x0 == x:
                stolpec.append(y0)

        if len(stolpec) > naj_dreves:
            naj_dreves = len(stolpec)
            naj_koord = (x, max(stolpec))
    return naj_koord

Najprej izvemo, širino: v množici drevesa poiščemo maksimalni element. Gre za pare, torej bomo dobili tistega z največjim prvim elementom. Iz tega para poberemo prvi element (zato [0]) in prištejemo 1, saj gredo x-i od 0, torej je širina za 1 večja od največje koordinate.

Nato gremo prek vseh stolpcev. Za vsakega naberemo v stolpec vse y koordinate v tistem stolpcu. Če je v tem stolpcu več dreves kot v največjem doslej, si zapomnimo to število dreves in koordinate spodnjega drevesa, torej trenutni x in največji element tega stolpca.

Zdaj pa z izpeljanimi množicami.

x bomo spustili prek množice vse x koordinat: for x in {x for x, y in drevesa}. Za vsak takšen x izračunamo vse koordinate dreves v njem {(y, x) for x0, y in drevesa if x0 == x}. Združimo: tole so množice dreves, grupirane po stolpcih.

({(y, x) for x0, y in drevesa if x0 == x}
 for x in {x for x, y in drevesa})

Izmed njih nas zanima največja:

max(({(y, x) for x0, y in drevesa if x0 == x}
             for x in {x for x, y in drevesa}), key=len)

Z max(..., key=len) dobimo tisti element, ki ima največ elementov. Torej stolpec z največ drevesi. En sam stolpec. Rezultat tega max-a je množice koordinat (y, x), ne (x, y). Zato lahko zdaj poiščemo "največjo" koordinato -- dobili bomo tisto, ki ima največji y.

max(
    max(({(y, x) for x0, y in drevesa if x0 == x}
        for x in {x for x, y in drevesa}), key=len)
)

Tole bo (y, x) koordinata najnižjega drevesa v stolpcu z največ drevesi. Ker je potrebno vrniti (x, y) in ne (y, x), to še obrnemo. Funkcija je torej

def zajec(drevesa):
    return max(
        max(({(y, x) for x0, y in drevesa if x0 == x}
             for x in {x for x, y in drevesa}), key=len)
    )[::-1]

Za oceno 9: Kot hudičev boršt, vendar jasa

razdalja, bliznja_drevesa in povezana_drevesa

Tole je skoraj dolgočasno.

def razdalja(x0, y0, x1, y1):
    return sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

def bliznja_drevesa(x, y, r, drevesa):
    return {(x0, y0) for (x0, y0) in drevesa if razdalja(x, y, x0, y0) <= r} - {(x, y)}

def povezana_drevesa(r, drevesa):
    return {(x, y): bliznja_drevesa(x, y, r, drevesa) for (x, y) in drevesa}

Edino, kar je vredno komentarja, je, da v bliznja_drevesa na koncu preprosto odštejemo množico, ki vsebuje koordinate podanega drevesa {(x, y)}.

jasa

Z jaso ne komplicirajmo: ena za levi x (x0), ena za desni (x1), ena za zgornji y (y0), ena za spodnji (y1). Pri tem najprej naredimo zanko za desni x, tako da levi teče le do njega. Enako za y.

Za vsako četvorico koordinat izračunamo ploščino. Če je ploščina med temi koordinatami večja od največje doslej, preverimo, da tam ni dreves. Če je tako, imamo novega zmagovalca.

def jasa(gozd):
    najni = None
    for x1 in range(len(gozd[0]) + 1):
        for x0 in range(x1):
            for y1 in range(len(gozd) + 1):
                for y0 in range(y1):
                    p = (x1 - x0) * (y1 - y0)
                    if (not najni or p > najni) and ni_dreves(x0, y0, x1, y1, gozd):
                        najni = p
    return najni

To se da na različne načine izboljševati, a ni vredno. Kakšne neverjetno hitre rešitve ne bomo dobili.

Le še v eno vrstico jo prevrnimo: iščemo največjo ploščino za koordinate, med katerimi ni dreves.

def jasa(gozd):
    return max((x1 - x0) * (y1 - y0)
               for x1 in range(len(gozd[0]) + 1)
               for x0 in range(x1)
               for y1 in range(len(gozd) + 1)
               for y0 in range(y1)
               if ni_dreves(x0, y0, x1, y1, gozd))

Tole je lep primer, zakaj se učimo programiranja z generatorji: tale rešitev je gotovo preglednejša od tiste, v kateri napišemo štiri "običajne" zanke.

Za oceno 10: Tujerodna vrsta

Rešitev

Za vse, kar je potrebno pisati v eni vrstici smo poskrbeli sproti.

Opico pa uženemo tako. Pripravili bomo slovar povezanih dreves. Tako bomo za vsako drevo hitro prišli do tistih, ki jih opica doseže z njega.

Sestavljali bomo seznam dosegljivih dreves. Na koncu je sicer res potrebno vrniti množico, vendar tole z množico ne bi delovalo. (Bomo videli, zakaj.)

Nato gremo z zanko prek dosegljivih dreves. Za vsako dosegljivo drevo, dodamo v seznam dosegljivih dreves vsa drevesa, ki so dosegljiva z njega in ga še ni v seznamu.

To je vse. :)

def opica(x, y, r, drevesa):
    povezave = povezana_drevesa(r, drevesa)

    dosegljiva = [(x, y)]
    for drevo in dosegljiva:
        for drevo0 in povezave[drevo]:
            if drevo0 not in dosegljiva:
                dosegljiva.append(drevo0)
    return set(dosegljiva)

Zanka for teče prek seznama, ki se sproti dopolnjuje. To deluje - za sezname. Za množice pa ne bi.

Gre pa še malo krajše, če gornji "vsa drevesa, ki so dosegljiva z njega in ga še ni v seznamu" izvedemo z razliko množic.

def opica(x, y, r, drevesa):
    dosegljiva = [(x, y)]
    povezave = povezana_drevesa(r, drevesa)
    for drevo in dosegljiva:
        dosegljiva += povezave[drevo] - set(dosegljiva)
    return set(dosegljiva)

Vse rešitve skupaj

# Ogrevanje

def dimenzije(gozd):
    return len(gozd[0]), len(gozd)  # to mmorajo v eni vrstici

def je_drevo(x, y, gozd):
    return gozd[y][x] == "#"   # to morajo v eni vrstici


# 6

def vsa_drevesa(gozd):
    return {(x, y)
            for x in range(len(gozd[0])) for y in range(len(gozd))
            if je_drevo(x, y, gozd)}

def stevilo_dreves(x0, y0, x1, y1, gozd):
    return sum(je_drevo(x, y, gozd)
               for x in range(x0, x1) for y in range(y0, y1))

def ni_dreves(x0, y0, x1, y1, gozd):
    return not stevilo_dreves(x0, y0, x1, y1, gozd)


# 7

def dreves_na_33(x, y, gozd):
    return stevilo_dreves(x, y, x + 3, y + 3, gozd)

def naj_kvadrat(gozd):
    return max(
        dreves_na_33(x, y, gozd)
        for x in range(len(gozd[0]) - 2) for y in range(len(gozd) - 2))


# 8

def lovec(x, y, pot, gozd):
    sirina, visina = dimenzije(gozd)
    buske = 0
    for c in pot:
        dx, dy = {"^": (0, -1), "v": (0, 1), "<": (-1, 0), ">": (1, 0)}[c]
        nx, ny = x + dx, y + dy
        if not (0 <= nx < sirina and 0 <= ny < visina):
            continue
        elif je_drevo(nx, ny, gozd):
            buske += 1
        else:
            x, y = nx, ny
    return buske

def zajec(drevesa):
    return max(
        max(({(y, x) for x0, y in drevesa if x0 == x}
             for x in {x for x, y in drevesa}), key=len)
    )[::-1]


# 9

def razdalja(x0, y0, x1, y1):
    return sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2)

def bliznja_drevesa(x, y, r, drevesa):
    return {(x0, y0) for (x0, y0) in drevesa if razdalja(x, y, x0, y0) <= r} - {(x, y)}

def povezana_drevesa(r, drevesa):
    return {(x, y): bliznja_drevesa(x, y, r, drevesa) for (x, y) in drevesa}

def jasa(gozd):
    return max((x1 - x0) * (y1 - y0)
               for x1 in range(len(gozd[0]) + 1)
               for x0 in range(x1)
               for y1 in range(len(gozd) + 1)
               for y0 in range(y1)
               if ni_dreves(x0, y0, x1, y1, gozd))


# 10

def opica(x, y, r, drevesa):
    dosegljiva = [(x, y)]
    povezave = povezana_drevesa(r, drevesa)
    for drevo in dosegljiva:
        dosegljiva += povezave[drevo] - set(dosegljiva)
    return set(dosegljiva)