From 236001ec7563804f87a40c924681461bc8b2d764 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20Mo=C5=BEina?= Date: Mon, 5 Dec 2016 11:51:58 +0100 Subject: Added a new set of exercises (regular expressions). --- .../problems/comprehensions/comprehensions_sl.html | 572 ++++++++++++++++++++ python/problems/dictionaries/dict_sl.html | 598 +++++++++++++++++++++ python/problems/re/common.py | 2 + python/problems/re/double_parentheses/common.py | 69 +++ python/problems/re/double_parentheses/en.py | 13 + python/problems/re/double_parentheses/sl.py | 24 + python/problems/re/en.py | 2 + python/problems/re/intnum/common.py | 74 +++ python/problems/re/intnum/en.py | 13 + python/problems/re/intnum/sl.py | 27 + python/problems/re/num/common.py | 75 +++ python/problems/re/num/en.py | 13 + python/problems/re/num/sl.py | 29 + python/problems/re/ones/common.py | 69 +++ python/problems/re/ones/en.py | 13 + python/problems/re/ones/sl.py | 26 + python/problems/re/ones3/common.py | 70 +++ python/problems/re/ones3/en.py | 13 + python/problems/re/ones3/sl.py | 24 + python/problems/re/parentheses/common.py | 69 +++ python/problems/re/parentheses/en.py | 13 + python/problems/re/parentheses/sl.py | 24 + python/problems/re/re_sl.html | 371 +++++++++++++ python/problems/re/sl.py | 2 + python/problems/re/words/common.py | 69 +++ python/problems/re/words/en.py | 13 + python/problems/re/words/sl.py | 24 + python/problems/recursion/recursion_sl.html | 407 ++++++++++++++ 28 files changed, 2718 insertions(+) create mode 100644 python/problems/comprehensions/comprehensions_sl.html create mode 100644 python/problems/dictionaries/dict_sl.html create mode 100644 python/problems/re/common.py create mode 100644 python/problems/re/double_parentheses/common.py create mode 100644 python/problems/re/double_parentheses/en.py create mode 100644 python/problems/re/double_parentheses/sl.py create mode 100644 python/problems/re/en.py create mode 100644 python/problems/re/intnum/common.py create mode 100644 python/problems/re/intnum/en.py create mode 100644 python/problems/re/intnum/sl.py create mode 100644 python/problems/re/num/common.py create mode 100644 python/problems/re/num/en.py create mode 100644 python/problems/re/num/sl.py create mode 100644 python/problems/re/ones/common.py create mode 100644 python/problems/re/ones/en.py create mode 100644 python/problems/re/ones/sl.py create mode 100644 python/problems/re/ones3/common.py create mode 100644 python/problems/re/ones3/en.py create mode 100644 python/problems/re/ones3/sl.py create mode 100644 python/problems/re/parentheses/common.py create mode 100644 python/problems/re/parentheses/en.py create mode 100644 python/problems/re/parentheses/sl.py create mode 100644 python/problems/re/re_sl.html create mode 100644 python/problems/re/sl.py create mode 100644 python/problems/re/words/common.py create mode 100644 python/problems/re/words/en.py create mode 100644 python/problems/re/words/sl.py create mode 100644 python/problems/recursion/recursion_sl.html (limited to 'python') diff --git a/python/problems/comprehensions/comprehensions_sl.html b/python/problems/comprehensions/comprehensions_sl.html new file mode 100644 index 0000000..4ebea98 --- /dev/null +++ b/python/problems/comprehensions/comprehensions_sl.html @@ -0,0 +1,572 @@ + + + + + + + + + + +

Matematiki si lahko privoščijo opisati množico dvakratnikov vseh naravnih + števil, katerih kvadrat je manjši od 120, takole: + \(S=\{\,2\cdot x\mid x \in \mathbb{N},\ x^2<120\,\}\). Mi tudi.

+ +

Seznami

+ +

Vendar pojdimo lepo počasi. Začnimo s tistim, kar najbolj poznamo: s seznami. + Doslej smo jih zapisali tako, da smo v oglatih oklepajih naštevali njihove + elemente,

+ +
k = [9, 16, 81, 25, 196]
+ +

Oglate oklepaje bomo uporabljali tudi poslej, le da znotraj njih ne bomo + našteli elementov, temveč napisali izraz, ki jih sestavi. Recimo, da bi + hotel seznam korenov števil iz gornjega seznama (po nekem čednem naključju + gornji seznam vsebuje ravno same kvadrate). Naredil bi tako:

+ +
>>> [sqrt(x) for x in k]
+[3.0, 4.0, 9.0, 5.0, 14.0]
+ +

Torej: napisal sem oglate oklepaje, kot vedno, kadar definiram seznam, a + namesto, da bi naštel elemente, sem povedal, kakšni naj bodo. Rekel sem, + naj bodo elementi mojega novega seznama koren iz x, pri čemer so + x elementi seznama k. Kaj pa, če bi hotel + namesto tega imeti kvadrate števil? Isti šmorn:

+ +
>>> [x**2 for x in k]
+[81, 256, 6561, 625, 38416]
+ +

Oblika tega, kar pišemo, je vedno + [izraz for spremenljivka in nekaj], +kjer je spremenljivka ime neke spremenljivke (npr. x, +izraz nek izraz, ki (običajno, ne pa čisto nujno) vsebuje to +spremenljivko (npr. sqrt(x) ali 2*x, nekaj +pa je nekaj, čez kar je možno spustiti zanko for, torej seznam, slovar, +množica, datoteka ali kaj, česar še ne poznamo, vendar bomo spoznali še danes. +

+ +

Imam seznam imen, recimo,

+
l = ["Ana", "Berta", "Cilka", "Dani", "Ema"]
+ +

Kako bi izračunal poprečno dolžino imena? Imam funkcijo sum, + ki zna sešteti števila v seznamu. Potrebujem torej le še seznam dolžin + (namesto seznama imen). Tega pač preprosto dobim: izračunati želim dolžino + niza ime za vsako ime v seznamu + imena.

+ +
>>> [len(ime) for ime in imena]
+[3, 5, 5, 4, 3]
+ +

Zdaj pa tole le še seštejem in delim z dolžino seznama.

+ +
>>> sum([len(ime) for ime in imena]) / len(imena)
+4.0
+ +

Poprečna dolžina imena ni nič posebej zanimivega. Računajmo raje poprečno +težo in, da nam ne bo dolgčas, jo bomo računali iz teh podatkov:

+ +
podatki = [
+    (74, "Anže", False),
+    (82, "Benjamin", False),
+    (58, "Cilka", True),
+    (66, "Dani", False),
+    (61, "Eva", True),
+    (84, "Franc", False),
+]
+ +

Takole nam je storiti: z zanko se zapeljemo čez podatke, izračunamo vsoto +prvih elementov in jo delimo z dolžino seznama.

+ +

Lepo prosim, ne tako:

+ +
vsota = 0
+for i in range(len(podatki)):
+    vsota += podatki[i][0]
+print(vsota / len(podatki))
+ +

Tole je že boljše:

+ +
vsota = 0
+for podatek in podatki:
+    vsota += podatek[0]
+print(vsota / len(podatki))
+ +

In še malo bolje:

+ +
vsota = 0
+for teza, ime, zenska in podatki:
+    vsota += teza
+print(vsota / len(podatki))
+ +

Zdaj pa naredimo tako, kot smo se naučili danes. Naredimo lahko + +

vsota = sum([podatek[0] for podatek in podatki])
+ +

ali, po zadnji različici

+ +
vsota = sum([teza for teza, ime, zenska in podatki])
+ +

Pri izpeljevanju seznamov lahko dodamo še pogoj, s katerim izbiramo +elemente, ki naj se dodajo.

+ +

Kako bi sestavili seznam kvadratov vseh lihih +števil do 100? Seznam kvadratov vseh števil do 100 je trivialen, napisati +nam je treba le:

+ +
s = [x**2 for x in range(100)]
+ +

Če želimo pobrati samo liha števila, lahko v izpeljavo seznama dodamo še +pogoj.

+ +
s = [x**2 for x in range(100) if x % 2 == 1]
+ +

Tole pravzaprav ni čisto potrebno, lahko bi rekli preprosto

+ +
s = [x**2 for x in range(1, 100, 2)]
+ +

Kaj pa, če bi hoteli seznam kvadratov vseh števil do 100, ki niso deljiva s + 7 in ne vsebujejo števke 7?

+ +
[x**2 for x in range(100) if (x % 7 != 0) and ("7" not in str(x))]
+ +

V pogoju smo zaradi preglednosti uporabili oklepaje, čeprav sicer niso +potrebni). Prvi del poskrbi, da število ni deljivo s 7 (ostanek po deljenju s +7 mora biti različni od 0). Drugi del poskrbi, da število ne vsebuje števke 7: +število preprosto pretvorimo v niz in preverimo, da ne vsebuje sedemke.

+ +

Kako bi izračunali vsoto tež moških v gornjem seznamu? Za zanko dodamo +pogoj. Za začetek sestavimo le seznam imen vseh moških.

+ +
[ime for teza, ime, zenska in podatki if not zenska]
+ +

V definicijo našega seznama lepo na konec, za for, dodamo še +if in pogoj, ki mu mora zadoščati element, da nas zanima.

+ +

Z vsoto je podobno.

+ +
vsota = sum([teza for teza, ime, zenska in podatki if not zenska])
+ +

Zdaj veste, zakaj sem tako utrujal, da ne uporabljajte +for i in range(len(s)): zato, ker z njim namesto lepega, kratkega +preglednega [ime for teza, ime, zenska in podatki if not zenska] +dobimo +[podatki[i][1] for i in range(len(podatki)) if not podatki[i][2]]. +Seveda lahko delate tudi na ta, drugi način. Svobodni ljudje ste in noben zakon +ne prepoveduje mazohizma.

+ +

Sestavimo seznam vseh deliteljev danega števila n. Vzemimo, + recimo n = 60. Seznam deliteljev je tedaj seznam vseh + x, pri čemer x prihaja z intervala + 1 ≤ x ≤ n, za katere velja, da je ostanek po deljenju + n z x enak 0 (torej x deli + n).

+ +
def delitelji(n):
+    return [x for x in range(1, n+1) if n % x == 0]
+ +

Zdaj lahko hitro ugotovimo, ali je dano število popolno: popolna +števila so (se še spomnimo?) števila, ki so enaka vsoti svojih +deliteljev (brez sebe samega). + +

def popolno(n):
+    return n == sum(delitelji(n))
+

+ +

Še bolj imenitna števila so praštevila, števila brez deliteljev. Se pravi + tista, pri katerih je seznam deliteljev med 2 in tem številom prazen.

+ +
def prastevilo(n):
+    return not delitelji(n)
+ +

Če funkcije delitelji še ne bi imeli - nič hudega. Ali je + število praštevilo, bi še vedno dognali v eni sami vrstici.

+ +
def prastevilo(n):
+    return not [x for x in range(2, n) if n % x == 0])
+ +

S to funkcijo hitro sestavimo seznam vseh praštevil med 2 in 100:

