Rešitev

Na steno pribijemo pravokotne plošče; nekatere se tudi prekrivajo. Koordinate oglišč so vedno cela števila. Primer kaže slika.

Razpored s slike opišemo s seznamom [(0, 1, 4, 3), (0, 6, 1, 8), (2, 2, 7, 6), (3, 4, 6, 5), (5, 1, 9, 7), (8, 0, 10, 2), (8, 3, 10, 5), (8, 6, 11, 8)]. Prvi števili četvorke sta koordinati levega gornjega, drugi pa desnega spodnjega oglišča.

Steno bomo uporabljali za strelske vaje.

Branje datoteke

Podatki o strelih se nahajajo v datoteki, ki je videti tako (števili predstavljata koordinati strela):

Ana: 0.55, 3.14
Berta: 5.5, 4.5
Ana: 6.5, 6.5
Cilka: 10.3, 6.3

Napiši funkcijo preberi_strele(ime_datoteke), ki prejme ime datoteke in vrne vsebino v obliki trojk (ime, x, y), na primer [("Ana", 0.55, 3.14), ("Berta", 5.5, 4.5), ("Ana", 6.5, 6.5), ("Cilka", 10.3, 6.3)].

Rešitev

Nalogo očitno zanima, ali znate brati datoteke in vleči narazen nize. Natančno to, kar smo delali v domači nalogi o spečih stražarjih.

Vrstico najprej razbijemo glede na ":", nato glede na ,. Terke zlagamo v seznam, pri čemer koordinati pretvorimo v float.

def preberi_strele(ime_datoteke):
    streli = []
    for vrstica in open(ime_datoteke):
        ime, koordinate = vrstica.split(":")
        x, y = koordinate.split(",")
        streli.append((ime, float(x), float(y)))
    return streli

Najboljši strelec

Napiši funkcijo najboljsi_strelec(streli, pravokotniki), ki prejme seznam strelov in pravokotnikov (kot v gornjih primerih) in vrne ime strelca, ki je največkrat zadel kak pravokotnik. Vsak strel šteje le enkrat, tudi če zadane več pravokotnikov. Če je enako dobrih več, vrne ime tistega, ki je prej.

Rešitev

Prvi del funkcije je štetje, drugi iskanje ključa, ki pripada največji vrednosti. Oboje poznamo iz (več) domačih nalog in vaj.

def najboljsi_strelec(streli, pravokotniki):
    zadetki = {}
    for ime, x, y in streli:
        if ime not in zadetki:
            zadetki[ime] = 0
        if any(x1 <= x <= x2 and y1 <= y <= y2
               for x1, y1, x2, y2 in pravokotniki):
            zadetki[ime] +=  1

    naj_ime = None
    for ime, zadetkov in zadetki.items():
        if naj_ime is None or zadetkov > zadetki[naj_ime] or zadetkov == zadetki[naj_ime] and ime < naj_ime:
            naj_ime = ime
    return naj_ime

Zakaj ne uporabimo defaultdict-a? Ker moramo imeti v slovarju tudi strelce, ki niso zadeli ničesar. Zato bomo na nekem mestu tako ali tako morali reči zadetki[ime] = 0. Če je tako, pa ne potrebujemo defaultdict-a.

Edina zanimiva reč tule je any, s katerim preverjamo, ali je kak pravokotnik zadet. Če tega ne znamo tako, je naše življenje nekoliko bolj zapleteno, a ne preveč.

def najboljsi_strelec(streli, pravokotniki):
    zadetki = {}
    for ime, x, y in streli:
        if ime not in zadetki:
            zadetki[ime] = 0
        for x1, y1, x2, y2 in pravokotniki:
            if x1 <= x <= x2 and y1 <= y <= y2:
                zadetki[ime] += 1
                break

    naj_ime = None
    for ime, zadetkov in zadetki.items():
        if naj_ime is None or zadetkov > zadetki[naj_ime] or zadetkov == zadetki[naj_ime] and ime < naj_ime:
            naj_ime = ime
    return naj_ime

Zdaj za vsak strel gremo prek vseh pravokotnikov in če je kateri zadet, povečamo rezultat tega strelca ter zanko prekinemo z break, saj vsak strel šteje le enkrat.

Kdor zna uporabiti any in poleg tega ve, da je True isto kot 1 in False isto kot 0, pa lahko reši hitreje - in to z defaultdict-om. Pa tudi drugega dela se lahko tisti, ki vedo malo več, zlahka znebijo.

def najboljsi_strelec(streli, pravokotniki):
    zadetki = defaultdict(int)
    for ime, x, y in streli:
        zadetki[ime] += any(x1 <= x <= x2 and y1 <= y <= y2
                            for x1, y1, x2, y2 in pravokotniki)
    return min(zadetki, key=lambda ime: (-zadetki[ime], ime))

Odstrani zadete

Napiši funkcijo odstrani_zadete(x, y, pravokotniki), ki prejme koordinate strela in seznam pravokotnikov. Funkcija ne vrne ničesar, pač pa iz podanega seznama odstrani preluknjane pravokotnike. Če je pravokotniki gornji seznam, odstrani_zadete(6, 4.5, pravokotniki) odstrani 2, 3 in 4 element seznama.

Rešitev

V tej nalogi ste morali znati napisati funkcijo, ki spreminja podani seznam. Brisanje elementov iz seznamov - ne da bi kakega izpustili - je prav tako nekaj, kar smo na predavanjih večkrat omenili, pa tudi v domačih nalogah vas je občasno pestilo.

