From 0bfa95be7046b101a00f83f082260b5d0e007159 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20Mo=C5=BEina?= Date: Tue, 25 Oct 2016 11:44:09 +0200 Subject: Added new exercises with recursion. Added description for functions. --- python/problems/functions/functions_sl.html | 587 +++++++++++++++++++++++++ python/problems/functions/sl.py | 2 +- python/problems/recursion/distance/common.py | 84 ++++ python/problems/recursion/distance/en.py | 13 + python/problems/recursion/distance/sl.py | 31 ++ python/problems/recursion/find_sum/find_sum.py | 19 - python/problems/recursion/map.png | Bin 0 -> 12202 bytes python/problems/recursion/maxroom/common.py | 73 +++ python/problems/recursion/maxroom/en.py | 13 + python/problems/recursion/maxroom/sl.py | 29 ++ python/problems/recursion/where_to/common.py | 77 ++++ python/problems/recursion/where_to/en.py | 13 + python/problems/recursion/where_to/map.png | Bin 0 -> 12202 bytes python/problems/recursion/where_to/sl.py | 55 +++ 14 files changed, 976 insertions(+), 20 deletions(-) create mode 100644 python/problems/functions/functions_sl.html create mode 100644 python/problems/recursion/distance/common.py create mode 100644 python/problems/recursion/distance/en.py create mode 100644 python/problems/recursion/distance/sl.py delete mode 100644 python/problems/recursion/find_sum/find_sum.py create mode 100644 python/problems/recursion/map.png create mode 100644 python/problems/recursion/maxroom/common.py create mode 100644 python/problems/recursion/maxroom/en.py create mode 100644 python/problems/recursion/maxroom/sl.py create mode 100644 python/problems/recursion/where_to/common.py create mode 100644 python/problems/recursion/where_to/en.py create mode 100644 python/problems/recursion/where_to/map.png create mode 100644 python/problems/recursion/where_to/sl.py diff --git a/python/problems/functions/functions_sl.html b/python/problems/functions/functions_sl.html new file mode 100644 index 0000000..1bd0a25 --- /dev/null +++ b/python/problems/functions/functions_sl.html @@ -0,0 +1,587 @@ + + + + + + + + + + +

Kako definiramo funkcije?

+ +

Funkcije smo si doslej predstavljali kot škatlice: nekaj gre noter +(temu smo in bomo rekli argument), nekaj pride ven (temu se reče + rezultat funkcije), vmes pa se lahko še kaj opaznega dogaja, recimo + izpisuje. Primer funkcije, ki je počela vse to, je input: kot +argument smo ji povedali, kaj naj vpraša uporabnika; kot rezultat je vrnila, +kar je vtipkal uporabnik; vmes se je zgodilo to, da je funkcija nekaj vprašala +uporabnika in počakala, da je le-ta odgovoril. Druga funkcija, ki smo jo +srečali, je bila sqrt, ki dobi kot argument neko število in vrne +njegov koren. Vmes se ne dogaja nič opaznega, funkcija le "neopazno" naredi, +kar mora narediti.

+ +

S tem, kako delujejo funkcije in kako kaj naredijo, se doslej nismo +ukvarjali. Te stvari so za nas napisali drugi (hvala, hvala) in mi jih lahko +uporabljamo, ne da bi nas vznemirjalo vprašanje, kako so napisane. S tem, kako +so napisane funkcije, ki so jih naredili drugi, se tudi v prihodnje ne bomo +ukvarjali. Pač pa se bomo danes naučili pisati svoje.

+ + +

Popolna števila

+ +

Število je popolno, če je enako vsoti svojih deliteljev. 28 je +deljivo z 1, 2, 4, 7 in 14 ter je popolno, saj je 1+2+4+7+14 ravno 28. Napišimo +program, ki sestavi seznam vseh popolnih števil do 1000.

+ +

Delitelji števila

+ +

Znamo napisati program, ki sestavi seznam vseh deliteljev nekega števila + n?

+ +
+n = int(input("Vnesi število: "))
+
+s = []
+for i in range(1, n):
+    if n % i == 0:
+        s.append(i)
+
+print(s)
+ +

Najprej naredimo prazen seznam, nato gremo prek vseh števil od 1 do n in +če število deli n, ga dodamo v s.

+ +

