Testi

Testi: testi-izvoz.py

Podatki: izvoz.txt

Naloga

Poberite si datoteko s podatki o izvozu iz posameznih držav in jo shranite v direktorij, v katerem boste pisali svoj program. Odprite jo v poljubnem urejevalniku besedil in si oglejte, kako je videti. (Pazite, da je pri tem ne bi ponesreči shranili, da ne bo kaj narobe.)

Ogrevalna naloga

Napiši program, ki bere datoteko izvoz.txt in jo izpiše (kar s print) v takšni obliki: 

Afghanistan
['opium', 'fruits', 'nuts', 'handwoven carpets', 'wool', 'cotton', 'hides', 'pelts', 'gems']

Albania
['textiles', 'footwear', 'asphalt', 'metals', 'metallic ores', 'oil', 'vegetables', 'fruits', 'tobacco']

Algeria
['petroleum', 'natural gas', 'petroleum products']

American Samoa
['tuna']

Andorra
['tobacco products', 'furniture']
(in tako naprej). Torej, v eni vrstici ime države, v naslednji vrstici sledi seznam (da, sestavite seznam in ga izpišite s print!) izvoženih dobrin, nato prazna vrstica in potem naslednja država.

Opomba: za to nalogo nismo pripravili testov. Če je ne boste napisali pravilno, vam pač ne bo pomagala pri ostalih nalogah. Rešitev morate kljub temu oddati.

Obvezna naloga

Dani sta funkciji kdo_izvaza in kaj_izvaza.

def kdo_izvaza(produkt): return produkti[produkt] def kaj_izvaza(drzava): return drzave[drzava]

Funkciji sta, kakršni sta, in ju ne smeš spreminjati! Prva za vsak produkt vrne množico držav, ki slove kot izvoznice tega produkta. Druga funkcija za vsako državo vrne množico produktov, ki jih ta izvaža.

Napiši funkcijo preberi_podatke, ki prebere podatke iz datoteke in jih shrani v takšne spremenljivke, da bosta funkciji delovali.

Ideja je torej v tem, da bi na začetku programa poklicali to funkcijo, da bi pripravila podatke, kasneje pa bi v programu klicali kdo_izvaza in kaj_izvaza.

>>> preberi_podatke() >>> kdo_izvaza("rum") {'Jamaica', 'Puerto Rico', 'Bahamas', 'British Virgin Islands', 'Guyana', 'Anguilla', 'Barbados'} >>> kdo_izvaza("aircraft") {'Canada', 'United States', 'European Union', 'Malta', 'France'} >>> kdo_izvaza("nickel") {'Botswana', 'Colombia', 'Cuba'}

Dodatna naloga

Podobnost med državami - glede na njihov izvoz - lahko merimo z Jaccardovim indeksom. Vzemimo dve državi, \(F_1\) in \(F_2\), ter recimo, da prva izvaža produkte \(P_1\) in druga \(P_2\). Podobnost med državama je enaka velikosti preseka množic produktov deljeni z velikostjo unije (torej: število skupnih produktov deljenem s številom vseh produktov), \[J(D_1, D_2) = \frac{|D_1\cap D_2|}{|D_1\cup D_2|}\]

Napiši funkcijo, ki za vsako državo poišče pet najbolj podobnih držav glede na izvožene produkte. Vrne naj seznam z imeni teh držav, urejen po abecedi (ne po podobnosti!). Če si več držav deli peto mesto, naj vrne tudi vse te države. Pri Franciji, recimo, so najbolj podobne države 

    1. European Union   0.375
    2. India            0.3076923076923077
    3. Austria          0.26666666666666666
    4. Bulgaria         0.25
  5-7. Slovakia         0.23076923076923078
  5-7. Macedonia        0.23076923076923078
  5-7. Lithuania        0.23076923076923078
Ker si peto mesto delijo tri države, funkcija vrne vseh sedem držav, konkretno ['Austria', 'Bulgaria', 'European Union', 'India', 'Lithuania', 'Macedonia', 'Slovakia'].

Več primerov najdete v testnih primerih.

Rešitev

Ogrevalna naloga

Ogrevalna naloga naj bi vam tokrat predvsem pomagala počasi sestavljati rešitev obvezne. Ko rešujemo težak problem (za poprečnega programerja je tole sicer trivialno, za začetnika pa gotovo že sodi v kategorijo težkega) se splača program sestavljati po korakih in sproti izpisovati, kar imamo. Če ste pravilno rešili ogrevalno nalogo, je s tem že praktično rešena polovica obvezne naloge.

