Rešitev

Ogrevalna naloga: Pari hiš

Napišite funkcijo pari_his(stevilke), ki dobi seznam številk in vrne množico vse parov hiš, ki imajo vsaj eno skupno števko.

>>> pari_his([12, 23, 26, 54]) {(12, 23), (12, 26), (23, 12), (23, 26), (26, 12), (26, 23)}

Če gornji klic v resnici vrne {(26, 23), (12, 26), (23, 26), (23, 12), (12, 23), (26, 12)}, se ne vznemirjajte, saj je to v resnici eno in isto.

Namigi: najbrž boste potrebovali dvojno zanko. Ne pa trojne: razmislite, kako najpreprosteje ugotoviti, ali imata dve številki skupno števko. (Ne pozabite, da se učimo o množicah. In ne pozabite, da se s števkami najlažje dela, če spremenimo številko v niz.) Končno, ne spreglejte, da v množici ne sme biti parov ene in iste hiše, npr. (12, 12)

Če sta hisa1 in hisa2 dve številki, bosta str(hisa1) in str(hisa2) niza s tema številkama. Torej bosta set(str(hisa1)) in set(str(hisa2)) množici števk, ki ju najdemo v teh nizih (oz. številkah). Zanima nas, ali imata množici kak skupen element, torej preverimo, kakšen je njun presek, set(str(hisa1)) & set(str(hisa2)). Tako kot nizi, seznami in slovarji so tudi množice "resnične", kadar so neprazne in "neresnične", ko so prazne.

Zdaj poglejmo celo funkcijo: kadar želimo sestaviti (ali pregledati ali narediti karkoli že s) pari elementov seznama, to storimo z dvojno zanko, v tem primeru

for hisa1 in stevilke: for hisa2 in stevilke:

Za vsak par je potrebno preveriti, ali imata kakšen skupen element in ali gre za dve različni številki,

if set(str(hisa1)) & set(str(hisa2)) and hisa1 != hisa2:

Zdaj pa še to, kar pride okoli: v začetku sestavimo prazno množico, vanjo zlagamo pare in to množico na koncu vrnemo.

def pari_his(stevilke): pari = set() for hisa1 in stevilke: for hisa2 in stevilke: if set(str(hisa1)) & set(str(hisa2)) and hisa1 != hisa2: pari.add((hisa1, hisa2)) return pari

Ne prezrite, da smo tule množice uporabili dvakrat. Enkrat za rezultat - ker je tako zahtevala naloga. Pare bi lahko zlagali tudi v seznam, če bi naloga hotela tako. Drugič smo množice uporabi interno, znotraj funkcije, za preverjanje skupnih števk. Naloga tega sicer ni zahtevala, bilo pa je praktično.

Za veselje nad tem, kar nas še čaka čez kak mesec, je tu rešitev v eni sami vrstici (ki smo jo samo zaradi preglednosti prelomili na pol).

def pari_his(stevilke): return {(hisa1, hisa2) for hisa1 in stevilke for hisa2 in stevilke if set(str(hisa1)) & set(str(hisa2)) and hisa1 != hisa2}

Obvezna naloga: Legalne poti

Napišite funkciji legalna_pot(pot, pari) in legalna_pot_bp(pot, pari).

Funkcija legalna_pot(pot, pari) prejme neko pot, podano kot seznam, in množico parov, kakršne vrača funkcija pari_his. Funkcija naj vrne True, če bo poštar pripravljen prehoditi takšno pot, in False, če ne.

>>> pari = pari_his([12, 23, 26, 54]) >>> legalna_pot([23, 12, 26, 12], pari) True

Druga funkcija, legalna_pot_bp(pot, pari), naj poleg tega preveri, da se nobena hiša v poti ne ponovi.

>>> legalna_pot([23, 12, 26, 12], pari) False

Za vsak i moramo preveriti, da je par (pot[i], pot[i + 1]) na seznamu dovoljenih parov. Pri tem i-ja ne spustimo do range(len(pot)), kot bi bilo običajno, temveč le do range(len(pot) - 1), saj zadnjega elementa nočemo primerjati z njegovim (neobstoječim) naslednikom.

Vzorec je znan in dolgočasen: čim naletimo na kak par, ki ga ne bi smelo biti, vrnemo False. Če takšnega para ni, torej za zanko, vrnemo True.

