Domača naloga: Miklavževa pisma

Prišel je čas, da pomagamo Miklavžu.

Nalogi so priloženi podatki. Programiraj tako, da se bodo nahajali v podimeniku "podatki" imenika, v katerem je tvoj program. Če je tvoj program v imeniku /Users/benjamin/programiranje/naloga, morajo biti podatki v /Users/benjamin/programiranje/naloga/podatki. (Pisma, recimo, bodo v /Users/benjamin/programiranje/naloga/podatki/pisma).

Pri reševanju ne smeš predpostaviti, kako je ime otrokom, ponudnikom, darilom. Z drugimi besedami, v tvojem programu se ne sme pojaviti nobeno ime otroka, nobeno ime ponudnika, nobeno konkretno darilo. Program mora biti uporaben tudi prihodnje leto, ko bo Miklavž obdaroval druge otroke z drugimi darili drugih dobaviteljev.

Za oceno 6

V delu za oceno 6 bomo pripravili funkcije, s katerimi bomo kasneje lahko razbirali sopomenke (oziroma, predvsem različne oblike besed), ki pomenijo isto darilo.

sopomenke_besede

Rešitev

Gremo čez niz, ki ga razdelimo na besede. V množico shranjujemo besede, od katerih od-strip-amo morebitno začetno zvezdico. Ko naletimo na besedo z zvezdico, si jo zapomnimo še kot glаvno besedo. Na koncu vrnemo glavno besedo in množico.

def sopomenke_besede(s):
    besede = set()
    for beseda in s.split():
        besede.add(beseda.strip("*"))
        if beseda[0] == "*":
            glavna = beseda[1:]
    return glavna, besede
sopomenke_besede("sladkarije bombončki *bomboni liziko")
('bomboni', {'bomboni', 'bombončki', 'liziko', 'sladkarije'})

preberi_sopomenke

Rešitev

Beremo datoteko, za vsako vrstico pokličemo prejšnjo funkcijo sopomenke_besede in v slovar kot ključe dodajamo besede iz množice, kot pripadajočo vrednost pa glavno besedo.

def preberi_sopomenke():
    slovar = {}
    for vrstica in open("podatki/sopomenke.txt", encoding="utf-8"):
        glavna, druge = sopomenke_besede(vrstica.strip())
        for beseda in druge:
            slovar[beseda] = glavna
    return slovar
sopomenke = preberi_sopomenke()

sopomenke["vlakec"]
'vlak'

Notranji zanki se lahko izognemo z dvema metodama slovarjev, ki smo ju na predavanjih komajda omenili, če sploh.

Prva je fromkeys, ki sestavi slovar s podanimi ključi in določeno vrednostjo (če je ne podamo, pa bodo vrednosti None). fromkeys ni običajna metoda, saj ne pripada posamičnemu slovarju, kot recimo get ali setdefault, temveč razredu. (Uradno: fromkeys je classmethod.)

imena = ["Ana", "Berta", "Cilka"]

dict.fromkeys(imena, 42)
{'Ana': 42, 'Berta': 42, 'Cilka': 42}

Druga malo omenjena metoda je update. Če sta d in e neka slovarja, bo d.update(e) v slovar d prepisal vse, kar je v slovarju e.

S tema metodama lahko skrajšamo funkcijo v

def preberi_sopomenke():
    slovar = {}
    for vrstica in open("podatki/sopomenke.txt", encoding="utf-8"):
        glavna, druge = sopomenke_besede(vrstica.strip())
        slovar.update(dict.fromkeys(druge, glavna))
    return slovar

Rešitev

Lahko bi napisali

def prevod_besede(beseda):
    beseda = beseda.lower()
    if beseda in sopomenke:
        return sopomenke[beseda]
    else:
        return None