+ +
>>> [n for n in range(2, 101) if prastevilo(n)]
+[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
+ +

Znamo pa, jasno, tudi brez funkcije; tisto, kar dela funkcija, pač kar +prepišemo v pogoj.

+ +
>>> [n for n in range(2, 101) if not [x for x in range(2, n) if n % x == 0])]
+[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
+ +

Takšnih reči sicer raje ne pišemo, saj hitro postanejo nepregledne.

+ +

Kdor je gledal stare naloge, je opazil nalogo z vislicami. V eni od nalog + je bilo potrebno napisati funkcijo pokazi_crke(beseda, crka), + ki kot argument dobi besedo in množico črk, vrniti pa mora besedo, v kateri + so "vidne" vse črke, ki so v množici, tiste, ki jih ni, pa je potrebno + zamenjati s piko. Tako mora, recimo, + pokazi_crke("BESEDA", {"E", "D"}) vrniti .E.ED.. +

+ +

Nalogo rešimo lepo po korakih. Vzemimo neko množico črk in neko besedo.

+ +
>>> crke = {"E", "D"}
+>>> beseda = "BESEDA"
+ +

Zdaj razsekajmo besedo na črke.

+ +
>>> [b for b in beseda]
+['B', 'E', 'S', 'E', 'D', 'A']
+ +

Zdaj pa naj seznam vsebuje b le, če je b v množici + crke, sicer pa piko.

+ +
>>> [b if b in crke else "." for b in beseda]
+['.', 'E', '.', 'E', 'D', '.']
+ +

Da združimo črke v niz, potrebujemo le še večno zeleni join.

+ +
>>> "".join([b if b in crke else "." for b in beseda])
+'.E.ED.'
+ +

Celotna rešitev naloge je torej

+ +
def pokazi_crke(beseda, crke):
+    print "".join((c if c in crke else ".") for c in beseda)
+
+ +

V splošnem: vsak kos kode, ki izgleda takole

+ +
r = []
+for e in s:
+    if pogoj(e):
+        r.append(funkcija(e))
+ +

lahko prepišemo v

+ +
r = [funkcija(e) for e in s if pogoj(e)]
+ +

Kdor želi še kakšen primer, si bo ogledal + rešitev + kronogramov in + napadalnih kraljic. +

+ +

Množice

+ +

Množice sestavljamo natančno tako kot sezname, le da namesto oglatih + oklepajev uporabimo zavite. Takole dobimo vse delitelje 60

+ +
>>> {i for i in range(1, 61) if 60 % i == 0}
+{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 60, 30}
+ + +

Slovarji

+ +

Ista reč. Če hočemo narediti slovar, ki bo kot ključe vseboval števila do + 10, kot vrednosti pa njihove kvadrate, napišemo

+ +
{i: i**2 for i in range(11)}
+ +

Generatorji

+ +

Tule bi pričakovali nekaj drugega: terke. Lahko tako kot sezname, množice in + slovarje naredimo tudi terke in nize? Ne. Na takšen način določeni nizi + očitno ne bi imeli nobenega smisla, pa tudi terke ne bi bile preveč + uporabne. Pač pa nas čaka - in bo pogosto v okroglih oklepajih - še nekaj + bolj nenavadnega in imenitnejšega: generatorji.

+ +
>>> g = (x**2 for x in range(10))
+ +

Tale g, kot se hitro prepričamo, ni terka, temveč nekaj + drugega.

+ +
>>> g
+ at 0x667bc0>
+ +

Kaj je generator, čemu služi in kako ga uporabljamo? Na prvi dve vprašanji + lahko odgovorimo naenkrat: generator je nekaj, kar generira objekte. + Vsakič, ko bomo od njega zahtevali nov objekt, bo vrnil novo število - + najprej 0, potem 1, potem 4, potem 9 ... pač kvadrate naravnih števil do + 10. Na tretje vprašanje, kako ga uporabljamo, nam skoraj ni potrebno + odgovarjati, saj generatorje (in njim podobne reči) že dolgo uporabljamo. + Generatorje najpreprosteje uporabimo z zanko for. Še več, zanka for deluje + na tistih rečeh - in samo tistih rečeh - ki se znajo obnašati kot + generatorji (torej: v resnici so generatorji ali pa podpirajo osnovne + funkcije generatorjev).

+ +
>>> for i in g:
+...     print(i, end=" ")
+...
+0 1 4 9 16 25 36 49 64 81
+ +

Če poskusimo ponoviti, ne gre: generator je že "iztrošen". Kar je imel + zgenerirati, je zgeneriral.

+ +
>>> for i in g:
+...     print(i, end=" ")
+...
+>>>
+ +

Generator je torej videti kot izpeljani seznam, le da namesto oglatih + oklepajev uporabimo okrogle. Kadar ga pošljemo kot edini argument funkciji, + smemo oklepaje celo izpustiti. Napišimo funkcijo, ki kot argument dobi + seznam števil in vrne prvo število, ki je večje od 50.

+ +
def nad50(s):
+    for e in s:
+        if e > 50:
+            return e
+ +

Preskusimo jo, trikrat:

+ +
>>> nad50([5, 1, 40, 1, 82, 12, 6])
+82
+>>> nad50([x**2 for x in range(10)])
+64
+>>> nad50(x**2 for x in range(10))
+64
+ +

V prvem primeru je dobila najobičajnejši seznam. Tako smo si predstavljali, + ko smo jo pisali. V drugem primeru smo ji dali seznam kvadratov števil do + 10 in vrnila je prvi kvadrat, ki je večji od 50. V tretjem klicu pa ji + sploh nismo dali seznama, temveč generator, ki je dajal kvadrate - + natančno isto reč kot gornji g. Funkcija je čez generator + pognala zanko for natančno tako, kot jo sicer poganja čez + sezname.

+ +

V čem je prednost generatorjev pred seznami? V tem, da ne sestavijo seznama. + Če želimo izračunati vsoto kvadratov prvih stotih števil in za to uporabimo + generator, na ta način ne sestavimo seznama teh števil (kot bi ga, če bi + rekli sum([x**2 for x in range(100)]), temveč števila, namreč + kvadrate, generiramo sproti (tako, da pokličemo + sum([x**2 for x in range(100)]). Hm, pa to v resnici deluje? + No, seveda. Funkcija sum bi lahko bila napisana takole

+ + 
def sum(s):
+     vsota = 0
+     for e in s:
+         vsota += e
+     return vsota
+ +

Zanka for lahko gre prek generatorja (in v resnici vedno gre prek + generatorja), torej ona reč deluje.

+ +

Že, že, poreče pozornejši študent: kaj pa range(100)? Mar ta + ne sestavi seznama stotih števil? Smo res kaj dosti pridobili - namesto + seznama kvadratov števil do 100 imamo pač števila do 100 - je to res tak + napredek? Tu lahko študenta pohvalimo za budnost, vendar se moti.

+ + 
>>> range(100)
+ range(0, 100)
+ +

V resnici range ne sestavi seznama, temveč generator. Res se + nam ni predstavil kot kak "generator object" temveč kot "range(0, 100)", + vendar v resnici ni ničesar sestavil. Nobenega seznama s stotimi števili + ni. Kako vem? Preprosto:

+ + 
>>> range(1000000000000)
+ range(0, 1000000000000)
+ +

Če bi range sestavljal sezname, bi bil to seznam z bilijon + elementi. Če bi vsak od njih zavzel samo en bajt (pa jih v resnici najbrž + vsaj 20, verjetneje pa 32), bi shranjevanje takšnega seznama zahtevalo + pomnilnik velik en terabajt.

+ +

Tako smo torej generatorje uporabljali že, odkar vemo za range. + (Morda se kdo spomni, da sem vam takrat, na onem davnem predavanju, ko sem + povedal za funkcijo range, le-to pokazal na Pythonu 2.7? Tako + je bilo lažje, saj je takrat še vračal sezname. To je ena od sprememb od + različice 3.0 naprej: po novem vrača generatorji.)

+ +

Podobno je s slovarji: metode __keys__, __values__ + in __items__ vračajo generatorje, ne seznamov.

+ +

Funkcije, ki generirajo

+ +

Še nekoliko naprednejša snov: Bi znali napisati generator Fibonaccijevih + števil, tako kot smo napisali generator kvadratov? Da, vendar bo + preprostejša nekoliko drugačna pot. Napisali bomo funkcijo, ki ne vrača le + enega rezultata temveč "generira" rezultate. Torej, nekaj takšnega:

+ +
def fibonacci(n):
+    a = b = 1
+    for i in range(n):
+        return a    # Tole ne deluje!
+        a, b = b, a+b
+ +

Tale funkcija ne deluje, napisali smo jo le, da ilustriramo idejo: radi bi + naredili zanko. Ko funkcijo prvič pokličemo, bi return vrnil + prvo Fibonaccijevo število. Ko jo pokličemo naslednjič, se funkcija ne bi + izvajala od začetka, temveč od tam, kjer smo nazadnje vrnili rezultat, se + pravi z vrstico, ki sledi returnu. No, v resnici naredimo + natanko tako, le namesto returna moramo uporabiti + yield:

+ +
def fibonacci(n):
+    a = b = 1
+    for i in range(n):
+        yield a
+        a, b = b, a+b
+ +

Preskusimo.

+ +
>>> for i in fibonacci(5):
+...    print(i)
+1
+1
+2
+3
+5
+ +

Napišemo lahko celo funkcijo, ki vrne (no, generira) vsa + Fibonaccijeva števila.

+ +
def fibonacci():
+    a = b = 1
+    while True:
+        yield a
+        a, b = b, a+b
+ +

Neskončno zanko, while True, smo že videli, vendar je bil v + njej vedno break, ki jo je nekoč prekinil. Kdo pa prekine to + zanko? Če nismo previdni, nihče. Če rečemo

+ +
>>> for i in fibonacci():
+...    print(i)
+ +

bo program izpisoval v nedogled. Pač pa lahko poiščemo, recimo, prvo + Fibonaccijevo število, ki je večje od 50.

+ +
>>> for i in fibonacci():
+...    if i > 50:
+...        print(i)
+...        break
+55
+ +

Ali pa, ah, saj imamo za to že funkcijo, nad50. Naj kar ta +pove, katero je prvo Fibonaccijevo število večje od 50!

+ +
>>> nad50(fibonacci())
+55
+ +

V zvezi z vsemi temi rečmi bi bilo mogoče povedati še zelo veliko. Tole je + ena najbolj kul tem v Pythonu. Pravzaprav treba priznati, da to niti ni + tema iz Pythona. V ozadju tega, kar počnemo tule, je poseben slog + programiranja, + funkcijsko + programiranje. Python ga omogoča in med "normalnimi" jeziki je za + takšen slog pravzaprav eden boljših. Obstajajo pa jeziki, ki so posebej + narejeni za takšno programiranje. Če je bilo komu tole, kar smo počeli + doslej, všeč naj si nujno ogleda kak + SML ali + + Haskell, morda pa ga bo zabaval tudi + + Racket (dialekt Lispa).

+ +

V Pythonu pa si bo ta, ki so mu bile te reči všeč, dobro ogledal module +functools, +iterools in +operator.

+ +

Generator deliteljev

+ +

Še en zanimiv primer je generator, ki vrne vse delitelje podanega števila. +

+ +
def delitelji(n):
+    for i in range(1, n + 1):
+        if n % i == 0:
+            yield i
+ +

Opazimo lahko, da z enim deliteljem dobimo dva: če je i delitelj +n-ja, je tudi n // i delitelj n-ja. +Če je tako, zadošča, da gremo do korena iz n in vrnemo po dva +delitelja.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            yield n // i
+ +

Koren iz n moramo spremeniti v celo število, ker range +ne mara necelih.

+ +

Pazite, tole sta dva yielda. Funkcija se izvaja tako, ad vrne +najprej eno število, in ko zahtevamo naslednje, se izvede naslednji +yield.

+ +

Funkcija je zdaj bistveno hitrejša (pri velikih številih bi se to utegnilo +kar poznati - namesto, da gre do milijona, bo šla le do 1000. Vendar žal ne +dela pravilno. Če je n, recimo, 25, bo funkcija +dvakrat vrnila 5. A tega se znamo hitro znebiti.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                yield n // i
+ +

Zdaj nas morda moti le še to, da števila ne prihajajo v pravem vrstnem redu. +Kot delitelje 42 bi namesto 1, 2, 3, 6, 7, 14, 21, 42 dobili 1, 42, 2, 21, 3, +14, 6, 7. To lahko popravimo tako, da n // i ne vračamo sproti, +temveč jih le shranjujemo in jih vračamo kasneje.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.append(n // i)
+    for e in ostali:
+        yield e
+ +

Nismo še čisto zmagali. Zdaj imamo 1, 2, 3, 6, 41, 21, 14, 7 - prva polovica +je iz prvega yielda, druga (od 41 naprej) iz drugega. Te, druge, +vrača v enakem vrstnem redu, v katerem jih je vstavljal v seznam, saj +append pač vstavlja na konec.

+ +

Pa vstavljajmo raje na začetek! Uporabimo insert.

+ +
from math import sqrt
+
+def delitelji(n):
+    for i in range(1, int(sqrt(n) + 1)):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.insert(0, n // i)
+    for e in ostali:
+        yield e
+ +

Žal se je insertu modro izogibati. Za to, da vstavi element +na prvo mesto, mora enega za drugim premakniti vse ostale. V teoriji (ki se jo +boste učili drugo leto) je ta program enako počasen kot bi bil, če bi prvo +zanko spustili prek range(1, n + 1). S tem, ko smo zamenjali +append z insert, smo, vsaj v teoriji, zapravili ves +prihranek.

+ +

To je preprosto urediti. Vstavljali bomo na konec, z append. +Pač pa bomo seznam nato prehodili v obratnem vrstnem redu. To se da narediti +z indeksiranjem (for i in range(-1, -n - n, -1): yield ostali[i], +vendar si bomo raje pomagali s priročno funkcijo reversed, ki +obrne seznam.

+ +
def delitelji(n):
+    ostali = []
+    for i in range(1, int(sqrt(n)) + 1):
+        if n % i == 0:
+            yield i
+            if i ** 2 != n:
+                ostali.append(n // i)
+    for e in reversed(ostali):
+        yield e
+ + diff --git a/python/problems/dictionaries/dict_sl.html b/python/problems/dictionaries/dict_sl.html new file mode 100644 index 0000000..8b7966d --- /dev/null +++ b/python/problems/dictionaries/dict_sl.html @@ -0,0 +1,598 @@ + + + + + + + + + + +

Slovar

+ +

Poglejmo še enkrat sezname. Seznam je nekakšna zbirka nekih poljubnih + reči, pri čemer je vsaka reč v svojem "predalčku", predalčki pa so + oštevilčeni. Prvi ima številko 0, drugi 1, tretji 2 in tako naprej. Za + vsak predalček lahko pogledamo, kaj je v njem, spremenimo njegovo vsebino, + predalčke lahko odvzemamo in dodajamo. + +

>>> s = [6, 9, 4, 1]
+>>> s[1]
+9
+>>> s.append(7)
+>>> s
+[6, 9, 4, 1, 7]
+>>> del s[3]
+>>> s
+[6, 9, 4, 7]
+>>> s[-2:]
+[4, 7]
+ +

Slovar (angl. dictionary, podatkovni tip pa se imenuje + dict) je podoben seznamu, le da se na predalčke sklicujemo z + njihovimi ključi (angl. key, ki so lahko števila, lahko + pa tudi nizi, logične vrednosti, terke... Temu, kar je shranjeno v predalčku + bomo rekli vrednost (value).

+ +

Seznam in slovar se že od daleč (če niste kratkovidni) razlikujeta po + oglatosti. Seznam smo opisali tako, da smo v oglatih oklepajih + našteli njihove elemente. Slovar opišemo tako, da v zavitih + oklepajih naštejemo pare ključ: vrednost. + +

Stalno omenjani Benjamin si lahko takole sestavi slovar s telefonskimi + številkami svojih oboževalk: +

stevilke = {"Ana": "041 310239", "Berta": "040 318319", "Cilka": "041 103194", "Dani": "040 193831",
+                "Eva": "051 123123", "Fanči": "040 135367", "Helga": "+49 175 4728 475"}
+ +

Do vrednosti, shranjenih v slovarju, pride podobno kot do vrednosti v + seznamu: z indeksiranjem, le da v oglate oklepaje ne napiše zaporedne + številke, temveč ključ.

+ +
>>> stevilke["Ana"]
+'041 310239'
+>>> stevilke["Dani"]
+'040 193831'
+ +

Slovarji ne poznajo vrstnega reda. V slovarju ni prvega, drugega, tretjega + elementa. Ne le zato, ker oznake niso številke. Ne, slovar si v resnici ne + zapomni vrstnega reda, v katerem smo našteli elemente, niti ne vrstnega + reda, v katerem jih dodajamo.

+ +
>>> stevilke
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Helga': '+49 175 4728 475',
+'Eva': '051 123123', 'Cilka': '041 103194', 'Berta': '040 318319',
+'Ana': '041 310239'}
+ +

(Čemu?! Čemu je to potrebno? Čemu zmeša vrstni red?! Mar ne more zlagati + teh reči lepo po vrsti? Izvedeli boste drugo leto. V resnici ni zmešan, + temveč prav premeteno premetan. V tem, drugače preurejenem seznamu lahko išče + veliko hitreje.)

+ +

Ker ni vrstnega reda, tudi ni rezin.

+ +
>>> stevilke["Ana":"Cilka"]
+Traceback (most recent call last):
+  File "", line 1, in 
+TypeError: unhashable type
+ +

Tole sporočilo o napaki je sicer zelo čudno, vendar povsem smiselno. Boste +razumeli, ko boste veliki. ;)

+ +

O "mehaniki" slovarjev morate vedeti le tole: slovarji so hitri, saj + elementov v resnici ne iščejo. Na nek za zdaj skrivnosten način "vedo", kje + je vrednost, ki pripada danemu ključu. Ne da bi iskali, vedo, kam morajo + pogledati. Tudi dodajanje novih elementov v slovar je zelo hitro, enako tudi + brisanje. Cena, ki jo plačamo za to, je dvojna. Ključi so lahko le + podatkovni tipi, ki so nespremenljivi. Nespremenljivi podatkovni tipi so, + vemo, nizi, števila, logične vrednosti in terke. Zgoraj smo kot ključ + uporabili niz. To je OK. Če bi poskušali kot ključ uporabiti seznam, ne bi + šlo. (V resnici je stvar malenkost bolj zapletena, ključ je lahko vsak + podatkovni tip, ki je "razpršljiv", vendar to ni za bruce). Omejitve + veljajo le za ključe. Vrednost je lahko karkoli.

+ +

Drugi obrok cene, ki jo plačamo za učinkovitost slovarjev, je poraba + pomnilnika: slovar porabi nekako dvakrat več pomnilnika kot seznam. Koliko, + točno, več, je odvisno od velikost slovarja in tega, kaj shranjujemo. + Pri tem predmetu se s pomnilnikom ne obremenjujte.

+ +

Aha, še tretji obrok cene, iz drobnega tiska: vsak ključ se lahko pojavi + največ enkrat. Če poskušamo prirediti neko vrednost ključu, ki že obstaja, le + povozimo staro vrednost. Ampak to je tako ali tako pričakovati. Tudi v + seznamu nimamo nikoli dveh različnih elementov na istem mestu.

+ +

Kaj lahko počnemo s slovarji?

+ +

Lahko jim dodajamo nove elemente: preprosto priredimo jim nov element.

+ +
>>> stevilke["Iva"] = "040 222333"
+>>> stevilke
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Iva': '040 222333',
+'Helga': '+49 175 4728 475', 'Eva': '051 123123', 'Cilka': '041 103194',
+'Berta': '040 318319', 'Ana': '041 310239'}
+ +

append ne obstaja, saj nima smisla: ker ni vrstnega reda, ne +moremo dodajati na konec. Prav tako (ali pa še bolj) ne obstaja +insert, saj prav tako (ali pa še bolj) nima smisla. + +

Vprašamo se lahko, ali v seznamu obstaja določen ključ.

+ +
>>> "Cilka" in stevilke
+True
+>>> "Jana" in stevilke
+False
+ +

Če se Cilka skrega z Benjaminom, jo lahko le-ta pobriše (mislim, pobriše + njeno številko).

+ +
>>> del stevilke["Cilka"]
+>>> stevilke
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Iva': '040 222333',
+'Helga': '+49 175 4728 475', 'Eva': '051 123123',
+'Berta': '040 318319', 'Ana': '041 310239'}
+>>> "Cilka" in stevilke
+False
+ +

Če gremo prek slovarjev z zanko for, dobimo vrednosti + ključev.

+ +
>>> for ime in stevilke:
+... 	print(ime)
+...
+Dani
+Fanči
+Iva
+Helga
+Eva
+Berta
+Ana

+ +Seveda lahko ob vsakem imenu izpišemo tudi številko. + +
>>> for ime in stevilke:
+... 	print(ime + ":", stevilke[ime])
+...
+Dani: 040 193831
+Fanči: 040 135367
+Iva: 040 222333
+Helga: +49 175 4728 475
+Eva: 051 123123
+Cilka: 041 103194
+Berta: 040 318319
+Ana: 041 310239
+ +

Vendar to ni najbolj praktično. Pomagamo si lahko s tremi metodami slovarja, + ki vrnejo vse ključe, vse vrednosti in vse pare ključ-vrednost. Imenujejo + se (ne preveč presenetljivo) keys(), values() in + items(). Delamo se lahko, da vračajo sezname ključev, + vrednosti oziroma parov ... čeprav v resnici vračajo le nekaj, prek česar + lahko gremo z zanko for. + +

Najprej poglejmo items().

+ +
>>> for t in stevilke.items():
+... 	ime, stevilka = t
+... 	print(ime + ":", stevilka)
+ +

Tole zgoraj je bilo seveda grdo. Lepo se reče takole:

+ +
>>> for ime, stevilka in stevilke.items():
+... 	print(ime + ":", stevilke)
+ +

Tako kot sem ob zanki for težil, da ne uporabljajte +for i in range(len(s)) temveč for e in s in da +že v glavi zanke razpakirajte terko, kadar je to potrebno, bom težil tudi +tule: uporabljajte items in vaši programi bodo preglednejši in +s tem pravilnejši.

+ +

Metoda values vrne vse vrednosti, ki so v slovarju. V našem + primeru torej telefonske številke. Metodo values človek včasih +potrebuje, prav pogosto pa ne.

+ +

V nasprotju s tem metodo keys potrebujejo samo študenti. Ne vem +točno, zakaj sploh obstaja. No, vem, zato da študenti lahko pišejo +for ime in stevilke.keys() namesto +for ime in stevilke. Druge uporabne vrednosti pa ne vidim. :)

+ +

Skratka: ne uporabljajte metode keys.

+ +

Slovar ima še dve metodi, ki smo ju videli tudi pri seznamu: metodo, ki + sprazni slovar in drugo, ki naredi nov, enak slovar.

+ +
>>> stevilke2 = stevilke.copy()
+>>> stevilke2
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Iva': '040 222333',
+'Helga': '+49 175 4728 475', 'Eva': '051 123123',
+'Berta': '040 318319', 'Ana': '041 310239'}
+>>> stevilke.clear()
+>>> stevilke
+{}
+>>> stevilke2
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Iva': '040 222333',
+'Helga': '+49 175 4728 475', 'Eva': '051 123123',
+'Berta': '040 318319', 'Ana': '041 310239'}
+ +

Omenimo le še eno od slovarjevih metod, get. Ta dela podobno + kot indeksiranje, stevilke.get("Ana") naredi isto kot + stevilke["Ana"]. Metodo get uporabimo, kadar ni + nujno, da je ključ v seznamu in želimo v tem primeru dobiti neko privzeto + vrednost. Privzeto vrednost podamo kot drugi argument.

+ +
>>> stevilke.get("Ema", "ni številke")
+'040 584928'
+>>> stevilke.get("Greta", "ni številke")
+'nimam stevilke'
+ +

Še enkrat: ne pišite stevilke.get("Ema"). To je čudno. +Piše se stevilke["Ema"]. Metodo get uporabite le +takrat, kadar niste prepričani, da slovar vsebuje ta ključ.

+ +

Primer: kronogrami

+ +

Neka naloga je šla takole.

+ +

Veliko latinskih napisov, ki obeležujejo kak pomemben dogodek, je napisanih + v obliki kronograma: + če seštejemo vrednosti črk, ki predstavljajo tudi rimske številke (I=1, V=5, + X=10, L=50, C=100, D=500, M=1000), dajo letnico dogodka.

+ +

Tako, recimo, napis na cerkvi sv. Jakoba v Opatiji, CVIVS IN HOC RENOVATA + LOCO PIA FVLGET IMAGO SIS CVSTOS POPVLI SANCTE IACOBE TVI, da vsoto 1793, + ko je bila cerkev prenovljena (o čemer govori napis).

+ +

Pri tem obravnavamo vsak znak posebej: v besedil EXCELSIS bi prebrali + X + C + L + I = 10 + 100 + 50 + 1 = 161 in ne + XC + L + I = 90 + 50 + 1 = 141.

+ +

Napiši program, ki izračuna letnico za podani niz.

+ +

Očitna rešitev je:

+ +
def kronogram(s):
+    v = 0
+    for c in s:
+        if c=="I":
+            v += 1
+        elif c=="V":
+            v += 5
+        elif c=="X":
+            v += 10
+        elif c=="L":
+            v += 50
+        elif c=="C":
+            v += 100
+        elif c=="D":
+            v += 500
+        elif c=="M":
+            v += 1000
+    return v
+ +

Pri njej vsi, ki poznajo stavek switch oz. case +postokajo, kako je možno, da Python tega stavka nima. (Pustimo ob strani, +ali je tole res toliko daljše od switch, sploh če program nespodobno +nabijemo skupaj:

+
def kronogram(s):
+    v = 0
+    for c in s:
+        if c=="I": v += 1
+        elif c=="V": v += 5
+        elif c=="X": v += 10
+        elif c=="L": v += 50
+        elif c=="C": v += 100
+        elif c=="D": v += 500
+        elif c=="M": v += 1000
+    return v
+

). Ne, nima ga, ker ga skoraj nikoli ne potrebujemo. Tisto, kar delamo z +njim, pogosto rešimo (tudi) s slovarji.

+ +

V slovar si bomo zapisali, katero številko pomeni katera črka.

+ +
stevke = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
+ +

Funkcija zdaj deluje tako, da gre prek niza in za vsako črko preveri, ali je v +slovarju. Če je ni, ne pomeni številke; če je, prištejemo toliko, kolikor je +vredna.

+ +
def kronogram(s):
+    v = 0
+    for c in s:
+        if c in stevke:
+            v += stevke[c]
+    return v

+ +

Še hitreje gre z get; če črke ni, je njena privzeta vrednost 0. +

+
def kronogram(s):
+    v = 0
+    for c in s:
+        v += stevke.get(c, 0)
+    return v
+ +

Ob tem si ne moremo kaj, da ne bi poškilili za en mesec naprej, ko se bomo + učili funkcijskega programiranja in znali biti še krajši in jedrnatejši, + spet predvsem po zaslugi slovarjev.

+ +
def kronogram(s):
+    return sum(stevke.get(c, 0) for c in s)
+ + +

Slovarji s privzetimi vrednostmi

+ +

Slovarji so uporabne reči. V veliko primerih pa uporabimo neko različico +slovarja, ki ima še eno dodatno sposobnost.

+ +

Denimo, da smo dobili v preskušanje igralno kocko, za katero nas zanima, ali + goljufa. Stokrat smo jo vrgli in zabeležili rezultate.

+ +
meti = [4, 4, 4, 3, 2, 3, 5, 3, 3, 4, 6, 6, 6, 1, 3,
+        6, 6, 4, 1, 4, 6, 1, 4, 4, 4, 6, 4, 6, 5, 5, 6, 6, 2, 4, 4, 6,
+		3, 2, 6, 1, 3, 6, 3, 2, 6, 6, 4, 6, 4, 2, 4, 4, 1, 1, 6, 2, 6,
+		6, 4, 3, 4, 2, 6, 5, 6, 3, 2, 5, 1, 5, 3, 6, 4, 6, 2, 2, 4, 1,
+		4, 4, 3, 1, 4, 2, 1, 3, 1, 4, 6, 1, 1, 3, 4, 1, 4, 3, 2, 4, 6, 6]
+ +

Zanima nas, kolikokrat je padla katera številka. Nič lažjega. Najprej si + pripravimo seznam s sedmimi ničlami.

+ +
>>> kolikokrat = [0] * 7
+>>> kolikokrat
+[0, 0, 0, 0, 0, 0, 0]
+ +

Zdaj nam bo, recimo kolikokrat[3] povedal, kolikokrat je padla + trojka. (Čemu sedem? Saj ima kocka samo šest ploskev. Boste videli. Finta.) + Zdaj pa štejmo: pojdimo čez vse mete in povečujmo števce.

+ +
>>> for met in meti:
+... 	kolikokrat[met] += 1
+...
+>>> kolikokrat
+[0, 14, 12, 15, 27, 6, 26]
+ +

(Kje je finta? kolikokrat[0] bo pove, kolikokrat je padla ničla. +Nikoli pač. Napišite isto reč s seznamom dolžine šest, ne sedem. Ni problem, +ampak tako, kot smo nardili je preprostejše.)

+ +

(Kocka je res videti nekoliko sumljiva: štirke in šestice so nekam pogoste + na račun petk. A pustimo statistikom vprašanje, ali je to še lahko + naključno ali ne.)

+ +

Ups, nalogo smo rešili kar s seznamom! Da, to gre, ker so "predalčki" + seznama oštevilčeni, tako kot ploskve kocke. Tole pa ne bo šlo: tule je + seznam telefonskih številk deklet, ki jih je danes klical Benjamin. Katero + je poklical kolikokrat?

+ +
klici = ['041 103194', '040 193831', '040 318319', '040 193831', '041 310239',
+        '040 318319', '040 318319', '040 318319', '040 193831', '040 193831',
+        '040 193831', '040 193831', '040 193831', '040 318319', '040 318319',
+        '040 318319', '040 193831', '040 318319', '041 103194', '041 103194',
+        '041 310239', '040 193831', '041 103194', '041 310239', '041 310239',
+        '040 193831', '041 310239', '041 103194', '040 193831', '040 318319']
+ +

Za tako velike številke bi moral imeti seznam zelo veliko predalčkov. Še + huje bi bilo, če bi namesto seznama številk dobili seznam klicanih oseb.

+ +
klici = ['Cilka', 'Dani', 'Berta', 'Dani', 'Ana', 'Berta', 'Berta',
+         'Berta', 'Dani', 'Dani', 'Dani', 'Dani', 'Dani', 'Berta', 'Berta',
+         'Berta', 'Dani', 'Berta', 'Cilka', 'Cilka', 'Ana', 'Dani', 'Cilka',
+         'Ana', 'Ana', 'Dani', 'Ana', 'Cilka', 'Dani', 'Berta']
+ +

Tu smo s seznamom pogoreli. No, ne čisto; rešitev s seznami seveda obstaja, + je pa zoprna - podobna je tistemu, kar smo v začetku počeli z bančnimi + računi.

+ +

S slovarji je veliko lepše: +

pogostosti = {}
+for ime in klici:
+    if ime not in pogostosti:
+        pogostosti[ime] = 0
+    pogostosti[ime] += 1
+print(pogostosti)
+ +

Ob vsakem novem klicu preverimo, ali je klicano ime že v + slovarju. Če ga ni, da dodamo. Nato - najsibo ime novo ali ne - povečamo + števec klicev pri tej osebi.

+ + +

Ker je ta stvar resnično pogosta, nam Python pomaga z modulom +collections, ki vsebuje podatkovni tip defaultdict. +(Modul, ki vsebuje podatkovni tip?! Da, da; tudi to je ena od stvari, ki jih +bomo našli v modulih.) Ta se obnaša tako kot slovar, z eno izjemo: če zahtevamo +kak element, ki ne obstaja, si ga meni nič tebi nič izmisli. Točneje, doda ga v +slovar in mu postavi privzeto vrednost. Katero, določimo. Pri tem ne podamo +privzete vrednosti, temveč "funkcijo", ki bo vračala privzeto vrednost. +defaultdict bo ustvarjal te, nove vrednosti tako, da bo poklical +to funkcijo brez argumentov in kot privzeto vrednost uporabil, kar vrne +funkcija, ki jo v ta namen vsakič sproti pokliče.

+ +

Zelo pogosto bo privzeta vrednost 0 in funkcija, ki vrača + 0, se imenuje, hm, int.

+ +

("Funkcija" int, je vedno sumljivejša in sumljivejša. Že od +začetka smo v zvezi z njo dajali besedo "funkcija" pod narekovaje, zdaj pa vidimo, +da zmore vedno več in več stvari. Pa še enako ji je ime kot tipu in funkcij, ki +jim je ime enako kot tipom, je vedno več. Kakšna skrivnost se skriva za tem? To +boste izvedeli v enem od prihodnjih napetih nadaljevanj Programiranja 1.)

+ +

Preštejmo torej še enkrat Benjaminove klice, tokrat s slovarjem s privzetimi + vrednostmi.

+ +
import collections
+
+pogostosti = collections.defaultdict(int)
+for ime in klici:
+    pogostosti[ime] += 1
+ +

Ni to kul?

+ +

Poglejmo si nekaj, kar je kul še bolj.

+ + +

Števec

+ +

Preštevanje je pravzaprav tako pogosta reč, da obstaja zanj specializiran + tip. Tako kot defaultdict je v modulu collections, +imenuje pa se Counter.

+ +
>>> stevilo_klicev = collections.Counter(klici)
+>>> stevilo_klicev
+Counter({'Dani': 11, 'Berta': 9, 'Cilka': 5, 'Ana': 5})
+ +

Komentirali ne bomo veliko, ker še ne znamo. Že ob tem, da sem temu rekel + tip, sem se moral ugrizniti v jezik, saj bi raje govoril o razredu. Kaj je + in kako deluje, pa nas še presega. Zna pa pravzaprav še veliko stvari, + tako da tem, ki jih zanima, priporočam, da si ga ogledajo. Mimogrede:

+ +
>>> napis = "CVIVS IN HOC RENOVATA LOCO PIA FVLGET IMAGO SIS" \
+        "CVSTOS POPVLI SANCTE IACOBE TVI"
+>>> collections.Counter()
+Counter({' ': 13, 'I': 8, 'O': 8, 'V': 7, 'A': 6, 'C': 6, 'S': 6, 'T': 5, 'E': 4,
+'L': 3, 'N': 3, 'P': 3, 'G': 2, 'B': 1, 'F': 1, 'H': 1, 'M': 1, 'R': 1})
+ +

Se pravi, da lahko kronogram rešimo tudi z

+ +
def kronogram(s):
+    crke = collections.Counter(s)
+    return crke["I"] + 5 * crke["V"] + 10 * crke["X"] + 50 * crke["L"] + \
+           100 * crke["C"] + 500 * crke["D"] + 1000 * crke["M"]
+ + + +

Množice

+ +

Množice so podobne seznamom, a s to razliko, da lahko vsebujejo vsak element + samo enkrat. Po drugi strani (in ne le po drugi strani, tudi tehnično) pa + so podobne slovarjem. Niso namreč urejene in vsebujejo lahko le elemente, + ki so nespremenljivi. Poleg tega pa lahko zelo hitro ugotovimo, ali množica + vsebuje določen element ali ne - tako kot lahko pri slovarjih hitro + ugotovimo, ali vsebujejo določen ključ ali ne.

+ +

Množice zapišemo z zavitimi oklepaji, tako kot smo vajeni pri matematiki.

+
danasnji_klici = {"Ana", "Cilka", "Eva"}
+ +

Tako lahko sestavimo le neprazno množico. Če napišemo le oklepaj in + zaklepaj, {}, pa dobimo slovar. (Čemu so se odločili, naj bo + to slovar, ne množica? Slovar je bil prej, množice je Python dobil kasneje. + Zato.) Če hočemo narediti prazno množico, rečemo

+ +
prazna = set()
+ +

"Funkcija" set je malo podobna "funkciji" int: + damo ji lahko različne argumente, pa jih bo spremenila v množico. Damo ji + lahko, recimo, seznam, pa bomo dobili množico z vsemi elementi, ki se + pojavijo v njem.

+ +
>>> set([1, 2, 3])
+{1, 2, 3}
+>>> set(range(5))
+{0, 1, 2, 3, 4}
+>>> set([6, 42, 1, 3, 1, 1, 6])
+{1, 42, 3, 6}
+ +

Mimogrede opazimo, da tudi množice, tako kot slovarji, res ne dajo nič na + vrstni red.

+ +

Poleg seznamov lahko množicam podtaknemo karkoli, prek česar bi lahko šli + z zanko for, recimo niz ali slovar.

+ +
>>> set("Benjamin")
+{'a', 'B', 'e', 'i', 'j', 'm', 'n'}
+>>> stevilke
+{'Dani': '040 193831', 'Fanči': '040 135367', 'Iva': '040 222333',
+'Helga': '+49 175 4728 475', 'Eva': '051 123123', 'Cilka': '041 103194',
+'Berta': '040 318319', 'Ana': '041 310239'}
+>>> set(stevilke)
+{'Iva', 'Helga', 'Eva', 'Berta', 'Fanči', 'Dani', 'Cilka', 'Ana'}
+ +

Spremenljivka stevilke (še vedno) vsebuje slovar, katerega + ključi so imena Benjaminovih oboževalk. Ker zanka prek slovarja "vrača" + ključe, bo tudi množica, ki jo sestavimo iz slovarja, vsebovala ključe.

+ +

V množico lahko dodajamo elemente in vprašamo se lahko, ali množica vsebuje + določen element.

+ +
>>> s = set("Benjamin")
+>>> "e" in s
+True
+>>> "u" in s
+False
+>>> s.add("u")
+>>> s
+{'a', 'B', 'e', 'i', 'j', 'm', 'n', 'u'}
+>>> "u" in s
+True
+>>> s.add("a")
+>>> s.add("a")
+>>> s.add("a")
+>>> s
+{'a', 'B', 'e', 'i', 'j', 'm', 'n', 'u'}
+ +

Na koncu smo poskušali v množico dodati element, ki ga že vsebuje. To seveda + ne gre, množica vsak element vsebuje le enkrat.

+ +

Če imamo dve množici, lahko izračunamo njuno unijo, presek, razliko...

+ +
>>> u = {1, 2, 3}
+>>> v = {3, 4, 5}
+>>> u | v
+{1, 2, 3, 4, 5}
+>>> u & v
+{3}
+ +

Preverimo lahko tudi, ali je neka množica podmnožica (ali nadmnožica druge). + To najpreprosteje storimo kar z operatorji za primerjanje.

+ +
>>> u = {1, 2, 3}
+>>> {1, 2} <= u
+True
+>>> {1, 2, 3, 4} <= u
+False
+>>> {1, 2, 3} <= u
+True
+>>> {1, 2, 3} < u
+False
+ +

{1, 2, 3}, je podmnožica u-ja, ni pa njegove + prava podmnožica, saj vsebuje kar cel u.

+ +

Z množicami je mogoče početi še marsikaj zanimivega - vendar bodi dovolj.

+ + +

Primer: Seznami v slovarjih

+ +

Recimo, da želimo sestaviti skupine datotek v nekem direktoriju glede na + končnice. Sestavili bomo slovar, katerega ključi bodo končnice, na primer + .py, .txt in .mp3, vrednosti pri vsakem ključu pa imena datotek s to + končnico.

+ +
datoteke = {}
+for ime in os.listdir(dir):
+    konc = os.path.splitext(ime)[1]
+    if not konc in datoteke:
+        datoteke[konc] = set()
+    datoteke[konc].add(ime)
+ + +

Če ste bili pozorni, niste spregledali, da je gornji program pravzaprav na + nek način enak programu, s katerim smo preštevali, kolikokrat je Benjamin + klical katero od deklet: + +

pogostosti = {}
+for ime in klici:
+    if not ime in pogostosti:
+        pogostosti[ime] = 0
+    pogostosti[ime] += 1
+

+ +

"Istost" je v tem, da obakrat naredimo prazen slovar. Nato gremo z zanko +for čez neke reči. Za vsako reč (v gornjem primeru datoteke, v +spodnjem ime dekleta) preverimo, ali je že v slovarju. Če je ni, jo dodamo tako, +da ji damo neko privzeto vrednost (zgoraj prazno množico, spodaj 0). Nato +pravkar dodano stvar posodobimo glede na trenutno reč (v gornjem primeru dodamo +datoteko v pravkar sestavljeno ali od prej obstoječo množico, v spodnjem povečamo +število klicev te osebe za 1).

+ +

Aja, to finto pa že poznamo. Slovarji s privzetimi vrednostmi!

+ +
datoteke = collections.defaultdict(set)
+for ime in os.listdir(dir):
+    konc = os.path.splitext(ime)[1]
+    datoteke[konc].add(ime)
+ \ No newline at end of file diff --git a/python/problems/re/common.py b/python/problems/re/common.py new file mode 100644 index 0000000..56b244e --- /dev/null +++ b/python/problems/re/common.py @@ -0,0 +1,2 @@ +id = 2009 +number = 9 diff --git a/python/problems/re/double_parentheses/common.py b/python/problems/re/double_parentheses/common.py new file mode 100644 index 0000000..5806559 --- /dev/null +++ b/python/problems/re/double_parentheses/common.py @@ -0,0 +1,69 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20907 +number = 7 +visible = True + +solution = '''\ +import re + +def double_parentheses(s): + return re.findall(r'\(\(.*?\)\)', s) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'double_parentheses' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('(a a) bb (cc)', []), + ('a a b b c c', []), + ('', []), + ('(()())(()', ['(()())']), + ('((aa (aa) aa)) bb ((cc)) (dd)', ['((aa (aa) aa))', '((cc))']), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/double_parentheses/en.py b/python/problems/re/double_parentheses/en.py new file mode 100644 index 0000000..57f27f1 --- /dev/null +++ b/python/problems/re/double_parentheses/en.py @@ -0,0 +1,13 @@ +id = 20907 +name = 'Double parentheses' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/double_parentheses/sl.py b/python/problems/re/double_parentheses/sl.py new file mode 100644 index 0000000..501bce7 --- /dev/null +++ b/python/problems/re/double_parentheses/sl.py @@ -0,0 +1,24 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20907 +name = 'Dvojni oklepaji' + +description = '''\ +

+Napišite funkcijo double_parantheses(s), ki vrne vse nize, ki se +pojavijo v dvojnih oklepajih.

+
+>>> double_parentheses('((aa (aa) aa)) bb ((cc)) (dd)')
+['((aa (aa) aa))', '((cc))']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/en.py b/python/problems/re/en.py new file mode 100644 index 0000000..247e5bb --- /dev/null +++ b/python/problems/re/en.py @@ -0,0 +1,2 @@ +name = 'Regular expressions' +description = 'Regular expressions exercises' diff --git a/python/problems/re/intnum/common.py b/python/problems/re/intnum/common.py new file mode 100644 index 0000000..8e8a92e --- /dev/null +++ b/python/problems/re/intnum/common.py @@ -0,0 +1,74 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20903 +number = 3 +visible = True + +solution = '''\ +def num(s): + res = re.search('-?[0-9]+', s) + if not res: + return None + return int(res.group(0)) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'num' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('abc', None), + ('1', 1), + ('111', 111), + ('12 1', 12), + ('5-112', 5), + ('m-221', -221), + ('Rač. 356', 356), + ('Ulica št. 15a', 15), + ('Višina 180, teža 76', 180), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/intnum/en.py b/python/problems/re/intnum/en.py new file mode 100644 index 0000000..33e0bd1 --- /dev/null +++ b/python/problems/re/intnum/en.py @@ -0,0 +1,13 @@ +id = 20903 +name = 'Signed integer' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/intnum/sl.py b/python/problems/re/intnum/sl.py new file mode 100644 index 0000000..8e4d8a6 --- /dev/null +++ b/python/problems/re/intnum/sl.py @@ -0,0 +1,27 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20903 +name = 'Predznačeno celo število' + +description = '''\ +

+Napišite funkcijo num(s), ki vrne prvo celo predznačeno število +v nizu. Število naj bo tipa int. Če števila v nizu ni, naj funkcija vrne +None.

+
+>>> num('Večna pot 113')
+113
+>>> num('a-20=22')
+-20
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/num/common.py b/python/problems/re/num/common.py new file mode 100644 index 0000000..4c2f0bf --- /dev/null +++ b/python/problems/re/num/common.py @@ -0,0 +1,75 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20904 +number = 4 +visible = True + +solution = '''\ +def num(s): + res = re.search(r'-?((\d*\.\d+)|(\d+\.?))([Ee][+-]\d*)?', s) + if not res: + return None + return int(res.group(0)) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'num' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('abc', None), + ('1', 1.0), + ('1.1', 1.1), + ('111e+2', 111e+2), + ('12-1', 12.0), + ('5.123-112', 5.123), + ('m-221.0', -221.0), + ('Rač. +356', 356.0), + ('Ulica št. 15a', 15), + ('Višina 180.42, teža 76.5', 180.42), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/num/en.py b/python/problems/re/num/en.py new file mode 100644 index 0000000..0feb5ff --- /dev/null +++ b/python/problems/re/num/en.py @@ -0,0 +1,13 @@ +id = 20904 +name = 'Signed any number (integer, float)' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/num/sl.py b/python/problems/re/num/sl.py new file mode 100644 index 0000000..cf96b5a --- /dev/null +++ b/python/problems/re/num/sl.py @@ -0,0 +1,29 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20904 +name = 'Predznačeno poljubno število' + +description = '''\ +

+Napišite funkcijo num(s), ki vrne prvo poljubno predznačeno število +(lahko ima tudi decimalko). Število naj bo tipa float. Če števila v nizu ni, +naj funkcija vrne None.

+
+>>> num('Večna pot 113')
+113
+>>> num('a-20.5=21.5')
+-20.5
+>>> num('Pregledali smo 10e+5 elementov.')
+10e+5
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/ones/common.py b/python/problems/re/ones/common.py new file mode 100644 index 0000000..851a53f --- /dev/null +++ b/python/problems/re/ones/common.py @@ -0,0 +1,69 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20901 +number = 1 +visible = True + +solution = '''\ +def ones(s): + return re.findall(r'1+', s) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'ones' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('', []), + ('111', ['111']), + ('121', ['1','1']), + ('112', ['11']), + ('221', ['1']), + ('222', []), + ('12211222111', ['1','11','111']), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/ones/en.py b/python/problems/re/ones/en.py new file mode 100644 index 0000000..615e777 --- /dev/null +++ b/python/problems/re/ones/en.py @@ -0,0 +1,13 @@ +id = 20901 +name = 'Repeated 1s' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/ones/sl.py b/python/problems/re/ones/sl.py new file mode 100644 index 0000000..91f6ec0 --- /dev/null +++ b/python/problems/re/ones/sl.py @@ -0,0 +1,26 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20901 +name = 'Ponovitve znaka' + +description = '''\ +

+Napišite funkcijo ones(s), ki vrne seznam vseh podnizov, ki +vsebujejo eno ali več ponovitev znaka 1.

+
+>>> ones('12211222111')
+['1', '11', '111']
+>>> ones('')
+[]
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/ones3/common.py b/python/problems/re/ones3/common.py new file mode 100644 index 0000000..4b151e8 --- /dev/null +++ b/python/problems/re/ones3/common.py @@ -0,0 +1,70 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20902 +number = 2 +visible = True + +solution = '''\ +def ones(s): + return re.findall(r'1{3,}', s) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'ones' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('', []), + ('111', ['111']), + ('121', []), + ('112', []), + ('221', []), + ('222', []), + ('12211222111', ['111']), + ('211111112211222111', ['1111111', '111']), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/ones3/en.py b/python/problems/re/ones3/en.py new file mode 100644 index 0000000..74c9dd5 --- /dev/null +++ b/python/problems/re/ones3/en.py @@ -0,0 +1,13 @@ +id = 20902 +name = 'Three times repeated 1s' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/ones3/sl.py b/python/problems/re/ones3/sl.py new file mode 100644 index 0000000..1d571c6 --- /dev/null +++ b/python/problems/re/ones3/sl.py @@ -0,0 +1,24 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20902 +name = 'Ponovitve znaka 3x' + +description = '''\ +

+Napišite funkcijo ones(s), ki vrne seznam vseh podnizov, ki +vsebujejo tri ali več ponovitev znaka 1.

+
+>>> ones('12211222111')
+['111']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/parentheses/common.py b/python/problems/re/parentheses/common.py new file mode 100644 index 0000000..7144bd8 --- /dev/null +++ b/python/problems/re/parentheses/common.py @@ -0,0 +1,69 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20906 +number = 6 +visible = True + +solution = '''\ +import re + +def parentheses(s): + return re.findall(r'\([^)]+\)', s) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'parentheses' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('(a a) bb (cc)', ['(a a)', '(cc)']), + ('a a b b c c', []), + ('', []), + ('To niso oklepaji (to so), (ta je pa pokvarjen', ['(to so)']), + ('()())(()', ['()', '()', '(()']), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/parentheses/en.py b/python/problems/re/parentheses/en.py new file mode 100644 index 0000000..035938e --- /dev/null +++ b/python/problems/re/parentheses/en.py @@ -0,0 +1,13 @@ +id = 20906 +name = 'Parentheses' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/parentheses/sl.py b/python/problems/re/parentheses/sl.py new file mode 100644 index 0000000..bdd6034 --- /dev/null +++ b/python/problems/re/parentheses/sl.py @@ -0,0 +1,24 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20906 +name = 'Oklepaji' + +description = '''\ +

+Napišite funkcijo parantheses(s), ki vrne vse nize, ki se pojavijo +v oklepajih.

+
+>>> parentheses('(a a) bb (cc)')
+['(a a)', '(cc)']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/re/re_sl.html b/python/problems/re/re_sl.html new file mode 100644 index 0000000..4432336 --- /dev/null +++ b/python/problems/re/re_sl.html @@ -0,0 +1,371 @@ + + + + + + + + + + +

Regularni izrazi

+ +

Ena najbolj uporabnih stvari v skriptnih jezikih so "regularni izrazi". Če jih boste znali, boste glavni frajerji in boste lahko delali odlične reči. Po drugi strani pa niso prav nič zapleteni, čisto enostavno se jih je naučiti ... in, no, priznam, kar zoprno sestavljati. Ko sestavljamo kaj bolj zapletenega, se tudi stari mački nekoliko zafrkavamo, preden jih spravimo v delujoče stanje.

+ +

Regularni izraz

+ +

Če bi hoteli teoretizirati, bi rekli, da opisujejo jezik, pri čemer z "jezikom" mislimo nekakšno množico nizov. So tudi v tesnem sorodu s končnimi avtomati, ki vam morda niso več neznani, če kaj sledite Uvodu v računalništvo.) A pustimo teorijo in uvode. Naučili se bomo pisati nize, s katerimi opišemo nekakšne vzorce. Recimo, da imamo na voljo naslednje oznake, ki jih lahko tlačimo v nize: +

