Govorice

Naloga

V nalogi bomo delali s slovarji, v katerih je zabeleženo, kdo hodi v kateri krožek. Če, recimo, Ana hodi na dramsko skupino in matematični krožek, Berta na dramsko skupino in elementarno geometrijo, Cilka pa na matematični krožek, plezanje in pevski zbor, bo to zapisano takole:

{"Ana": {"dramska skupina", "matematični krožek"}, "Berta": {"dramska skupina", "elementarna geometrija"}, "Cilka": {"matematični krožek", "plezanje", "pevski zbor"}}

Ključi slovarja so torej imena učencev, vrednosti pa so množice imen krožkov.

(V testih je bo nekoliko poenostavljeno; testi so narejeni tako, da hodi, recimo, A na krožke a, b, c in B na krožke a, b, d. Ker se vašemu učitelju ne tipka več, kot je potrebno, tega ne zapiše z {"A": {"a", "b", "c"}, "B": {"a", "b", "d"}}, temveč kot {"A": set("abc"), "B": set("abd")}. Povem, da boste znali brati teste in razumeli, v kakšnem primeru vaš program ne deluje. Če bi prišlo do česa takšnega, seveda.)

Ogrevanje: Znanci

Napišite funkcijo znanci(krozki), ki vrne množico vseh parov učencev, ki se srečujejo na kakem krožku. V gornjem primeru mora {("Ana", "Berta"), ("Berta", "Ana"), ("Ana", "Cilka"), ("Cilka", "Ana")}. Ana in Berta se namreč srečujeta v dramski skupini, Ana in Cilka pa na matematičnem krožku.

Obvezna naloga: Govorica

Po šoli krožijo govorice. Ker učenci med poukom seveda ne klepetajo (tega se naučijo šele kasneje, na faksu), na hodnikih pa so itak tiho, se lahko govorica širi le na krožku). Napišite funkcijo govorica(pot, krozki), ki dobi pot govorice in seznam krožkov. Vrniti mora True, če je pot možna in False, če ni.

Pot je podana kot seznam imen. Možna je, če gre le prek parov, ki se srečujejo. Tako je pot ["Berta", "Ana", "Cilka"] možna, saj Berta lahko pove Ani in Ana Cilki. Potem ["Berta", "Cilka", "Ana"] pa ni možna, saj se Berta in Cilka ne srečujeta na nobenem krožku.

Dodatna naloga: najkrajša pot

Napišite funkcijo najkrajsa_pot(oseba1, oseba2, krozki), ki vrne najkrajšo pot med dvema osebama.

Namig: poženite naslednji program in razmislite, ali si lahko kaj pomagate s funkcijo permutations.

from itertools import permutations s = ["A", "B", "C", "D", "E"] for x in permutations(s, 3): print(x)

Disclaimer: najkrajše poti se sicer iščejo drugače in veliko hitrejše. Kako, boste izvedeli v tretjem letniku.

Rešitev

Rešitev ogrevalne in obvezne naloge (predvsem slednje!) je smešno kratka.

def znanci(krozki): pari = set() for oseba1, krozki1 in krozki.items(): for oseba2, krozki2 in krozki.items(): if oseba1 != oseba2 and krozki1 & krozki2: pari.add((oseba1, oseba2)) return pari def govorica(pot, krozki): return set(zip(pot, pot[1:])) < znanci(krozki)

Za rešitev prve je potrebno znati napisati zanko znotraj zanke. Gremo prek vseh oseb in njenih krožkov ter za vsako osebo (in njene krožke) prek vseh drugih oseb. Če ne gre za isto osebo in če imata kak skupen krožek (kar preverimo tako, da izračunamo presek krožkov in se prepričamo, da ta ni prazen -- prazne množice so neresnične, neprazne pa resnične), dodamo par v množico.

Da naženemo zanko for prek parov, uporabimo krozki.items().

V obvezni nalogi se moramo spomniti dveh trikov. Prvi je trik z zipom. Vzamemo pot in pot[1:], torej seznam in taisti seznam brez prvega elementa. Če seznama zazipamo skupaj, dobimo seznam parov -- ničti in prvi element, prvi in drugi, drugi in tretji... Iz tega seznama parov naredimo množico parov. To je torej množica vseh parov, prek katerih je šla govorica. Če je ta množica podmnožica množice znancev, je pot govorice možna.

Rešitev, ki je manj imenitna od zgornje, je takšna:

def govorica(pot, krozki): znanstva = znanci(krozki) for oseba1, oseba2 in zip(pot, pot[1:]): if (oseba1, oseba2) not in znanstva: return False return True

Za začetek spravimo množico znancev v znanstva - da je ne bomo kasneje računali za vsak par posebej. Nato gremo prek vseh parov oseb, ki nastopajo v poti (pridelamo jih enako kot prej). Če kak par ni v množici znanstva, vrnemo False. Če se zanka izteče, ne da bi naleteli na kak tak par, vrnemo True.

Še malo manj ugledna rešitev ne uporablja zipa. Takšnih je bilo največ; njihovi avtorji so si sami krivi, če se jim je zdela naloga težka (ehm, razen, če v prvem semestru niste spoznali zipa; v tem primeru se lahko zdaj veselite, da ga poznate ;).

def govorica(pot, krozki): znanstva = znanci(krozki) for i in range(len(pot) - 1): if (pot[i], pot[i + 1]) not in znanstva: return False return True

Kmalu bomo znali napisati obe funkciji še krajše. Takšna bo celotna rešitev ogrevalne in obvezne naloge.

def znanci(krozki): return {(oseba1, oseba2) for oseba1, krozki1 in krozki.items() for oseba2, krozki2 in krozki.items() if krozki1 & krozki2 and oseba1 != oseba2} def govorica(pot, krozki): return set(zip(pot, pot[1:])) < znanci(krozki)

Dodatna naloga

Namig je predlagal uporabo funkcije permutations. Kdor si jo je ogledal, je videl, da vrne vse izbore določenega števila elementov iz podanega seznama. Nalogo torej lahko rešimo tako, da poskušamo vse poti od dolžine 0 (saj je vseeno...) do števila oseb, zgradimo vsa možna zaporedja in za vsako preverimo, ali predstavlja veljavno pot. Funkcija vrne prvo pot, ki je veljavna. Če veljavne poti ni, ne bo vrnila ničesar. Tudi prav.

from itertools import permutations def najkrajsa_pot(oseba1, oseba2, krozki): osebe = set(krozki) - {oseba1, oseba2} for i in range(len(osebe)): for pot in permutations(osebe, i): pot = [oseba1] + list(pot) + [oseba2] if govorica(pot, krozki): return pot

Algoritmi za iskanje najkrajših poti (recimo tisti v Garminu) seveda ne delujejo tako. Že pri desetih osebah obstaja 10!, to je 3628800 različnih kombinacij. Pri sto osebah (ali krajih) je kombinacij

>>> math.factorial(100) 93326215443944152681699238856266700490715968264381621468592963895217599993229915 608941463976156518286253697920827223758251185210916864000000000000000000000000

in pri 1000 krajih (kar niti slučajno ne pokrije Slovenije!) jih je

>>> math.factorial(1000) 40238726007709377354370243392300398571937486421071463254379991042993851239862902 05920442084869694048004799886101971960586316668729948085589013238296699445909974 24504087073759918823627727188732519779505950995276120874975462497043601418278094 64649629105639388743788648733711918104582578364784997701247663288983595573543251 31853239584630755574091142624174743493475534286465766116677973966688202912073791

To je kar veliko. Kako v resnici delujejo programi za iskanje najkrajših poti, boste izvedeli v tretjem letniku.