Kaj ne bi bilo lepo, če bi imel Python kar funkcijo delitelji, +ki bi jo lahko uporabili? Potem bi lahko napisali kar

+ +
+stevilka = int(input("Vnesi število: "))
+s = delitelji(stevilka)
+print(s)
+ +

Napišimo si takšno funkcijo, da jo bomo lahko klicali.

+ +
def delitelji(n):
+    s = []
+    for i in range(1, n):
+        if n % i == 0:
+            s.append(i)
+    return s
+ +

Definicijo funkcije začnemo z def; to je rezervirana beseda, ki +pomeni, da to, kar sledi, ni "program, ki ga je treba takoj izvesti", temveč +funkcija. Z drugimi besedami, def delitelji pomeni: "kadar bo +kdo poklical funkcijo delitelji, naredi naslednje:".

+ +

Imenu sledijo oklepaji, v katerih navedemo imena argumentov +funkcije. V našem primeru bo funkcija zahtevala en argument. Torej, ta, +ki bo poklical funkcijo, bo moral v oklepaje napisati eno reč (upamo, da bo +napisal število, sicer pa naj si sam pripiše posledice).

+ +

Tista reč, ki jo bomo ob klicu funkcije podali kot argument, se bo znotraj +funkcije pojavila kot spremenljivka z imenom n. Takšno ime smo +namreč uporabili v prvi vrstici, v "glavi" funkcije. Vrednosti ji ne bomo +priredili: ko bo nekdo poklical funkcijo, bo Python tej "spremenljivki" kar sam +od sebe priredil vrednost, ki jo bo "klicatelj" napisal kot argument funkcije. +Če torej nekdo pokliče + +

s = delitelji(35)
+ +bo imel n vrednost 35 in če pokliče + +
s = delitelji(13)
+ +bo imel n vrednost 13. n ima vrednost argumenta.

+ +

Za def delitelji(n) sledi dvopičje in zamik. Vse, kar sledi +takole zamaknjeno, je koda funkcije. Kaj mora narediti le-ta? No, tisto, kar +pač dela funkcija: sestaviti seznam deliteljev n. To pa ne le +znamo narediti, temveč smo celo ravno prejle tudi zares naredili in lahko le +skopiramo.

+ +

Na koncu (ali tudi že kje vmes - bomo že videli primer) funkcija pove, kaj +naj klicatelj dobi kot rezultat. To stori s stavkom return s.

+ +

Geometrija

+ +

Napišimo funkcijo, ki dobi kot argument dolžine stranic trikotnika in vrne + njegovo ploščino. Ta funkcija bo imela tri argumente; poimenujmo jih + a, b in c. + + +

from math import *
+def ploscina_trikotnika(a, b, c):
+    s = (a + b + c) / 2
+    return sqrt(s * (s - a) * (s - b) * (s - c))
+ +

Ko smo pri tem, napišimo še funkcijo funkcijo za obseg trikotnika ter za + obseg in ploščino kroga.

+ +
from math import *
+
+def obseg_trikotnika(a, b, c):
+    return a + b + c
+
+def ploscina_kroga(r):
+    return pi * r ** 2
+
+def obseg_kroga(r):
+    return 2 * pi * r
+ +

Vsota števil v seznamu

+ +

Zdaj napišimo drugo funkcijo: funkcijo, ki dobi seznam števil in izračuna +njihovo vsoto.

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

Funkcija ima spet en argument, tokrat smo ga poimenovali s. +Ta argument bo seznam števil, ki jih je potrebno sešteti. Funkcija gre - z +zanko for - prek tega seznama in sešteva, kot smo počeli že +prejšnji teden, le brez funkcij. Na koncu rezultata ne izpiše +(print), kot smo delali doslej, temveč ga vrne +(return).

+ +

(Mimogrede povejmo še, da nam funkcije vsota ne bi bilo +potrebno napisati, saj obstaja: imenuje se sum.)

+ + +

Za napredno misleče

+ +

Nekateri se sprašujejo, kako funkcija ve, kakšnega tipa bodo argumenti, +ki jih bo dobila. Nekateri se zdaj, ko so izvedeli, da se nekateri sprašujejo +o tem, sprašujejo, zakaj bi se kdo to spraševal.

+ +

