Rešitev

Preživeli

Na šahovnico polagamo figure, recimo takole: [("kmet1", "a2"), ("kmet2", "b2"), ("kmet3", "c2"), ("lovec1", "c1"), ("top1", "a1"), ("konj2", "b2"), ("kraljica", "d1"), ("lovec2", "b2"), ("top2", "c2")]. Pri tem so a2, b2, ... oznake polj. Vsaki figuri, smo, očitno, dali drugo ime, tako da jih ločimo. Opazimo pa še nekaj: na polje b2 smo dali najprej kmet2, nato konj2, nato lovec2. Na koncu se tam nahaja lovec2; figuri kmet2 in konj2 sproti odstranimo.

Napiši funkcijo preziveli(postavitev), ki prejme seznam, kot je gornji, in vrne množico imen preživelih figur. V gornjem primeru mora vrniti {"kmet1", "lovec1", "top1", "kraljica", "lovec2", "top2"}.

Rešitev

Rešitev bi bila lahko takšna:

def preziveli(postavitev):
    sahovnica = {}
    for figura, polje in postavitev:
        sahovnica[polje] = figura
    return set(sahovnica.values())

Bistvene so prve tri vrstice: sahovnica bo slovar, katerega ključi bodo polja, vrednosti pa figura, ki je trenutno na tam polju. V zanki postavljamo figure in nove figura na določenem polju bo izpodrinila prejšnjo, kot bi jo na šahovnici.

Na koncu iz slovarja poberemo le vrednosti (sahovnica.values()) in jih spravimo v množico.

Če znamo uporabljati izpeljane slovarje, lahko funkcijo skrajšamo kar v

def preziveli(postavitev):
    return set({polje: figura for figura, polje in postavitev}.values())

Pri tej nalogi gre toraj za to, ali se bo študent sponnil uporabiti slovar ali ne. Dodatna past je v tem, da naloga zahteva, da funkcija vrne množico, ne slovarja -- na ta način ne namigne, kaj pravzaprav hoče, istočasno pa še malo zavaja, čeprav je množica, če malo premislimo, neuporabna za sledenje temu, kdo je na katerem polju.

Brez slovarjev bi lahko, recimo, za vsako figuro pogledali, ali kdaj kasneje na isto polje postavimo drugo figuro. Če smo spretni (torej: poznamo enumerate, znamo razpakirati bolj zapletene terke in znamo uporabiti else po for - skratka, če znamo solidno dobro programirati), bomo dobili tole:

def preziveli(postavitev):
    neodstranjeni = set()
    for i, (figura, polje) in enumerate(postavitev):
        for _, polje1 in postavitev[i + 1:]:
            if polje1 == polje:
                break
        else:
            neodstranjeni.add(figura)
    return neodstranjeni

Vendar študent, ki se ne spomni ne slovarje, najbrž ne pozna vsega zgoraj naštetega, in se v tej nalogi žal ... malo izgubi.

Prosta polja

Kraljice ogrožajo vsa polja v isti vrstici, stolpcu ali na diagonali. Napiši funkcijo prosta_polja(kraljice), ki prejme koordinate kraljic (teh je lahko poljubno veliko) in vrne število neogroženih polj. Koordinate bomo poslej opisovali s terkami, da bo lažje programirati.

Za sliko na desni klic prosta_polja([(1, 1), (3, 7)]) vrne 24 – kolikor je neprečrtanih polj.

Rešitev

Dve možnosti imamo. Sestavimo množico vseh polj, nato pa gremo prek vseh kraljiv in za vsako iz množice pobrišemo vsa polja, ki jih ta kraljica ogroža. Druga je, da gremo čez vsa polja in za vsako polje pogledamo, ali je ogroženo. Drugo zveni boljše.

def prosta_polja(kraljice):
    prostih = 0
    for px in range(1, 9):
        for py in range(1, 9):
            for x, y in kraljice:
                if px == x or py == y or abs(px - x) == abs(py - y):
                    break
            else:
                prostih += 1
    return prostih

