Rešitev

1. Če želiš (ni pa ti treba), si napiši funkciji:

• preblizu(x1, y1, x2, y2), ki vrne True, če je razdalja med podanima koordinatama manjša od 1,5;
• koordinate(ime, osebe), ki vrne koordinate osebe s podanim imenom.

Rešitev

def preblizu(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2 < 1.5 ** 2

def koordinate(ime, osebe):
    for ime1, x1, y1 in osebe:
        if ime == ime1:
            return x1, y1
    return None, None

Pri prvi funkciji je lepo, da vrnemo vrednost izraza (x1 - x2) ** 2 + (y1 - y2) ** 2 < 1.5 ** 2, ki je pač že True ali False, ne pa da se norčujemo iz računalnika tako, da mu pišemo

    if (x1 - x2) ** 2 + (y1 - y2) ** 2 < 1.5 ** 2:
        return True
    else:
        return False

Mimogrede sem se izognil korenjenju tako, da preverjam, ali je kvadrat razdalje manjši od 1.5 ** 2. Tako, za hec.

V drugi funkciji se nam splača vedeti, da se lahko vrnemo tudi sredi zanke. Kaj se zgodi, če funkcije ne najde osebe s tem imenom? Izkazalo se bo, da je v tem primeru praktično vrniti par None, None. Boste videli, zakaj. Sicer pa sta to pomožni funkciji, ki jih pišete zase, da boste lažje reševali naslednje naloge. Torej lahko vračajo, kar želite.

Preblizu stoječi

Razpored oseb na določeni prireditvi, je podan s seznamom trojk, ki vsebujejo ime in koordinati (v metrih); glej primer. Napiši funkcijo krsitelji(osebe), ki prejme takšen seznam in vrne množico imen vseh oseb, ki so manj kot 1,5 m oddaljene od najbližje osebe. V primeru na sliki so to vsi razen Dani in Klare.

osebe = [("Ana", 2, 4.5),
         ("Berta", 1, 3),
         ("Cilka", 1, 4),
         ("Dani", -1, 2),
         ("Ema", 1, 1),
         ("Fanči", 2, 0.5),
         ("Greta", -1, -1.5),
         ("Helga", 0, -1),
         ("Iva", 2, 0),
         ("Jana", 0, 0),
         ("Klara", 5, 1)]

Rešitev

Ni kaj: gremo čez vse pare oseb, torej potrebujemo gnezdeni zanki -- kar je v bistvu poanta te funkcije. Za vsak par preverimo, če si stoji preblizu - in da ne gre slučajno za isto osebo! Mnogi študenti so na to pozabili. Tudi jaz bi lahko. Vendar je del tega predmeta tudi, da znate odkriti napako v svojem programu (in jo potem popraviti, kar je tule preprosto).

def krsitelji(osebe):
    krsijo = set()
    for ime1, x1, y1 in osebe:
        for ime2, x2, y2 in osebe:
            if ime1 != ime2 and preblizu(x1, y1, x2, y2):
                krsijo.add(ime1)
    return krsijo

Ne spreglejte, da je dovolj, da v množico dodamo ime1. Druga oseba pride na vrsto kasneje. Prav tako ni potrebno preverjati, ali je določena oseba že v množici: četudi jo dodamo večkrat, bo v množici enkrat.

Funkcijo je mogoče napisati tudi krajše

def krsijo(osebe):
    return {ime1
            for ime1, x1, y1 in osebe for ime2, x2, y2 in osebe
            if ime1 != ime2 and preblizu(x1, y1, x2, y2)}

Če prej rešimo drugo nalogo, pa gre še veliko krajše.

def krsitelji(osebe):
    return set(kazni(osebe))

Kazni

Vsaki osebi izrečemo toliko kazni, kolikor osebam stoji preblizu. Emi, recimo, 3, ker stoji preblizu Fanči, Ive in Jane. Napiši funkcijo kazni(osebe), ki vrne slovar, katerega ključi so imena kaznovanih oseb, vrednosti pa število izrečenih kazni.

Rešitev

Če uporabimo slovar s privzetimi vrednostmi, je ta naloga samo preprosta variacija prve.

def kazni(osebe):
    krsijo = defaultdict(int)
    for ime1, x1, y1 in osebe:
        for ime2, x2, y2 in osebe:
            if ime1 != ime2 and preblizu(x1, y1, x2, y2):
                krsijo[ime1] += 1
    return krsijo

Severni veter

Na prireditvi se je pojavila nova različica virusa, omega, ki te v trenutku okuži in naredi kužnega. Ker pa je pihal severni veter, vsaka oseba okuži le vse osebe, ki stojijo južno od nje na razdalji manjši od 1,5 metra. Če je Ema bolna, zaradi nje zbolijo Fanči, Iva, Jana, Greta in Helga. Če pa je bolna Jana, zaradi nje zbolita samo Greta in Helga, ne pa tudi Ema.

Napiši funkcijo okuzeni(ime, osebe), ki prejme ime okužene in seznam oseb; vrne množico imen oseb, ki se okužijo.

Rešitev

Tole je naloga iz rekurzije.

Okužena je podana oseba. Poleg nje so okužene vse osebe, ki jih okuži ta oseba -- torej tiste, ki stojijo preblizu in južno (y2 < y1). In tako rekurzivno naprej.

Naloga je praktično enaka nalogi s predavanj, na kateri smo morali najti imena vseh članov neke rodbine.

def okuzeni(ime, osebe):
    x1, y1 = koordinate(ime, osebe)
    nasrkali = {ime}
    for ime2, x2, y2 in osebe:
        if preblizu(x1, y1, x2, y2) and y2 < y1:
            nasrkali |= okuzeni(ime2, osebe)
    return nasrkali

Prireditev

Če oseba kihne, s prireditve takoj odstranijo njo in vse, ki so manj kot 1,5 m oddaljene od nje. Če torej kihne Jana, takoj odstranijo tudi Helgo in Emo. Napiši funkcijo kihanje(imena, osebe), ki prejme seznam imen oseb, ki so kihale (naštete so v vrstnem redu kihanja!) in seznam oseb na prireditvi. Vrne naj množico imen oseb, ki so po tem še na prizorišču.

Pazi na tole: če najprej kihne Jana in nato Helga, ostane Greta na prizorišču, saj je Helga kihnila, ko je bila že odstranjena!

Rešitev

No, tole je ta težka naloga.

Iti moramo prek imen kihajočih in za vsako od njih odstraniti vse pokihane. Na prvi pogled se to naredi tako

def kihanje(imena, osebe):
    for ime1 in imena:
        x1, y1 = koordinate(ime1, osebe)
        if x1 == None:  # Ta oseba je že odstranjena s seznama:
            # preskoči ostanek zanke, nadaljuj z naslednjim imenom
            continue 
        for ime2, x2, y2 in osebe:
            if preblizu(x1, y1, x2, y2):
                osebe.remove((ime2, x2, y2))

    return {ime for ime, x, y in osebe}

To ne deluje. Če spustimo zanko for prek seznama, iz katerega brišemo elemente, bo za vsakim izbrisanim elementom preskočila naslednjega. To smo menda videli na predavanjih.

Če hočemo reševati na ta način, moramo napisati nekaj takšnega:

def kihanje(imena, osebe):
    osebe = osebe.copy()

    for ime1 in imena:
        x1, y1 = koordinate(ime1, osebe)
        if x1 == None:
            continue
        i = 0
        while i < len(osebe):
            ime2, x2, y2 = osebe[i]
            if preblizu(x1, y1, x2, y2):
                del osebe[i]
            else:
                i += 1
    return {ime for ime, x, y in osebe}

Čez seznam gremo z zanko while, i je indeks. V vsakem koraku bodisi pobrišemo element bodisi povečamo indeks.

Zelo pomembno je, da na začetku funkcije naredimo kopijo seznama. Funkcije ne smejo meni nič tebi nič spreminjati vrednosti argumentov.

Nalogo preprosteje rešimo tako, da ne brišemo elementov seznama, temveč zložimo tiste, ki bodo ostali na prireditvi v nov seznam.

def kihanje(imena, osebe):
    for ime1 in imena:
        x1, y1 = koordinate(ime1, osebe)
        if x1 == None:
            continue
        ostanejo = []
        for ime2, x2, y2 in osebe:
            if not preblizu(x1, y1, x2, y2):
                ostanejo.append((ime2, x2, y2))
        osebe = ostanejo

    return {ime for ime, x, y in osebe}

Z osebe = ostanejo poskrbimo, da bomo v naslednjem krogu zanke delali le s tistimi, ki ostanejo na prireditvi.

V prejšnji funkciji smo napisali osebe = osebe.copy(), ker funkcija ne sme spreminjati vrednosti argumentov. Tu pa napišemo osebe = ostanejo?! To ne spremeni vrednosti argumenta osebe? Če ne razumeš, zakaj ne, poglej predavanje, na katerem smo risali puščice.

Sestavljanje novega seznama lahko poenostavimo z izpeljanim seznamom.

def kihanje(imena, osebe):
    for ime1 in imena:
        x1, y1 = koordinate(ime1, osebe)
        if x1 != None:
            osebe = [(ime2, x2, y2) for ime2, x2, y2 in osebe
                     if not preblizu(x1, y1, x2, y2)]
    return {ime for ime, x, y in osebe}

Če človek pogleda to funkcijo, potem se naloga niti ne zdi več tako težka, ne?

Bolj drugačna je tale rešitev: vse osebe, ki so na prireditvi, damo v množico. Odstranjene odstranimo iz množice. Če naletimo na ime, ki ga, ko kihne, sploh ni več v množici, ga ignoriramo.

def kihanje(imena, osebe):
    ostanejo = {ime for ime, x, y in osebe}
    for ime1 in imena:
        if ime1 not in ostanejo:
            continue
        x1, y1 = koordinate(ime1, osebe)
        for ime2, x2, y2 in osebe:
            if ime2 in ostanejo and preblizu(x1, y1, x2, y2):
                ostanejo.remove(ime2)
    return ostanejo

Prireditev

Sprogramiraj razred Prireditev z naslednjimi metodami.

• konstruktor kot argument prejme minimalno predpisano razdaljo (in, seveda, inicializira objekt)
• prihod(ime, x, y) prejme ime in želeni koordinati oseb. Če na predpisani razdalji (tisti, ki jo je prejel konstruktor) od teh koordinat ni nobene druge osebe, sprejme to osebo na te koordinate. V nasprotnem primeru to osebo zavrne. Metoda naj ne vrača ničesar.
• udelezenci() vrne množico imen vseh oseb, ki so bile sprejete na prireditev.

Rešitev

Kako razred shranjuje podatke, ki jih potrebuje za delo, je naša stvar. Očitno mora shraniti minimalno razdaljo, poleg tega pa koordinate in imena oseb na prireditvi. Meni se je zazdelo praktično shranjevati koordinate in imena ločeno.

class Prireditev:
    def __init__(self, razdalja):
        self.razdalja = razdalja
        self.zasedeno = []
        self.sprejeti = set()

    def prihod(self, ime, x, y):
        for x1, y1 in self.zasedeno:
            if (x - x1) ** 2 + (y - y1) ** 2 < self.razdalja ** 2:
                return
        self.zasedeno.append((x, y))
        self.sprejeti.add(ime)

    def udelezenci(self):
        return self.sprejeti

Metodo prihod bi se dalo skrajšati v

    def prihod(self, ime, x, y):
        if all((x - x1) ** 2 + (y - y1) ** 2 >= self.razdalja ** 2
                for x1, y1 in self.zasedeno)
            self.zasedeno.append((x, y))
            self.sprejeti.add(ime)

No, mogoče niti ni krajše, samo bolj fancy.