Vsebina tega razdelka je namenjena samo prvim. Kasneje bo vse, kar pišemo +tu, postalo samoumevno, ne da bi bilo potrebno razlagati. Tule pa povejmo +zaradi tistih, ki prihajajo iz drugih jezikov.

+ +

V nekaterih jezikih je potrebno za vsako spremenljivko, preden jo uporabimo, +povedati, kakšnega tipa bo. Python ni eden izmed teh "nekaterih jezikov". +Podobno je z argumenti funkcij. V nekaterih jezikih bi morali povedati, +kakšnega tipa bodo argumenti funkcije in kakšen bo rezultat. Tudi takšen +Python ni. Funkcija sprejme, kar sprejme in vrača, kar vrača.

+ +

Za primer vzemimo preprostejšo funkcijo vsota, ki ji podamo dva + argumenta, funkcija pa vrne njuno vsoto.

+ +
def vsota(a, b):
+    return a + b
+ +

Če jo pokličemo z vsota(2, 5), vrne 2 + 5, torej + 7. Če jo pokličemo z vsota("Ana", "Marija") vrne + "Ana" + "Marija", torej "AnaMarija". Če jo + pokličemo z vsota(2, "Ana"), poskuša izračunati + 2 + "Ana" in vrne napako, ker se ne da seštevati števil in + nizov.

+ +

Jezikom, ki delajo tako, pravimo dinamično tipizirani jeziki. Stvar deluje +(približno) tako, da Python, ko pride do a + b, reče objektoma +a in b, naj se seštejeta. Če se znata, je to v redu, +če ne, pa javita napako in Python jo izpiše. Python v resnici ne zna seštevati, +seštevati (se) znajo objekti.

+ +

Vrnimo se k prvi funkciji vsota, oni od prej. Kaj bi se + zgodilo, če bi dali funkciji namesto seznama kaj drugega, recimo + terko ali kaj podobnega? No, preskusimo jo nekoliko.

+ +
 vsota([1, 5, 3])
+9
+>>> vsota((1, 5, 3))
+9
+>>> vsota(range(4))
+6
+ +

S seznamom dela. Prvi klic pomeni isto, kot če bi napisali: +

s = [1, 5, 3]
+v = 0
+for e in s:
+    v += e
+ +Drugi klic je podoben, le da je s zdaj terka (1, 5, 3), +torej dobimo + +
v = 0
+for e in (1, 5, 3):
+    v += e
+ +Tretji klic pa je isto, kot če bi rekli + +
v = 0
+for e in range(4):
+    v += e
+

+ +

Kaj pa, če bi namesto seznama celih števil podali seznam necelih?

+ +
>>> vsota([1.3, 2.2, 3.1])
+6.6
+ +

Dela, jasno. Zakaj pa ne bi?

+ +

Kaj pa, če bi dali seznam nizov? Poglejmo, poučno bo.

+ +
>>> vsota(["Ana", "Berta", "Cilka"])
+Traceback (most recent call last):
+  File "", line 1, in 
+  File "", line 4, in vsota
+TypeError: unsupported operand type(s) for +=: 'int' and 'str'
+ +

Zgodi se tole. Najprej je v enak 0. V prvem koraku zanke +poskuša izračunati 0 + "Ana", kar se ne da.

+ +

Funkcijo je mogoče popraviti, da bo delovala tudi za nize.

+ +
def vsota(s):
+    v = None
+    for e in s:
+        if v == None:
+            v = e
+        else:
+            v += e
+    return v
+ +

(
Komur se mozga, naj razmisli, zakaj dela tudi naslednja (grda) + različica funkcije:

+
def vsota(s):
+    v = None
+    for e in s:
+        v = v and v + e or e
+    return v
+

.)

+ +

Tule smo torej naleteli na None. Tole je kar tipična situacija, + v kateri ga uporabimo. v-ju moramo bo v začetku dati neko + vrednost, ki bo povedala, da še nima nobene vrednosti. None je + idealna konstanta, s katero povemo kaj takega. V zanki preverimo, ali je + v še vedno nič in mu v tem primeru priredimo e, + sicer mu prištejemo e.

+ +

Razlika je v tem, da v-ju zdaj ne priredimo vrednosti že pred +zanko, temveč jo dobi šele pri prvem elementu zanke. Tako bo gotovo pravega +tipa. Zdaj zna seštevati vse živo.

