Kalkulator
Testi
Testi: kalkulator.zip
Naloge
Ideja za nalogo prihaja z Advent of Code, naloga Some Assembly Required. Priporočam, da si jo preberete tudi tam. (V Pythonu bomo sicer dobili nekoliko drugačne rezultate; konkretno, vrednosti h in i bosta pri nas -124 in -457 in ne 65412 in 65079. Kdor ne ve, zakaj, naj se ne vznemirja.) V nalogah do ocene 9 bomo rešili problem z Advent of Code, v nalogi za oceno 10 pa preverjali še, ali je rešljiv. Delali bomo korak za korakom, lepo počasi.
Ker postajajo naši programi daljši, bomo vse pogosteje programirali v angleščini. Žal je to neizbežno.
Navodila so tokrat podana v obliki dokumentacije za funkcije, ki jih morate napisati. Dokumentaciji je oblikovana skladno s pravili za dokumentacijo knjižnic v Pythonu. Še več: zapisana je v funkcijah, ki jih morate napisati. Namesto datoteke s testi imate tokrat datoteko calculator.py, ki vsebuje teste in nastavke vseh funkcij, ki jih je potrebno napisati. Vsaka funkcija se začne z nizom, ki jo dokumentira.
Vse funkcije
Tule je najprej rešitev celotne naloge. Podrobna razlaga sledi spodaj.
# Ocena 6
def to_number(s):
return int(s) if s.isdigit() else s
def parse(s):
s = s.split()
var = s[-1]
if len(s) == 3:
op, arg = "SET", [0]
elif len(s) == 4:
op, arg = "NOT", [1]
elif len(s) == 5:
op, arg = s[1], [0, 2]
return var, op, tuple(to_number(s[i]) for i in arg)
def read(filename):
return [parse(s) for s in open(filename)]
# Ocena 7
def outputs(exprs):
return set(var for var, op, args in exprs)
def inputs(exprs):
outs = set()
for var, op, args in exprs:
outs |= set(arg for arg in args if isinstance(arg, str))
return outs
def check_names(exprs):
return inputs(exprs) <= outputs(exprs)
def check_operators(exprs):
return all(x[1] in {"SET", "NOT", "AND", "OR", "LSHIFT", "RSHIFT"}
for x in exprs)
# Ocena 8
def compute_expr(op, args):
a = args[0]
if op == "SET": return a
if op == "NOT": return ~a
b = args[1]
if op == "AND": return a & b
if op == "OR": return a | b
if op == "LSHIFT": return a << b
if op == "RSHIFT": return a >> b
def get_value(name, variables):
if isinstance(name, int):
return name
else:
return variables[name]
def get_values(args, variables):
return tuple(get_value(arg, variables) for arg in args)
def compute_list(exprs):
variables = {}
for var, op, args in exprs:
variables[var] = compute_expr(op, get_values(args, variables))
return variables
# Ocena 9
def dict_expr(exprs):
return {var: (op, args) for var, op, args in exprs}
def compute(var, exprs, variables):
op, args = exprs[var]
for arg in args:
if isinstance(arg, str) and arg not in variables:
variables[arg] = compute(arg, exprs, variables)
return compute_expr(op, get_values(args, variables))
def compute_file(var, filename):
return compute(var, dict_expr(read(filename)), {})
# Ocena 10
def computable(exprs):
if not check_names(exprs):
return False
izrazi = dict_expr(exprs)
while izrazi:
vars = list(izrazi.items())
for var, (op, args) in vars:
if all(arg not in izrazi for arg in args):
del izrazi[var]
if len(vars) == len(izrazi):
return False
return True
Vsebina po ocenah
Naloga za oceno 6 je bila naloga iz dela z nizi, seznami, terkami in datotekami.
Pri nalogi za oceno 7 je bilo potrebno poznati delo z množicami; koristno je bilo vedeti tudi za izpeljane množicami.
Pri reševanju naloge za oceno 8 je bilo potrebno poznati slovarje in jih
pametno uporabljati. Predvsem pri compute_list je bilo potrebno pomisliti,
kaj bomo vanj zapisovali in brali.
Naloga za oceno 9 je bila v bistvu naloga iz rekurzije. Od trivialnih nalog na predavanjih se je razlikovala po tem, da ni šlo z preprosto rekurzijo z odbijanjem prvega in/ali zadnjega elementa seznama ali niz, ali za rekurzijo po nekem eksplicitno podanem drevesu.
Ocena 6
Funkcija to_number(s)
def to_number(s):
"""Convert string to int if possible, else return the original string.
`to_number('42')` returns 42, while `to_number('x')` returns 'x'.
Args:
s (str): string that is converted to a number
Returns:
int: if the argument contains a number; `to_number('42')` return `42`
str: otherwise; `to_number('x')` return `'x'`
"""
if s.isdigit():
return int(s)
else:
return s
Funkcija je nekajkrat krajša od dokumentacije. Gre tudi krajše. else je
nepotreben. Enak rezultat bi dobili z
if s.isdigit():
return int(s)
return s
Ali se nam zdi prvo preglednejše je čisto stvar okusa. Še krajše je tole
return int(s) if s.isdigit() else s
Spet stvar okusa.
Funkcija parse(s)
def parse(s):
"""Parse a string with expression into tuple `(name, operation, arguments)`.
Args:
s (str): expression
Returns:
tuple: expression parsed into `(name, operation, arguments)`
See documentation for function :func:`read` for examples of expressions.
The operation can be unary SET or NOT, or binary AND, OR, LSHIFT or RSHIFT.
Note that SET is not spelled out in the input string; see the examples
below. The last element, `arguments` is itself a tuple of arguments; that
is, a tuple with 1 or 2 elements. Numeric arguments are converted to `int`.
Examples:
- `parse('abc OR x -> z')` returns `('z', 'OR', ('abc', 'x'))`
- `parse('t RSHIFT 3 -> a')` returns `('a', 'RSHIFT', ('t', 3))`
(the second element of the tuple, `3` is an `int`, ot a str `'3'`)
- `parse('42 -> ever')` returns `('ever', 'SET', (42, ))`
Note that 'SET' is not present (but only applied) in the input
string, yet it is explicit in the parsed string. Also note that
arguments is a tuple with a single element, `(42, )`.
- `parse('NOT big -> small')` returns `('small', 'NOT', ('big')`
"""
s = s.split()
var = s[-1]
if len(s) == 3:
op, arg = "SET", (to_number(s[0]), )
if len(s) == 4:
op, arg = "NOT", (to_number(s[1]), )
if len(s) == 5:
op, arg = s[1], (to_number(s[0]), to_number(s[2]))
return var, op, arg
Niz razbijemo glede na presledke. Zadnji element bo gotovo ime spremenljivke,
torej var = s[-1]. Izvedeti moramo še, kakšen je operator (shranili ga bomo
v op in sestaviti terko z argumenti (dali jo bomo v arg).
Opazujmo, iz koliko elementov je sestavljen niz.
Če iz treh, gre za nekaj oblike
a -> b, pri čemer jebneka spremenljivka (pobrali smo jo vvar),apa je lahko ime ali številka. Naloga pravi, da številke pretvorimo v številke, torej pokličemoto_number. Operacija (op) je torej"SET", argumenti (arg) pas[0], ki ga spravimo skozito_number, da ga po možnosti spremeni v številko, in ga zapakiramo v terko. Ne spreglejte vejice: če bi pisali(to_number(s[0])), to ne bi bila terka, temveč smo le dalito_number(s[0])v oklepaj.Če imamo niz iz štirih elementov, gre za
NOT a -> b. Reč je podobna, le da je operator zdaj"NOT", argument pa je na prvem mestu, saj je na ničtem NOT.Če imamo niz iz petih elementov, je oblike
a OPERACIJA b -> c. Zdaj jeopprvi element (s[1]), argumenta pa sta ničti in drugi.
Ko so elementi tako nabrani, vrnemo trojko var, op, arg.
Pri reševanju te naloge je zelo koristno, da se spomnimo, da smo maloprej
napisali funkcijo to_number, saj bomo sicer morali tule, v parse,
nevemkolikokrat ponoviti tiste pogoje iz to_number in pretvarjati nize v
števila.
Zakaj najprej shranjujemo v op in arg - čemu ne vračamo vrednosti kar
znotraj if-ov? No, da, pravilno je tudi
def parse(s):
s = s.split()
if len(s) == 3:
return s[-1], "SET", (to_number(s[0]), )
if len(s) == 4:
return s[-1], "NOT", (to_number(s[1]), )
if len(s) == 5:
return s[-1], s[1], (to_number(s[0]), to_number(s[2]))
Sovražniki oklepajev bi se morda domislili tegale.
def parse(s):
s = s.split()
var = s[-1]
if len(s) == 3:
oparg = "SET", to_number(s[0])
if len(s) == 4:
oparg = "NOT", to_number(s[1])
if len(s) == 5:
oparg = s[1], to_number(s[0]), to_number(s[2])
return var, oparg[0], oparg[1:]
Tu je oparg terka, ki vsebuje operator in vse argumente - kolikor jih pač je.
Ko v return pišemo oparg[1:], bo to vedno terka s preostalimi argumenti,
tudi če gre samo za enega.
Sam bi tole naredil tako:
def parse(s):
s = s.split()
var = s[-1]
if len(s) == 3:
op, arg = "SET", [0]
elif len(s) == 4:
op, arg = "NOT", [1]
elif len(s) == 5:
op, arg = s[1], [0, 2]
return var, op, tuple(to_number(s[i]) for i in arg)
Tu v arg zabeležim le indekse argumentov. V return pa mimogrede sestavim
terko, ki vsebuje vse elemente na teh mestih,
tuple(to_number(s[i]) for i in arg). Tako se znebim zoprnih klicev
to_number.
Funkcija read(filename)
def read(filename):
"""Read a file with expressions (one in each line) into a list.
Args:
filename: the name of the file
Returns:
a list of expressions as tuples, such as returned by :obj:`parse`
"""
return [parse(s) for s in open(filename)]
Živeli izpeljani seznami!
Če ne znamo, kar bi morali znati, pa pišemo nekaj v slogu
def read(filename):
exprs = []
for s in open(filename):
exprs.append(parse(s))
return exprs
V vsakem primeru je zelo koristno, da se spomnimo poklicati funkcijo parse,
sicer bomo tule, znotraj read ponavljali vse, kar smo naredili že tam.
Ocena 7
Funkcija outputs(exprs)
def outputs(exprs):
"""Return a set of names of all variables that are computed by expressions
Args:
exprs (list): a list of expressions, like those returned be :obj:`read`
Returns:
set: a set of variable names
Examples:
Call ::
outputs([('a', 'SET', ('b',)),
('e', 'AND', (12, 'x')),
('x', 'AND', ('z', 5))]`
returns `{'a', 'e', 'x'}`
"""
return {var for var, op, args in exprs}
Preden se pogovorimo o tej rešitvi, morda najprej sprogramirajmo na najnerodnejši še smiseln način.
def outputs(exprs):
outs = set()
for expr in exprs:
outs.add(expr[0])
return outs
Sestavimo prazno množico; to naredimo s set() in ne {}, ki bi sestavil
slovar, ne množice. Nato gremo čez seznam izrazov. expr bodo terke (trojke)
z imenom, operacijo in argumenti. Zanima nas le prva reč expr[0]. Te pridno
zlagamo v množico, ki jo na koncu vrnemo.
Kadar gremo z zanko čez trojke, jih raje jemljimo v tri spremenljivke. Vedno
je boljše delati z imeni (var, op, args) kot z indeksi. Tako dobimo
def outputs(exprs):
outs = set()
for var, op, args in exprs:
outs.add(var)
return outs
Odtod je za tiste, ki poznamo izpeljane množice, le še korak do gornje rešitve,
def outputs(exprs):
return {var for var, op, args in exprs}
Funkcija inputs(exprs)
def inputs(exprs):
"""Return a set of names of all variables that appear as arguments
Args:
exprs (list): a list of expressions, like those returned be :obj:`read`
Returns:
set: a set of variable names
Examples:
Call ::
outputs([('a', 'SET', ('b',)),
('e', 'AND', (12, 'x')),
('x', 'AND', ('z', 5))]`
returns `{'b', 'x', 'z'}`. Note that 12 and 5 are absent from the list
since these are not variables.
"""
ins = set()
for var, op, args in exprs:
ins |= {arg for arg in args if isinstance(arg, str)}
return ins
Tule ne bomo tlačili vsega v eno vrstico. Gre, a ni prav lepo.
Naredimo torej prazno množico in gremo čez seznam trojk var, op, args.
Zdaj nas var in op ne zanimata; kar iščemo, je v args. Konkretno,
args vsebuje imena (kot recimo b, x in z) ter številke (kot 5
in 12). Gremo čez vse elemente args (for arg in args) in jih zlagamo
v množico, vendar le, če je arg niz (if isinstance(arg, str)). Dobimo
torej množico vseh imen, ki se pojavijo med argumenti,
{arg for arg in args if isinstance(arg, str)}. To množico dodamo k vsem
imenom, ki smo jih našli doslej,
ins = ins | {arg for arg in args if isinstance(arg, str)}
kjer |, kot vemo, pomeni unijo množic. Krajše pa lahko pišemo
ins |= {arg for arg in args if isinstance(arg, str)}
Na podoben način, kot += pomeni prištevanje, += pomeni "priunijanje".
Funkcija check_names(exprs)
def check_names(exprs):
"""Check whether all inputs are also computed by some expression
Args:
exprs (list): a list of expressions
Returns:
bool: `True` if all inputs also appear as outputs of some expression
"""
return inputs(exprs) <= outputs(exprs)
Preveriti moramo le, ali so vhodi podmnožica izhodov. Pokličemo oni, prejšnji
funkciji in se spomnimo, da to, ali je neka množica podmnožica druge,
preverjamo z <=.
Funkcija check_operators(exprs)
def check_operators(exprs):
"""Check the validity of operator names
Valid operator names are SET, NOT, AND, OR, LSHIFT and RSHIFT
Args:
exprs (list): a list of expressions
Returns:
bool: `True` if all operators are valid
Example:
The function returns `False` for a list like this::
[('a', 'SET', ('b',)),
('e', 'LSHIFT', (12, 'x')),
('f', 'NOSUCHTHING', ('z', 5)),
('g', 'OR', (7, 5)),
('b', 'NOT', ('c',))]
"""
valid_operators = {"SET", "NOT", "AND", "OR", "LSHIFT", "RSHIFT"}
return all(op in valid_operators for var, op, args in exprs)
Dokumentacija funkcije vsebuje še primere; tule sem jih izpustil, saj bi se rešitev naloge sicer popolnoma izgubila v besedilu.
Spet moramo z zanko čez vse izraze. Tokrat nas ne zanimata var in args
temveč op. Lahko bi naredili tako
def check_operators(exprs):
valid_operators = {"SET", "NOT", "AND", "OR", "LSHIFT", "RSHIFT"}
for var, op, args in exprs:
if op not in valid_operators:
return False
return True
Spet nam pridejo prav množice: sestavimo množico veljavnih operatorjev. Za
vsak operator, ki ga vidimo (for var, op, args in exprs) preverimo, ali je
v tej množici in če ni (if op not in valid_operators), nemudoma vrnemo
False. Če je, bomo vrnili True, vendar šele na koncu, po tem, ko smo
preverili vse.
Kot smo se učili ob izpeljanih seznamih in generatorjih, se takle "preveri vse"
napiše hitreje s funkcijo all: sestavimo generator, ki generira True in
False glede na to, ali je operator veljaven ali ne,
(op in valid_operators for var, op, args in exprs) in ga podamo funkciji
all.
Ocena 8
Funkcija get_value(name, variables)
def get_value(name, variables):
"""Return the value corresponding to the name.
Args:
name (str or int): the name of a variable or an `int`
variables (dict): a dictionary with variables names as keys and their
values as values
Returns:
int: the value of the variable or the integer given as argument
The function assumes that the name exists in the dictionary.
Examples:
- `get_value(42, {'a': 13, 'foo': -65)` returns `42`
- `get_value('foo', {'a': 13, 'foo': -65)` returns `-65`
"""
if isinstance(name, int):
return name
else:
return variables[name]
</code></pre>
<p>Narediti je potrebno le, kar hoče naloga: če gre za število, ga vrneš. Če niz,
ga vzameš iz slovarja.</p>
<p>Krajše gre tudi tako:</p>
<pre><code>def get_value(name, variables):
return name if isinstance(name, int) else variables[name]
</code></pre>
<p>Testi so bili napisani tako, da so poskusili poklicati funkcijo z imenom
spremenljivke, ki ne obstaja. Pričakovali so, da se bo zgodila napaka, ki se
pač zgodi, če iz slovarja poskusimo vzeti kaj, česar ni. To so počeli zato,
da bi zagrenili življenje tistim, ki ne vedo, da po slovarjih na iščemo z</p>
<pre><code>for key, value in variables.items():
if key == var:
return value
</code></pre>
<p>Slovarje imamo prav zato, da nam tega ni potrebno početi: slovarji sami, v
trenutku poiščejo vsak element.</p>
<p>Kdor se je lotil iskanja na ta način, je imel manjši problem s simuliranjem
napake, ki se mora zgoditi, če ime ne obstaja. S tem seveda ne trdim niti,
da simuliranje te napake ni preprosto (je preprosto) in da tega nihče ni
naredil (so naredili).</p>
<h2>Funkcija <code>get_values(args, variables)</code></h2>
<pre><code>def get_values(args, variables):
"""Return the tuple of values corresponding to the names in the tuple.
Args:
args: a tuple of `str` and/or `int`
variables (dict): a dictionary with variables names as keys and their
values as values
Returns:
tuple: values of variables as `int`
The function is similar to :obj:`get_value` except that it takes a tuple
and returns a tuple.
Example:
`get_values(('foo', 42), {'a': 13, 'foo': -65)` returns `(-65, 42)`
"""
return tuple(get_value(arg, variables) for arg in args)
</code></pre>
<p>Za vsak argument iz <code>args</code> (<code>for arg in args</code>) pokličemo prejšnjo funkcijo
(<code>get_value(arg, variables)</code>) in vse skupaj strpamo v terko.</p>
<p>Tisti, ki ne poznajo generatorjev ... mah, ne, za oceno 8 jih je pa že
potrebno poznati. :)</p>
<h2>Funkcija <code>compute_expr(op, args)</code></h2>
<pre><code>def compute_expr(op, args):
"""Compute an expression
Args:
op: operator, one of 'SET', 'NOT', 'AND', 'OR', 'LSHIFT', 'RSHIFT'
args: arguments, given as a tuple with one or two `int`
Returns:
int: result of an expression
The function assumes that the operator is valid and that the number of
arguments matches the operator type.
Operations are interpreted as bitwise, not logical operations.
The function uses Python built-in operators `~` for NOT, `&` for AND,
`|` for OR, `<<` for LSHIFT and `>>` for RSHIFT.
Let `a` and `b` be the first and the second argument (if there are two).
The function works as follows. If the operator is
- "SET", result is `a`,
- "NOT", result is `~a` (note: tilde, not minus),
- "AND" and "OR", results are `a AND b` and `a OR b`, respectively,
- "LSHIFT" and "RSHIFT", results are `a << b` and `a >> b`, respectively.
Examples:
- `compute_expr("SET", (12, ))` returns 12
- `compute_expr("AND", (13, 69))` returns 5, computed as `13 & 69`
"""
a = args[0]
if op == "SET":
return a
if op == "NOT":
return ~a
b = args[1]
if op == "AND":
return a & b
if op == "OR":
return a | b
if op == "LSHIFT":
return a << b
if op == "RSHIFT":
return a >> b
</code></pre>
<p>Reč je preprosta, z malo spretnosti pa celo pregledna. Najprej shranimo
prvi argument v spremenljivko <code>a</code>, <code>a = args[0]</code>. Tako bo vse skupaj
veliko lepše, saj ne bo potrebno stalno pisati <code>args[0]</code>. Če gre za operaciji
SET in NOT, je to tudi edini argument, zato najprej opravimo z njima.</p>
<p>Sicer poberemo še drugi argument in poskrbimo še za ostale operacije.</p>
<p>Priznati moram, da sem sam to oblikoval malo drugače.</p>
<pre><code>def compute_expr(op, args):
a = args[0]
if op == "SET": return a
if op == "NOT": return ~a
b = args[1]
if op == "AND": return a & b
if op == "OR": return a | b
if op == "LSHIFT": return a << b
if op == "RSHIFT": return a >> b
</code></pre>
<p>Nadaljevati vrstico za dvopičjem velja za tako grdo navado, da študentom
za to možnost niti ne povem. Tistim, ki tako pridno berejo rešitve domačih
nalog, da so prišli do sem, pa že lahko zaupam, da tega ne bodo počeli brez
dobrih razlogov. Tule je že eden: tole je na ta način vendarle veliko
preglednejše.</p>
<h2>Funkcija <code>compute_list(exprs)</code></h2>
<p>Navodila so tokrat vsebovala daljši namiv:</p>
<p><code>compute_list</code> naj najprej sestavi prazen slovar, v katerega bo sproti
zapisovala imena spremenljivk (kot ključe) in vrednosti, ki jih naračuna.
Nato naj gre čez seznam izrazov. Iz terke z argumenti naj s pomočjo
funkcije <code>get_values</code> sestavi terko z vrednostmi teh argumentov (pri tem
uporablja slovar z dosedaj izračunanimi vrednostmi). Operator in to terko
da funkciji <code>compute_expr</code>; rezultat tega izračuna shrani v slovar.</p>
<p>Če dobro razumemo namig, je funkcija zelo preprosta.</p>
<pre><code>def compute_list(exprs):
"""Compute a list of expressions; return a dictionary with names and values
Args:
exprs (list): a list of expressions
Returns:
dict: dictionary with names of output variables and the corresponding
values
The function assumes (without checking) that expressions are valid and
that they can be evaluated from top to bottom.
Example:
Call ::
compute_list([('a', 'SET', (12,)),
('b', 'NOT', ('a',)),
('c', 'LSHIFT', ('a', 2)),
('d', 'AND', ('b', 'c'))])
returns `{'a': 12, 'b': -13, 'c': 48, 'd': 48}`, which corresponds to
`{'a': 12, 'b': ~12, 'c': 12 << 2, 'd': ~12 & (12 << 2)}`.
"""
variables = {}
for var, op, args in exprs:
variables[var] = compute_expr(op, get_values(args, variables))
return variables
Tu skoraj ni kaj komentirati. Gremo čez izraze. Argumente damo v get_values,
da izračuna njihove vrednosti; pri tem si pomaga s slovarjem variables, ki
sicer nastaja sproti. Argumenti gredo skupaj z operacijo op v funkcijo
compute_expr. Rezultat shranimo v variables[var], kjer bo na voljo
za prihodnje klice get_values in, seveda, za return.
Ocena 9
Funkcija dict_expr(exprs)
def dict_expr(exprs):
"""Construct a dictionary from a list of expressions
Args:
exprs (list): a list of expressions
Returns:
dict: dictionary with names of output variables as keys and tuples with
operands and arguments as values
Example:
Call ::
dict_expr([('a', 'SET', (12,)),
('b', 'NOT', ('a',)),
('c', 'LSHIFT', ('a', 2)),
('d', 'AND', ('b', 'c'))])
returns ::
{'a': ('SET', (12,)),
'b': ('NOT', ('a', )),
'c': ('LSHIFT', ('a', 2)),
'd': ('AND', ('b', 'c'))}
"""
return {var: (op, args) for var, op, args in exprs}
Tole je čista tehnična zadeva - samo seznam preobrnemo v obliko, v kateri
bo uporabnejši za "pravo" funkcijo, compute.
Funkcija compute(var, exprs, variables)
def compute(var, exprs, variables):
"""Return the value of a variable given a list of expressions and values
This function is similar to :obj:`compute_list` except that it evaluates
the expressions in a different order if needed. For instance, it computes
[('b', 'SET', ('a',)),
('a', 'SET', (42, ))]
by first computing `a` and then `b`.
The function assumes that the list of expressions is valid and that
each variable appears as output only once.
The function may modify the dictionary `variables` by adding the
intermediate results, that is, the values of variables that are computed
in while computing the value of the target variable `var`.
Args:
var (str): the name of the variable to compute
exprs (dict): a dictionary with expressions (see :obj:`dict_expr`)
variables (dict): known variable values
Returns:
int: the value of variable `var`
Examples:
Call `compute('b', {'b': ('SET', ('a',)), 'a': ('SET', (42, ))}, {})`
returns `42`.
Call `compute('b', {'b': ('SET', ('a',))}, {'a': 42})` also returns
`42`.
"""
op, args = exprs[var]
for arg in args:
if isinstance(arg, str) and arg not in variables:
variables[arg] = compute(arg, exprs, variables)
return compute_expr(op, get_values(args, variables))
Namig je bil takšen: funkcija compute bo rekurzivna: za vsako spremenljivko,
katere vrednosti ne pozna, vendar jo potrebuje, pokliče samo sebe. Pri tem je
pomembno, da vse, kar naračuna, sproti beleži v variables, da ne bo večkrat
računala enih in istih stvari.
Vemo, katero spremenljivko moramo izračunati, vars. Iz slovarja zato
preberemo operacijo in argumente. Če bi takoj poklicali
variables[var] = compute_expr(op, get_values(args, variables)), kot smo
počeli pri funkciji iz prejšnje naloge, to ne bi bilo dobro, saj vrednosti
te spremenljivke morda še ne poznamo. Zato gremo najprej previdno čez
vse argumente, for arg in args. Preverimo, ali je argument morda niz
(ime spremenljivke) in v tem primeru ga (rekurzivno) izračunamo in dodamo
v slovar:
for arg in args:
if isinstance(arg, str):
variables[arg] = compute(arg, exprs, variables)
Če bi delali tako, bi program deloval pravilno, ne bi pa bil nujno ravno hiter.
Ko smo reševali naloge z rodbino, je bil vsak otrok otrok le enega starša. Ker se Adamovi potomci niso možili in ženili med sabo, je od kogarkoli do kateregakoli od potomcev vodila le ena pot. Tu ni nujno tako. Ista spremenljivka se lahko pojavi kot vhod za več drugih spremenljivk. Zato se lahko zgodi - in tudi se zgodi - da isto vrednost računamo zelo velikokrat. Zato dodamo še nekaj
for arg in args:
if isinstance(arg, str) and arg not in variables:
variables[arg] = compute(arg, exprs, variables)
Vrednost računamo le, če je še nimamo v slovarju. Ker si v vseh rekurzivnih klicih delimo isti slovar (ponovno premislite zapiske s predavanja o imenskih prostorih, če ste jih morda pozabili), stalno dodajamo v en in isti slovar, zato bomo vsako stvar računali le enkrat.
Ostalo je enako kot pri compute_list iz prejšnje naloge.
Funkcija compute_file(var, filename)
def compute_file(var, filename):
"""Return the value of a variable for the expressions in the given file.
The function is similar to compute except that it reads expressions from
the file and then calls `compute`.
Args:
var (str): the name of the variable to compute
filename (str): file name
Returns:
int: the value of `var`
"""
return compute(var, dict_expr(read(filename)), {})
Ni vredno besed. Funkciji dict_expr damo odprto datoteko. Brala jo bo v
zanki for, torej po vrsticah.
Ocena 10
Funkcija computable(exprs)
def computable(exprs):
"""Check whether the list of expressions is computable.
The list is not computable is some variables appear as outputs without
appearing as inputs or if there are cycles, like in the following case::
[('a', 'SET', ('b',)),
('b', 'SET', ('c',)),
('c', 'SET', ('a',))
Note that cycles can also be more complicated, like in this case ::
[('a', 'AND', ('b', 'd')),
('b', 'AND', ('c', 'd')),
('c', 'LSHIFT', ('f', 2)),
('d', 'OR', ('c', 'f')),
('e', 'NOT', ('d',)),
('f', 'SET', ('g',)),
('g', 'SET', ('a',))]
where *g* needs *a*, *a* needs *b* and *d*, *b* needs *c* and *d*,
*c* needs *f* and *f* needs *g*, which completes the cycle.
Args:
exprs (list): a list of expressions
Returns:
bool: `True` if expressions can be evaluated, `False` otherwise
"""
if not check_names(exprs):
return False
unknown = dict_expr(exprs)
while unknown:
vars = list(unknown.items())
for var, (op, args) in vars:
if all(arg not in unknown for arg in args):
del unknown[var]
if len(vars) == len(unknown):
return False
return True
Najprej preverimo, ali se vsi vhodi pojavijo kot izhodi. Če se ne, smo končali: izrazov se ne da izračunati.
Sicer sestavimo slovar izrazov, kakršnega smo uporabljali pri nalogi za oceno
9. Slovarju bo ime unknown in v njem bo vse, za kar še nismo prepričani, da
znamo izračunati.
Nato ponavljamo tole. Iz slovarja naredimo seznam parov z imenom
spremenljivke, operatorjem (ki ga niti ne potrebujemo) in argumenti. Zakaj ta
seznam, bomo videli. Gremo čez seznam in preverimo, ali drži, da nobeden
od argumentov ni v slovarju stvari, ki jih (še) ne znamo izračunati,
if all(arg not in unknown for arg in args). Če to drži, bi znali to
spremenljivko izračunati, torej ni nobenega razloga, da bi bila v slovarju
reči, ki jih ne znamo izračunati - torej jo pobrišemo iz njega,
del unknown[var].
Ko tako pobrišemo vse, kar bi znali izračunati, preverimo, ali smo v resnici kaj pobrisali: je velikost slovarja manjša od velikosti seznama, v katerega smo ga skopirali? Če ni, ni mogoče pobrisati (izračunati) ničesar več, torej imamo neka krožna sklicevanja. Če se je slovar zmanjšal, pa nadaljujemo z brisanjem, dokler se reč ne ustavi ali slovar izprazni.
Zakaj je bilo potrebno kopiranje v seznam? Z zanko for ne smemo hoditi prek stvari, iz katere znotraj zanke brišemo (ali vanjo dodajamo) elemente. Kaj se zgodi v takšnem primeru, ni jasno določeno - odvisno je od naključja.
To seveda ni edina možna rešitev. Matematiki bi rekli, da je to, kar počnemo, preverjanje, ali v grafu obstaja cikel. Algoritmov za to je na pretek.
Druge rešitve naloge za oceno 9
Slovar kot v nalogi za oceno 10
Pri reševanju naloge za oceno 9 smo napisali funkcijo, ki gleda, kaj bi znala izračunati. Namesto tega lahko računa, kar zna. Ko naračuna, kar iščemo, to vrne.
def compute(var, exprs, variables):
while True:
for var1, (op, args) in exprs.items():
if all(arg in variables for arg in args if isinstance(arg, str)):
variables[var1] = compute_expr(op, get_values(args, variables))
if var in variables:
return variables[var]
Tako kot predvideva naloga, bomo vse, kar naračunamo, shranjevali v
variables.
Funkcija se v zanki for znova in znova in znova sprehaja prek vseh izrazov.
Za vsakega preveri, ali so vsi njegovi argumenti v variables - točneje, vsi
argumenti, ki so imena spremenljivk, ne konstante. Če so, s compute_expr
izračuna vrednost in jo shrani v variables.
Po vsakem krogu računanja preveri, ali je morda naračunal vrednost iskane spremenljivke. Če je, jo vrne, sicer gre ponovno čez izraze.
Prepustimo težave Pythonu
Tule je rešitev celotne naloge, skupaj z branjem podatkov - torej brez uporabe katerekoli funkcije, ki smo jo napisali pri ocenah za nižje naloge.
Rešitev uporablja nekaj reči, ki se jih še nismo učili; nekaterih se niti ne bomo.
def read(filename):
from functools import reduce
import keyword
replacements = [("AND", "&"), ("OR", "|"), ("NOT", "~"), ("LSHIFT", "<<"), ("RSHIFT", ">>")] + \
[(x, x + "_") for x in keyword.kwlist]
definitions = []
for v in open(filename):
expr, name = v.strip().split("->")
definitions.append(reduce(lambda o, s: o.replace(*s), replacements, "{}={}".format(name, expr).strip()))
return definitions
def compute(var, definitions):
while True:
for expr in definitions:
try:
exec(expr) # If it fails, don't mind
return eval(var)
except:
pass
Prvi del je branje podatkov. Datoteko spremeni v seznam nizov, ki so videti
kot izrazi v Pythonu. Tako iz, na primer, a AND b -> c naredi c = a & b.
Poleg tega se znebi imen spremenljivk, ki so enaki ključnim besedam v Pythonu:
if spremeni v if_, or spremeni v or_ in tako naprej.
Drugi del reši nalogo na podoben način kot rešitev, ki smo jo videli prejle.
Gre prek seznama izrazov (definitions). Vsakega poskusi izvesti: exec je
funkcija, ki izvede niz. exec("c = a & b") naredi isto, kot če bi na tem
mestu v programu v resnici pisalo c = a & b. Nato vrne vrednost iskane
spremenljivke; dobi jo z eval(var).
To seveda ne deluje. Večine izrazov se (še) ne da izračunati. In tudi
return var bo deloval šele po tem, ko bomo v resnici izračunali vrednost
iskane spremenljivke. A nič ne de: če pride do napake, z blokom try-except
(ki ga še ne poznamo) Pythonu rečemo, naj napako ignorira in računa naprej.
Rekurzivna rešitev z regularnimi izrazi
Tudi tule prvi del le bere podatke, drugi del - funkcija solve_for pa
računa. Funkcija solve_for - ki opravi vse delo, brez klicanja drugih
funkcij! - je dolga le eno vrstico!
from functools import reduce, lru_cache
import re
# Change expressions to Python expressions, store in dictionary
# For instances, `a AND b -> c` becomes declaratiion['c'] = 'a & b'
replacements = [("AND", "&"), ("OR", "|"), ("NOT", "~"), ("LSHIFT", "<<"), ("RSHIFT", ">>")]
declaration = {}
for v in open("input.txt"):
expr, name = v.strip().split("->")
declaration[name.strip()] = reduce(lambda o, s: o.replace(*s), replacements, expr)
# Find the number by recursively evaluating expressions, using regular expressions
# to replace variable names with values
@lru_cache(10000) # This is important: do not compute the same thing twice!
def solve_for(name):
return str(eval(re.sub("[a-z]+", lambda mo: solve_for(mo.group()), declaration[name])))
Funkcija vsebuje več reči, ki se jih nismo in ne bomo učili, zato je tudi tule ne bomo posebej razlagali. Kdor hoče, pa se lahko poglobi.