To torej ni naloga iz slovarjev ali česa podobnega, temveč le iz zank. Študent mora znati ugnezdiiti tri zanke: prvi dve gresta čez dvodimenzionalno polje, tretja čez kraljice. Če naletimo na takšno, ki ogroža polje, prekinemo zanko z break. Blok else se bo izvedel, če zanke nismo prekinili - v tem primeru imamo eno prosto polje več.

Pogoj, ki preverja, ali je polje ogroženo, očitno najprej preveri stolpec in vrstico, tretji pogoj pa hkrati preveri obe diagonali: dve polji sta na isti diagonali, če sta razdalji v smeri x in y enaki, pri čemer z abs odstranimo morebitni negativni predznak.

Zoprnij s for-break-else se znebimo, če znamo uporabljati generatorje in all.

def prosta_polja(kraljice):
    prostih = 0
    for px in range(1, 9):
        for py in range(1, 9):
            if all(px != x and py != y and abs(px - x) != abs(py - y)
                   for x, y in kraljice):
                prostih += 1
    return prostih

Če vemo, da je True isto kot 1 in False isto kot 0, se znebimo še pogoja.

def prosta_polja(kraljice):
    prostih = 0
    for px in range(1, 9):
        for py in range(1, 9):
            prostih += all(px != x and py != y and abs(px - x) != abs(py - y)
                           for x, y in kraljice)
    return prostih

Če opazimo, da v resnici računamo vsoto prek (dvojne zanke), pa vse skupaj stlačimo v

def prosta_polja(kraljice):
    return sum(
        all(px != x and py != y and abs(px - x) != abs(py - y) for x, y in kraljice)
        for px in range(1, 9) for py in range(1, 9)
    )

Dostopna polja

Top (AKA trdnjava) se lahko pomika le vodoravno in navpično. Trdnjavi na sliki je v tem trenutku dostopnih 8 polj (vključno s tem, na katerem stoji).

Napiši funkcijo dostopnih_polj(koordinate, zasedena), ki prejme koordinati trdnjave in vseh figur ter vrne število dostopnih polj. Koordinati sta podani kot terka. Za sliko na desni klic dostopnih_polj((6, 5), [(1, 2), (3, 5), (4, 2), (5, 3), (6, 2), (7, 3), (8, 4), (6, 7), (1, 5), (6, 8)]) torej vrne 8.

Rešitev

def dostopnih_polj(koordinate, zasedena):
    xk, yk = koordinate
    vrstica = [x for x, y in zasedena if y == yk] + [0, 9]
    stolpec = [y for x, y in zasedena if x == xk] + [0, 9]
    return (
        min(x for x in vrstica if x > xk) - max(x for x in vrstica if x < xk) - 1
        + min(y for y in stolpec if y > yk) - max(y for y in stolpec if y < yk) - 1
        - 1)

Najprej bomo razkopali koordinati topa v xk in yk, ker je lepše imeti spremenljivke kot stalno pisati koordinate[0] in koordinate[1].

Nato v seznama vrstica poberemo koordinate x vseh figur iz vrstice, v kateri je top (torej koordinate x vseh figur, ki imajo enako koordinato y kot top). To so figure, ki bodo omejevale gibanje topa. Za vsak slučaj si izmislimo, da imamo še dve figuri na koordinateh 0 in 9, da poskrbimo za primer, ko levo ali desno od topa ni nobene figure. Podobno naredimo z vrstico.

Nato poiščemo najmanjšo koordinato x, ki je večja od topove (min(x for x in vrstica if x > xk)) in največjo koordinato x, ki je manjša. Odštejemo ju, od razlike pa odštejemo 1. Če sta figuri, ki omejujeta trdnjavo, na poljih 6 in 2, so vmes tri prosta polja (3, 4 in 5), zato 6 - 2 - 1.

Na enak način kot število prostih polj v vrstici dobimo še število prostih polj v stolpcu. Števili seštejemo, od vsote pa odštejemo še 1, ker smo polje, na katerem stoji trdnjava, šteli dvakrat - enkrat pri vrsticah in enkrat pri stolpcih.

V gornji rešitvi smo na debelo uporabljali izpeljane sezname. Seveda bi šlo tudi brez njih, le nekaj vrstic daljše bi bilo.

