Najpogostejše polje

Podan je razred Robot. Ta se v začetku nahaja na koordinatah (0, 0) in je obrnjen na desno. Koordinatni sistem je takšen kot pri matematiki: koordinata y narašča navzgor. Robot ima naslednje metode:

  • naprej(d) gre za d naprej v podani smeri;
  • desno() se obrne za 90 stopinj v desno;
  • levo() se obrne za 90 stopinj levo;
  • koordinate() vrne trenutne koordinate (x in y)

Napišite funkcijo najpogostejse_polje(navodila), ki prejme navodila za robota v obliki niza, na primer "7D3221LL", kar bi pomenilo, da skoči za 7 polj naprej, se obrne desno, nato skoči za 3 polja naprej, za 2 polji naprej, za 2 polji naprej, za 1 polje naprej, nato se obrne levo in še enkrat levo. Funkcija vrne koordinati polja, na katerega je robot najpogosteje prišel. (Robot "pride" tudi na začetno polje. Ko se robot obrne, se to ne šteje, kot da je ponovno prišel na to polje. Polja, prek katerih gre, vendar se na njih ne ustavi, ne štejejo.)

Rešitev

Pri tej nalogi me je zanimalo, ali boste znali pametno uporabiti razred, ki ga že imamo (iz domače naloge). Če ne, bo to zahtevalo (pre)več programiranja. Sicer pa je to naloga iz slovarjev.

Najprej vodenje robota. To je preprosto: gremo čez znake in vsakega od njih prevedemo v eno od akcij.

def najpogostejse_polje(navodila):
    robot = Robot()
    for c in navodila:
        if c == "L":
            robot.levo()
        elif c == "D":
            robot.desno()
        else:
            robot.naprej(int(c))

Zdaj pa dodamo še beleženje polj: obiski bo defaultdict, katerega ključi bodo koordinate polj, vrednosti pa števila obiskov tega polja. Za vsako polje, na katerega pridemo (le v zadnjem else - polja, na katerih se obračamo, ne štejejo!), povečamo ustrezen element slovarja za 1.

def najpogostejse_polje(navodila):
    from collections import defaultdict
    robot = Robot()
    obiski = defaultdict(int)
    obiski[robot.koordinate()] += 1
    for c in navodila:
        if c == "L":
            robot.levo()
        elif c == "D":
            robot.desno()
        else:
            robot.naprej(int(c))
            obiski[robot.koordinate()] += 1
    return naj_kljuc(obiski)

Na koncu smo poklicali funkcijo naj_kljuc, ki bo vrnila ključ, ki pripada največji vrednosti. Samo ... sprogramirati jo moramo. :)

def naj_kljuc(d):
    naj_k = None
    naj_v = 0
    for k, v in d.items():
        if v > naj_v:
            naj_k, naj_v = k, v
    return naj_k

Seveda bi lahko tole naredili tudi brez posebne funkcije in te vrstice vključili kar v najpogostejse_polje. A takole je morda lepše, saj so dolge funkcije hitro nepregledne. V nobenem primeru pa ta funkcija ne bi smela predstavljati prehudih težav, saj smo prav to velikokrat mleli na predavanjih in domačih nalogah.

Nekateri pa vedo, da gre tudi brez te funkcije, saj lahko ključ, ki pripada največji vrednosti, dobimo tudi z

return max(naj_kljuc, key=naj_kljuc.get)

Navodila

Napiši funkcijo navodila(zaporedje), ki prejme zaporedje, kot je, na primer "7D3221LL" in vrne seznam [7, "D", 3221, "L", "L"]. Tole je podobno, a ravno prav različno, da si ne morete pomagati s prejšnjo nalogo. :) Razlika je v tem, da je tu potrebno več zaporednih števk šteti kot eno število.

Rešitev

Ko naletimo na števko (torej nekaj, kar ni L ali D), jo shranimo v niz, v katerega shranjujemo števke.

Ko naletimo na L ali D, to (morda) pomeni konec nekega števila. Ali je tako, prepoznamo po tem, da niz s številom ni prazen. Če torej ni, v seznam dodamo to število. V vsakem primeru pa dodamo še L ali D in spraznimo niz s številom.

Kar zoprno.

def navodila(zaporedje):
    stevilo = ""
    koraki = []
    for c in zaporedje:
        if c in "LD":
            if stevilo:
                koraki.append(int(stevilo))
                stevilo = ""
            koraki.append(c)
        else:
            stevilo += c
    if stevilo:
        koraki.append(int(stevilo))
    return koraki

Praktično vsi, ki so rešili nalogo, so jo rešili na tak način (le z malo več if-i, ker ste običajno ločeno obravnavali "L" in "D", nekateri pa so komplicirali z isdigit in podobnimi metodami nizov).

Obstajajo seveda tudi drugi. Zanimiv, krajši, je tale:

