Playing with toy programming problems can be fun, and also be useful in order to revisit some concepts and preconceived ideas.
Here is one that I encountered recently, called Staircases: acm.timus.ru/problem.aspx?num=1017&locale=en
In short:
N
bricks and all of them must be used to build a staircaseThe program reads the number of bricks N
from the standard input, and outputs the number of possible staircases C
to the standard output.
This problem can be solved using a technique called Dynamic Programming. There are already plenty of resources online covering the topic.
This post will be very practical. We will only focus on the use of Python (3.5.1+) for solving this problem, and describe different ways to approach it.
Dynamic programming is based on the concept of states or sub-problems, with the idea of finding a solution for a bigger problem given the solutions to sub-problems it depends on.
In this case, a state can be defined as: (height of the current stair, number of bricks left)
. Moving to the next state is possible only if there are enough bricks left, under the constraint that the next stair must be higher than the previous.
In Python, it can be implemented like this:
Let’s try with a small number of bricks:
It gives the right answer. And now with a bigger number N
:
I had to stop the execution as it was taking too long! The search space turns out to be quite big, which is why the program times out. The issue is caused by the same states being computed several times, which can be cached instead.
Since we are using Python, it would be great to add the caching mechanism in the most pythonic way. Fortunately, Python provides the functools
module with a lru_cache
decorator. Let’s try it. It is the same code as before with just two new lines.
Still gives the right answer. Let’s try with a bigger N:
Ouch, we hit the recursion limit. This is too bad, because the implementation looked very clean and pythonic. It felt like the right thing to do. Although the use of function decorators is elegant, it adds extra function calls (a decorator is a wrapper function).
We can convince ourselves by looking at the source code for the lru_cache
: github.com/python/cpython/blob/3.5/Lib/functools.py#L391. Whenever the user function is called (our count
function), many more functions will also be called (decorating_function
> wrapper
…) to check if the value has already been computed before.
sys.getrecursionlimit()
returns 1000
on my machine (CPython 3.5.1). So getting this RecursionError makes sense since the program will go at least 500 levels deep by just calling the count
function (for the largest N), and the decorator adds 3 more levels of overhead in the worst case.
How to fix this?
The simplest is to raise the recursion limit.
Which runs quite decently:
It works for this toy problem, BUT this can be considered quite dangerous for real programs. Python sets a recursion limit to avoid C stack overflows (CPython). So for real world applications, changing this limit must be done with care as advised in the documentation.
Another way to solve this problem without using decorators is to implement our own memoization. This basically means adding a dictionary or lookup table to retrieve solutions to sub-problems more quickly.
The implementation is straightforward as it is again just a slight modification of the previous code:
Not very pythonic but it does the job.
One way to avoid recursion problems is to build the solution bottom-up instead of top-down. The bottom-up approach is also called the tabular method, as it mainly consists of looping through a multi-dimensional array (usually 2D or 3D), starting from the base cases. I tend to think this method is slightly more difficult to implement, because it is not as intuitive as the top-down approach.
Here is one possible bottom-up implementation for the same problem:
The running time is similar to the top-down approach, but we can notice it is a little bit slower than for the custom memoization implementation. In the bottom-up approach, all the states are visited (2 for-loops => 500 ** 2 = 250000 states). In the top-down approach, only the states that are needed are computed. This is why sometimes one method will be faster than the other, depending on how frequently states are visited.
Although Python could be well suited for toy problems like this one, the use of “magic” functions can sometimes trick us when we are not entirely sure what’s happening under the hood.
The main issue with dynamic programming in Python is the recursive aspect of the method. Recursivity brings many function calls, and function calls in Python are slow due the additional overhead. In this post, we saw how to approach the same problem in different ways to overcome this issue.
That’s it!
comments powered by DisqusBy Jeremy Tuloup – 2018 – Theme by bootswatch (slightly tweaked)