+
.
katerikoli znak
+
\w
katerakoli črka ali števka
+
\W
katerikoli znak, ki ni črka ali števka
+
\d
katerakoli števka
+
\D
katerakoli znak, ki ni števka
+
\s
beli prostor (presledek, tabulator, nova vrstica...)
+
\S
karkoli, kar ni beli prostor
+
^
začetek niza
+
$
konec niza
< +
\
vzvratno poševnico uporabimo, ko bi radi v vzorec vpisali, recimo, piko. Znak . ima namreč poseben pomen (glej zgoraj), zato takrat, kadar v resnici želimo piko, napišemo \.. Enako velja za zvezdico, vprašaj, plus... in tudi vzvratno poševnico.
+
oglati oklepaji
mednje napišemo seznam znakov in opisujejo katerikoli znak s tega seznama; če je prvi znak ^, pa to pomeni katerikoli znak, ki ni na tem seznamu. Znotraj oglatih oklepajev je pika samo pika in celo vzvratna poševnica samo vzvratna poševnica.
+
+Poglejmo nekaj preprostih primerov vzorcev +
+
l.pa
Ta izraz opisuje "l", ki mu sledi karkoli in nato "pa". To je lahko "lipa", "lepa" ali "lopa", pa tudi "lrpa", "lmpa", "lgpa". In celo "l3pa", "l/pa" in "l pa". Vzorcu pa ne ustrezata, recimo, "sipa", saj se ne začne z "l" ali "lotupa", saj ima med "l" in "pa" več kot eno samo črko.
+
l.p.
Tole pa je lahko tudi "lipi" ali "lopi" ali "lspt" ali "l1p4" ali "l-p)"... Torej vse besede s štirimi znaki, pri čemer mora biti prvi znak "l", tretji pa "p".
+
l\wp\w
Ta vzorec je podoben prejšnjemu, le da zahteva, da sta drugi in četrti znak črki ali številki. "lipa" in "l1p4" sta še vedno spremenljivi, "l-p)" pa ne več.
+
lip[aieo]
Tole pa je lahko "lipa", "lipi", "lipe" ali "lipo". Ne pa "lipu" ali "lipm".
+
lip[^u t]
Ta vzorec opisuje "lip", ki mu sledi katerikoli znak, razen u-ja, presledka ali t-ja.
+
s[tpr]anje
"stanje", "spanje" in nekatere druge reči.
+
+Zdaj pa še par posebnih znakov. +
+
okrogli oklepaji
Z okroglimi oklepaji označimo skupino
+
*
Z zvezdico označimo, da se sme prejšnji znak ali prejšnja skupina (ki smo jo zaprli v okrogle oklepaje) poljubnokrat ponoviti - lahko tudi ničkrat.
+
+
Plus pomeni isto kot zvezdica, le da zahteva, da se prejšnja skupina ali znak pojavi vsaj enkrat.
+
?
Z vprašajem povemo, naj se prejšnja skupina pojavi enkrat ali nobenkrat.
+
+Spet si oglejmo nekaj primerov. +
+
Go*l!
Ta vzorec opisuje nize, kot so "Gol!", "Gooooooool!" in "Goooooooooooooooool!". Žal pa tudi "Gl!". :)
+
Go+l!
Popravljena verzija gornjega: zahteva, da se "o" pojavi vsaj enkrat.
+
Go+l?!
Tole pa je podobno kot zgoraj, le da se črka l lahko pojavi ali pa tudi ne. To je torej lahko karkoli od tega, kar smo našteli zgoraj, poleg tega pa tudi "Go!" ali "Gooooooooooo!"
+
+Pa še par bolj zapletenih. +
+
(brm)+
Opisuje motor, ki dela "brmbrmbrmbrmbrmbrm" ali "brmbrmbrmbrmbrmbrmbrmbrm" ali vsaj "brm".
+
ra(ta)*
Opisuje mitraljez (ki je lahko tudi pokvarjen in reče samo "ra" in razpade)
+
tr([aeiou]l)*[aeiou]
Opisuje prepevanje, ko ne poznamo besedila ("tralalelalalalilolololu")
+
jodl(dodl)*dii
Jodlanje (in jodldodlanje in jodldodldodldodldodlanje).
+
jodl(dodl)?dii
Tole pa je samo jodlanje in jodldodlanje, ne pa tudi jodldodldodldodldodlanje.
+
+Pri plusu, zvezdici in vprašaju nas včasih zmoti, da požrejo preveč. Če hočemo, da požrejo čim manj, jim dodamo vprašaj. +
+
*?, +?, ??
Če k zvezdici, plusu ali vprašaju dodamo še en vprašaj, zahtevamo, naj ta zvezdica, plus ali vprašaj "požre" čim manj znakov. Tole je na prvi pogled zelo praktično; v resnici bo začetnik, ko odkrije te vprašaje, naredil veliko naivnih napak, zato se jim, vsaj v začetku, raje izognite in poskusite to, kar želite povedati, povedati brez njih.
+
+Vzemimo stavek "Ta nas Janez je en dolgocasnez, prav res". Če poskusimo v tem stavku poiskati podniz, ki ustreza vzorcu "J.*nez", bomo izvedeli, da "Janez je en dolgocasnez", kar ni ne lepo ne prav in nikakor ni tisto, kar smo hoteli. Težava je v tem, da je zvezdica požrla "nez je en dolgocas"; izraz namreč pravi, da hočemo "Ja", potem (karseda veliko) drugih črk in potem "nez". Če pa poiščemo "J.*?nez", bomo dobili samo "Janez", saj bo ".*" požrlo le toliko znakov, kolikor jih potrebujemo, da je iskanje uspešno, torej, v tem primeru, le črko "a".