def izpisi(): for vrstica in open("izvoz.txt"): drzava, stvari = vrstica.strip().split("\t") stvari = [stvar.strip() for stvar in stvari.split(", ")] print(drzava) print(stvari) print()

Datoteko se splača brati po vrsticah. Nekateri so pisali

vrstice = open("izvoz.txt").read().split("\n") for vrstica in vrstice: To ni preveč dobra ideja, saj ni pregledna, poleg tega pa se ne obnaša vedno in povsod enako, saj je odvisna od tega, ali se zadnja vrstica zaključi z \n ali ne.

Od vsake vrstice odluščimo šaro na začetku in (predvsem) koncu ter jo razdelimo po \t v dva dela; v prvem je država, v drugem stvari, ki jih država izvaža. Nekateri so pisali

b = vrstica.strip().split("\t") nekateri pa a, b = vrstica.strip().split("\t") Kaj je boljše: da državi rečemo drzava, b[0] ali b. Rekel bi, da država. Upam, da vi tudi.

V naslednji vrstici razbijemo še niz s produkti v seznam produktov; z dodatnim stripom se rešimo nepotrebnega presledka na začetku.

Obvezna naloga

def preberi_podatke(): global drzave, produkti drzave = {} produkti = collections.defaultdict(set) for vrstica in open("izvoz.txt"): drzava, stvari = vrstica.strip().split("\t") stvari = stvari.strip().split(", ") drzave[drzava] = set(stvari) for stvar in stvari: produkti[stvar].add(drzava)

Spremenljivki drzave in produkti bosta globalni, kar je najlepše povedati na začetku funkcije. Nato sestavimo dva prazna slovarja. Eden bo običajni slovar, za drugega se bo pokazalo, da je bolj praktičen defaultdict. Funkcija se nato nadaljuje po zgledu prve, le da držav in stvari ne izpisujemo, temveč v slovar drzave zabeležimo, da država izvaža te in te stvari: drzave[drzava] = set(stvari). Seznam stvari mimogrede pretvorimo v množico stvari. Za to nalogo to ni potrebno, prav pa pride pri naslednji.

Zadnji dve vrstici poskrbita za obratni slovar. Ta je dal mnogim reševalcem precej vetra. Če uporabimo defaultdict, nam ni hudega: za vsak produkt zabeležimo, da je med njegovimi izvozniki tudi drzava, tako da jo dodamo v slovar izvoznikov: produkti[stvar].add(drzava). Če ne bi imeli defaultdicta, bi se morali prej potruditi, da bi dodali stvar v slovar. Točneje: za vsako stvar, ki jo vidimo prvič, dodamo v slovar pod ključ stvar prazno množico. Zadnji dve vrstici se s tem spremenita v

for stvar in stvari: if not stvar in produkti: produkti[stvar] = set() produkti[stvar].add(drzava)

Pogosta napaka je bila takšna:

for stvar in stvari: produkti[stvar] = set() produkti[stvar].add(drzava)

Če delamo tako, pri vsakem produktu vedno znova ustvarimo prazno množico in vanj dodamo državo. Na ta način bo vsak produkt navidez izvažala samo ena država.

Najpodobnejših pet

def najpodobnejsi(drzava): podobne = [] p1 = drzave[drzava] for drzava2, p2 in drzave.items(): if drzava != drzava2: podobne.append((len(p1 & p2) / len(p1 | p2), drzava2)) podobne.sort() peta = podobne[-5][0] najpod = [] for podobnost, drzava in podobne: if podobnost >= peta: najpod.append(drzava) return sorted(najpod)

Najprej sestavimo seznam parov (podobnost, drzava). Tu nam pride prav, da imamo množice produkto, saj lahko mirno računamo njihove preseke in unije. Seznam uredimo. Ker je seznam urejen naraščajoče, bo peta najpodobnejša država bo na koncu, torej podobne[-5]. Njena podobnost je podobne[-5][0]. V seznam najpod zložimo tiste države, katerih podobnost je večja ali enaka podobnosti pete države. Vrnemo po abecedi urejen seznam teh držav.

Zadnja sprememba: sreda, 24. marec 2021, 15.48