def legalna_pot(pot, pari): for i in range(len(pot) - 1): if (pot[i], pot[i + 1]) not in pari: return False return True

Če se spomnimo funkcije zip, ne potrebujemo indeksov.

def legalna_pot(pot, pari): for prva, druga in zip(pot, pot[1:]): if (prva, druga) not in pari: return False return True

Z zipom, kot smo se učili, sestavimo dva seznama v seznam parov (ali tri v seznam trojk in tako naprej). Tule sestavljamo seznama pot in pot[1:], to je pot brez prvega elementa. Tako dobimo točno tiste pare, ki jih želimo pregledati.

Čez kak mesec bomo znali še veliko elegantneje:

def legalna_pot(pot, pari): return all(kos in pari for kos in zip(pot, pot[1:]))

Legalna pot brez ponavljanj le še preveri, ali se kaka številka na poti ponovi. To najpreprosteje naredimo tako, da spremenimo seznam številk v množico številk in preverimo, ali ima ta še vedno toliko elementov kot seznam. Če jih nima, se je to zgodilo zato, ker se je (vsaj) ena od številk ponovila.

def legalna_pot_bp(pot, pari): return legalna_pot(pot, pari) and len(set(pot)) == len(pot)

Dodatna naloga (čisto preprosta): Graf številk

Napišite funkcijo graf_his(pari), ki prejme seznam parov in vrne graf, zapisan kot slovar, katerega ključi so točke (številke), vrednosti pa množice točk, v katere je mogoče priti iz njih. Če jo pokličemo s pari iz naloge z Bobra,

graf_stevilk( {(83, 36), (36, 83), (36, 61), (61, 36), (61, 11), (11, 61), (61, 19), (19, 61), (11, 19), (19, 11), (19, 29), (29, 19), (29, 52), (52, 29), (70, 74), (74, 70), (74, 44), (44, 74), (44, 40), (40, 44), (40, 70), (70, 40), (40, 74), (74, 40)}),

mora vrniti

{83: {36}, 36: {83, 61}, 61: {36, 11, 19}, 11: {61, 19}, 19: {61, 29, 11}, 29: {19, 52}, 52: {29}, 70: {74, 40}, 74: {70, 44, 40}, 44: {74, 40}, 40: {70, 44, 74}}

Tu ni kaj filozofirati, posebej ne tistim, ki so vajeni uporabljati slovarje s privzetimi vrednostmi: če je graf slovar, ki ga kani funkcija vrniti, mora za vsak par (hisa1, hisa2) dodati v množico graf[hisa1] element hisa2, torej graf[hisa1].add(hisa2).

from collections import defaultdict def graf_stevilk(pari): graf = defaultdict(set) for hisa1, hisa2 in pari: graf[hisa1].add(hisa2) return graf

Dodatna naloga (za malo razmišljanja): Dosegljivost

Napišite funkcijo dosegljivi(stevilka, graf), ki prejme začetno hišno številko in graf, kakršnega vrne prejšnja funkcija. Kot rezultat naj vrne množico vseh hiš, ki so dosegljive iz določene hiše.

>>> dosegljivi(36, graf) {83, 36, 61, 11, 19, 29, 52} >>> dosegljivi(74, graf) {70, 74, 44, 40}

Takole se bomo lotili: imeli bomo množico preiskati, ki bo vsebovala vse tiste točke grafa, za katere vemo, da je do njih mogoče priti, njihovih sosedov pa še nismo pregledali. V množico dosegljivo pa bomo zbirali vse dosegljive točke.

V začetku bo množica preiskati vsebovala začetno vozlišče, množica dosegljivo pa bo prazna. Nato v vsakem koraku iz množice preiskati vzamemo poljubno točko (dobimo jo s preiskati.pop(), ki vrne neko točko iz množice in jo odstrani iz nje). To točko dodamo med dosegljive, njene sosede pa dodamo v množico točk, ki jih je potrebno še preiskati. Pri tem pa popazimo, da med točke, ki jim moramo preiskati, ne dodamo, tistih, ki so bile že preiskane (torej dosegljive).

Vse skupaj ponavljamo, dokler imamo kaj preiskovati.

def dosegljivi(zacetek, graf): preiskati = {zacetek} dosegljivo = set() while preiskati: tocka = preiskati.pop() dosegljivo.add(tocka) preiskati |= graf[tocka] - dosegljivo return dosegljivo

