Rešitev

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

Branje datoteke

Podatki o ploščah se nahajajo v datoteki, ki je videti tako:

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

Vsaka vrstica predstavlja en pravokotnik, opisan s koordinatama levega zgornjega (prvi števili) in desnega spodnjega (drugi števili) oglišča.

Napiši funkcijo preberi_pravokotnike(ime_datoteke), ki prejme ime datoteke in vrne njeno vsebino kot seznam četverk. Za gornji primer vrne [(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)].

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 razdelimo glede na "-", in vsak del še naprej glede na ",". Dobljena števila pretvarjamo v int in zlagamo v seznam.

def preberi_pravokotnike(ime_datoteke):
    pravokotniki = []
    for vrstica in open(ime_datoteke):
        k1, k2 = vrstica.split("-")
        x1, y1 = k1.split(",")
        x2, y2 = k2.split(",")
        pravokotniki.append((int(x1), int(y1), int(x2), int(y2)))
    return pravokotniki

Nepokrita stena

Napiši funkcijo nepokrito(pravokotniki, sirina, visina), ki prejme seznam četvork, kot je gornji, ter širino in višino stene, ter vrne ploščino nepokritega dela stene. V gornjem primeru je to 34.

Rešitev

To nalogo zanima, ali se boste spomnili uporabiti množice - ali pa boste zviti na kak drug način.

Zelo preprosto lahko namreč sestavimo množico vseh pokritih kvadratkov mreže, pri čemer vsak kvadratek "shranimo" s koordinatami njegovega levega zgornjega kota. Množica je tu praktična zato, ker bo vsak kvadratek v njej le enkrat. Število nepokritih je potem enako ploščini celotne stene, od katere odštejemo število pokritih.

def nepokrito(pravokotniki, visina, sirina):
    pokrite = set()
    for x1, y1, x2, y2 in pravokotniki:
        pokrite |= {(x, y) for x in range(x1, x2) for y in range(y1, y2)}
    return visina * sirina - len(pokrite)

Ne bistveno bolj zapletena rešitev je, da se z dvema zankama zapeljemo prek vseh koordinat in za vsako preverimo, ali je znotraj vsaj enega pravokotnika. Če ni, je kvadratek nepokrit.

def nepokrito(pravokotniki, sirina, visina):
    nepokritih = 0
    for x in range(sirina):
        for y in range(visina):
            if not any(x1 <= x < x2 and y1 <= y < y2 for x1, y1, x2, y2 in pravokotniki):
                nepokritih += 1
    return nepokritih

Če so x1, y1, x2 in y2 meje pravokotnika, je točka x, y znotraj njega, če velja x1 <= x <= x2 and y1 <= y <= y2. Vendar želimo vsak kvadratek upoštevati le enkrat, torej na njegovi levi in gornji, ne pa tudi desni in spodnji meji, zato x1 <= x <= x2 and y1 <= y <= y2.

Če kdo ne zna delati z izpeljanimi seznami oz. generatorji, ne bo uporabil any, temveč se bo do tega, ali je strel kaj zadel, prebil po daljši poti. Najboljše, da kar s pomožno funkcijo.

def zadetek(x, y, pravokotniki):
    for x1, y1, x2, y2 in pravokotniki:
        if x1 <= x < x2 and y1 <= y < y2:
            return True
    return False

def nepokrito(pravokotniki, sirina, visina):
    nepokritih = 0
    for x in range(sirina):
        for y in range(visina):
            if not zadetek(x, y, pravokotniki):
                nepokritih += 1
    return nepokritih

Odstrani zgrešene

Steno uporabimo za strelske vaje. Napiši funkcijo odstrani_zgresene(streli, pravokotniki), ki prejme seznam koordinat strelov in seznam pravokotnikov. Funkcija ne vrne ničesar, temveč iz seznama strelov odstrani tiste, ki niso zadeli nobenega pravokotnika. Pravokotnik je zadet, tudi če ga krogla le oplazi.

Če imamo streli = [(0.55, 0.4), (0.1, 5), (5.1, 3.2), (7.1, 7.1), (8.5, 3.5)] in pokličemo odstrani_zgresene(streli, pravokotniki), bo streli po tem vseboval le še [(5.1, 3.2), (8.5, 3.5)].

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.

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

Komentirali ne bomo, ker smo že velikokrat.

Tule nam je, tako kot pri prejšnji nalogi, prišel prav any. A tudi če ga ne znamo uporabiti, nas ne bo konec:

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

Če strel naleti na kak pravokotnik, pustimo strel v seznamu in gremo na naslednjega (i + = 1, break). Če se zanka prek pravokotnikov izteče, ne da bi strel zadel katerega od njih, pa strel pobrišemo. Pazite, else se nanaša na for, ne na if.