Lahko pa bi se spomnili, da natančno to - če ključ obstaja, vrne pripadajočo vrednost, sicer pa None - naredi metoda `get.

def prevod_besede(beseda):
    return sopomenke.get(beseda.lower())

Za oceno 7

V nalogah za oceno 7 bomo brali pisma Miklavžu. Nahajajo se v imeniku podatki/pisma in so videti, na primer, tako

Dragi Miklavž,

Pozdravljen! Kako kaj? Jaz sem v redu. Letos sem bila pridna (vsaj večino časa).
Prosim, prosim, prinesi mi kakšno knjigo, ki jo lahko prebiram pred spanjem. In
če lahko, dodaj še mehkega plišastega medvedka, da bova lahko skupaj brala.
Obljubljam, da bom vedno pospravljala svojo sobo.

Lepo se imej,
Ema

Opomba: večino pisem mi je prijazno sestavil chatGPT. :))))

poenostavi_besedilo

Rešitev

Nekateri so to reševali z neskončno verigo replace, s katerimi so zamenjevali vse, na kar so naleteli v kakem pismu. s.replace(".", "").replace(",", "").replace("-", "").replace("(", "")... in tako naprej. To ni preveč varna ideja. Bogve, kakšne znake bodo otroci še dopisali. Boljše je obdržati, kar želimo obdržati - pa čeprav bo takšna rešitev malo daljša.

def poenostavi_besedilo(s):
    t = ""
    for c in s.lower():
        if c.isalpha() or c in " \n\t":
            t += c
    return t
poenostavi_besedilo(
    "Dragi Miklavž,\n\npišem ti (kot vsako leto): lep božič!")
'dragi miklavž\n\npišem ti kot vsako leto lep božič'

V resničnem svetu se to rešuje z regularnimi izrazi. Če boste pridni, vam jih bom nekoč razložil.

import re

def poenostavi_besedilo(s):
    return re.sub("[^\w\s]", "", s.lower())

izlusci_avtorja

Rešitev

Beremo vrstice in si jih zapomnimo - če niso prazne. Na koncu vrnemo zadnjo zapomnjeno vrstico.

def izlusci_avtorja(ime_dat):
    for vrstica in open(ime_dat):
        if vrstica.strip():
            avtor = vrstica.strip()
    return avtor

Edini trik tule je, da moramo pisati if vrstica.strip(). Nobena vrstica datoteke ni prazna, vsaka vsebuje vsaj \n. Zato je potreben strip(); vrstica nas zanima, če je neprazna tudi potem, ko odstranimo beli prostor (\n in morebitne presledke v sicer praznih vrsticah).

izlusci_darila

Rešitev

Skoraj vse, kar smo programirali doslej, služi poenostavljanju te funkcije. Konkretno, vsako besedilo je potrebno poenostaviti, potem pa za vsako besedo preveriti, ali se (prek sopomenk) preslika v kako darilo. Kdor ni uporabljal doslej napisanih funkcij, je imel problem, ki si ga je nakopal čisto sam. Kdor jih je uporabljal, pa je tule napisal čisto preprosto funkcijo.

Odpremo datoteko, jo z read preberemo v celoti, nato pokličemo poenostavi_besedilo, rezultat razbijemo na besede in jih zlagamo v množico.

def izlusci_darila(ime_dat):
    darila = set()
    besedilo = open(ime_dat, encoding="utf-8").read()
    besedilo = poenostavi_besedilo(besedilo)
    for beseda in besedilo.split():
        darilo = prevod_besede(beseda)
        if darilo:
            darila.add(darilo)
    return darila

Bolj neučakani pa sestavijo množico prevodov vseh besed, ki jih najdejo v poenostavljenem besedilu iz datoteke prebranem (besedni red tega stavka sledi kodi :), iz katere odstranijo None, ki ga v to množico nvlačejo besede, ki ne predstavljajo daril.

def izlusci_darila(ime_dat):
    return {
        prevod_besede(beseda)
        for beseda in poenostavi_besedilo(
            open(ime_dat, encoding="utf-8").read()).split()
    } - {None}

darila_po_otrocih

Rešitev

Gremo po datotekah v poddirektoriju "podatki/pisma". Iz vsake datoteke izluščimo avtorja in darila; prvo bo ključ, drugo pripadajoča vrednost.

import os

def darila_po_otrocih():
    darila = {}
    for ime_dat in os.listdir("podatki/pisma"):
        ime_dat = "podatki/pisma/" + ime_dat
        darila[izlusci_avtorja(ime_dat)] = izlusci_darila(ime_dat)
    return darila

Glavna zafrkancija te funkcije je, da os.listdir vrača le imena datotek, ne pa tudi poti, ki smo jo podali listdir-u. Zato je potrebno to dodati. Ker bomo ime datoteke, skupaj s potjo, potrebovali na dveh mestih, kar spremenimo vrednost spremenljivke.

Veliko preprosteje je, če v okviru funkcije začasno zamenjamo trenutni direktorij.

def darila_po_otrocih():
    darila = {}
    os.chdir("podatki/pisma")
    for ime_dat in os.listdir():
        darila[izlusci_avtorja(ime_dat)] = izlusci_darila(ime_dat)
    os.chdir("../..")
    return darila

Pripravljaje to nalogo pa sem odkril, da ima Pythonov modul contextlib funkcijo, ki začasno zamenja direktorij. (Kako sem to odkril? Kako človek kar tako, slučajno odkrije takšne stvari? Preprosto, zazdelo se mi je, da se to velikokrat potrebuje in da za to morda obstaja taka in taka bližnjica, vedel pa sem tudi, kje jo iskati.)

Funkcija contextlib.chdir vrne kontekst in uporabiti ga moramo z with. Kaj je to, vam najrž ne bom razlagal niti, če boste pridni. Če želite, uporabljajte kot magični urok za začasno menjavo direktorija.

import contextlib

def darila_po_otrocih():
    darila = {}
    with contextlib.chdir("podatki/pisma"):
        for ime_dat in os.listdir():
            darila[izlusci_avtorja(ime_dat)] = izlusci_darila(ime_dat)
    return darila

To potem vodi v briljantno kratko rešitev.

def darila_po_otrocih():
    with contextlib.chdir("podatki/pisma"):
        return {izlusci_avtorja(ime_dat): izlusci_darila(ime_dat)
                for ime_dat in os.listdir()}

Podobno jedrnati bi lahko bili tudi brez contextlib.chdir, le s prištevanjem poti bi se morali zafrkavati.

zbirnik_daril

Rešitev

Pokličemo darila_po_otrocih. Ker nas imena otrok ne zanimajo, gremo le čez vrednosti in seštevamo.

Tu se nam splača uporabiti collections.defaultdict(int). Na ta način nam ne bo treba preverjati, ali smo na določen predmet že naleteli in je ključ že v slovarju ter ga v nasprotnem primeru dodajati.

from collections import defaultdict

def zbirnik_daril():
    zbirnik = defaultdict(int)
    for darila in darila_po_otrocih().values():
        for darilo in darila:
            zbirnik[darilo] += 1
    return zbirnik

Da se naučimo še nečesa novega iz zakladnice funkcij, ki se valjajo po Pythonovi standardni knjižnici: Counter iz modula collections. Counter je posebna vrsta slovarja. Ko ga konstruiramo, mu lahko podamo nek seznam ali kaj takega, pa bo preštel njegove elemente: ključi bodo elementi, vrednosti pa število pojavitev.

from collections import Counter

s = ["Cilka", "Ana", "Berta", "Ana", "Ana", "Cilka"]
t = ["Ana", "Dani"]

c = Counter(s)
c
Counter({'Ana': 3, 'Cilka': 2, 'Berta': 1})

K že preštetim lahko dodajamo nove.

c.update(t)
c
Counter({'Ana': 4, 'Cilka': 2, 'Berta': 1, 'Dani': 1})

Če ga pokličemo brez argumentov, seveda dobimo prazen slovar. In mu potem kasneje dodajamo elemente.

S Counter lahko rešimo nalogo tako:

def zbirnik_daril():
    vsa_darila = Counter()
    for darila in darila_po_otrocih().values():
        vsa_darila.update(darila)
    return vsa_darila

Naloga pravi, da mora funkcija vrniti slovar. Ta vrne Counter. Vendar je Counter vrsta slovarja, torej je vse v redu. (Kaj pomeni biti "vrsta slovarja", pri tem predmetu ne bomo jasno definirali; za nas bodi dovolj, da se da z njim delati vse, kar se da delati s slovarjem - pa še par stvari zraven.)

Ocena 8

Miklavž nabavlja darila pri dolgoletnih dobaviteljih: Godler s.p., Klemenčič s.p., Lampič s.p., Pavlič s.p. in Dežman s.p. Njihovi ceniki so v podatki/dobavitelji. V kakšni obliki so, si oglej sam.

preberi_cenik

Rešitev

Tule preprosto uporabimo cvs.reader. Vse, kar vrača, zlagamo v slovar, ki ga na koncu vrnemo.

import csv

def preberi_cenik(ime_ponudnika):
    cenik = {}
    for vrstica in csv.reader(
            open(f"podatki/dobavitelji/{ime_ponudnika}.txt",
                 encoding="utf-8"),
            delimiter=":"):
        cenik[vrstica[0]] = float(vrstica[1])
    return cenik

Pri vseh funkciji je najbolj zanimivo, kako smo sestavili ime datoteke: ime ponudnika smo vstavili kar v f-niz.

Kdor počasneje tipka, pa raje napiše samo

def preberi_cenik(ime_ponudnika):
    return {vrstica[0]: float(vrstica[1])
            for vrstica in csv.reader(
                open(f"podatki/dobavitelji/{ime_ponudnika}.txt",
                     encoding="utf-8"),
                delimiter=":")}

csv.reader je sicer praktičen vobče, pri tej nalogi pa od njega pravzaprav ni posebne koristi, saj rešitev brez njega ni prav nič bolj zapletena. Skoraj nasprotno.

def preberi_cenik(ime_ponudnika):
    cenik = {}
    for vrstica in open(f"podatki/dobavitelji/{ime_ponudnika}.txt"):
        predmet, cena = vrstica.split(": ")
        cenik[predmet] = float(cena)
    return cenik

ceniki

Rešitev

To je podobno kot darila_po_otrocih: gremo čez datoteke direktorija in zlagamo prebrano v slovar. Ime ponudnika pa dobimo tako, da imenu datoteke odbijemo zadnje štiri znake (.txt).

def ceniki():
    vsi_ceniki = {}
    for ime_ponudnika in os.listdir("podatki/dobavitelji"):
        ime_ponudnika = ime_ponudnika[:-4]
        vsi_ceniki[ime_ponudnika] = preberi_cenik(ime_ponudnika)
    return vsi_ceniki

najcenejsi_ponudnik

Rešitev

Prav neumno je, da ima tako preprosta funkcija tako dolg opis. Gre za običajno funkcijo, ki išče največjo vrednost oziroma nekaj povezanega z njo (najnižjo ceno, oziroma ponudnika, ki jo ponuja).

import math

def najcenejsi_ponudnik(ceniki, darilo):
    najcenejsi = None
    najcena = math.inf
    for ponudnik, cenik in ceniki.items():
        if cenik.get(darilo, math.inf) < najcena \
                or (cenik.get(darilo) == najcena
                    and ponudnik > najcenejsi):
            najcena = cenik[darilo]
            najcenejsi = ponudnik
    return najcenejsi, najcena

Glavni trik tu je pogoj. Kdaj je ponudnik boljši od vseh doslej? V osnovni, če je cenik[darilo] < najcena.

Oklepaj v pogoju niti ni potreben, saj and veže močneje kot or. Napišemo ga zaradi preglednosti, pa tudi zato, da Python ve, da se pogoj nadaljuje v naslednji vrstici, ne da bi morali na konec vrstice pisati \, tako kot smo morali narediti vrstico višje.

ponudniki_in_cene

Rešitev

Ta funkcija le pokliče prejšnjo za vsako darilo.

Bodisi tako

def ponudniki_in_cene(ceniki, darila):
    pic = {}
    for darilo in darila:
        pic[darilo] = najcenejsi_ponudnik(ceniki, darilo)
    return pic

bodisi kar tako

def ponudniki_in_cene(ceniki, darila):
    return {darilo: najcenejsi_ponudnik(ceniki, darilo)
            for darilo in darila}

Ocena 9

vrednost_daril

Rešitev

Iz pisma z izlusci_darila preberemo darila, ki jih želi otrok. Nato pokličemo ponudniki_in_cene, da izvemo ponudnike in cene teh daril. V dobljenem slovarju nas ne zanimajo ključi (darila) temveč le vrednosti, .values(). Vrednosti so pari (ponudnik, cena); zanimajo nas le cene.

def vrednost_daril(otrok):
    vrednost = 0
    darila = izlusci_darila(f"podatki/pisma/{otrok}.txt")
    for _, cena in ponudniki_in_cene(ceniki(), darila).values():
        vrednost += cena
    return vrednost

Spet je zabavno, kako smo sestavili ime datoteke.

Jedrnateje (a ne prav zares) je

def vrednost_daril(otrok):
    return sum(
        cena for _, cena in ponudniki_in_cene(
            ceniki(),
            izlusci_darila(f"podatki/pisma/{otrok}.txt")
        ).values())

preberi_tockovalnik

Rešitev

Ta je dokaj rutinska.

def preberi_tockovalnik():
    tockovalnik = {}
    for vrstica in open("podatki/tockovalnik.txt", encoding="utf-8"):
        otrok, dela = vrstica.split(":")
        pridnost = 0
        for delo in dela.split():
            pridnost += int(delo)
        tockovalnik[otrok] = pridnost
    return tockovalnik

dolocitev_daril

Rešitev

To je pa ta zabavna naloga. Edina, v kateri ne gre samo za neko relativno mehansko prekladanj vrednosti po slovarjih in množicah.

def dolocitev_daril(proracun, darila, ponudniki_cene):
    cene_in_darila = []
    for darilo in darila:
        cene_in_darila.append((ponudniki_cene[darilo][1], darilo))
    cene_in_darila.sort(reverse=True)
        
    darila = set()
    for cena, darilo in cene_in_darila:
        if cena <= proracun:
            darila.add(darilo)
            proracun -= cena
    return darila

V prvem delu sestavimo seznam parov cen in daril. V tem vrstnem redu. Nato ta seznam uredimo. Urejanje najprej primerja prve elemente (cene) in če imata dve stvari enak prvi element, ju primerja po drugem (ime darila). Če dodamo reverse=True, bo uredil po padajočih cenah in znotraj tega po padajočih imenih daril. (Naloga je napisana prijazno. Če bi zahtevala, da otrok dobi darilo, ki je prej po abecedi, bi bilo to bolj zopno.

V drugem delu gremo čez ta seznam. Vsako darilo, ki je v okviru proračuna, dodamo v košarico in ustrezno zmanjšamo proračun.

Lahko pa gremo tudi v drugo smer: darila uredimo naraščajoče in jih jemljemo s konca. Če za to uporabimo pop, ki vrne in pobriše zadnji element seznama, lahko zanko for zamenjamo z while, ki jo pustimo teči, dokler je seznam cene_in_darila neprazen - while cene_in_darila.

def dolocitev_daril(proracun, darila, ponudniki_cene):
    cene_in_darila = []
    for darilo in darila:
        cene_in_darila.append((ponudniki_cene[darilo][1], darilo))
    cene_in_darila.sort()

    dobi = set()
    while cene_in_darila:
        cena, darilo = cene_in_darila.pop()
        if cena <= proracun:
            dobi.add(darilo)
            proracun -= cena
    return dobi

darila_za_otroka

Rešitev

Pri tej nalogi sem videl neke dolge izdelke, v resnici pa moramo le poklicati prejšnjo funkcijo z ustreznimi argumenti. Vse podatke, ki jih potrebujemo, dobimo že v argumentih.

def darila_za_otroka(otrok, tockovalnik, otroci_darila, ponudniki_cene):
    return dolocitev_daril(
        tockovalnik[otrok] / 10,
        otroci_darila[otrok],
        ponudniki_cene)

Ocena 10

Napiši funkcijo narocila(), ki sestavi naročila za dobavitelje: funkcija mora sestaviti datoteke z imeni Dezman.txt, Godler.txt in tako naprej z vsebino v naslednji obliki:

Spoštovani dobavitelj,

pri vas bi rad naročil naslednja darila:

                     kosov
barvice..................6
blazina..................2
kocke....................2

Lep pozdrav,
Sveti Miklavž

Konkretna vsebina je za vsakega dobavitelja seveda drugačna. Datoteka mora biti oblikovana do pike in presledka tako, kot kaže vzorec. Naročeni predmeti naj bodo urejeni po abecedi.

Funkcija mora prej seveda ugotoviti, katera darila dobi kateri otrok in pri kom bodo nabavljena.

Rešitev

Tole pa zdaj zahteva, da združimo vse, kar imamo: preberemo vsa pisma, ugotovimo cene želenih daril, preberemo točkovalnike, določimo, kaj bo dobil kateri otrok... To se zgodi v prvem bloku spodnje funkcije.

V drugem sestavimo slovar narocila: njegovi ključi bodo imena ponudnikov, vrednosti pa slovarji, katerega ključi bodo darila, pripadajoče vrednosti pa število kosov tega darila.

V tretjem gremo čez ta slovar. Vsak element pripada ponudniku, torej za vsak element odpremo datoteko in vanjo zapišemo seznam daril, ki jih naročamo pri tem ponudniku.

def narocila():
    otroci_darila = darila_po_otrocih()
    vsa_darila = set(zbirnik_daril())
    ponudbe = ceniki()
    ponudniki_cene = ponudniki_in_cene(ponudbe, vsa_darila)
    tockovalnik = preberi_tockovalnik()

    narocila = {}
    for ponudnik, _ in ponudniki_cene.values():
        narocila[ponudnik] = defaultdict(int)
    for otrok in otroci_darila:
        for darilo in darila_za_otroka(otrok,
                                       tockovalnik,
                                       otroci_darila,
                                       ponudniki_cene):
            narocila[ponudniki_cene[darilo][0]][darilo] += 1

    for ponudnik, darila in narocila.items():
        f = open(ponudnik + ".txt", "wt")
        f.write("Spoštovani dobavitelj,\n\n"
                "pri vas bi rad naročil naslednja darila:\n\n")
        f.write(f"{'kosov':>26}\n")
        for darilo, kosov in sorted(darila.items()):
            f.write(f"{darilo:.<20}{kosov:.>6}\n")
        f.write("\nLep pozdrav,\nSveti Miklavž")