Temu, ki se je tega naučil, se je morala zdeti naloga preprosta.

def odstrani_zadete(x, y, pravokotniki):
    i = 0
    while i < len(pravokotniki):
        x1, y1, x2, y2 = pravokotniki[i]
        if x1 <= x <= x2 and y1 <= y <= y2:
            del pravokotniki[i]
        else:
            i += 1

Najbolj levo

Za vsak pravokotnik izvemo še, kateri pravokotniki so direktno pod njim, na primer prekrivanja = {3: (2, ), 2: (0, 4), 4: (5, 6, 7), 1: (), 0: (), 5: (), 6: (), 7: ()} pomeni, da pravokotnik 2 prekriva pravokotnika 0 in 4 (pravokotnik 4 pa potem pokriva 5, 6 in 7). Številke predstavljajo indekse v seznamu koordinat pravokotnikov.

Lesni črv leze na vse štiri smeri in proti steni, nikoli pa navzven. Iz 2 lahko gre v 0 in 4, ne pa obratno. Iz 3 gre v 2, ne pa iz 2 v 3.

Napiši funkcijo naj_levo(zacetek, pravokotniki, prekrivanja), ki dobi številko pravokotnika, v katerem črv začne pot, seznam pravokotnikov in prekrivanja. Vrniti mora najbolj levo koordinato, ki jo lahko črv doseže.

Pazi: črvu se ne splača vedno riniti na levo. Včasih mora iti desno, da bo potem lahko prišel bolj levo.

Rešitev

Naloga je očitno naloga iz rekurzije. Pravokotniki so kot rodbina, za vsakega poznamo njegove naslednike. Naloga je torej podobna nalogi iskanja najmlajšega člana rodbine, ali pa najdaljšega imena v rodbini. Kdor se je znašel, je rešitev praktično prepisal iz zapiskov - res pa je moral prepoznati, za kaj v tej nalogi v bistvu gre.

def naj_levo(odkod, pravokotniki, prekrivanja):
    levo = pravokotniki[odkod][0]
    for spodaj in prekrivanja[odkod]:
        levo_spod = naj_levo(spodaj, pravokotniki, prekrivanja)
        if levo_spod < levo:
            levo = levo_spod
    return levo

Najprej predpostavimo, da je najbolj levo ta pravokotnik, na katerem smo trenutno. Nato gremo prek vseh "naslednikov" tega pravokotnika in pogledaom, kdo je najbolj levo v njegovi "rodbini". Če se najde v rodbini kdo, ki je bolj levo od najbolj levega, ki smo ga našli doslej, si to zapomnimo.

Turnir

Napiši razred Turnir z naslednjimi metodami.

• Konstruktor prejme seznam pravokotnikov.
• strel(x, y) prejme koordinate strela.
• zadetkov(x1, y1, x2, y2) prejme koordinate enega od pravokotnikov in vrne število krogel, ki ga je zadelo (ali se ga vsaj dotaknilo). Krogla preluknja vse pravokotnike na poti skozi steno.

Rešitev

Očitno bo potrebno spet nekaj šteti. Dril poznamo: potrebujemo slovar, ključi so tisto, kar štejemo, vrednosti so števila. Slovar bo shranjen med atributi razreda Turnir.

class Turnir:
    def __init__(self, pravokotniki):
        self.pravokotniki = {}
        for pravokotnik in pravokotniki:
            self.pravokotniki[pravokotnik] = 0

    def strel(self, x, y):
        for pravokotnik in self.pravokotniki:
            x1, y1, x2, y2 = pravokotnik
            if x1 <= x <= x2 and y1 <= y <= y2:
                self.pravokotniki[pravokotnik] += 1

    def zadetkov(self, x1, y1, x2, y2):
        return self.pravokotniki[(x1, y1, x2, y2)]

Ključi so celi pravokotniki, zato

```for pravokotnik in self.pravokotniki: x1, y1, x2, y2 = pravokotnik

Potrebujemo namreč tako terko kot posamične koordinate.

Zanimivo je, da lahko v zadnji vrstici pozabimo oklepaje in pišemo kar `return self.pravokotniki[x1, y1, x2, y2]`. Če je indeksov več (Python ima knjižnice za delo z večdimenzionalnimi matrikami), se ti kar sami spremenijo v terke. To spoznanje nam poenostevi tudi metodo `strel`.

```python
class Turnir:
    def __init__(self, pravokotniki):
        self.pravokotniki = {}
        for pravokotnik in pravokotniki:
            self.pravokotniki[pravokotnik] = 0

    def strel(self, x, y):
        for x1, y1, x2, y2 in self.pravokotniki:
            if x1 <= x <= x2 and y1 <= y <= y2:
                self.pravokotniki[x1, y1, x2, y2] += 1

    def zadetkov(self, x1, y1, x2, y2):
        return self.pravokotniki[x1, y1, x2, y2]

Če se spet spomnimo, da je True isto kot 1 in False isto kot 0, pa pišemo kar

class Turnir:
    def __init__(self, pravokotniki):
        self.pravokotniki = dict.fromkeys(pravokotniki, 0)

    def strel(self, x, y):
        for x1, y1, x2, y2 in self.pravokotniki:
            self.pravokotniki[x1, y1, x2, y2] += x1 <= x <= x2 and y1 <= y <= y2

    def zadetkov(self, x1, y1, x2, y2):
        return self.pravokotniki[x1, y1, x2, y2]

Aja, pa še nekdo nam mora prišepniti, da ima dict metodo fromkeys - kaj naredi, je menda očitno.