+ +

Funkcije za uporabo regularnih izrazov

+ +

Naučili smo se opisovati vzorce. Kaj pa lahko s temi opisi počnemo?

+ +

Regularni izrazi, ki smo jih spoznali, so bolj ali manj enaki v vseh jezikih. Jeziki, ki imajo veliko opraviti z iskanjem po besedilih, na primer php in javascript, imajo regularne izraze tesno vdelane v jezik - tako kot ima Python vdelana števila in nize (za nize nimamo "posebnega modula", ki bi ga morali uvoziti, preden lahko delamo z njimi), imajo ti jeziki vdelane tudi regularne izraze. Ne da bi potrebovali poseben modul, lahko preverimo, ali ima določen niz določeno obliko, podano z regularnim izrazom. Python je splošnejši jezik, zato regularnih izrazov ne sili v ospredju, temveč so lepo v posebnem modulu. Imenuje se re, kar je okrajšava za regular expression.

+ +

Za primer uporabimo rdečo nit predavanj izpred nekaj let: v besedilu iščemo imena potencialnih teroristov, pri čemer so nam sumljive kar vse besede, ki se začnejo z veliko črko. Besedilo nekega prestreženega elektronskega sporočila je bilo takšno: +

msg = """Dragi Ahmed,
+
+kako si kaj? Upam, da so otroci ze zdravi.
+
+Mustafa, Osama in jaz smo se sli danes malo razgledat in
+kaze kar dobro. Abdulah pa ni mogel zraven, je sel v Pesavar
+prodat se tri kamele. Osama sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je Abdulah. Harun in
+on, nic jima ne dopoves, se Osama ne. Jibril me klice,
+moram iti; oglasi se kaj na Skype!
+
+tvoj Husein
+
+"""
+ +

