Rešitev

Nogavice brez para

Ker smo moški, vemo, barvno slepi, obenem pa v družini z ženo in n otroki ni mogoče, da bi imel vsak same enake nogavice, se lahko znajdemo tako, da na vsako nogavico prišijemo številko. Enake nogavice imajo enako številko; ker imamo več enakih nogavic, ima lahko več nogavic enako številko.

Recimo, da iz pralnega stroja potegnemo nogavice s številkami [1, 2, 3, 2, 3, 1, 3, 1, 1, 1, 1]. Imamo torej tri pare nogavic 1, en par nogavic 2 in en par nogavic 3 in (eh, spet!) še eno 3 brez para.

Napiši funkcijo nogavice(s), ki prejme seznam številk nogavic in vrne seznam vseh številk nogavic brez para. V gornjem primeru torej vrne [3].

Vrstni red elementov v seznamu naj bo enak vrstnemu redu zadnjih pojavitev teh številk; za [1, 1, 4, 1, 3, 1] vrne [4, 3] in ne [3, 4].

Rešitev

S številkami ravnajmo enako, kot bi z nogavicami. Zlagajmo jih na mizo (oziroma v nov seznam). Za vsako novo nogavico najprej pogledamo, ali je ena taka že na mizi. Če je, jo odstranimo. Če ni, jo dodamo.

def nogavice(s):
    brez_para = []
    for e in s:
        if e in brez_para:
            brez_para.remove(e)
        else:
            brez_para.append(e)
    return brez_para

Ze nekaj spretnosti - še krajše:

def nogavice(s):
    brez_para = []
    for e in s:
        [brez_para.append, brez_para.remove][e in brez_para](e)
    return brez_para

Bingo

Igra Bingo poteka tako, da ima vsak igralec listek z nekaj številkami. Voditelj žreba številke. Če se izžrebana številka nahaja na igralčevem listku, jo ta prečrta. Zmaga igralec, ki prvi prečrta vse številke.

Vedeževalka nam je napovedala vrstni red, v katerem bodo žrebane številke. Imamo seznam listkov za Bingo; izbrali bi radi tistega, na katerem bodo prej prečrtane se številke.

Napiši funkcijo bingo(listki, vrstni_red), ki prejme listke (seznam seznamov številk) in vrne listek, na katerem bodo najprej prečrtane vse številke.

bingo([[4, 1, 2, 3, 5], [6, 1, 2, 3, 4], [7, 6, 4, 3, 2]],
    [4, 2, 8, 3, 1, 6, 5, 7])

vrne [6, 1, 2, 3, 4] (saj bo ta očitno prehitel prvega in zadnjega, zaradi 5 in 7).

Funkcija naj ne spreminja podanega seznama!

Rešitev

Lahko, recimo, gledamo množico doslej izžrebanih številk. Po vsakem žrebanju preverimo, ali so številke na kakem izmed listkov podmnožica doslej izžrebanih. Če je tako, vrnemo ta listek.

def bingo(listki, vrstni_red):
    izklicano = set()
    for stevilka in vrstni_red:
        izklicano.add(stevilka)
        for listek in listki:
            if set(listek) <= izklicano:
                return listek

Tule pa je malo ustvarjalnejša rešitev.

def bingo(listki, vrstni_red):
    return min(listki, key=lambda listek: max(map((vrstni_red + listek).index, listek)))

Selitve

Napiši funkcijo selitve(zacetek, datoteka_selitev, kraj), ki prejme začetno razdelitev oseb, ime datoteke s selitvami in ime nekega kraja. Vrniti mora množico imen oseb, ki po podanih selitvah živijo v podanem kraju.

Začetna razdelitev oseb po krajih je lahko, recimo, [("Ljubljana", "Jana"), ("Šentvid", "Vid"), ("Mala Polana", "Ana"), ("Maribor", "Bor"), ("Kamnik", "Nik"), ("Ozeljan", "Jan"), ("Županje Njive", "Ive"), ("Koroška Bela", "Ela"))]. Vedno le po ena oseba v vsakem mestu.

Argument datoteka_selitev pove ime datoteke z vsebino, ki je lahko, recimo, taka

Najprej grejo iz "Mala Polana" v "Šentvid".
Iz "Kamnik" pa tudi v "Šentvid".
Pa še iz "Koroška Bela" odidejo v "Ozeljan".
Potem pa iz "Šentvid" v "Maribor" (kwa?!).

Vsaka vrstica torej vsebuje dve imeni krajev, zapisani v dvojnih narekovajih. V vrstici ni drugih dvojnih narekovajev. Vedno se preselijo vsi prebivalci podanega kraja.

