Solving Algorithmic Problems in Python with Pytest2019-04-21
I occasionally enjoy solving algorithmic problems, for example Project Euler or The Advent of Code. I’ve been doing them since I was a pimply PHP-slinging teenager, competing with my peers across the UK in the British Informatics Olympiad. It was terribly nerdy and terribly fun.
Algorithmic problems are often used in technical interviews, which I find less fun. Strict deadlines stress me out.
In either case, using automated tests makes these problems way easier. I wish I knew this earlier!
Online algorithmic platforms, such as Codility, provide their own automated tests. You use these for basic validation on some examples, but edge cases are sneakily reserved for final marking. To ensure your solution covers all the bases, you need to write your own tests.
In Python, there’s no better test framework than Pytest - I use it on all my open source projects.
It makes it easy for you to add tests for any Python code.
And it’s much better than Python’s built-in
unittest is an old horse and cart, whilst
pytest is the batmobile.
Let’s look at a small problem together using Pytest. Here’s the problem statement:
Write a function
items, a list of integers, and returns the smallest integer greater than 0 that appears in the list, or 0 if there is none.
solution([1, 2])should return 1, and
solution([-1])should return 0.
itemswill contain up to 1,000,000 integers.
First, let’s write the most basic sketch of a
Since 0 is a default value to return, if we always return that we can score some easy points.
Create a file called
example.py with the contents:
Let’s test the function manually by running it in the Python 3 interpreter. Open the command line and run the examples:
So we failed on the first example, but succeeded with the second.
Doing this each time we modify the code would get tiresome quickly. We have to restart the interpreter, rerun the import and tests, and manually compare the outputs. Writing automated tests now, before we’ve tried to solve the problem properly, makes the whole loop faster. It also makes us think about all the cases up front.
Let’s write the tests and solve the problem with the Red, Green, Refactor pattern.
First, let’s add tests that fail.
Pytest can work with tests in the same file as our code, as simple functions with names starting
We use Python’s
assert statement to compare the results of our code with our expectations.
Add tests for the two examples:
Then install Pytest and run the tests:
In the middle of the output, we see the tests in
Pytest outputs an
F for the failing test, and a dot
. for the passing one.
FAILURES section expands on the failure with the line that failed.
It then shows that
solve([1, 2]) returned
0 which doesn’t compare equal to the expected value
The tests we have are a start but they don’t cover all the cases.
We don’t have any lists that contain
Also two extremes are missing: the empty list and a list of 1,000,000 items.
Long lists could also contain lots of negative or positive integers, so we should try both of these.
Let’s add more tests. We can make a list of 1,000,000 items in Python by multiplying a short list. Add these tests at the end of the file:
Run them again:
There are more failures - which is good!
Now we can work to a solution that makes all the tests pass.
solve with this first attempt:
Re-run the tests:
We have two different failures now. It seems we have yet to ignore negative numbers, woops!
Modify the solution to do so, by adding the
i > 0 condition:
Now re-run the tests:
Re-running the tests produces the same, all-passing output as above. Yay, we got the code down to one line!
I hope this tutorial has been useful, and you use this technique to level up your algorithmic game,
Thanks to Mafalda Marques for testing this tutorial.
© 2019 All rights reserved.