Vzorec, ki bo predstavljal ime - nekaj, kar se začne z veliko črko in nadaljuje s vsaj eno črko, je [A-Z]\w+.

+ +

Najpreprostejša za uporabo (a ne tudi najbolj uporabna) funkcija, na kateri lahko poženemo ta izraz, je findall, ki, kot bi bili ob imenu nemara presenečeni (posebej, če ne bi znali angleško) poišče vse (neprekrivajoče se) podnize, ki jim ustreza izraz. Če imamo sporočilo shranjeno v nizu msg, bomo seznam imen dobili z +

>>> re.findall(r"[A-Z]\w+", msg)
+['Dragi', 'Ahmed', 'Upam', 'Mustafa', 'Osama', 'Abdulah', 'Pesavar', 'Osama', 'Abdulah', 'Harun', 'Osama', 'Jibril', 'Skype', 'Husein', 'PS', 'Python']

+ +

Opazka: pred narekovaj sem dodal r. Iz davnega začetka semestra se morda spomnite, kakšne posledice ima to: vse vzvratne poševnice (po domače: backslashi) po tem pomenijo le vzvratne poševnice, ne ubežnih zaporedij (torej, \n pomeni vzvratno poševnico in n, ne pa prehoda v novo vrsto). V regularnih izrazih se bo vedno trlo vzvrtanih poševnic, medtem ko bodo nove vrste in tabulatorji strašno redki, zato bomo skoraj vedno uporabljali nize z r-jem pred narekovaji.

