Rešitev
Nadmorske višine točk na pravokotni mreži lahko shranimo v terko terk. Tako lahko višine na desni predstavimo s
teren = ((6, 17, 18, 19, 21, 21),
(8, 12, 3, 19, 23, 22),
(14, 14, 13, 19, 20, 21),
(15, 16, 12, 19, 23, 23),
(9, 5, 11, 11, 25, 24),
(8, 6, 8, 22, 22, 22, 22),
(8, 6, 8, 22, 22, 22, 22))
Višina točke s koordinatama x, y je očitno zapisana v teren[y][x].
Vrhovi
Napiši funkcijo koordinate_sosedov(x, y, teren), ki prejme koordinati neke točke in teren (potrebuje ga le, da razbere širina in dolžina mreže). Funkcija vrne množico koordinat vseh sosednjih štirih točk (ali manj, če je točka na robu ali v kotu). Klic koordinate_sosedov(4, 2, teren) vrne {(3, 2), (5, 2), (4, 1), (4, 3)} in klic koordinate_sosedov(5, 2, teren) vrne {(5, 1), (5, 3), (4, 2)} (ker je koordinata x že na robu). Ta funkcija bo prišla prav pri dveh drugih funkcijah.
Napiši funkcijo vrhovi(teren), ki vrne množico koordinat vrhov. Točka je vrh, če ne leži na robu in je višja od vseh sosedov. Prepoznaš jih po tem, da iz njih kažejo štiri puščice. V gornjem primeru so to {(1, 3), (4, 1), (4, 4)}.
Rešitev
Ko bi nam ne bilo potrebno paziti na robove, bi lahko napisali kar
# Ta rešitev ni pravilna
def koordinate_sosedov(x, y, teren):
return {(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)}
Vendar lahko vsakega od teh elementov dodamo le, če je znotraj meja, torej
def koordinate_sosedov(x, y, teren):
sosedi = set()
if x - 1 >= 0:
sosedi.add((x - 1, y))
if y - 1 >= 0:
sosedi.add((x, y - 1))
if x + 1 < len(teren[0]):
sosedi.add((x + 1, y))
if y + 1 < len(teren):
sosedi.add((x, y + 1))
return sosedi
Višina terena je len(teren), širina pa je dolžina prvega (ali kateregakoli drugega) elementa, torej len(teren[0]).
Krajši možnosti sta
def koordinate_sosedov(x, y, teren):
return {(x + dx, y + dy) for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1))
if 0 <= x + dx < len(teren[0]) and 0 <= y + dy < len(teren)}
in
def koordinate_sosedov(x, y, teren):
return {(x, y) for x, y in ((x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1))
if 0 <= x < len(teren[0]) and 0 <= y < len(teren)}
Funkcija vrhovi bo takšna:
def vrhovi(teren):
vrh = set()
for y in range(1, len(teren) - 1):
for x in range(1, len(teren[0]) - 1):
je_vrh = True
for sx, sy in koordinate_sosedov(x, y, teren):
if teren[sy][sx] >= teren[y][x]:
je_vrh = False
break
if je_vrh:
vrh.add((x, y))
return vrh
Ali, če se spomnimo else-a po for-u, takšna:
def vrhovi(teren):
vrh = set()
for y in range(1, len(teren) - 1):
for x in range(1, len(teren[0]) - 1):
for sx, sy in koordinate_sosedov(x, y, teren):
if teren[sy][sx] >= teren[y][x]:
break
else:
vrh.add((x, y))
return vrh
Nič od tega ni posebej prijazno: tri gnezdene zanke for. V prvih dveh ne gremo po celotnem terenu (range(len(teren))) temveč izpustimo prvo in zadnjo vrstico (oz. stolpec), zato range(1, len(teren) - 1). Robne točke po definiciji namreč niso vrhovi. Nato za vsak vrh preverimo sosede in če med njimi ni nobenega, ki bi bil višji od te točke, gre za vrh.
Kot (skoraj) vedno, si lahko izdatno pomagamo z izpeljanimi množicami.
def vrhovi(teren):
return {(x, y) for y in range(1, len(teren) - 1)
for x in range(1, len(teren[0]) - 1)
if all(teren[y][x] > teren[sy][sx]
for sx, sy in koordinate_sosedov(x, y, teren))
}
Najnižja
Lenuh gre vedno le navzdol. Napiši funkcijo najnizja(x, y, teren), ki vrne višino najnižje točke, ki jo lahko doseže lenuh, če začne pot na koordinatah x, y. Če začne na 3, 3, gre lahko levo ali dol. Če gre dol, bo dosegel le 11, če levo, pa lahko nadaljuje dol in levo (ali pa levo, dol, dol, levo, gor) ter doseže 5. Funkcija torej vrne 5.
Pazi, lenuh ne gre v najnižjo možno točko v danem trenutku. V gornjem primeru gre iz 19 na 12, ne 11.
Rešitev
Naloga je precej podobna nalogi, v kateri smo iskali najmlajšega člana rodbine, le da imamo tu namesto potomcev sosede. Se pravi, čisto klasična rekurzija.
# Tole ne deluje!
def najnizja(x, y, teren):
naj = teren[y][x]
for sx, sy in koordinate_sosedov(x, y, teren):
naj_pod = najnizja(sx, sy, teren)
if naj_pod < naj:
naj = naj_pod
return naj
Vendar imamo problem: v rodbini se nikoli ne zgodi, da bi se vrnili k osebi, ki smo jo že pregledovali. Tu se lahko - ena točka je sosed druge, druga pa spet sosed prve. Če poženemo gornjo funkcijo, se znajdemo v neskončni rekurziji.
Po drugi strani slika na začetku izpita vsebuje puščice. Če bomo rekurzijo izvedli tako, da bomo sledili le puščicam in ne vsem sosedom, do gornje težave ne bo prišlo: če gremo iz neke točke v neko drugo, gotovo nikoli ne bomo šli nazaj. Potrebujemo torej še dodatni pogoj:
def najnizja(x, y, teren):
naj = teren[y][x]
for sx, sy in koordinate_sosedov(x, y, teren):
if teren[sy][sx] < teren[y][x]:
naj_pod = najnizja(sx, sy, teren)
if naj_pod < naj:
naj = naj_pod
return naj
Krajše pa je tako:
def najnizja(x, y, teren):
return min([najnizja(sx, sy, teren)
for sx, sy in koordinate_sosedov(x, y, teren)
if teren[sy][sx] < teren[y][x]], default=teren[y][x])
Višinski metri
Kolesar pa šteje "višince". Če začne na 1, 3 in gre po poti ">>>^<<^v", bo vozil prek točk z višinami 16, 12, 19, 23, 20, 19, 13, 3, 13. Vsota vzponov je (19–12) + (23–19) + (13–3) = 7 + 4 + 10 = 21. Napiši funkcijo visinski_metri(pot, x, y, teren), ki vrne skupno višino vzponov. Predpostaviti smeš, da pot nikoli ne pelje izven meja mreže.
Rešitev
Edina spretnost, ki jo je zahtevala ta naloga, je, da si pred vsakim korakom zapomnimo prejšnjo višino, da jo lahko primerjamo z novo.
def visinski_metri(pot, x, y, teren):
visinci = 0
visina = teren[y][x]
for korak in pot:
if korak == "<":
x -= 1
elif korak == ">":
x += 1
elif korak == "^":
y -= 1
else:
y += 1
nova_visina = teren[y][x]
if nova_visina > visina:
visinci += nova_visina - visina
visina = nova_visina
return visinci
Žretje
Koordinate polj na šahovnici so označene s črko in številko. "c6" pomeni tretji stolpec in šesto vrstico.
V neki igri, ki se igra na šahovnici, vendar nima zveze s šahom, igralca premikata figure. Kadar nekdo premakne figuro na polje, kjer že stoji druga figura, slednjo odstrani s šahovnice.
Napiši funkcijo zretje(figure, poteze), ki prejme terko s polji, na katerih stojijo figure, in poteze v obliki seznama terk (odkod, kam). Funkcija vrne število figur, ki po teh potezah ostanejo na šahovnici. zretje(("a2", "b1"), [("a2", "a3"), ("b1", "a3")]), vrne 1: prvi igralec premakne figuro iz a2 na a3, drugi pa z b1 na a3, s čimer odstrani prvo figuro in na koncu je na igralni plošči le še ena figura.
Rešitev
Na vsakem polju je lahko le ena figura. Če naloga sprašuje po številu figur, je to isto, kot če bi spraševala po številu zasedenih polj. Funkcija mora torej le opazovati množico zasedenih polj: posledica vsakega premika je, da neko polje ni več zasedeno, neko pa (p)ostane zasedeno.
def zretje(figure, poteze):
figure = set(figure)
for odkod, kam in poteze:
figure.remove(odkod)
figure.add(kam)
return len(figure)
Figure
V testih je podan razred Figura, ki predstavlja figuro na šahovnici. Tega ne spreminjaj, pač pa iz njega izpelji razreda Trdnjava in Lovec. Definiraj jima nov konstruktor in metodo premik z enakimi argumenti kot podedovani metodi.
Trdnjava (top) se premika vodoravno ali navpično. Metoda premik prejme smer, ki je lahko "|" ali "-" in razdaljo. Metoda spremeni x ali y za podano razdaljo; pozitivna razdalja poveča x oz. y, negativna ga zmanjša.
Lovec (tekač, laufar) se premika diagonalno. Metoda premik prejme smer \ ali / in razdaljo. Pozitivna razdalja vedno poveča y in negativna ga zmanjša. Sprememba x je odvisna od smeri: pri smeri / pozitivna razdalja poveča x, negativna ga zmanjša. Pri smeri \ pozitivna razdalja zmanjša x, negativna ga poveča.
Poleg tega, ne da bi spremenil(a) ali sestavila novo metodo opis, poskrbi, da bo metoda opis za trdnjavo na, recimo, koordinatah 3, 5 vrnila "Trdnjava na c5" (in ne "Figura na c5"), za lovca na 3, 5 pa "Lovec na c5".
Rešitev
V testih je bil podan razred:
# Ta razred je bil že podan v testih
class Figura:
def __init__(self, x, y):
self.x = x
self.y = y
self.ime = "figura"
def opis(self):
return f"{self.ime} na {' abcdefgh'[self.x]}{self.y}"
def premik(self, smer, razdalja):
pass
Trdnjava je preprostejša. Konstruktor pokliče podedovani konstruktor in potem spremeni self.ime v "Trdnjava", kar je vse, kar moramo storiti, da dobimo zahtevani opis. Metoda premik pa x ali y poveča za razdalja.
class Trdnjava(Figura):
def __init__(self, x, y):
super().__init__(x, y)
self.ime = "Trdnjava"
def premik(self, smer, razdalja):
if smer == "-":
self.x += razdalja
else:
self.y += razdalja
Pričakoval sem (v času pisanja teh rešitev pa še ne vem, ali se je to zgodilo), da bo veliko študentov pisalo
if smer == "-":
if razdalja > 0:
self.x += razdalja
else:
self.x -= abs(razdalja)
# in potem enako še za y
To je seveda nepotrebno, saj je abs(razdalja) pri negativnih razdaljah isto kot -razdalja, in self.x -= -razdalja je, jasno, isto kot self.x += razdalja. Pa smo pri krajši, zgornji rešitvi. self.x += razdalja namreč naredi natančno to, kar mora: poveča self.x, če je razdalja pozitivna, in ga zmanjša, če je negativna.
Po tem premisleku na enak način sprogramiramo še lovca, le da v tem primeru pri smeri \ pri x-u zamenjamo += z -=.
class Lovec(Figura):
def __init__(self, x, y):
super().__init__(x, y)
self.ime = "Lovec"
def premik(self, smer, razdalja):
if smer == "/":
self.x += razdalja
self.y += razdalja
else:
self.x -= razdalja
self.y += razdalja