+ +
>>> vsota([1, 2, 3])
+6
+>>> vsota(["Ana", "Benjamin", "Cilka"])
+'AnaBenjaminCilka'
+ +

Kaj pa tole?

+ +
>>> vsota("Benjamin")
+'Benjamin'
+ +

Zanka for gre prek niza in sešteje njegove črke. Rezultat je, +seveda, spet isti niz.

+ +

Pač pa funkcija ne deluje, če ji damo seznam, ki vsebuje reči, ki jih ni +mogoče sešteti.

+ +
>>> vsota([1, "a"])
+Traceback (most recent call last):
+  File "", line 1, in 
+  File "", line 8, in vsota
+TypeError: unsupported operand type(s) for +=: 'int' and 'str'
+ + + +

Popolno število

+ +

Vrnimo se k popolnim številom. Rekli smo, da je število popolno, če je enako + vsoti svojih deliteljev. Lahko bi torej rekli

+ +
stevilo = int(input("Vnesi število: "))
+d = delitelji(stevilo)
+v = vsota(d)
+if v == d:
+    print("Število", stevilo, "je popolno")
+else:
+    print("Število", stevilo, "ni popolno")
+ +

vendar ne bomo. Napisali bomo funkcijo, ki vrne True, če je +število popolno in False, če ni.

+ +
def popolno(n):
+    d = delitelji(n)
+    v = vsota(d)
+    return v == n
+ +

Pazite, tule nismo pisali

+ +
def popolno(n):
+    d = delitelji(n)
+    v = vsota(d)
+    if v == n:
+        return True
+    else:
+        return False
+ +

Lahko bi, vendar bi bilo smešno. Pač pa lahko funkcijo še skrajšamo (in +navadno bi jo tudi res), takole

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

Končno ostane še program, ki bo z uporabo gornje funkcije sestavil seznam +vseh popolnih števil manjših od 1000. +V njem z zanko for preštejemo do 1000, za vsako število posebej +preverimo, ali je popolno in če je, ga dodamo na seznam.

+ +
s = []
+for i in range(1, 1001):
+    if popolno(i):
+        s.append(i)
+
+print(s)
+ +

Lepo prosim, ne pišite if popolno(i) == True:. Smo že povedali, +zakaj, ne?

+ +

Klici funkcij

+ +

Najprej zberimo vse skupaj:

+ +
def delitelji(n):
+    s = []
+    for i in range(1, n):
+        if n % i == 0:
+            s.append(i)
+    return s
+
+def vsota(s):
+    v = 0
+    for e in s:
+        v += e
+    return v
+
+def popolno(n):
+    d = delitelji(n)
+    v = vsota(d)
+    return v == n
+
+
+s = []
+for i in range(1, 1001):
+    if popolno(i):
+        s.append(i)
+
+print(s)
+ +

Kako se izvaja tako napisan program? Malo drugače, kot smo vajeni. Začetek +programa - vse do mesta s = [], so definicije funkcij. Python tega +dela programa ne izvede, le zapomni si funkcije, da jih bo kasneje lahko +poklical. Stvari se začnejo zares dogajati šele, pri s = []. Ko +program pride do klica funkcije popolno, skoči v to funkcijo -- +vendar si zapomni, odkod je skočil, tako da se bo kasneje lahko vrnil na to +mesto.

+ +

Prav. Zdaj smo v funkciji popolno in n je neka +številka (najprej 1, naslednjič bo 2 in tako naprej). Že takoj, v prvi +vrstici skoči izvajanje v funkcijo delitelji. Ta sestavi seznam +deliteljev in ga vrne - tistemu, ki jo je poklical, funkciji +popolno. Nato se nadaljuje izvajanje funkcije popolno: +ta v naslednji vrsti pokliče funkcijo vsota. Funkcija +vsota izračuna in vrne vsoto. Spet smo v funkciji +popolno, ki izračuna vrednost izraza v == n; +vrednost izraza je True ali False. Funkcija +popolno ga vrne tistemu, ki jo je klical, se pravi oni zanki +na koncu skripte. Če je rezultat True, dodamo število v seznam, +sicer ne.

+ +