+ +

Metoda findall je najpreprostejša, ker vrne kar (pod)nize, ki ustrezajo vzorcu. Druge funkcije vračajo objekt, iz katerega lahko razberemo še kaj več. Vzemimo search, ki poišče prvo pojavitev vzorca.

+ +
>>> mo_ime = re.search(r"[A-Z]\w+", msg)
+>>> mo_ime
+<_sre.SRE_Match object at 0x045812F8>
+ +

mo_ime ni niz, tako kot prej, temveč objekt, ki vsebuje podatke o podnizu, ki se ujema z izrazom. (Ker gre za "Match object", zato sem mu pripel mo_. To spet spominja na madžarsko notacijo, ki sem jo omenil pri Qtju in tudi tu izvira iz (mojih) izkušenj: če imaš spremenljivko, ki predstavlja objekt, ki se nanaša na najdeno ime, boš imel najbrž tudi spremenljivko, ki bo vsebovala niz z najdenim imenom in imeli bosta tendenco, da se bosta enaki. Če prvemu vedno pripnemo mo_, je problem rešen.

) + +
>>> mo_ime.group()
+'Dragi'
+>>> mo_ime.start()
+0
+>>> mo_ime.end()
+5
+>>> mo_ime.span()
+(0, 5)
+ +

Tule start pove indeks črke v nizu, kjer se ujemanje začne in end indeks črke za ujetim podnizom; span pove oboje hkrati. Najdeni niz se torej nahaja v msg[0:5]. Razlog, da se metoda, ki vrne celotni podniz, imenuje group(), pa bo postal jasen malo kasneje, ko se bomo pogovarjali o skupinah.

+ +

Če želimo poiskati vse pojavitve vzorca in jih obdelati v zanki, bomo uporabili finditer, kot recimo tule: +

for s in re.finditer(r"[A-Z]\w+", msg):
+    print(s.group())

+ +

Metoda sub je podobna metodi replace, ki smo jo spoznali pri nizih: z njo lahko zamenjamo vse pojavitve danega vzorca s čim drugim.

+ +
>>> print(re.sub(r"[A-Z]\w+", "XXX", msg))
+XXX XXX,
+
+kako si kaj? XXX, da so otroci ze zdravi.
+
+XXX, XXX in jaz smo se sli danes malo razgledat in
+kaze kar dobro. XXX pa ni mogel zraven, je sel v XXX
+prodat se tri kamele. XXX sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je XXX. XXX in
+on, nic jima ne dopoves, se XXX ne. XXX me klice,
+moram iti; oglasi se kaj na XXX!
+
+tvoj XXX
+
+ +

V zvezi s sub lahko opazimo, da so argumenti funkcije obrnjeni nekoliko drugače kot pri replace: replace je metoda razreda str, torej je niz, katerega podnize želimo spreminjati že implicitno podan (kot self), povedati je potrebno le, kakšen podniz zamenjamo s katerim. Za primer: na nekaterih operacijskih sistemih so presledki v imenih datotek precej tečna reč. Kako bi se jih znebili? Če bi poznali le nize, bi rekli + +

fname = fname.replace(" ", "_")
+ +Metodi sub pa kot argument povemo vzorec, niz, po katerem naj išče in s čim naj zamenjuje. Če bi želeli gornjo zamenjavo opraviti z regularnimi izrazi, bi napisali: +
fname = re.sub(" ", "_", fname)
+

+ +

Regularni izrazi so za tako preprosto zamenjavo prevelik kanon. sub namreč zmore še veliko več; namesto niza, s katerim naj zamenja ujemajoči se podniz, ji lahko podamo kar funkcijo, ki naj jo pokliče ob vsakem ujemanju: funkcija bo kot argument dobila Match object, kot rezultat mora vrniti niz, ki naj zamenja ujemajoči se podniz. Podniz lahko zamenjamo z, recimo, enakim podnizom, vendar zapisanim z velikimi črkami.

+ +
>>> def velike_crke(mo):
+... 	return mo.group().upper()
+... 
+>>> print re.sub(r"[A-Z]\w+", velike_crke, msg)
+DRAGI AHMED,
+
+kako si kaj? UPAM, da so otroci ze zdravi.
+
+MUSTAFA, OSAMA in jaz smo se sli danes malo razgledat in
+kaze kar dobro. ABDULAH pa ni mogel zraven, je sel v PESAVAR
+prodat se tri kamele. OSAMA sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je ABDULAH. HARUN in
+on, nic jima ne dopoves, se OSAMA ne. JIBRIL me klice,
+moram iti; oglasi se kaj na SKYPE!
+
+tvoj HUSEIN
+
+
> + +

Da ne definiramo brez potrebe takšnih kratkih funkcij, si lahko pomagamo z lambda-funkcijami. O njih se pri Programiranju 1 nismo pogovarjali; primeren trenutek je bil kvečjemu prejšnji teden, saj je njihovo naravno mesto funkcijsko programiranje. Tule jih bomo samo uporabili, v izziv radovednim: +

print(re_ime.sub(lambda mo: mo.group().upper(), msg))
+Za primer obrnimo vsa imena po arabsko, z desne na levo: + +
>>> print(re.sub(r"[A-Z]\w+", lambda mo: "".join(reversed(mo.group())), msg))
+...
+igarD demhA,
+
+kako si kaj? mapU, da so otroci ze zdravi.
+
+afatsuM, amasO in jaz smo se sli danes malo razgledat in
+kaze kar dobro. haludbA pa ni mogel zraven, je sel v ravaseP
+prodat se tri kamele. amasO sicer pravi, da se mu to pred
+zimo ne splaca, ampak saj ves, kaksen je haludbA. nuraH in
+on, nic jima ne dopoves, se amasO ne. lirbiJ me klice,
+moram iti; oglasi se kaj na epykS!
+
+tvoj niesuH
+

+ +

Še ena (in zadnja, za danes) zanimiva funkcija, ki jo nudijo regularni izrazi, je split. Tej smo doslej podajali točen podniz, po katerem naj deli. Tako bo tudi poslej, modul za regularne izraze pa ima še eno, drugo funkcijo split, ki ji povemo vzorec, po katerem naj deli. Lahko, recimo, rečemo, naj sporočilo razdeli ob vsakem imenu (kar ni posebej uporaben zgled, je pa preprost).

+ +
+>>> re.split(r"[A-Z]\w+", msg)

+['', ' ', ',\n\nkako si kaj? ', ', da so otroci ze zdravi.\n\n', ', ', 
+' in jaz smo se sli danes malo razgledat in\nkaze kar dobro. ', 
+' pa ni mogel zraven, je sel v ', '\nprodat se tri kamele. ', 
+' sicer pravi, da se mu to pred\nzimo ne splaca, ampak saj ves, kaksen je ', 
+'. ', ' in\non, nic jima ne dopoves, se ', ' ne. ', 
+' me klice,\nmoram iti; oglasi se kaj na ', '!\n\ntvoj ', '\n\n']
+
+ +

V zvezi z Match objecti so nam ostale še skupine. Kaj so in kaj počnemo z njimi, pa bomo videli na primerih.

+ +

Prevedeni regularni izrazi

+ +

V davnih časih smo se pri predmetih, kot je Uvod v računalništvo, učili Moorevoih in Mealyjevih avtomatov. Danes so menda iz mode, zato bo moral ta, ki ga zanima, kako delujejo regularni izrazi, najbrž počakati do Prevajalnikov in navideznih strojev, ki si jih lahko izbere v tretjem letniku. Za zdaj vam lahko povem le, da se izraz, preden lahko računalnik v resnici naredi karkoli z njim, prevede v nekaj, čemur se reče končni avtomat, ta pa je neke vrste usmerjen graf. (Tako da boste vsaj vedeli, čemu služi to, kar počnete pri Diskretnih strukturah.)

+ +

Za razumevanje tega, kar je pomembno tu, je bistveno le: regularni izraz se mora v nekaj prevesti. Če napišete program, ki vsebuje nekaj takšnega: +

for i in range(10000):
+    re.findall(r"[A-Z]\w+", msg[i])
+	# in potem še kaj naprej
+bo moral nesrečni računalnik deset tisočkrat prevesti regularni izraz [A-Z]\w+ v tisto, v kar ga pač prevaja. Pri tako kratkem in preprostem izrazu še gre, pri čem bolj zapletenem pa bi program tekel bistveno hitreje, če bi ga lahko prevedli enkrat za vselej. In res ga lahko.

+ +

re_ime = re.compile(r"[A-Z]\w+")
+for i in range(10000):
+    re_ime.findall(msg[i])
+	# in potem še kaj naprej
+Spremenljivka re_ime (spet madžarska notacija!) zdaj predstavlja prevedeni izraz. Objekt re_ime ima vse funkcije, ki smo jih poznali prej, le da gre zdaj pač za metode objekta in ne funkcije modula: namesto re.findall, re.finditer, re.sub, re.split, zdaj pišemo re_ime.findall, re_ime.finditer, re_ime.sub, re_ime.split. Poleg tega pa še izpustimo prvi argument, vzorec, saj je izraz že pripravljen.

+ +

Sam vedno eksplicitno pokličem prevajanje izraza, preden ga uporabim; tako sem se navadil in škoditi ne more. Tule pa bomo počeli, kakor bo naneslo.

+ +

Primeri

+ +

Primer: teroristi

+ +

Rešimo, za začetek, kar staro nalogo, ki je zahtevala, da izpišemo, kolikokrat se v sporočilu pojavi posamezno ime.

+ +
import re
+
+imena = {}
+for ime in re.findall(r"[A-Z]\w+", msg):
+    imena.setdefault(ime, 0)
+    imena[ime] += 1
+
+for ime, stevec in imena.items():
+    print("{} {}".format(ime, stevec))
+ +

Gre pa, jasno, tudi hitreje: modul collections ima razred Counter, ki prešteje število ponovitev v poslanem seznamu, slovarju, množici... Takole: + +

>>> collections.Counter(re.findall(r"[A-Z]\w+", msg))
+Counter({'Osama': 3, 'Abdulah': 2, 'PS': 1, 'Ahmed': 1, 'Mustafa': 1, 'Python': 1,
+'Pesavar': 1, 'Upam': 1, 'Dragi': 1, 'Harun': 1, 'Husein': 1, 'Skype': 1,
+'Jibril': 1})
+ +

To naš program precej poenostavi, saj nas odreši glavnega opravila, štetja.

+ + +
import re, collections
+for ime, stevec in collections.Counter(re.findall(r"[A-Z]\w+", msg)).items():
+    print("{} {}".format(ime, stevec))
+ + +

Primer: branje vseh slik z določene strani

+ +

Tisti, ki vsaj malo poznate HTML, veste, da so slike na spletnih straneh praviloma postavljene tako, da HTML vsebuje značko IMG, ki videti nekako tako: +

<img src="ime_slike.gif"/> +Z malo potencialnimi komplikacijami, seveda. Oklepaju sicer vedno sledi najprej img, a poleg src lahko naletimo še na kaj drugega. Lepo vzgojen HTML ima poleg src vsaj še alt, slabo vzgojen pa tudi onclick ali kaj hujšega. Poleg tega so lahko kjerkoli, razen sredi besed, tudi presledki.

+ +

