Reading Time: 9 minutes

In October 2020 I took Dave Beazley’s Advanced Programming with Python course. Since I wrote a series about his SICP course and the Raft course, I figured I’d write about this one too :).

In the last post I asked you to consider this

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

how would you solve it in Python?

Option 1: Chaos

Suppose we represent the tenant arrangement with a list of their names, with the index of the list representing the floor they live on, and we codify all of our requirements like so:

while tenants.index("Baker") == 4 or \
        tenants.index("Cooper") == 0 or \
        tenants.index("Fletcher") == 0 or \
        tenants.index("Fletcher") == 4 or \
        tenants.index("Miller") < tenants.index("Cooper") or \
        tenants.index("Smith") + 1 == tenants.index("Fletcher") or \
        tenants.index("Smith") - 1 == tenants.index("Fletcher") or \
        tenants.index("Fletcher") + 1 == tenants.index("Cooper") or \
        tenants.index("Fletcher") - 1 == tenants.index("Cooper"):
            #put the names in the tenants list in a different order and try again

    return iterations, tenants

You could move systematically through the permutations. I didn’t because I’m lazy and chaotic:

def sort_tenants():
    tenants = ["Baker", "Cooper", "Fletcher", "Miller", "Smith",]
    iterations = 0

    while tenants.index("Baker") == 4 or \
        tenants.index("Cooper") == 0 or \
        tenants.index("Fletcher") == 0 or \
        tenants.index("Fletcher") == 4 or \
        tenants.index("Miller") < tenants.index("Cooper") or \
        tenants.index("Smith") + 1 == tenants.index("Fletcher") or \
        tenants.index("Smith") - 1 == tenants.index("Fletcher") or \
        tenants.index("Fletcher") + 1 == tenants.index("Cooper") or \
        tenants.index("Fletcher") - 1 == tenants.index("Cooper"):
            random.shuffle(tenants)
            iterations += 1

    return iterations, tenants

iterations, tenants = sort_tenants()
print(f"Arrived after {iterations} iterations")
print(f"result: {tenants}")

The results on this were terrible:

Arrived after 262 iterations
result: ['Smith', 'Cooper', 'Baker', 'Fletcher', 'Miller']

Arrived after 53 iterations
result: ['Smith', 'Cooper', 'Baker', 'Fletcher', 'Miller']

Arrived after 201 iterations
result: ['Smith', 'Cooper', 'Baker', 'Fletcher', 'Miller']

That doesn’t look like a lot of iterations, but in a list of 5, there are only 5 factorial (5!) ways to arrange the items. 5 x 4 x 3 x 2 x 1 = 120. So where it says “Arrived after [more than 120] iterations”, the random shuffle hit the same wrong permutations more than once. It might be better to systematically cycle through the options.

Option 2: Brute Force, but at least it’s organized

So, we could delineate the options like this:

    baker={1, 2, 3, 4, 5}
    cooper={1, 2, 3, 4, 5}
    miller={1, 2, 3, 4, 5}
    fletcher={1, 2, 3, 4, 5}
    smith={1, 2, 3, 4, 5}

And write a function that outputs all the different possible combinations of these as dictionaries*:

def all_candidates(named_option_sets):
    import itertools
    keys = list(named_option_sets)
    for vals in itertools.product(*named_option_sets.values()):
        yield (dict(zip(keys, vals)))

*In general, don’t import stuff inside random functions; do it at the top of the file so that anything that might need to be installed for this set of tools to be used gets called out immediately. This blog post is a demonstration of Bending Rules in Python for Fun, not of recommended programming practices, so I left it here.

What that does is it turns this set:

{
'baker': {1, 2, 3, 4, 5}, 
'cooper': {1, 2, 3, 4, 5}, 
'miller': {1, 2, 3, 4, 5}, 
'fletcher': {1, 2, 3, 4, 5}, 
'smith': {1, 2, 3, 4, 5}
}

Into a set like this:

{
...
{'baker': 5, 'cooper': 5, 'miller': 5, 'fletcher': 5, 'smith': 1}
{'baker': 5, 'cooper': 5, 'miller': 5, 'fletcher': 5, 'smith': 2}
{'baker': 5, 'cooper': 5, 'miller': 5, 'fletcher': 5, 'smith': 3}
{'baker': 5, 'cooper': 5, 'miller': 5, 'fletcher': 5, 'smith': 4}
{'baker': 5, 'cooper': 5, 'miller': 5, 'fletcher': 5, 'smith': 5}
}

Then we can iterate through the combinations, running a function that checks all the requirements and fails if one of the requirements isn’t met:

def solver(check_requirements_func):
    def run_solver(**kwargs):
        for candidate in all_candidates(kwargs):
            try:
                check_requirements_func(**candidate)
            except BreaksTheRules:
                pass

    return run_solver

A Familiar Pattern?

Check out the pattern in this function here. What we have done is we have:

1. Defined an outer function that takes in a function as a parameter
2. Defined an inner function that takes in some arguments and calls the parameter function on those arguments until it doesn’t fail
3. Returned the inner function from the outer function.

It’s an odd pattern the first few times you see it, but a framework developer might recognize it: this is how you write a decorator function (known in some programming languages as an annotation function). If the decorator pattern is new to you, this video I made for my Python Programming students should help. After that video, you’ll recognize the above as “A decorator that accounts for the named parameters of the function it decorates” (run_solver would have to take in *args in addition to *kwargs to account for positional parameters, too).

Now we can annotate/decorate a function with this function, and define all the requirements in there, and fail if they aren’t true:

class BreaksTheRules(Exception):
    pass