Ta program je lep zato, ker je pregleden. Razdelili smo ga na tri funkcije, +vsaka opravlja svoje delo. Ko pišemo eno funkcijo, se ne ukvarjamo +s celo sliko, temveč le s tem, kar počne ta funkcija. Če mislimo +le na eno stvar naenkrat, nam bo lažje programirati in manj se bomo motili.

+ +

Rezultat sredi funkcije

+ +

Napišimo funkcijo, ki pove, ali je dano število praštevilo. Vrnila bo +True (je) ali False (ni).

+ +

Prejšnjič smo v te namene spoznali break - break + je bil ukaz, s katerim smo lahko prekinili zanko. No, prekinemo jo lahko + tudi z return.

+ +
def prastevilo(n):
+    for i in range(2, n):
+        if n % i == 0:
+            return False
+    return True
+

+ +

Prvi return je znotraj stavka if. Če odkrijemo, +da kakšno število med 2 in n-1 deli n (se pravi, če je ostanek po deljenju +n z i enak 0), dano število ni praštevilo in vrnemo +False. S tem se izvajanje funkcije prekine, funkcija vrne +rezultat in konec. Nobenega break ali česa podobnega ne +potrebujemo. return vedno konča izvajanje funkcije. Do drugega +returna tako pridemo le, če se ni izvedel prvi +return. To pa seveda pomeni, da ni bilo nobenega števila, ki bi +delilo dano število n.

+ + +

Funkcije (navadno) vračajo rezultate, ne izpisujejo

+ +

Iz neznanega razloga so študentom - kot opažam na izpitih in v domačih +nalogah - veliko bolj pri srcu funkcije, ki nekaj izpišejo, kot funkcije, +ki vračajo rezultat. Tako bi jih mikalo, recimo, funkcijo za vsoto +napisati tako, da bi na koncu namesto return v pisalo +print(v).

+ +

Vendar to ni prav! S takšno funkcijo si nimamo kaj pomagati! Ne potrebujemo +funkcije, ki izpiše vsoto; potrebujemo funkcijo, ki vrne +vsoto, da bomo lahko s to vsoto še kaj počeli. Če jo bomo hoteli izpisati, bomo +pač poklicali funkcijo in izpisali, kar vrne. Funkcija naj jo le izračuna. Si +predstavljate, kako neuporabna bi bila funkcija sin, če bi le +izpisala sinus, namesto da ga vrne? Bi si lahko pri programiranju topov z njo +sploh kaj pomagali?

+ +

To seveda ne pomeni, da funkcije ne smejo ničesar izpisovati. Smejo; nekatere +so pač namenjene temu. Najbolj očiten primer takšne funkcije je očitno kar +print.

+ +

Funkcije, ki ne vračajo ničesar

+ +

Vse funkcije v Pythonu vračajo rezultat. Če funkcija ne vrača ničesar, vrača + nič, torej None. To se bo zgodilo, kadar funkcija nima + return ali kadar se ta ne izvede.

+ +

Napišimo, na primer, funkcijo, ki kot argument dobi seznam in vrne prvo sodo + število v njem.

+ +
def prvo_sodo(s):
+    for e in s:
+        if e % 2 == 0:
+            return e
+ +

In zdaj jo preskusimo: +

>>> prvo_sodo([1, 2, 3, 4, 5])
+2
+>>> prvo_sodo([1, 3, 5])
+>>> print(prvo_sodo([1, 3, 5]))
+None
+ +

Prvi klic je jasen: funkcija vrne 2. V drugem primeru pa nikoli ne pride do + returna, zato funkcija pač ne vrne ničesar. Ko smo jo + poklicali, se tudi ni nič izpisalo, saj Python, kadar ga poganjamo v + načinu za čvekanje, ne izpiše None ... razen, kadar ga k temu + prisilimo s print, kot smo storili v zadnji vrstici.

+ +

Konstanta None se šteje za neresnično. To je praktično, saj jo +lahko uporabljamo v pogojnih stavkih. Imejmo nek seznam s in +izpišimo prvo sodo število ali pa povejmo, da v seznamu ni sodih števil.

+ +
sodo = prvo_sodo(s)
+if sodo:
+    print("Prvo sodo število je", sodo)
+else:
+    print("V seznamu ni sodih števil.")
+ +

Vendar moramo biti pri takšnem početju majčkeno previdni. Kaj, če je prvo sodo +število v seznamu 0? Ker je tudi 0 neresnično, bo program v tem primeru napisal, +da ni sodih števil. Pravilno bi bilo torej