Kar iščemo, lahko z besedami opišemo kot oklepaj (namreč tale: <), ki mu lahko sledi kaj praznega prostora, nato pa img. Potem sme biti čisto karkoli razen zaklepaja, > in nekoč mora priti na vrsto src, pred njim pa mora biti kak znak, ki ni črka (če bi, recimo, pisalo mesrc, to ni OK, če je pred src presledek, tabulator, nova vrsta ali, zaradi mene tudi narekovaj ali vejica (čeprav to ni povsem po predpisih) pa je OK. Besedi src mora slediti enačaj, pred in za njim sme biti bel prostor. Nato pa narekovaj, za katerim pride tisto, kar nas v resnici zanima: URL slike. Ta je sestavljen iz poljubnih znakov razen narekovajev... in na koncu pride še narekovaj.

+ +

Z regularnim izrazom taisto povemo tako: +

<\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"
+Se pravi + + + + + + + + + + + + + +
<oklepaj, <
\s*poljubno praznega prostora (lahko tudi nič)
imgbeseda img
[^>]*poljubno dolga poljubna šara, razen zaključnega oklepaja
\Wkarkoli, kar ni črka
srcbeseda src
\s*poljubno praznega prostora (lahko tudi nič)
=enačaj
\s*poljubno praznega prostora (lahko tudi nič)
"narekovaj
([^"]*)poljubne reči razen narekovaja; čemu oklepaji, bomo še videli
"narekovaj
+ +Ko smo rekli poljubno dolga poljubna šara, razen zaključnega zaklepaja: kdo nam jamči, da ta "poljubna šara" ne bo požrla tudi srcja in URLja? To nam jamči sam regularni izraz! Če bi [^>]* požrl src, potem se regularni izraz ne bi mogel ujemati s sicer pravilno vstavljeno sliko. Regularni izraz (oziroma knjižnica, ki ga poganja) pa vedno naredi vse, da bi se izraz ujemal, torej tudi ukroti požrešne dele.

+ +

Podobno, a ravno obratno vprašanje je, kdo zagotavlja, da bo ([^"]*), to so, poljubne reči razen narekovaja, res požrle ves URL in ne odnehale, tako, za hec, po treh znakih? Tako kot prej, nam tudi to zagotavlja preostanek izraza. V opisu regularnega izraza delu ([^"]*) namreč sledi "; če ([^"]*) ne požre vsega do narekovaja, se tisto, kar sledi, ne bo ujemalo z narekovajem, kot zahteva izraz.

+ +

Je kdo opazil, da nikjer ne lovimo zaključnega zaklepaja, >. Res je, ne omenjamo ga. Z razlogom. Vseeno nam je zanj. Ko ulovimo URL, nam je za vse, kar se dogaja naprej, vseeno. Da bo še jasneje, pripnimo h gornji tabeli še en preprost in en zapleten podniz, ki se ujame v izraz. Najprej<img src="ime_slike.gif"/>

+ + + + + + + + + + + + + + +
<<
\s*
imgimg
[^>]*
\W(presledek med img in src)
srcsrc
\s*
==
\s*
""
([^"]*)ime_slike.gif
""
+ +

Pa še bolj zapleten primer: kako regularni izraz zgrabi < img alt="Tvoj brskalnik ne kaže slik" onclick="http://www.fri.uni-lj.si" src= "x.gif" class="psl" >

+ + + + + + + + + + + + + + +
<<
\s*(presledka pred img)
imgimg
[^>]* alt="Tvoj brskalnik ne kaže slik" onclick="http://www.fri.uni-lj.si" (pred src so trije presledki; "šara" pograbi prva dva)
\W(tretji presledek pred src)
srcsrc
\s*
==
\s*(presledek)
""
([^"]*)x.gif
""
+ +

Zdaj pa uporabimo izraz v funkciji download_images, ki bo kot argument sprejela URL strani in ciljni direktorij. Prebrala bo s stran, nato pa z nje snela vse slike in jih shranila v ciljni direktorij.

+ +
import re
+import urllib.request
+import os
+
+re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"', re.DOTALL + re.IGNORECASE)
+
+def download_images(url, target_dir):
+    if not os.path.exists(target_dir):
+        os.mkdir(target_dir)
+    elif not os.path.isdir(target_dir):
+        raise IOError("'%s' is not a directory" % target_dir)
+
+    page = urllib.request.urlopen(url).read().decode("utf-8")
+    for mo in re_img.finditer(page):
+        img_url = mo.group(1)
+        img = urllib.request.urlopen(img_url).read()
+        img_name = os.path.split(img_url)[1]
+        target_name = os.path.join(target_dir, img_name)
+        open(target_name, "wb").write(img)
+ + +

Regularni izraz smo tokrat enkrat za vselej prevedli pred funkcijo in ga shranili v re_img. Dodali smo še en argument, zastavice, s katerimi povemo, naj vzorec . požira tudi znake za novo vrstico, \n (re.DOTALL) in da nam je vseeno za male in velike črke (re.IGNORECASE), tako da se bo, denimo, img ujemal tudi z IMG, Img in iMg... + +

Funkcija nato preveri ali ciljni direktorij obstaja; če ga ni, ga naredi, če je, pa preveri, ali je v resnici direktorij in v nasprotnem primeru - kot znamo od prejšnjič - sproži izjemo.

+ +

Sledi pravo delo: poberemo podano stran. Kar dobimo z read, ni niz (str) temveč bajti (bytes). Ker regularni izrazi brskajo le po nizih, pretvorimo bajte v niz. Če bi hoteli narediti, kot se šika, bi ugotovili, kako je stran v resnici kodirana, tule pa bomo predpostavili, da gre za utf-8 in poklicali decode("utf-8") + +Potem poiščemo vse pojavitve značke img. Zdaj pride, kar sem zamolčal: group. Ko smo v prejšnjih primerih želeli iz match objecta dobiti podniz, ki se je prilegal regularnemu izrazu, smo poklicali group(). Zdaj bi želeli priti do podniza, ki se prilega URLju slike, torej tistemu med narekovaji za srcem. Zato smo ta del zaprli v oklepaje in s tem naredili novo skupino. Do njene vsebine pridemo z group(1). Čemu 1? Zato pač, ker gre za prvo skupino. Če bi jih imeli več, bi jih lepo prešteli in povedali, ali želimo vsebino tretje ali šeste.

+ +

"Lepo prešteli"? Tole štetje ni prav nič lepo in prikladno. Regularni izrazi so zapleteni in kaj lahko se uštejemo. Še huje: ko izraz spremenimo, bomo morda dodali novo skupino in vse bo treba preštevilčiti. Zato je skupine bolj praktično poimenovati. Namesto +

re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"([^"]*)"', re.DOTALL + re.IGNORECASE)
+napišemo +
re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"(?P[^"]*)"', re.DOTALL + re.IGNORECASE)
+in skupina je dobila ime, url. Do vsebine te skupine potem pridemo z mo.group("url").

+ +

Sliko poberemo v niz z urllib.request.urlopen. Zdaj pa jo je potrebno še shraniti. URL slike bo, recimo, takšen: http://i1.nyt.com/images/2011/01/01/arts/design/01moth_costa/01moth_costa-moth.jpg in takšno sliko želimo shraniti pod imenom 01moth_costa-moth.jpg. Da pridemo do njega, lahko za prvi približek posilimo kar funkcijo os.path.split(p), ki kot argument (običajno) prejme datoteko skupaj s potjo do nje, na primer, c:\Users\Janez\Desktop\desktop.ini, kot rezultat pa vrne terko s potjo in datoteko, na primer ("c:\Users\Janez\Desktop", "desktop.ini"). URL je dovolj podobna reč, da ga bo os.path.split pravilno razcepil.

+ +

Funkcija deluje, lahko jo preskusimo. Ker vaje ni nikoli preveč, pa poskusimo spremeniti izraz tako, da se izognemo klicu os.path.join. Pot vodi prek razmisleka, da je URL sestavljen iz dveh delov; prvi del je pot, drugi ime datoteke in slednji ne vsebuje poševnic, /. (Tole je le zmerno res: pri, denimo, slikah, ki se generirajo sproti, URL navadno ne bo vseboval imena datoteke. Ta detajl za zdaj pozabimo.) Ime, torej tisto med narekovaji, bi zato spremenili iz [^"]*, karkoli razen narekovaja, v [^"]*[^"/]*, to je, karkoli razen narekovaja, ki mu sledi karkoli razen narekovaja in poševnice. No, tole še ne bo povsem dobro, saj prvemu delu nič ne preprečuje, da ne bi kar vedno požrl celotnega imena in za drugi del ne bi ostalo nič. Prva rešitev, ki nam pride na misel, je [^"]*/[^"/]*, torej, karkoli razen narekovaja, ki mu sledi poševnica in potem karkoli razen narekovaja in poševnice. Tudi to ne bo povsem dobro, saj zdaj zahtevamo, da URL vsebuje poševnico in zdaj ne bomo več prepoznali povsem legalne slike <img src="ime_slike.gif"/>. Prava rešitev je, da prvemu delu pač zapovemo, naj požre čim manj, tako da zvezdici dodamo vprašaj, [^"]*?[^"/]*. Zdaj vse deluje, kot mora: prvi del lahko požira karkoli (vendar čim manj), drugi pa ne mara poševnic. Če obstaja (vsaj ena) poševnica, bo prvi del požrl vse do (zadnje) poševnice in tako omogočil drugemu, da se ujame (a požrl ne bo nič več, kot je nujno treba, saj požira čim manj). Če pa poševnice sploh ni, bo vse požrl drugi del, saj prvemu ni potrebno požreti ničesar.

+ +

In zdaj določimo in poimenujmo še skupine. Dve bosta in ena bo del druge. Najprej poskrbimo za ime datoteke, se pravi to, kar sledi poševnici: [^"]*?(?P[^"/]*). Vse skupaj pa zapremo še enkrat, saj celoten URL vsebuje tako prvi del kot tudi ime: (?P[^"]*?(?P[^"/]*)). Funkcija s takšnim regularnim izrazom je taka:

+ +
re_img = re.compile(r'<\s*img[^>]*\Wsrc\s*=\s*"(?P[^"]*?(?P[^"/]*))"', re.DOTALL+re.IGNORECASE)
+
+def download_images(url, target_dir):
+    if not os.path.exists(target_dir):
+        os.mkdir(target_dir)
+    elif not os.path.isdir(target_dir):
+        raise IOError("{}' is not a directory".format(target_dir))
+    page = urllib.request.urlopen(url).read().decode("utf-8")
+    for mo in re_img.finditer(page):
+        img_url, img_name = mo.group("url", "fname")
+        img = urllib.request.urlopen(img_url).read()
+        target_name = os.path.join(target_dir, img_name)
+        open(target_name, "wb").write(img)
+ + + diff --git a/python/problems/re/sl.py b/python/problems/re/sl.py new file mode 100644 index 0000000..e450d4c --- /dev/null +++ b/python/problems/re/sl.py @@ -0,0 +1,2 @@ +name = 'Regularni izrazi' +description = 'Vaje iz regularnih izrazov' diff --git a/python/problems/re/words/common.py b/python/problems/re/words/common.py new file mode 100644 index 0000000..79a94db --- /dev/null +++ b/python/problems/re/words/common.py @@ -0,0 +1,69 @@ +import re +from python.util import has_token_sequence, string_almost_equal, \ + string_contains_number, get_tokens, get_numbers, get_exception_desc, \ + all_tokens, has_comprehension, has_loop, almost_equal, get_ast +from server.hints import Hint + +id = 20905 +number = 5 +visible = True + +solution = '''\ +import re + +def words(s): + return re.findall(r'[a-zA-Z]+', s) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +def test(python, code, aux_code=''): + func_name = 'words' + tokens = get_tokens(code) + if not has_token_sequence(tokens, ['def', func_name]): + return False, [{'id' : 'no_func_name', 'args' : {'func_name' : func_name}}] + + in_out = [ + ('Vse besede brez locil', ['Vse', 'besede', 'brez', 'locil']), + ('Vse besede. Brez locil!!!', ['Vse', 'besede', 'Brez', 'locil']), + ('', []), + ('Ulica st. 15a', ['Ulica', 'st', 'a']), + ('Visina 180.42, teza 76.5', ['Visina', 'teza']), + ] + + test_in = [('{0}("{1}")'.format(func_name, str(l[0])), None) + for l in in_out] + test_out = [l[1] for l in in_out] + + answers = python(code=aux_code+code, inputs=test_in, timeout=1.0) + n_correct = 0 + tin, tout = None, None + for i, (ans, to) in enumerate(zip(answers, test_out)): + res = ans[0] + corr = res == to + n_correct += corr + if not corr: + tin = test_in[i][0] + tout = to + + passed = n_correct == len(test_in) + hints = [{'id': 'test_results', 'args': {'passed': n_correct, 'total': len(test_in)}}] + if tin: + hints.append({'id': 'problematic_test_case', 'args': {'testin': str(tin), 'testout': str(tout)}}) + if passed: + hints.append({'id': 'final_hint'}) + + return passed, hints + + +def hint(python, code, aux_code=''): + tokens = get_tokens(code) + + # run one test first to see if there are any exceptions + answer = python(code=aux_code+code, inputs=[(None, None)], timeout=1.0) + exc = get_exception_desc(answer[0][3]) + if exc: return exc + + return None diff --git a/python/problems/re/words/en.py b/python/problems/re/words/en.py new file mode 100644 index 0000000..3392baf --- /dev/null +++ b/python/problems/re/words/en.py @@ -0,0 +1,13 @@ +id = 20905 +name = 'Words' + +description = '''\ +

(translation missing)

''' + +hint = { + 'plan': '''\ +

(translation missing)

''', + + 'no_input_call': '''\ +

(translation missing)

''', +} diff --git a/python/problems/re/words/sl.py b/python/problems/re/words/sl.py new file mode 100644 index 0000000..ad5fe4c --- /dev/null +++ b/python/problems/re/words/sl.py @@ -0,0 +1,24 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20905 +name = 'Besede' + +description = '''\ +

+Napišite funkcijo words(s), ki vrne vse besede v nizu. Beseda +je sestavljena iz malih in velikih črk. Pazite, da ne vračate ločil. +

+>>> words('Vse besede. Brez locil!!!')
+['Vse', 'besede', 'Brez', 'locil']
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''], +} diff --git a/python/problems/recursion/recursion_sl.html b/python/problems/recursion/recursion_sl.html new file mode 100644 index 0000000..340055e --- /dev/null +++ b/python/problems/recursion/recursion_sl.html @@ -0,0 +1,407 @@ + + + + + + + + + + +

Rekurzija na primeru družinskega drevesa

+ +

Najstarejši član rodbine Novakovih, Adam, 111 let, ima štiri otroke: Matjaža, +Cilko, Danieka in Erika. Matjaž ima enega, namreč Viljema. Danijel ima +Elizabeto in Hansa (kasneje se je namreč preselil v predmestje Graza, kjer ima +manjše podjetje), Cilka in Erik pa nimata otrok. In tako naprej. Vse skupaj je +nabrano v spodnjem slovarju.

+
+otroci = {
+	"Adam":	["Matjaž", "Cilka", "Daniel", "Erik"],
+	"Aleksander": [],
+	"Alenka": [],
+	"Barbara": [],
+	"Cilka": [],
+	"Daniel": ["Elizabeta", "Hans"],
+	"Erik": [],
+	"Elizabeta": ["Ludvik", "Jurij", "Barbara", "Herman", "Mihael"],
+	"Franc": [],
+	"Herman": ["Margareta"],
+	"Hans": [],
+	"Jožef": ["Alenka", "Aleksander", "Petra"],
+	"Jurij": ["Franc", "Jožef"],
+	"Ludvik": [],
+	"Margareta": [],
+	"Matjaž": ["Viljem"],
+	"Mihael": [],
+	"Petra": [],
+	"Tadeja": [],
+	"Viljem": ["Tadeja"],
+}
+
+ +