Zaščiteni kmetje

Kmet ščiti kmeta, ki se nahajata eno vrsto višje na levi in na desni. Tako kmet, ki stoji na (4, 2) (glej zadnjo sliko) ščiti kmeta na (5, 3). Kmet na (5, 3) ščiti kmeta na (4, 4) in (6, 4). Kmet (4, 4) ščiti kmeta (3, 5). Tako lahko rečemo tudi, da kmet (4, 2) posredno ščiti kmeta (3, 5).

Napiši funkcijo sciti_kmeta(x1, y1, x2, y2, kmetje), ki prejme koordinate prvega in drugega kmeta ter položaje vseh kmetov (vključno s tema dvema). Vrne True, če prvi kmet (posredno ali neposredno) ščiti drugega, in False, če ne.

Pomoč: Kmet A ščiti kmeta B, če A neposredno ščiti B, ali pa A ščiti nekoga, ki posredno ali neposredno ščiti B.

Rešitev

Zadnji odstavek je izdal vse. Definicija ščitenja je očitno rekurzivna.

def sciti_kmeta(x1, y1, x2, y2, kmetje):
    return y2 == y1 + 1 and abs(x1 - x2) == 1 \
        or (x1 + 1, y1 + 1) in kmetje and sciti_kmeta(x1 + 1, y1 + 1, x2, y2, kmetje) \
        or (x1 - 1, y1 - 1) in kmetje and sciti_kmeta(x1 - 1, y1 + 1, x2, y2, kmetje)

V prvi vrstici se vprašamo, ali prvi kmet neposredno ščiti drugega. V drugi preverimo, ali je desno od prvega nekdo, ki (posredno ali neposredno - zato rekurzija!) ščiti drugega. V tretji podobno preverimo še kmeta na levi.

Popotni top

Napiši razred Top.

• Konstruktor prejme koordinati topa (kot števili).
• Metoda premik(smer, polj) prejme smer, ki je lahko "^", "v", "<", ">", in razdaljo. Metoda premakne topa.
• Metoda koordinate() vrne trenutne koordinate topa (kot terko).
• Metoda razdalja() vrne skupno razdaljo, ki jo je prehodil top.

Poleg tega iz razreda Top izpelji razred StarTop. Značilnost starega topa je, da se ne more dvakrat zapored premakniti za več kot tri polja. Če enemu premiku za štiri polja (ali več) sledi nov tak ukaz, ga ignorira. Naslednji ukaz po tem spet upošteva, saj se je vmes spočil.

Rešitev

Top mora vedeti, kje je (koordinati bomo poimenovali x in y) in kakšno razdaljo je prevozil (temu recimo kilometrina). Konstruktor prejme argumenta, ki je shrani v x in y, kilometrina pa bo v začetku 0. Metode, ki jih moramo napisati, so potem trivialne.

class Top:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.kilometrina = 0

    def premik(self, smer, polj):
        if smer == "^":
            self.y += polj
        elif smer == "v":
            self.y -= polj
        elif smer == "<":
            self.x -= polj
        elif smer == ">":
            self.x += polj
        self.kilometrina += polj

    def koordinate(self):
        return self.x, self.y

    def razdalja(self):
        return self.kilometrina

Razred StarTop bo moral vedeti še, kakšna je bila zadnja prevožena razdalja. Temu bomo rekli prejsnja_razdalja. V konstruktorju jo bomo nastavili na 0.

class StarTop(Top):
    def __init__(self, x, y):
        super().__init__(x, y)
        self.prejsnja_razdalja = 0

    def premik(self, smer, polj):
        if self.prejsnja_razdalja > 3 and polj > 3:
            self.prejsnja_razdalja = 0
        else:
            super().premik(smer, polj)
            self.prejsnja_razdalja = polj

Metoda premik najprej preveri, ali sta tako prejsnja kot nova zahtevana razdalja večja od 3. V tem primeru se ne premakne in v prejsnja_razdalja napiše 0.

Če se bo premaknil, pa to stori tako, da pokliče podedovano metodo premik, nato pa si zapomni, kakšno razdaljo je pravkar naredil.