@solver
def tenant_requirements(baker, cooper, fletcher, miller, smith):
    if baker == 4 or \
        cooper == 0 or \
        fletcher == 0 or \
        fletcher == 4 or \
        miller < cooper or \
        smith + 1 == fletcher or \
        smith - 1 == fletcher or \
        fletcher + 1 == cooper or \
        fletcher - 1 == cooper or \
        len(set([baker, cooper, fletcher, miller, smith])) < 5:
            raise BreaksTheRules()
    else:
        print(f"Solution: baker={baker} cooper={cooper} fletcher={fletcher} miller={miller} smith={smith}")

(Note the addition of a requirement at the end for the values at each name to be unique—we did not need this in the beginning when the names got their numeric values from their order, and therefore were guaranteed to be unique.)

We can then call this function to get our solutions:

>>> tenant_requirements(
    baker={1, 2, 3, 4, 5},
    cooper={1, 2, 3, 4, 5},
    miller={1, 2, 3, 4, 5},
    fletcher={1, 2, 3, 4, 5},
    smith={1, 2, 3, 4, 5},
)

Solution: baker=3 cooper=2 fletcher=5 miller=4 smith=1

We could add some syntactic sugar, if we like, by writing functions to encapsulate each requirement and raise BreaksTheRules if it doesn’t pass:

def require(test):
    if not test:
        raise BreaksTheRules()

def distinct(*vals):
    return len(set(vals)) == len(vals)

@solver
def tenant_requirements(baker, cooper, fletcher, miller, smith):
    require(distinct(baker, cooper, fletcher, miller, smith))
    require(baker != 5)
    require(cooper != 1)
    require(fletcher != 1 and fletcher != 5)
    require(miller > cooper)
    require(abs(smith-fletcher) > 1)
    require(abs(fletcher-cooper) > 1)
    print(f"Solution: baker={baker} cooper={cooper} fletcher={fletcher} miller={miller} smith={smith}")

And if we were to add that syntactic sugar, we wouldn’t be the first.

“Practical” Applications of Parametrized Decorators

The pystest unit testing library provides a number of annotations for party tricks like, say, defining a bunch of data examples up front and then looping through them in a test:

TEST_DATA = [
             ("", "", []),
             ("2", "2", [2]),
             ("2", "21, 1", []),
             ]

@pytest.mark.parametrize(str1, str2, expected_lst', TEST_DATA)
def test_find_twos(str1, str2, expected_lst):
    got_lst = find_twos(str1, str2)

    if sorted(got_lst) != sorted(expected_lst):
        fail_str = f'TCalled find_twos({str1},{str2})\nGot List:{got_lst}\nExpected List:{expected_lst}'
        pytest.fail(fail_str)

We can replicate this behavior in plain old Python (though in practice I’m not sure I’d use this because I find this test hard to read, and having a legible explanation of what a program does is like 50% of the reason to have tests in my opinion):

def my_parametrize(*args):
    def decorator(function):
        for example in args[-1]:
            function(*example)
    return decorator 

data = [
    ("x", "x"),
    ("2", "2"),
    ("2", "21")
]

@my_parametrize('one', 'two', data)
def test_one_two_equal(one, two):
    assert(one == two)
    
test_one_two_equal()

To be fair, annotations/decorators also do more useful things with this construct. Another Python unit testing library, appropriately named unittest, uses it for mocking:

from unittest.mock import patch, PropertyMock

@patch('app.computations.Scene.height', new_callable=PropertyMock, return_value=1000)
def test_y_scale(self, *args):
    assert(self.operation.y_scale==0.1)

Though I still actually don’t like this because decorators run from the inside out, which means that in a case like this with multiple things mocked…

@patch('app.computations.Scene.y_scale', new_callable=PropertyMock, return_value=0.1)
@patch('app.computations.Scene.top_edge', new_callable=PropertyMock, return_value=10)
@patch('app.computations.Scene.height', new_callable=PropertyMock, return_value=1000)
def test_transform_y(self, *args):
    assert(self.operation.transform_y(500)==60)
    assert(self.operation.transform_y(1000)==110)
    assert(self.operation.transform_y(1500)==110)

…the bottom one (mocking height) runs first, followed by mocking top_edge, followed by mocking y_scale. That’s not intuitive.

Popular Java unit testing libraries take this pattern even further. With a number of unit testing frameworks in Java, what you do is:

1. Make the test class inherit from some TestClass superclass
2. Annotate every test method in the class with @Test
3. Use provided matchers like .assertThat(), .isEqualTo(), or .hasValue(), which will raise custom failures with descriptive messages for debugging assistance

In practice, I don’t find the mechanics of the annotation appropriate for a lot of the testing uses I see. I do think they’re helpful, for example, in the Django web framework, where a developer can implement authentication and then place a @login_required annotation on any number of endpoints to mark them as requiring someone to sign in to visit them.

But the @solver, by visiting a maximum amount of work-done-by-decorator that’s maybe above my tolerance in a practical application, gave me a better idea of how they work and where it might (or might not) make sense to use them.

If this looks cool to you and you’d like to play with it, here’s what I recommend:

Try rewriting the solver and its helper functions to solve logic puzzles by a more elegant, perhaps more performant means. For example, for the five floors problem, perhaps your solution can detect that the requirements say that certain tenants don’t live on certain floors, and remove those floors from the set of options for those tenants—yielding a smaller set of possibilities in which to check the other requirements.

If you liked this piece, you might also like:

The Philosophy of Software Design series

How to Jump-Start a New Programming Language, or maybe, even, gain a more concrete mental model of the one you already use!

Lessons from Space: Edge-Free Programming, which also explores an Android app’s design and the engineering choices behind it (plus, cool pictures of rockets!)