Znane so tudi starosti vseh teh ljudi.

+
+starost = {
+	"Adam": 111, "Matjaž": 90, "Cilka": 88, "Daniel": 85, "Erik": 83,
+	"Viljem": 58, "Tadeja": 20, "Elizabeta": 68, "Hans": 64, "Ludvik": 50,
+	"Jurij": 49, "Barbara": 45, "Herman": 39, "Mihael": 32, "Franc": 30,
+	"Jožef": 29, "Margareta": 3, "Alenka": 9, "Aleksander": 5, "Petra": 7}
+
+ +

Napišimo, takole, za preprosto vajo, funkcijo, ki ji podamo osebo in pove, +koliko otrok ima.

+
+def stevilo_otrok(oseba):
+	return len(otroci[oseba])
+
+ +

Če pokličemo, recimo, `stevilo_otrok("Adam")`, dobimo 4.

+ +

Kako pa bi izvemo število vnukov posamezne osebe? Tako da gremo prek vseh + otrok in seštevamo število njihovih otrok, recimo z

+
+def stevilo_vnukov(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += len(otroci[otrok])
+	return v
+
+ +

ali, brez velike razlike,

+
+def stevilo_vnukov(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += stevilo_otrok(otrok)
+	return v
+
+ +

Uh, kaj kompliciramo, saj že znamo

+
+def stevilo_vnukov(oseba):
+	return sum(stevilo_otrok(otrok) for otrok in otroci[oseba])
+
+ +

Velikost rodbine

+ +

Do sem - nič posebnega. Zdaj pa pridejo zanimive reči: za nekoga nas zanima, +velika je njegova rodbina, skupaj z njim, njegovimi otroki, vnuki, pravnuki +in tako naprej. Recimo, da ima rojstni dan in bo povabil vso svojo rodbino +na večerjo. Koliko krožnikov za juho potrebuje.

+ +

Kaj mu je storiti? Vse svoje otroke, bo vprašal, kako velike so njihove +rodbine. To bo seštel in prištel še sebe. Kako bodo ti otroci izvedeli velikosti +svojih rodbin? Tako, da bodo vprašali vse svoje otroke po velikosti njihovih +rodbin, to sešteli in prišteli še sebe. Pa njihovi otroci? Enako.

+ +

Spremenimo to v funkcijo. Velikost rodbine dobimo tako, da gremo prek otrok +in seštevamo velikosti njihovih rodbin.

+
+def velikost_rodbine(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += velikost_rodbine(otrok)
+	return v + 1
+
+ +

Za tiste, ki so se dobro naučili prejšnjo snov:

+
+def velikost_rodbine(oseba):
+	return sum(velikost_rodbine(otrok) for otrok in otroci[oseba]) + 1
+
+ +

Poišči osebo

+ +

Potem nas je zanimalo, kako odkriti, ali je v rodbini določene osebe oseba +s takšnim in takšnim imenom. Storiti nam je tole: če je tako ime ravno vprašani +osebi, bo odgovorila True. Sicer bo enega za drugim spraševala +otroke, dokler prvi ne odgovori True; tedaj vrnemo +True. Če noben otrok nima takšnega potomca - in torej noben otrok +ne odgovori True, odgovorimo False. Z drugimi + besedami,

+
+def obstaja_ime(oseba, ime):
+	if oseba == ime:
+		return True
+	for otrok in otroci[oseba]:
+		if obstaja_ime(otrok, ime):
+			return True
+	return False
+
+ +

S snovjo izpred dveh tednov:

+
+def obstaja_ime(oseba, ime):
+	return oseba == ime or any(obstaja_ime(otrok, ime) for otrok in otroci[oseba])
+
+ +

Največja družina

+ +

Kako velika je največja družina v rodbini neke osebe - s temi mislimo le +otroke, brez staršev? Tu osebe razmišljajo tako: najprej predpostavijo, da je to +njihova družina - največ otrok je torej toliko otrok, kolikor jih imajo oni. +Potem vprašajo vsakega od otrok, kako velika je največja družina v njegovi +rodbini. Če naleti na koga z večjo družino, si to zapomni. Na koncu vrne največ, +kar je videl.

+
+def najvec_otrok(oseba):
+	najvec = len(otroci[oseba])
+	for otrok in otroci[oseba]:
+		koliko = najvec_otrok(otrok)
+		if  koliko > najvec:
+			najvec = koliko
+	return najvec
+
+ +

Kdor zna, zna takole:

+
+def najvec_otrok(oseba):
+	return max([len(otroci[oseba])] + [najvec_otrok(otrok) for otrok in otroci[oseba]])
+
+ + +

Študenti pogosto zagrešijo tole precej napačno rešitev:

+
+def najvec_otrok(oseba):
+	najvec = len(otroci[oseba])
+	for otrok in otroci[oseba]:
+		if najvec_otrok(otrok) > najvec:
+			najvec = najvec_otrok(otrok)
+	return najvec
+
+ +

Tu vsaka oseba večkrat vpraša svoje otroke, kako velike so največje družine. +Vsaj tistega z največjo družino vpraša dvakrat. Doslej smo takšno programiranje +tolerirali (in le občasno postokali, da to ni najlepše). Tu ga ne moremo več. +Vsak od teh, ki so bili po nepotrebnem vprašani dvakrat, spet dvakrat vpraša +svoje otroke vpraša po dvakrat, torej se v bistvu vprašajo po štirikrat. Oni +spodaj so vprašani že po osemkrat. Pri tako majhnih drevesih to ni tako hudo. +Pri velikih pa si tega ne bi mogli privoščiti.

+ + +

Najdaljše ime v rodbini

+ +

Katero je najdaljše ime v rodbini neke osebe? Tole je precej podobno +največjemu številu otrok: najdaljše je moje, razen če je daljše katero od imen +v rodbini katerega od otrok.

+
+def najdaljse_ime(oseba):
+	najdaljse = oseba
+	for otrok in otroci[oseba]:
+		naj_pod = najdaljse_ime(otrok)
+		if len(naj_pod) > len(najdaljse):
+			najdaljse = naj_pod
+	return najdaljse
+
+ +

Globina rodbine

+ +

Kako globoka je rodbina določene osebe? Torej, nekdo, ki nima otrok, ima +rodbino globinee 1. Če ima otroke, nima pa vnukov, ima rodbino globine +2. Če ima tudi kakega vnuka, vendar nobenega pravnuka, ima rodbino globine 3.

+ +

Globino rodbine izračunamo tako, da vprašamo vse otroke po globinah njihovih +rodbin in k največji globini, ki jo dobimo, prištejemo 1.

+
+def globina(oseba):
+	najvecja = 0
+	for otrok in otroci[oseba]:
+		g = globina(otrok)
+		if g > najvecja:
+			najvecja = g
+	return najvecja + 1
+
+ +

Ali, krajše

+
+def globina(oseba):
+	return max(globina(otrok) for otrok in otroci[oseba]) + 1
+
+ +

Velikost potomstva

+ +

Pripadnike Novakove rodbine smo nato spraševali, koliko potomstva imajo. S +potomci mislimo nekaj takšnega kot rodbino, a brez te osebe same. Jurij +(ki ima dva otroka in tri vnuke) ima pet potomcev).

+ +

Tale zahteva malo razmisleka. Navidez bi jo lahko ugnali tako, kot smo +velikost rodbine, le 1 ne smemo prišteti na koncu, saj oseba ne sme šteti +sebe.

+
+def velikost_rodbine(oseba):
+	v = 0
+	for otrok in otroci[oseba]:
+		v += velikost_rodbine(otrok)
+	return v
+
+ +

Zoprna reč je, da je ta funkcija nekoliko napačna. No, precej napačna. +Vedno vrne 0 - ker nihče nikoli ničesar ne prišteje, vse seštevajo samo ničle. +In iz ničel nikoli ne boš dobil ničesar, pa jih seštevaj, kolikor dolgo hočeš.

+ + +

Ena rešitev je, da vsak vrne število svojih otrok, ki čemur morajo otroci +prišteti število svojih otrok, in vnuki število svojih...

+
+def stevilo_potomcev(oseba):
+	potomcev = len(otroci[otroci])
+	for otrok in otroci[oseba]:
+		potomcev += stevilo_potomcev(otrok)
+	return potomcev
+
+ +

Ali isto, le na drug način:

+
+def stevilo_potomcev(oseba):
+	potomcev = 0
+	for otrok in otroci[oseba]:
+		potomcev += 1 + stevilo_potomcev(otrok)
+	return potomcev
+
+ +

Lahko pa si pomagamo tudi z rodbino:

+
+def stevilo_potomcev(oseba):
+	return velikost_rodbine(oseba) - 1
+
+ +

Rekurzivne funkcije na seznamih

+ +

Palindrom

+ +

Niz je palindrom, če se naprej in nazaj bere enako.

+ +

Pisati funkcijo, ki pove, ali je podani niz palindrom, je sicer železni +repertoar pouka programiranja - v Pythonu pa je nekoliko trivialen. Če imamo +niz s, bomo z s[1:-1] dobili obrnjen niz, niz +"prebran" nazaj. Če sta tadva enaka, je funkcija palindrom.

+ +

Ker vem, da ste pametni ljudje, ne boste pisali

+ +
def palindrom(s):
+    if s == s[::-1]:
+        return True
+    else:
+        return False
+ +

temveč, kratko in jedrnato

+ +
def palindrom(s):
+    return s == s[::-1]
+ +

Zdaj pa recimo, da za tole obračanje nizov ne vemo (ali pa, da programiramo +v jeziku, ki česa takšnega nima. V tem primeru potrebujemo zanko: rekli bomo, +da je s palindrom, če je ničti znak enak zadnjemu, prvi +predzadnjemu in tako naprej do konca. Po vzorcu, ki nam je že čisto domač, +bomo ob prvem neujemanju zatulili Falsch!; če pridemo do konca +brez težav, vrnemo True.

+ +
def palindrom(s):
+    for i in range(len(s)):
+        if s[i] != s[-i - 1]:
+            return False
+    return True
+ +

(Pravzaprav ni potrebno, da gremo "tako naprej do konca", saj bi zadoščalo +"tako naprej do sredine". A to tule ni pomembno.)

+ +

Palindrome lahko definiramo na drug način, ki ne zahteva štetja: rečemo +lahko, da je s palindrom, če je ničti znak enak zadnjemu in je +palindrom tudi vse med njima. Poskrbeti je le potrebno za nize, ki nimajo +dveh znakov: če je niz krajši od dveh znakov, bomo rekli, da je palindrom.

+ +

Z enim stavkom: s je palindrom, če je krajši od dveh znakov ALI +pa je ničti znak enak zadnjemu IN so vsi znaki od prvega do predzadnjega +palindrom.

+ +
def palindrom(s):
+    return len(s) < 2 or s[0] == s[-1] and palindrom(s[1:-1])
+ +

Študente tole pogosto zbega. Funkcija palindrom je definirana +s funkcijo palindrom. Sama s sabo. Je to sploh dovoljeno? Deluje? +

+ +

Razlog, da deluje, je v tem, da je niz vedno krajši. Ko se vprašamo, ali je +"abcdcba" palindrom, funkcija ugotovi, da to sicer ni manj kot dva znaka, +vendar je palindrom, če je ničti znak enak zadnjemu (kar je) in če je "bcdcb" +palindrom. Ko preverja, ali je "bcdcb" palindrom, ugotovi, da je daljši od dveh +znakov, zato bo palindrom, če je ničti enak zadnjemu (kar je) in če je "cdc" +palindrom. Ta je daljši od dveh znakov, zato bo palindrom, če je ničti znak +enak zadnjemu in je "d" palindrom. Niz "d" je krajši od dveh znakov, torej je +palindrom. Zato je torej tudi "cdc" palindrom. Zato je "bcdcb" palindrom. +Zato je "abcdcba" palindrom.

+ +

Vsota elementov seznama

+ +

Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa +poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to potrebujemo +rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.

+ +

Takole lahko rečemo: vsoto elementov seznama dobimo tako, da k prvemu +elementu prištejemo vsoto ostalih. Če je seznam prazen, pa je vsota 0.

+ +
def vsota(s):
+    if not s:
+        return 0
+    return s[0] + vsota(s[1:])
+ +

Ima seznam sama soda števila

+ +

Seznam ima sama soda števila, če je prazen ali pa je prvi element sod in +ima preostanek sama soda števila.

+ +
def soda(s):
+    return not s or s[0] % 2 == 0 and soda(s[1:])
+ +

Vsota sodih števil v seznamu

+ +

Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem +seznamu.

+ +

Če je seznam prazen, je vsota enaka 0. Sicer pa naredimo tole: če je ničti +element sod, vrnemo vsoto ničtega elementa in vsote ostalih. Če ni sod, vrnemo +le vsoto ostalih.

+ +
def vsota_sodih(s):
+    if not s:
+        return 0
+    if s[0] % 2 == 0:
+        return s[0] + vsota_sodih(s[1:])
+    else:
+        return vsota_sodih(s[1:])
+ +

Prvi sodi element seznama

+ +

Napisali bomo funkcijo, ki vrne prvi sodi element.

+ +

Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med +ostalimi.

+ +
def prvi_sodi(s):
+    if s[0] % 2 == 0:
+        return s[0]
+    else:
+        return prvi_sodi(s[1:])
+ +

Funkcija ima manjšo težavo, kadar v +seznamu ni nobenega sodega elementa. Ker prvi ni sod, išče sodega v preostanku. +Ker prvi iz preostanka ni sod, išče sodega v preostanku. Ker prvi v tem +preostanku ni sod ... in tako naprej, dokler ne pride do praznega seznama. +Takrat bomo v prvi vrstici funkcije spraševali po prvem (no, ničtem) elementu, +s[0] in Python bo javil napako, Index out of range. +

+ +

Recimo, da bo funkcija v takšnem primeru vrnila None.

+ +
def prvi_sodi(s):
+    if not s:
+        return None
+    if s[0] % 2 == 0:
+        return s[0]
+    else:
+        return prvi_sodi(s[1:])
+ + + + -- cgit v1.2.1