Testi

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 je b neka spremenljivka (pobrali smo jo v var), a pa je lahko ime ali številka. Naloga pravi, da številke pretvorimo v številke, torej pokličemo to_number. Operacija (op) je torej "SET", argumenti (arg) pa s[0], ki ga spravimo skozi to_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 dali to_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 je op prvi 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.

Last modified: Thursday, 25 March 2021, 9:05 PM

Testi

Naloge

Vse funkcije

Vsebina po ocenah

Ocena 6

Funkcija to_number(s)

Funkcija parse(s)

Funkcija read(filename)

Ocena 7

Funkcija outputs(exprs)

Funkcija inputs(exprs)

Funkcija check_names(exprs)

Funkcija check_operators(exprs)