+ +
sodo = prvo_sodo(s)
+if sodo != None:
+    print("Prvo sodo število je", sodo)
+else:
+    print("V seznamu ni sodih števil.")
+ +

Iz nekega razloga, ki ga bomo pojasnili čez dva tedna, pa običajno pišemo

+ +
sodo = prvo_sodo(s)
+if sodo is not None:
+    print("Prvo sodo število je", sodo)
+else:
+    print("V seznamu ni sodih števil.")
+ + +

Več rezultatov

+ +

Funkcija lahko vrača tudi "več rezultatov", tako kot tale funkcija, ki vrne, +kvadrat in kub števila.

+ +
def kk(x):
+    return x ** 2, x ** 3
+ +

Pokličemo jo lahko takole.

+ +
kvad, kub = kk(5)
+ +

Pozoren študent je najbrž že spregledal mojo laž. V resnici funkcija +vrača en sam rezultat, namreč terko in ob klicu funkcije to terko razpakiramo. +Vendar nam o tem, tehničnem vidiku zadeve, ni potrebno razmišljati. Mirno se +lahko vedemo, kot da smo dobili dve vrednosti.

+ +

V tem primeru navadno ne pišemo oklepajev okrog terk. Funkcija bo delovala +tudi, če pišemo return (x ** 2, x ** 3), vendar to ni običajen +zapis za vračanje dveh vrednosti.

+ +

Več returnov

+ +

Funkcija ima seveda lahko več returnov. Izvede se tisti, na + katerega naleti. En primer smo že videli (določanje praštevilskosti). + Naredimo še enega: funkcijo, ki vrne absolutno vrednost danega števila.

+ +
def abs(x):
+    if x < 0:
+        return -x
+    else:
+        return x
+
+ +

Funkcija ima torej dva return. Eden se izvede, če je število + negativno in drugi, če pozitivno.

+ + +

Funkcije brez argumentov

+ +

Funkcija je lahko tudi brez argumentov. Tule je funkcija, ki nima argumentov, + vrne pa 42. Vedno.

+ +
def odgovor():
+    return 42
+
+ +

Tako funkcijo je potrebno tudi poklicati s praznim seznamov argumentov - +oklepajev pa vseeno ne smemo pozabiti.

+ +
koliko = odgovor()
+ +

Malo pametnejši primer funkcije brez argumentov bi bila funkcija, ki + uporabniku zastavi račun in pove (s True ali + False), ali ga je pravilno rešil.

+ +
def uganka():
+    a = randint(2, 10)
+    b = randint(2, 10)
+    c = int(input("Koliko je {}x{}? ".format(a, b)))
+    return a * b  == c
+ +

Z njo postane rešitev lanske domače naloge precej preglednejša.

+ +
from random import *
+from time import *
+
+konec = time() + 20
+tock = 0
+while time() < konec:
+    if uganka():
+        print("Pravilno.")
+        tock += 1
+    else:
+        print("Napačno.")
+print("Dosegli ste", tock, "tock")
+ +

Zdaj, ko znamo definirati funkcije, bo postalo naše življenje veliko lažje +in preglednejše. Naši programi so, z vsem kar znamo, začeli postajati +dolgi in razvlečeni. Zdaj jih bomo lahko razsekali v posamezne funkcije in se +v njih tako lažje znašli.

