Rešitev

Pecivo

Tole je naloga, ki so jo na nekem tekmovanju reševali učenci od četrtega razreda OŠ naprej.

Suzana in Aljaž sta odprla pekarno. Suzana peče pecivo v obliki črk A, B in O. Vedno speče vse tri oblike in jih obesi tako, da najprej natakne A, nato B, nato O. Aljaž jih medtem prodaja (vendar ne proda nobene v tem času, ko jih Suzana natika). Suzana jih peče hitreje, kot se prodajajo.

Če je pekarna videti, kot kaže slika: najmanj koliko kosov peciva sta prodala?

Rešitev: devet kosov.

Kako dobimo takšno zaporedje? Napišemo zaporedje, ki vsebuje toliko Ajev, kolikor jih je na sliki: ABOABOABOABOABOABO. Nato prečrtamo, česar ni na sliki: ABOABOABOABOABOABO. Preštejemo prečrtane črke: devet jih je.

Napiši funkcijo pecivo(s), ki prejme niz s, na primer AAABAABOAABO in vrne najmanjše možno število prodanih prest (v gornjem primeru 9).

Namig: raje ne rešuj natančno tako, kot predlaga gornja rešitev; z računalnikom se da preprosteje.

Rešitev

Primerjati moramo zaporedne pare črk. Ko vidimo A, preverimo, kaj je pred njim. Če O, med dvema "paketoma" niso prodali ničesar. Če B, so prodali en kos. Če A, dva.

Zaporedne pare najlepše primerjamo z zip(s, s[1:]). Na konec pa prilepimo še en A, da bomo v primeru, da se zaporedje konča z, na primer, ...AB prišteli prodani O.

def pecivo(s):
    vseh = 0
    for prej, ta in zip(s, s[1:] + "A"):
        if ta == "A":
            if prej == "A":
                vseh += 2
            elif prej == "B":
                vseh += 1
    return vseh

Gre pa tudi hitreje, če se domislimo, da so spekli (vsaj) trikrat toliko kosov peciva, kot je A-jev. Prodali pa so toliko, kolikor ga ni v nizu. Torej

def pecivo(s):
    return 3 * s.count("A") - len(s)

Najmanjši unikat

Napiši funkcijo najmanjsi_unikat(s), ki prejme seznam nekih stvari (lahko so števila, nizi, … karkoli, kar je možno primerjati) in vrne najmanjši element, ki se v seznamu pojavi le enkrat. Če takega ni, ker je seznam prazen ali pa se vsi pojavijo večkrat, ne vrne ničesar (torej None).

Rešitev

Tole je bila naloga, za katero ste pisali tako dolge funkcije, da bi bil še Dostojevski ponosen. V resnici pa je čisto preprosto: preštejemo, koliko je katerih znakov stevci = Counter(s). Vzamemo vse pare (element, število ponovitev) in jih uredimo, sorted(stevci.items()). Nato vrnemo prvi element, ki se ponovi le enkrat.

def najmanjsi_unikat(s):
    stevci = Counter(s)
    for e, c in sorted(stevci.items()):
        if c == 1:
            return e

Skoraj vsi ste skrbeli za to, da boste takrat, ko ni nobenega ne-unikatnega elementa, z return None vrnili None. Ni treba. Tudi gornja funkcija vrne None, pač tako, da ne vrne ničesar.

Če znamo uporabljati generatorje, pa bo program bistveno krajši (in, kot se boste učili v drugem letniku, tudi hitrejši).

def najmanjsi_unikat(s):
    return min((e for e, c in Counter(s).items() if c == 1), default=None)

Neprazne vrstice

Napiši funkcijo neprazne(ime_datoteke), ki prejme ime datoteke in vrne število nepraznih vrstic v njej. Kot prazne vrstice štejemo tudi vrstice, ki vsebujejo same presledke ali tabulatorje.

Rešitev

Tudi tu smo v rešitvah videli vsa mogoča čudesa... ki so jih pisali študenti, ki se niso spomnili, da strip() iz vrstice odstrani vse, česar se ne vidi. Potem pa le še preverimo, ali je od vrstice še kaj ostalo.

def neprazne(ime_datoteke):
    nepraznih = 0
    for vrstica in open(ime_datoteke):
        if vrstica.strip():
            nepraznih += 1
    return nepraznih

Gre pa, kot vedno, tudi krajše.

def neprazne(ime_datoteke):
    return sum(bool(s.strip()) for s in open(ime_datoteke))

s.strip() je niz. Ko ga spremenimo v bool, dobimo True, če je neprazen, in False, če je prazen. True in False sta isto kot 1 in 0. To seštejemo, pa je.

Collatz

Na drugih predavanjih smo se učili o zankah in napisali program, ki izračuna dolžino Collatzovega zaporedja. Vzamemo poljubno število in z njim počnimo tole: če je sodo, ga delimo z 2, če je liho, pa ga pomnožimo s 3 in prištejmo 1. To ponavljamo, dokler ne dobimo 1.

Napiši rekurzivno funkcijo collatz(n), ki pove, kako dolgo je Collatzovo zaporedje, ki se začne s številom n. Tako mora collatz(42) vrniti 9, saj ima zaporedje, ki se začne z 42 devet členov: 42, 21, 64, 32, 16, 8, 4, 2, 1.

Rešitev

Če je n enak 1, vrnemo 1. Sicer pa vrnemo za 1 več, kot je dolgo zaporedje od naslednjega člena naprej.

def collatz(n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + collatz(n // 2)
    else:
        return 1 + collatz(n * 3 + 1)

Če že rešujemo vse naloge v eni vrstici, dajmo pa še to.

def collatz(n):
    return 1 + (n != 1 and collatz(n // 2 if n % 2 == 0 else n * 3 + 1))

Ladja

Ladja je v začetku na točki (0, 0), gleda proti severu in ima hitrost 0. Koordinatni sistem je obrnjen tako, da x in y naraščata proti vzhodu in severu.

Napiši razred Ladja z naslednjimi metodami (poleg njih pa še konstruktor, če se ti zdi potreben).

• kje_si(): vrne koordinate ladje kot terko koordinat x in y,
• premikaj(cas): spremeni koordinate ladje tako, kot da se je podani čas premikala s svojo trenutno hitrostjo,
• spremeni_hitrost(koliko): poveča hitrost ladje za koliko (ali pa jo zmanjša, če je argument negativen),
• obrni(kam): obrne ladjo v podani smeri; kam je lahko "L" ali "D" – levo ali desno; če je obrnjena na vzhod, bo po obratu na levo obrnjena proti severu.
• dolzina_poti(): vrne dolžino poti, ki jo je doslej prevozila ladja.

Primer s komentarji je v testih.

Rešitev

class Ladja:
    def __init__(self):
        self.x = self.y = 0
        self.smer = "S"
        self.hitrost = 0
        self.razdalja = 0

    def premikaj(self, cas):
        koliko = cas * self.hitrost
        self.razdalja += koliko
        if self.smer == "S":
            self.y += koliko
        elif self.smer == "V":
            self.x += koliko
        elif self.smer == "J":
            self.y -= koliko
        elif self.smer == "Z":
            self.x -= koliko

    def obrni(self, kam):
        if kam == "D":
            self.smer = "VJZS"["SVJZ".index(self.smer)]
        else:
            self.smer = "SVJZ"["VJZS".index(self.smer)]

    def spremeni_hitrost(self, koliko):
        self.hitrost += koliko

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

    def dolzina_poti(self):
        return self.razdalja

Gre tudi krajše, vendar je potem morda nekoliko bolj kriptično.