def navodilo(zaporedje):
    koraki = []
    for c in zaporedje:
        if c in "LD":
            koraki.append(c)
        elif not koraki or koraki[-1] in "LD":
            koraki.append(int(c))
        else:
            koraki[-1] = 10 * koraki[-1] + int(c)
    return koraki

Če naletimo na L ali D, ga dodamo v seznam. Sicer pa preverimo ali je zadnji element seznama L ali D (ali pa je ta celo prazen). V tem primeru dodamo c, pretvorjen v številko. Če imamo na koncu seznama že številko, pa jo pomnožimo z 10 in prištejemo c.

Menjave

Napiši funkcijo zamenjano(s, menjave), ki prejme seznam s in slovar menjave. Vrne naj nov seznam, v katerem so vsi elementi seznama, ki nastopajo kot ključi v slovarju, zamenjani s pripadajočimi vrednostmi. Elemente, ki se ne pojavijo v slovarju, pusti pri miru.

Klic zamenjano(["Ana", "Ana", "Berta", "Ana", "Cilka"], {"Ana": "Peter", "Berta": "Ana"}) vrne ["Peter", "Peter", "Ana", "Peter", "Cilka"].

Funkcija zamenjano ne sme spremeniti podanega seznama s.

Poleg tega napiši podobno funkcijo zamenjaj(s, menjave), ki pa ne vrne ničesar temveč ustrezno spremeni podani seznam s.

Rešitev

Čeprav obstajajo tudi precej daljše rešitve :), pokažimo kratko.

def zamenjano(skatla, menjave):
    return [menjave.get(e, e) for e in skatla]

def zamenjaj(skatla, menjave):
    skatla[:] = zamenjano(skatla, menjave)

Slovarji, vemo, imajo metodo get, ki vrne vrednost, ki pripada podanemu ključu, če ključ ne obstaja, pa vrnejo podano privzeto vrednost. menjave.get(e, e) vrne vrednost, ki pripada ključu e, sicer pa kar e. No, to zložimo v seznam, ki ga vrnemo: vsak element zamenjamo, s tistim, s čimer ga je potrebno zamenjati, ali pa ga ne zamenjamo.

Funkcija zamenjaj pa zamenja vse elemente škatle s tem, kar vrne funkcija zamenjano.

Sprazni

Napiši rekurzivno funkcijo sprazni(s), ki prejme seznam, katerega elementi so None in seznami, katerih elementi so None in seznami in tako naprej. Funkcija naj vrne prav tak seznam, a brez None-ov. Če pokličemo sprazni([None, None, [None], [None, None, []], None]), dobimo [[], [[]]].

Pomoč: funkcija sestavlja seznam. Če vidi None, ga preskoči. Če vidi seznam, ga doda v nastajajoči seznam ... a spraznjenega.

Rešitev

Le pomoči sledimo: gremo čez seznam. Sestavimo nov seznam. Če vidimo kaj, kar ni None, torej seznam, vstavimo v novi seznam izpraznjeni seznam.

def sprazni(s):
    novi = []
    for e in s:
        if e is not None:
            novi.append(sprazni(e))
    return novi

Čarovnik

Napiši razred Carovnik, katerega konstruktor kot argument dobi niz, ki pove, kaj čarovnik zna in koliko zaračuna za to, na primer alkemist = Carovnik("svinec -> zlato", 10). Niz bo vedno vseboval dve enobesedni stvari, ločeni z ->.

Razred ima metodo caraj(s), ki prejme seznam in vrne nov seznam, v katerem so vsi elementi prečarani v nove. Tako bi klic alkemist(["svinec", "les", "zlato", "svinec"]) vrnil ["zlato", "les", "zlato", "zlato"]. Alkemist bi za to zaračunal 20 evrov. (Poceni!)

Poleg tega ima razred metodo zasluzek(), ki pove, koliko je čarovnik doslej zaslužil. V gornjem primeru bi klic alkemist.zasluzek() torej vrnil 20.

Rešitev

Konstruktor si mora zapomniti, kaj spreminjamo v kaj, ceno spremembe in število opravljenih sprememb.

Metoda caraj na nek način pričara seznam s spremenjenimi elementi in si zapomni, koliko sprememb je naredila.

Metoda zaslužek vrne produkt števila sprememb in cene posamezna spremembe.

class Carovnik:
    def __init__(self, sprememba, cena):
        self.iz, _, self.v = sprememba.split()
        self.cena = cena
        self.sprememb = 0

    def caraj(self, skatla):
        self.sprememb += skatla.count(self.iz)
        return [self.v if e == self.iz else e for e in skatla]

    def zasluzek(self):
        return self.sprememb * self.cena

V metodi čaraj smo uporabili izpeljan seznam in malo hecen pogojni stavek. Gre pa tudi po daljši, a marsikomu razumljivejši poti:

    def caraj(self, skatla):
        nova_skatla = []
        for e in skatla:
            if e == self.iz:
                nova_skatla.append(self.v)
                self.sprememb += 1
            else:
                nova_skatla.append(e)
        return nova_skatla
Последнее изменение: четверг, 25 января 2018, 14:18