+ + + diff --git a/python/problems/functions/sl.py b/python/problems/functions/sl.py index 7de0a40..7e00895 100644 --- a/python/problems/functions/sl.py +++ b/python/problems/functions/sl.py @@ -1,3 +1,3 @@ name = 'Funkcije' -description = 'Pisanje in uporaba funkcij.' +description = 'Pisanje in uporaba funkcij' diff --git a/python/problems/recursion/distance/common.py b/python/problems/recursion/distance/common.py new file mode 100644 index 0000000..f9a8c13 --- /dev/null +++ b/python/problems/recursion/distance/common.py @@ -0,0 +1,84 @@ +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 = 20811 +number = 11 +visible = True + +solution = '''\ +def distance(map, room1, room2): + if room1 not in map or room2 not in map: + return -1 + if room1 == room2: + return 0 + d1 = distance(map, map[room1][0], room2) + if d1 > -1: + return d1 + 1 + d2 = distance(map, map[room1][1], room2) + if d2 > -1: + return d2 + 1 + return -1 +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18], +81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27], +18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12], +7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None], +61: [None, None], 4: [None, None], 12: [None, None]} + +def test(python, code, aux_code=''): + func_name = 'distance' + 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 = [ + ((0, 42), 3), + ((0, 4), 4), + ((0, 5), 2), + ((0, 3), 1), + ((0, 0), 0), + ((42, 42), 0), + ((8, 66), 2), + ] + test_in = [('{}({}, {}, {})'.format(func_name, str(map), l[0][0], l[0][1]), 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/recursion/distance/en.py b/python/problems/recursion/distance/en.py new file mode 100644 index 0000000..316859b --- /dev/null +++ b/python/problems/recursion/distance/en.py @@ -0,0 +1,13 @@ +id = 20811 +name = 'Distance' + +description = '''\ +

(translation missing)

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

(translation missing)

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

(translation missing)

''', +} diff --git a/python/problems/recursion/distance/sl.py b/python/problems/recursion/distance/sl.py new file mode 100644 index 0000000..9cf9418 --- /dev/null +++ b/python/problems/recursion/distance/sl.py @@ -0,0 +1,31 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20811 +name = 'Razdalja' + +description = '''\ +

+

+Nadaljujmo z meglenim gorovjem. Napiši funkcijo +distance(map, start_room, ring_room), +ki prejme zemljevid, številko začetne sobe in številko sobe s prstanom, +kot rezultat pa vrne dolžino poti do nje. Če katerakoli od sob ne obstaja, +vrni -1. +Na gornjem zemljevidu je globina sobe 42 enaka 3. Zato:

+
+>>> distance(map, 0, 42)
+3
+>>> distance(map, 0, 43)
+-1
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''] +} diff --git a/python/problems/recursion/find_sum/find_sum.py b/python/problems/recursion/find_sum/find_sum.py deleted file mode 100644 index 85f472b..0000000 --- a/python/problems/recursion/find_sum/find_sum.py +++ /dev/null @@ -1,19 +0,0 @@ -def find_sum(xs, gs): - if gs < 0: - return False - if gs == 0: - return True - if not xs: - return False - return find_sum(xs[1:], gs-xs[0]) or find_sum(xs[1:], gs) - -print (find_sum([2,7,3,1,4], 10)) -print (find_sum([2,3,2,4], 10)) -print (find_sum([], 10)) -print (find_sum([1,2,3], 2)) -print (find_sum([1,2,3], 7)) -print (find_sum([2,7,3,1,4], 9)) -print (find_sum([2,7,3,2,4], 17)) - - - diff --git a/python/problems/recursion/map.png b/python/problems/recursion/map.png new file mode 100644 index 0000000..014d78e Binary files /dev/null and b/python/problems/recursion/map.png differ diff --git a/python/problems/recursion/maxroom/common.py b/python/problems/recursion/maxroom/common.py new file mode 100644 index 0000000..2709d76 --- /dev/null +++ b/python/problems/recursion/maxroom/common.py @@ -0,0 +1,73 @@ +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 = 20812 +number = 12 +visible = True + +solution = '''\ +def maxroom(map, room): + if room == None: + return -1 + return max(room, maxroom(map, map[room][0]), maxroom(map, map[room][1])) +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18], +81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27], +18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12], +7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None], +61: [None, None], 4: [None, None], 12: [None, None]} + +def test(python, code, aux_code=''): + func_name = 'maxroom' + 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 = [ + (0, 81), + (3, 66), + (63, 63), + (5, 35), + ] + test_in = [('{}({}, {})'.format(func_name, str(map), 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/recursion/maxroom/en.py b/python/problems/recursion/maxroom/en.py new file mode 100644 index 0000000..a876812 --- /dev/null +++ b/python/problems/recursion/maxroom/en.py @@ -0,0 +1,13 @@ +id = 20812 +name = 'Max room' + +description = '''\ +

(translation missing)

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

(translation missing)

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

(translation missing)

''', +} diff --git a/python/problems/recursion/maxroom/sl.py b/python/problems/recursion/maxroom/sl.py new file mode 100644 index 0000000..bfc5313 --- /dev/null +++ b/python/problems/recursion/maxroom/sl.py @@ -0,0 +1,29 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20812 +name = 'Največja številka' + +description = '''\ +