Če se ne spomnimo niti tega, pa lahko še vedno napišemo ločeno funkcijo zadetek, kot v prejšnji nalogi, le da pri gornjih mejah ne uporabimo < temveč <=.

Je zlat

Pravokotnike oštevilčimo. Vsak ima svojo barvo, na primer barve = {1: "zlata", 2: "zlata", 3: "modra", 4: "rdeca", 5: "rumena", 6: "zelena", 7: "rumena", 8: "modra", 9: "zelena"}. Za vsak pravokotnik vemo, katere pravokotnike prekriva, na primer pravokotniki = {3: (4, 5), 5: (1, ), 4: (6, 7, 8), 2: (), 1: (), 6: (), 7: (), 8: ()} pomeni, da pravokotnik 3 prekriva pravokotnika 4 in 5.

Napiši funkcijo je_zlata(stevilka, barve, pravokotniki), ki prejme številko nekega pravokotnika ter podatke o barvah in prekrivanju. Funkcija vrne True, če je pravokotnik zlat ali pa ta pravokotnik prekriva kak pravokotnik, ki je zlat, ali pa prekriva katerega, ki prekriva katerega, ki prekriva katerega, ... ki je zlat. Sicer pa vrne False.

Rešitev

Očitno gre za nalogo iz rekurzije. In to takšno, ki smo jo pravzaprav že rešili. Lahko si predstavljamo, da so pravokotniki rodbina, za vsakega vemo, kdo so njegovi nasledniki, zanima pa nas, ali je med nasledniki kdo z imenom Zlatka.

def je_zlata(zgoraj, barve, pravokotniki):
    if barve[zgoraj] == "zlata":
        return True
    for spodaj in pravokotniki[zgoraj]:
        if je_zlata(spodaj, barve, pravokotniki):
            return True
    return False

Pravokotnik

Napiši razred Pravokotnik z naslednjimi metodami.

• Konstruktor prejme koordinate gornjega levega in spodnjega desnega oglišča (kot štiri cela števila).
• strel(x, y, ime_strelca) prejme koordinate nekega strela v steno in ime strelca.
• vseh_zadetkov() vrne število strelov, ki so zadeli ta pravokotnik.
• vseh_strelcev() vrne število strelcev, vštevši te, ki niso zadeli ničesar.
• zadetkov(ime_strelca) pove, kolikokrat je strelec s podanim imenom zadel ta pravokotnik.

Rešitev

Kakšne podatke si bo moral shraniti Pravokotnik? Svoje koordinate in števce zadetkov. Ti bodo v slovarju, katerega ključi so imena strelcev, vrednosti pa število zadetkov.

class Pravokotnik:
    def __init__(self, x1, y1, x2, y2):
        self.x1, self.y1 = x1, y1
        self.x2, self.y2 = x2, y2
        self.zadetki = {}

    def strel(self, x, y, strelec):
        if strelec not in self.zadetki:
            self.zadetki[strelec] = 0
        if self.x1 <= x <= self.x2 and self.y1 <= y <= self.y2:
            self.zadetki[strelec] += 1

    def zadetkov(self, strelec):
        return self.zadetki[strelec]

    def vseh_zadetkov(self):
        return sum(self.zadetki.values())

    def vseh_strelcev(self):
        return len(self.zadetki)

Tule nismo uporabili slovarja s privzetimi vrednostmi, saj mora vsebovati tudi strelce, ki niso zadeli ničesar, tako da bi nekje v vsakem primeru morali imeti tudi self.zadetki[strelec] = 0. Sicer pa so metode trivialne. V nalogi ste morali pokazati, da znate sestaviti razred; da znate programirati, ste (upam) pokazali v prejšnjih nalogah.

Šport

import re

def preberi_pravokotnike(ime_datoteke):
    return [tuple(int(mo) for mo in re.findall("\d+", vrstica)) for vrstica in open(ime_datoteke)]

def nepokrito(pravokotniki, sirina, visina):
    return sum(not any(x1 <= x < x2 and y1 <= y < y2 for x1, y1, x2, y2 in pravokotniki)
               for x in range(sirina) for y in range(visina))

def odstrani_zgresene(streli, pravokotniki):
    streli[:] = [(x, y) for x, y in streli
                 if any(x1 <= x <= x2 and y1 <= y <= y2 for x1, y1, x2, y2 in pravokotniki)]

def je_zlata(zgoraj, barve, pravokotniki):
    return barve[zgoraj] == "zlata" \
        or any(je_zlata(spodaj, barve, pravokotniki) for spodaj in pravokotniki[zgoraj])