Če je gornje začetno stanje shranjeno v seznamu zacetek, one štiri vrstice pa v datoteki selitve.txt, mora klic selitve(zacetek, "selitve.txt", "Maribor") vrniti {"Ana", "Vid", Nik", "Bor"}, klic selitve(zacetek, "selitve.txt", "Šentvid") pa vrne prazno množico (saj so šli Šentvidčani v Maribor).

Pri reševanju si lahko - ni pa nujno - pomagaš s tem, kar boš sprogramiral(a) v peti nalogi.

Rešitev

Pripravili si bomo slovar, katerega ključi so imena krajev, pripadajoče vrednosti pa množice prebivalcev tega kraja.

Naslednji podvig: kako priti do imen krajev v vsaki vrstici datoteke? Preprosto. Ker v vrstici ni drugih narekovajev, vrstico razbijemo glede na narekovaje. Druga in tretja reč sta iskana kraja. (Da bo koda preglednejša, vrstico razpakiramo, odvečnim spremenljivkam pa damo ime _.)

Ostalo je preprosto.

def selitve(zacetek, navodila, kraj):
    lokacije = {kraj: {prebivalec} for kraj, prebivalec in zacetek}
    for vrstica in open(navodila):
        _, odkod, _, kam, _ = vrstica.strip().split('"')
        lokacije[kam] |= lokacije[odkod]
        lokacije[odkod] = set()
    return lokacije[kraj]

Funkcija, ki smo jo napisali tule, predpostavlja, da se prebivalci nekega kraja nikoli ne bodo selili v isti kraj - Kamničani se nikoli ne selijo v Kamnik. Kaj bi se zgodilo, če bi bila v datoteki tudi taka selitev? Kako bi popravili funkcijo?

Rekurzivni štumfi, zokni, kalcete, fuzetlne in kucjte

Napiši rekurzivno funkcijo brez_para(nogavica, nogavice), ki prejme številko nogavice in podoben seznam kot prva naloga. Vrniti mora True, če je nogavica brez para, in False, če ni.

Klic brez_para(39, [41, 39, 39, 41, 41, 39, 39]) vrne False in klic brez_para(41, [41, 39, 39, 41, 41, 39, 39]) vrne True, saj imamo eno 41 brez para.

Rešitev

Če je seznam nogavic prazen, podana nogavica ni brez para in vrnemo False. Sicer preverimo, ali je prva nogavica enaka podani. Če je, bo brez para, če v ostanku seznama ta nogavica ni brez para. Sicer pa prvi element ignoriramo in gledamo ostanek seznama.

def brez_para(stevilka, nogavice):
    if not nogavice:
        return False
    if nogavice[0] == stevilka:
        return not brez_para(stevilka, nogavice[1:])
    else:
        return brez_para(stevilka, nogavice[1:])

Ker gre za same if-e in return-e, lahko to brez težav povemo v eni vrstici. Le nekaj zabavnega potrebujemo v drugem pogoju. Ga razumeš?

def brez_para(stevilka, nogavice):
    return nogavice != [] and (nogavice[0] == stevilka) != brez_para(stevilka, nogavice[1:])

Sledilnik

Napiši razred Sledilnik, katerega konstruktor prejme začetno razdelitev po krajih v takšni obliki, kot smo jo imeli tudi v tretji nalogi. Te podatke si shrani v poljubni obliki, ki sem vam zdi primerna. Če vam pride prav (ni pa nujno, da vam bo), lahko predpostavite, da so imena unikatna, torej, da ni dveh oseb z enakim imenom.

Razred ima naslednje metode:

• kje_zivi(self, oseba) vrne kraj, v katerem trenutno živi podana oseba;
• prebivalci(self, kraj) vrne množico prebivalcev podanega kraja;
• preseli(self, oseba, kraj) preseli podano osebo v podani kraj;
• preseli_vse(self, odkod, kam) preseli vse prebivalce kraja odkod v kraj kam;
• selitev(self) vrne število vseh selitev. Če se oseba seli v kraj, v katerem že živi, se to šteje za selitev. Če se iz nekega kraja preselijo tri osebe v drug kraj, so to tri selitve.

Rešitev

Ves trik je v tem, da si pametno shranimo podatke. In pri tej nalogi se to da storiti na precej načinov. Tule bomo naredili slovar, katerega ključi so osebe (saj vemo, da nimamo dveh oseb z istim imenom), vrednosti pa kraji, v katerih živijo. Vse ostalo je potem rutinsko.

class Sledilnik:
    def __init__(self, zacetek):
        self.osebe = {prebivalec: kraj for kraj, prebivalec in zacetek}
        self.n_selitev = 0

    def kje_zivi(self, oseba):
        return self.osebe[oseba]

    def prebivalci(self, kraj):
        return {oseba for oseba, kje in self.osebe.items() if kje == kraj}

    def preseli(self, koga, kam):
        self.osebe[koga] = kam
        self.n_selitev += 1

    def preseli_vse(self, odkod, kam):
        for oseba in self.prebivalci(odkod):
            self.preseli(oseba, kam)

    def selitev(self):
        return self.n_selitev