+

+Napiši funkcijo maxroom(map, room), ki vrne največjo številko, +v katero lahko pridemo, če se spustimo iz te sobe.

+
+>>> maxroom(map, 0)
+81
+>>> maxroom(map, 3)
+66
+>>> maxroom(map, 12)
+12
+
+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''] +} diff --git a/python/problems/recursion/where_to/common.py b/python/problems/recursion/where_to/common.py new file mode 100644 index 0000000..55a9aed --- /dev/null +++ b/python/problems/recursion/where_to/common.py @@ -0,0 +1,77 @@ +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 = 20810 +number = 10 +visible = True + +solution = '''\ +def where_to(map, room, path): + if path: + return where_to(map, map[room][path[0] == "R"], path[1:]) + else: + return room +''' + +hint_type = { + 'final_hint': Hint('final_hint') +} + +map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18], +81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27], +18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12], +7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None], +61: [None, None], 4: [None, None], 12: [None, None]} + +def test(python, code, aux_code=''): + func_name = 'where_to' + 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 = [ + ((0, "LLR"), 18), + ((0, "RRRR"), 12), + ((0, "L"), 6), + ((0, ""), 0), + ((0, "RLL"), 42), + ((0, "RRLL"), 61), + ((0, "LLLL"), 7), + ] + test_in = [('{}({}, {}, "{}")'.format(func_name, str(map), l[0][0], l[0][1]), 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/recursion/where_to/en.py b/python/problems/recursion/where_to/en.py new file mode 100644 index 0000000..df43164 --- /dev/null +++ b/python/problems/recursion/where_to/en.py @@ -0,0 +1,13 @@ +id = 20810 +name = 'Where to' + +description = '''\ +

(translation missing)

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

(translation missing)

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

(translation missing)

''', +} diff --git a/python/problems/recursion/where_to/map.png b/python/problems/recursion/where_to/map.png new file mode 100644 index 0000000..014d78e Binary files /dev/null and b/python/problems/recursion/where_to/map.png differ diff --git a/python/problems/recursion/where_to/sl.py b/python/problems/recursion/where_to/sl.py new file mode 100644 index 0000000..365d7cd --- /dev/null +++ b/python/problems/recursion/where_to/sl.py @@ -0,0 +1,55 @@ +import server +mod = server.problems.load_language('python', 'sl') + +id = 20810 +name = 'Kam?' + +description = '''\ +

+od Meglenim gorovjem je, kot nekateri vedo že dolgo, +nekateri pa so morali čakati na film, cel labirint votlin. +Bilbu bi bilo veliko lažje, če bi imel zemljevid. Mi ga imamo. + +Zemljevid lahko shranimo tudi v obliki slovarja, +v katerem so ključi številke sob, vrednosti pa sobe, +v katere pridemo po levi in po desni poti. +Kadar kakšne poti ni, je ustrezni element enak None.

+ + + +
+map = {0: [6, 3], 6: [5, 81], 3: [8, 24], 5: [2, 18],
+81: [None, None], 8: [42, None], 24: [63, 13], 2: [7, 27],
+18: [None, 35], 42: [None, 66], 63: [61, None], 13: [4, 12],
+7: [None, None], 27: [None, None], 35: [None, None], 66: [None, None],
+61: [None, None], 4: [None, None], 12: [None, None]}
+ +

Napiši funkcijo where_to(map, room, path), +ki kot argument prejme zemljevid (npr. zgornji slovar), +začetno sobo (ta bo vedno 0, a to naj te ne moti) in pot (path), +podano kot zaporedje znakov L in R (levo in desno). +Kot rezultat mora vrniti sobo, v katero pelje podana pot.

+ +
+>>> where_to(map, 0, "LLR")
+18
+>>> where_to(map, 0, "RRRR")
+12
+>>> where_to(map, 0, "L")
+6
+>>> where_to(map, 0, "")
+0
+
+ +

Predpostaviti smeš, da je pot pravilna in se nikoli ne odpravi v hodnik, +ki ga ni.

+''' + +plan = [] + +hint = { + 'final_hint': ['''\ +

Program je pravilen!
+

+'''] +} -- cgit v1.2.1