Dodatna naloga (za malo lomit zobe): Najdaljša pot

Rešite nalogo, ki so jo morali reševati otroci. ;)

Konkretno, napišite funkcijo najdaljsa_pot_od(zacetek, graf), ki prejme začetno številko in graf, kot rezultat pa vrne seznam s številkami na najdaljši poti, ki jo lahko opravi poštar, če začne na tej številki.

Nato napišite še funkcijo najdaljsa_pot(graf), ki vrne seznam s številkami na najdaljši poti, pri čemer sama ugotovi, kje začeti.

Pri reševanju naloge vam bo zelo v pomoč, kar se bomo predvidoma učili prihodnji teden.

Prihodnji teden smo se učili rekurzijo.

Funkcijo se da obrniti na različne načine, večina "normalnih" načinov pa je rekurzivnih. Za začetek bomo sestavili nekaj malenkost napačnega: rekurzivno funkcijo najdaljsa_0, ki kot argument dobi nek začetek poti, na primer [83, 36, 61] in vrne najdaljšo pot, ki se začne s temi točkami, recimo [83, 36, 61, 11, 19, 29, 52].

def najdaljsa_0(doslej): naj = doslej for naslednji in graf[doslej[-1]] - set(doslej): naj_ta = najdaljsa_0(doslej + [naslednji]) if len(naj_ta) > len(naj): naj = naj_ta return naj

Prezrimo, da funkcija uporablja spremenljivko oz. argument graf, ki ga nima. Ta problem se bo sam od sebe rešil kasneje.

Funkcija deluje takole: najprej reče, da je najdaljša pot (naj) kar enaka začetku, ki ga je dobila kot argument. Nato poskusi vsa vozlišča, s katerimi bi se pot lahko nadaljevala: zadnja točka na doslejšnji poti je doslej[-1], njene sosede so graf[doslej[-1]], vendar smemo pot nadaljevati le v točki, v kateri še nismo bili, zato od množice sosednjih točk odštejemo množico točk, v katerih smo že bili,

for naslednji in graf[doslej[-1]] - set(doslej):

Za vsako nadaljevanje se vprašamo, kakšna je najdaljša pot, ki se začne na ta na način,

naj_ta = najdaljsa_0(doslej + [naslednji])

Če je ta pot daljša od doslej najdaljše, si jo zapomni. Funkcija na koncu vrne najdaljšo pot.

Kar smo napisali, je že zelo podobno temu, kar bi morali napisati, le argumenti niso pravi: naloga zahteva funkcijo, ki sprejme začetno točko (ne seznama) in graf. Napačno funkcijo smo sprogramirali, ker moramo narediti rekurzivno funkcijo (če nočemo kakšne strašne, bistveno težje programerske telovadbe brez rekurzije). Iz tistega, kar je zahtevala naloga, se ne bi dalo narediti rekurzivne funkcije (vsaj ne da bi jaz vedel - vsaj na lep način ne). Zato smo pač sprogramirali, kar smo morali. Da dobimo, kar hoče naloga, bi lahko napisali funkcijo, kakršno hoče naloga, ki pa prepusti delo naši funkciji, s tem da jo pokliče s primernimi argumenti.

def najdaljsa_0(doslej, graf): naj = doslej for naslednji in graf[doslej[-1]] - set(doslej): naj_ta = najdaljsa_0(doslej + [naslednji], graf) if len(naj_ta) > len(naj): naj = naj_ta return naj def najdaljsa_pot_od(zacetek, graf): return najdaljsa_0([zacetek])

Da reč deluje, mora imeti najdaljsa_0 še argument graf. To ni nujno potrebno: funkcijo najdaljsa_0 lahko postavimo znotraj funkcije najdalja_pot_od:

def najdaljsa_pot_od(zacetek, graf): def najdaljsa_0(doslej): naj = doslej for naslednji in graf[doslej[-1]] - set(doslej): naj_ta = najdaljsa_0(doslej + [naslednji]) if len(naj_ta) > len(naj): naj = naj_ta return naj return najdaljsa_0([zacetek])

Drugi del te naloge, funkcija najdaljsa_pot, je v primerjavi s tem trivialen.

def najdaljsa_pot(graf): naj = [] for zacetek in graf: naj_od = najdaljsa_pot_od(zacetek, graf) if len(naj_od) > len(naj): naj = naj_od return naj