Sample 1: Circuits

The Circuit class represents a simulation of a Boolean circuit, with operations (a.k.a. gates) AND, OR, and NOT. You can also think of these as Boolean formulas. For example, the following tests simulate the formulas $0 \vee 1$, $0 \vee x$, $1 \wedge x$ and $\neg x$. Your main task is to write the eval method which takes a dictionary giving truth values for all used variables, and computes the resulting truth value.

def test_or1():
    circuit = Circuit('OR',False, True)
    assert circuit.eval({}) == True

def test_or2():
    circuit = Circuit('OR',False, 'x')
    assert circuit.eval({'x' : True}) == True

def test_and1():
    circuit = Circuit('AND', True, 'x')
    assert circuit.eval({'x' : True}) == True
    assert circuit.eval({'x' : False}) == False

def test_not1():
    circuit = Circuit('NOT', 'x')
    assert circuit.eval({'x' : True}) == False
    assert circuit.eval({'x' : False}) == True

Syntax and coverage

MARKS: 2

Submitted code should run without errors and have complete test coverage.

Operations

MARKS: 3

Starting with the following class skeleton, implement the NOT, AND, and OR operations. Your code should pass the single gate tests above.

class Circuit:
    def __init__(self, op, left, right=None):
        self.op = op
        self.left = left
        self.right = right

    def eval(self,assignment):
        # your code here

Combining gates

MARKS: 2

Implement support for left and right fields that are themselves Circuit objects. Hint: isinstance(v,str) tests if v is a string. Your code should pass the following tests.

def test_demorgan():
    circuit1 = Circuit('NOT', Circuit('AND','x','y'))
    circuit2 = Circuit('OR', Circuit('NOT','x'), Circuit('NOT','y'))
    for x,y in [(False, False), (False, True), (True, False), (True, True)]:
        assert circuit1.eval({'x': x, 'y': y}) == \
            circuit2.eval({'x': x, 'y': y})

def test_xor():
    circuit = Circuit('AND', Circuit('OR','x','y'),
                      Circuit('OR', Circuit('NOT','x'), Circuit('NOT','y')))
    assert circuit.eval({'x' : True, 'y' : True})==False
    assert circuit.eval({'x' : True, 'y' : False})==True

Error Handling

MARKS: 1

Implement appropriate error handling using exceptions. At least the following tests should pass.

import pytest
# undefined variable
def test_or4():
    circuit = Circuit('OR','x', True )
    with pytest.raises(RuntimeError) as e:
        circuit.eval({}) == True

# bad operator
def test_and5():
    circuit = Circuit('MAYBE','x', True )
    with pytest.raises(ValueError) as e:
        circuit.eval({}) == True

Arbitrary size circuits

MARKS: 2

Your eval method should work for arbitrary size circuits, including the following list like circuits.

def test_list():
    nodes = 256
    circuit=Circuit('NOT', f'y{nodes-1}')
    for j in range(0,nodes-1):
        circuit = Circuit('OR', f'y{j}', circuit)

    assert circuit.eval({f'y{j}' : False for j in range(nodes)}) == True
    assert circuit.eval({f'y{j}' : (j>=nodes-1) for j in range(nodes)}) == False

Bonus Question

MARKS: 2

Write the function tree to build a complete binary tree of ’AND’ gates, with ’NOT’ gates at the leaves. Your code should pass at least the following tests.

def test_tree1():
    circuit=tree(2)
    assert circuit == Circuit('AND',
                              Circuit('AND',
                                      Circuit('NOT', 'x0'), Circuit('NOT', 'x1')),
                              Circuit('AND',
                                      Circuit('NOT', 'x2'), Circuit('NOT', 'x3')))
def test_tree2():
    levels = 8
    circuit = tree(levels)
    assert circuit.eval({f'x{j}' : False for j in range(2**levels)})
    assert not circuit.eval({f'x{j}' : (j<1) for j in range(2**levels)})

To pass test_tree1, you will need to override __eq__; here is a possible implementation.

def __eq__(self, other):
    if not isinstance(self, other.__class__):
        return False
    return self.op == other.op and self.left == other.left and \
        self.right == other.right

Sample 2: Filter

Good solution

Define a class Filter whose constructor Filter(iterable, rules) takes two arguments, an iterator (e.g. a list) iterable, and a dictionary rules and whose instances support expressions of the form line in obj, which returns true if line in iterable, every key of rules with value True is a word in line, and no key with value False is a word in line. For 7 marks (roughly a “B”), your solution should

Have complete test coverage
Work for arbitrary list (for iterable) and dictionary (for rules) arguments.
Handle a missing rules argument correctly.
Pass the following tests.

list1 = [f'hello {n}' for n in range(10)] + ['hello world' ] + \
  [f'goodbye {n}' for n in range(10)] + [ 'goodbye world' ] + \
  [f'pi{n}' for n in range(10)] + [ 'pizza' ]

def contains_test(flt, tuple1, tuple2):
    assert 'banana' not in flt
    assert ('hello world' in flt, 'goodbye world' in flt, 'pizza' in flt) == \
        tuple1
    for n in range(10):
        f'hello {n}' in flt and f'goodbye {n}' in flt and f'pi{n}' in flt == \
            tuple2

def test_in_default():
    contains_test(Filter(list1), (True,True,True), (True, True, True))

def test_in_irrelevant():
    contains_test(Filter(list1, {'food' : False}),
                  (True,True,True), (True, True, True))

def test_in_exclude():
    contains_test(Filter(list1, {'world' : False}),
                  (False,False,True), (True, True, True))

def test_in_include():
    contains_test(Filter(list1, {'world' : True}),
                  (True, True, False), (False, False, False))

def test_in_include_exclude():
    contains_test(Filter(list1, {'world' : True, 'goodbye': False}),
                  (True, False, False), (False, False, False))

Full marks

In this part, you need to add support for the iterator protocol to your Filter class. For full marks, your solution must

Meet the requirements above.
Correctly implement the iterator protocol.
Work for arbitrary iterators as the iterable argument (i.e. not just lists).
Pass the following tests.

def test_default_filter():
    flt = Filter(list1)
    assert list(flt) == list1
    assert list(flt) == list1

def test_irrelevant_filter():
    flt = Filter(list1, {'food' : False})
    assert list(flt) == list1
    assert list(flt) == list1

def test_exclude():
    assert list(Filter(list1, {'world' : False})) == \
        [f'hello {n}' for n in range(10)] + \
        [f'goodbye {n}' for n in range(10)] + \
        [f'pi{n}' for n in range(10)] + [ 'pizza' ]

def test_include():
    flt = Filter(list1, {'world' : True})
    assert list(flt) == ['hello world', 'goodbye world']
    assert list(flt) == ['hello world', 'goodbye world']

def test_include_exclude():
    flt=Filter(list1, {'world' : True, 'goodbye': False})
    assert list(flt) == [ 'hello world' ]
    assert list(flt) == [ 'hello world' ]

def test_nest():
    flt1=Filter(list1, {'world' : True})
    flt2=Filter(flt1, {'goodbye': False})
    assert list(flt2) == [ 'hello world' ]
    assert list(flt2) == [ 'hello world' ]