Rešitev

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.

Napiši funkcijo bingo(listki, vrstni_red), ki prejme listke, ki jih imajo igralci (seznam seznamov številk) in vrstni red, v katerem bodo žrebane številke (recimo, da smo izumili časovni stroj). Funkcija naj pove, po koliko izžrebanih številkah bodo na enem od listkov prečrtane vse številke.

Funkcija naj ne spreminja podanih seznamov!

Rešitev

Izklicane številke zlagamo v množico. Po vsaki preverimo, ali je množica številk na katerem izmed listkov podmnožica množice izklicanih številk in v tem primeru vrnemo zaporedno številko števila + 1, ker enumerate šteje od 0.

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

Nalogo je mogoče - kot vsako - rešiti še na veliko drugih načinov. Eden je, recimo, da številke prečrtavamo. Ker ne smemo spreminjati originalnih listkov, moramo seznam prepisati; nič ne bo narobe, če ga spremenimo tako, da bomo imeli namesto seznamov množice.

def bingo(listki, vrstni_red):
    listki = [set(listek) for listek in listki]
    for i, stevilka in enumerate(vrstni_red):
        for listek in listki:
            if stevilka in listek:
                listek.remove(stevilka)
                if not listek:  # Je listek že prazen?
                    return i + 1

Brez parov

Ker smo moški, vemo, barvno slepi in ne ločimo med črnimi in (domnevno!) temno modrimi nogavicami, se lahko znajdemo tako, da na vsako nogavico prišijemo številko. Obe nogavici iz para imata enako številko.

Recimo, da iz pranja dobimo nogavice [15, 12, 17, 18, 12, 4, 15, 4, 7]. Nekaj nogavic je kot vedno seveda brez para: tokrat so to nogavice 17, 18 in 7. Nato pride naslednja žehta; v njej so, recimo, [3, 4, 3, 5, 17, 7]. Nogavice, ki se jim je našel par, pokombiniramo.

Napiši funkcijo brez_parov(s, t), ki prejme dva takšna seznama in vrne dve številki, ki povesta, koliko nogavic iz vsake žehte je še vedno brez para. V gornjem primeru vrne (1, 2), saj je brez para ena nogavica iz prve žehte (7) in dve iz druge (4 in 5).

Rešitev

Sestavimo množici številk nogavic brez para. Zdaj naloga sprašuje po številu vseh nogavic, ki se pojavijo v eni množici in ne v drugi ter obratno.

def brez_parov(s, t):
    s = {x for x in s if s.count(x) == 1}
    t = {x for x in t if t.count(x) == 1}
    return len(s - t), len(t - s)

Seznam iz parov

Nekateri računalniški jeziki nimajo seznamov, temveč le pare - v Pythonu bodo to terke z dvema elementoma. Seznam predstavimo tako, da naredimo par, ki vsebuje prvi element in ostanek. Ostanek je spet par, ki vsebuje prvi element ostanka in ostanek ostanka. Namesto ["Ana", "Berta", "Cilka", "Dani", "Ema"] bi napisali ("Ana", ("Berta", ("Cilka", ("Dani", ("Ema", None))))). Zadnji element je vedno None, ki pomeni, da ne sledi nič več. Prazen seznam, [], predstavimo z None (in ne s kakim (None, None)).

Napiši nerekurzivno funkcijo v_seznam(pari), ki prejme seznam v obliki parov in vrne običajni seznam.

Napiši tudi rekurzivno funkcijo v_seznam_rek(pari), ki prejme seznam v obliki parov in vrne običajni seznam.

Če je argument pari enak None, to pomeni, da je seznam prazen in funkcija mora vrniti [].

Nasvet: rekurzivna funkcija mora vrniti seznam, ki vsebuje prvi element in vse ostale, pretvorjene v seznam.

Rešitev

Funkcijo je lažje napisati kot opisati. Bistvo je, da jemljemo prvi, pari = pari in zlagamo prvi v seznam, dokler pari niso None.

def v_seznam(pari):
    s = []
    while pari is not None:
        prvi, pari = pari
        s.append(prvi)
    return s

Rekurzivna funkcija je precej lažja. Vrnemo seznam, v katerem je prvi element in seznam iz ostanka.

def v_seznam_rek(pari):
    if pari is None:
        return []
    return [pari[0]] + v_seznam_rek(pari[1])

Pari iz seznama

Zdaj pa še obratna vaja: napiši nerekurzivno funkcijo v_pare(s) in rekurzivno funkcijo v_pare_rek(s), ki spremenita seznam v pare.

Rešitev

Tokrat pokažimo najprej rekurzivno rešitev, ki je res bistveno lažja.

Če seznam ni prazen vrnemo par, ki vsebuje prvi element in pare, sestavljene iz ostankov. Če je prazen, funkcija ne vrne ničesar, torej vrne None.

def v_pare(s):
    if s:
        return (s[0], v_pare(s[1:]))

Brez rekurzije je težje: ko poskusimo sestaviti prvo terko, bi morali že imeti na razpolago tudi ves ostanek, saj je terko kasneje nemogoče spreminjati. Se pravi, ko sestavljamo prvi par, moramo že imeti nared drugega. Ko sestavljamo drugega, moramo imeti nared tretjega... Edini način, da to sestavimo, je, da sestavljamo od konca proti začetku.

def v_pare(s):
    seznam = None
    for e in reversed(s):
        seznam = (e, seznam)
    return seznam

Krajšo rešitev dobimo, če uporabimo nekaj, česar se nismo učili. Objavljam, če bo to kdaj bral kdo, ki bi ga to zanimalo.

from functools import reduce

def v_pare(s):
    return reduce(lambda s, e: (e, s), reversed(s), None)

Sledilnik

Napiši razred Sledilnik, katerega konstruktor prejme slovar, katerega ključi so imena oseb, pripadajoče vrednosti pa povejo, kje posamezna oseba živi. Te podatke si shrani v poljubni obliki, ki sem vam zdi primerna.

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 iz nekega kraja preselijo tri osebe v drug kraj, so to tri selitve.

Rešitev

Tole je popolnoma rutinsko.

class Sledilnik:
    def __init__(self, zacetek):
        self.osebe = 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