Rešitev

Rešitev

Najprej (ne preveč skompresirana) rešitev celotnega izpita. Rešitve posameznih nalog so razložene spodaj.

# 1

def preveri_vrsto(vrsta, prepovedani):
    prepovedani = set(prepovedani)
    for a, b in zip(vrsta, vrsta[1:]):
        if (a, b) in prepovedani or (b, a) in prepovedani:
            return False
    return True

# 2

def odprepovej(vrsta, prepovedani):
    zaporedni = set(zip(vrsta, vrsta[1:])) | set(zip(vrsta[1:], vrsta))
    prepovedani[:] = [x for x in prepovedani if x not in zaporedni]

# 3

def najbolj_oddaljena(kraj, kraji):
    for meja1, xm, ym in kraji:
        if meja1 == kraj:
            break

    naj1 = naj2 = naj_razdalja = 0
    for kraj1, x1, y1 in kraji:
        if y1 >= ym:
            continue
        for kraj2, x2, y2 in kraji:
            if y2 >= ym:
                continue
            razdalja = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if razdalja > naj_razdalja:
                naj1, naj2 = kraj1, kraj2
                naj_razdalja = razdalja
    return naj1, naj2

# 4

def kdo_dobi(bot, boti):
    kdo = {bot}
    for kam, st in boti[bot]:
        if kam == "bot":
            kdo |= kdo_dobi(st, boti)
    return kdo

# 5

class Ladja:
    def __init__(self, nosilnost):
        self.nosilnost = nosilnost
        self.paketi = []
        self.odstr = 0

    def natovori(self, teza):
        self.paketi.append(teza)
        while self.skupna_teza() > self.nosilnost:
            del self.paketi[0]
            self.odstr += 1

    def skupna_teza(self):
        return sum(self.paketi)

    def odstranjenih(self):
        return self.odstr

    def __len__(self):
        return len(self.paketi)

Ne maram

Imamo seznam parov oseb, ki nočejo biti skupaj, na primer [("Ana", "Cilka"), ("Berta", "Ana"), ("Berta", "Dani")]. Imamo vrstni red oseb, na primer, ["Ana", "Berta", "Cilka", "Dani", "Ema"]. Potrebujemo samo še funkcijo, preveri_vrsto(vrsta, prepovedani), ki vrne True, če bodo uvrščenke zadovoljne z vrsto in False, če ne. Za gornji primer vrne False, ker Ana in Berta nočeta biti ena zraven druge.

Vrsta ne vsebuje nujno nizov, lahko so tudi številke. Oba seznama sta lahko tudi zelo dolga. Če bo vaša funkcija delovala le s kratkimi seznami, boste bodili 2/3 točk.

Rešitev

Najpreprostejša rešitev je, da pač za vsak par zaporednih elementov preverimo, ali je na seznamu prepovedanih parov ali ne. Popaziti moramo, da se lahko zgodi, da prva noče biti z drugo ali pa druga s prvo.

def preveri_vrsto(vrsta, prepovedani):
    for a, b in zip(vrsta, vrsta[1:]):
        if (a, b) in prepovedani or (b, a) in prepovedani:
            return False
    return True

Ker je prepovedani seznam, bo iskanje po njem počasno. Funkcijo bistveno pospešimo, če ga spremenimo v množico.

def preveri_vrsto(vrsta, prepovedani):
    prepovedani = set(prepovedani)
    for a, b in zip(vrsta, vrsta[1:]):
        if (a, b) in prepovedani or (b, a) in prepovedani:
            return False
    return True

Če pa smo pri množicah: čemu ne bi spremenili še parov, ki jih imamo v vrsti, v množico. Tedaj nas zanima le, če je presek teh dveh množic prazen: če je, bodo uvrščenke zadovoljne.

def preveri_vrsto(vrsta, prepovedani):
    return not (set(zip(vrsta, vrsta[1:])) | set(zip(vrsta[1:], vrsta))) & set(prepovedani)

Odprepovej

Napiši funkcijo odprepovej(vrsta, prepovedani), ki reši problem prepovedanih sosedov tako, da iz seznama prepovedani pobriše tiste pare, ki sedijo skupaj, čeprav ne bi hoteli - tako da bo izgledalo, kot da je vse v redu.

Funkcija ne vrača ničesar, temveč spremeni podani seznam. Zadnji odstavek prejšnje naloge velja tudi za to.

Rešitev

Sestavimo množico vseh parov, ki se pojavijo v vrsti. To je set(zip(vrsta, vrsta[1:])). Poleg tega sestavimo še množico z obrnjenimi pari. Naredimo njuno unijo: set(zip(vrsta, vrsta[1:])) | set(zip(vrsta[1:], vrsta)). Zdaj potrebujemo seznam vseh parov, ki so (bili) prepovedani in niso v množici parov, ki se v resnici pojavijo: [x for x in prepovedani if x not in zaporedni]. Seznam prepovedani moramo spremeniti v ta seznam.

def odprepovej(vrsta, prepovedani):
    zaporedni = set(zip(vrsta, vrsta[1:])) | set(zip(vrsta[1:], vrsta))
    prepovedani[:] = [x for x in prepovedani if x not in zaporedni]

Gre tudi daljše, vendar sem prelen. :)

Najbolj oddaljena

Imamo seznam krajev in njihovih koordinat, kot v domači nalogi Razdalje med kraji.

Druga koordinata gre v smeri sever-jug in narašča proti severu. Napiši funkcijo najbolj_oddaljena(kraj, kraji), ki vrne imeni tistih dveh krajev, ki sta južno od podanega (podani ni vključen!) in sta najbolj oddaljena eden od drugega.

Rešitev

Najprej poiščemo koordinate podanega kraja. To bomo storili tako, da bomo šli čez seznam; ko pridemo do elementa, pri katerem se ime kraja ujema s podanim imenom, ustavimo zanko. Trenutna koordinata y je tedaj pač ravno koordinata "mejnega kraja".

Zdaj pa gremo le še enkrat čez seznam. Če je kraj preveč severno, ne naredimo ničesar, če je dovolj južno, pa izračunamo razdaljo, primerjamo z največjo doslej ... Ta dril poznamo.

def najbolj_oddaljena(kraj, kraji):
    for meja1, xm, ym in kraji:
        if meja1 == kraj:
            break

    naj1 = naj2 = naj_razdalja = 0
    for kraj1, x1, y1 in kraji:
        if y1 >= ym:
            continue
        for kraj2, x2, y2 in kraji:
            if y2 >= ym:
                continue
            razdalja = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if razdalja > naj_razdalja:
                naj1, naj2 = kraj1, kraj2
                naj_razdalja = razdalja
    return naj1, naj2

Tule je bližnjica, za katero pa je treba znati več, kot smo se učili pri predmetu.

def najbolj_oddaljena(kraj, kraji):
    kraji = {ime: (x, y) for ime, x, y in kraji}
    ym = kraji[kraj][1]
    return max(((kraj1, kraj2) for kraj1 in kraji for kraj2 in kraji
                if kraji[kraj1][1] < ym and kraji[kraj2][1] < ym),
               key=lambda k: (kraji[k[0]][0] - kraji[k[1]][0]) ** 2 +
                             (kraji[k[0]][1] - kraji[k[1]][1]) ** 2)

Kdo dobi čip

Napiši funkcijo kdo_dobi(bot, boti), ki kot argument dobi številko bota in mrežo, opisano v enaki obliki kot v domači nalogi. Funkcija naj vrne množico vseh botov, ki bi lahko dobili čip, ki ga ima podani bot. Množica naj vsebuje tudi podanega bota.

Funkcija naj seveda deluje tudi pri nekoliko večjih (čeprav ne nujno tudi zelo velikih) mrežah. Najbrž bo rekurzivna.

Rešitev

To je enako iskanju množice vse oseb v rodbini, le med boti in izhodi moramo razlikovati.

boti[bot] je podobno kot otroci[oseba]. Pri vsakem botu dodamo v množico njega. Nato gremo pred "otrok", za vsakega preverimo ali je bot (in ne izhod) in v tem primeru z rekurzivnim klicem dodamo še njega in njegove "otroke".

Na koncu vrnemo množico, ki smo jo sestavili.

def kdo_dobi(bot, boti):
    kdo = {bot}
    for kam, st in boti[bot]:
        if kam == "bot":
            kdo |= kdo_dobi(st, boti)
    return kdo

Ladja

Napiši razred Ladja z naslednjimi metodami.

• Konstruktor prejme nosilnost ladje.
• natovori(teza) natovori paket s podano težo. Če skupna teža s tem preseže nosilnost ladje, z nje vržejo toliko paketov, da je teža spet v okviru dovoljene. Pakete odstranjujejo v enakem vrstnem redu, kot so jih nalagali, torej najprej najstarejšega. Metoda ne vrne ničesar.
• skupna_teza() vrne skupno težo vseh paketov na ladji.
• odstranjenih() vrne število paketov, ki so bili doslej odstranjeni z ladje zaradi preseganja nosilnosti.
• Če je ladja objekt tipa Ladja, potem len(ladja) vrne število vseh paketov na ladji.

• Recimo, da imamo ladjo z nosilnostjo 42.

• Nanjo natovorimo paket s težo 30 in nato paket s težo 10. Skupna teža je 40.

• Dodajo paket s težo 21. Ker je nosilnost presežena (30 + 10 + 21 = 61 > 42), z ladje vržejo prvi paket, 30. Skupna teža je zdaj 10 + 21 = 31, na ladji sta dva paketa in število odstranjenih je 1.
• Nato natovorijo paket s težo 41. Nosilnost je presežena (10 + 21 + 41 = 72 > 42), zato bodo vrgli z ladje prvi paket (10). Ker je nosilnost še vedno presežena, vržejo z ladje še drugi paket. Ostane le en paket, skupna teža je 41, število doslej odstranjenih je 3.
• Nato natovorijo paket s težo 50. Z ladje vržejo paket s težo 41. Ker je nosilnost še vedno presežena, odstranijo še pravkar naloženi paket (50). Skupna teža je 0, število odstranjenih je 5.

Rešitev

Razred bo imel tri atribute: - nosilnost bo vseboval nosilnost, - paketi bo seznam tež vseh paketov na ladji, - odstr bo število odstranjenih paketov.

Za odstr ne potrebujemo seznama, saj zadošča, da poznamo število. Atribute ste seveda lahko poimenovali drugače. Če ga je kdo poimenoval odstranjenih, pa je imel problem, saj je tako ime že metodi.

Ko je to narejeno, je edina "zapletena" metoda natovori. Ta mora najprej dodati paket s to težo v self.paketi, nato pa dokler teža presega dovoljeno, odstranjevati prvi paket iz seznama (in pri tem povečevati število odstranjenih paketov).

class Ladja:
    def __init__(self, nosilnost):
        self.nosilnost = nosilnost
        self.paketi = []
        self.odstr = 0

    def natovori(self, teza):
        self.paketi.append(teza)
        while self.skupna_teza() > self.nosilnost:
            del self.paketi[0]
            self.odstr += 1

    def skupna_teza(self):
        return sum(self.paketi)

    def odstranjenih(self):
        return self.odstr

    def __len__(self):
        return len(self.paketi)