Dynamic programming

Dynamic Programming (DP) problems are fun, but they can be also difficult to solve. For a better definition than I could give you here I'll redirect you to the Wikipedia article, and there are some nice tutorials and sample problems in TopCoder and CodeChef. In this post I'm just going to add commentaries to the DP problem I solved previously without giving much explanation. This problem comes from the Project Euler site:

An n×n grid of squares contains n^2 ants, one ant per square.
All ants decide to move simultaneously to an adjacent square
(usually 4 possibilities, except for ants on the edge of the grid or at the corners). 
We define f(n) to be the number of ways this can happen without any ants ending on 
the same square and without any two ants crossing the same edge between two squares.
You are given that f(4) = 88. Find f(10).

So where to start? Well, if Mr. Intelligence is not around you can always trust in your old pal the Brute Force. In this post I sketched the code for computing (and drawing) all the different board positions for (n = 4) using a DFS algorithm:

Let's try to guess how much time it would take this algorithm to calculate the number of possible boards when (n = 10). Every ant can move to 2, 3 or 4 cells, however the limitations of 2 ants never crossing the same border and not leaving empty cells make the real options less than 4, lets say that in average every ant has 2 possible options, because there are (n^2) ants this means that there are still (2^(n^2)) = 2^100 different boards. For give you an idea about how much time it would take to compute this, lets say we are using C, and that the code to compute one final board position is almost trivial as the code below:

If this were the case the time my computer would take to compute 10^9 boards would be nearly 0.8 seconds (with an Intel Core 2 Duo at 2.4 GHz for processor). Lets round that time to one second for 10^9 boards, therefore it would take (2^100/10^9) seconds to compute all the other boards. This is more than 40 millions of millions of years! Forever. However, this is just a wild guess, we'll see that the constraints in this particular problem are a lot more restrictive and that the real answer is not that big, (more in the order of 2^57) and I'll need to await "only" 1300 days to get the answer.

So, How do we compute this faster? This is where DP comes to save the day. The main idea behind DP is to construct the final answer from the smaller parts. What is the smallest part in this problem? A single cell. We need to find a way to construct the final board adding one cell in every step. With every added cell we need to maintain the list of incomplete boards already formed. The total number of these boards when the whole board is assembled is our answer. Easier said than done, let's go step by step. What are the valid moves for the first cell?

Every arrow is an ant passing the border going inside or outside the cell. As we add cells to our zone (the solid color) we need to check that the number of arrows entering the zone is equal to the number of arrows leaving the zone, because the contrary would imply that there are empty cells or cells with more than one ant per cell in the zone. What are examples of invalid moves?

The first case is invalid because we need all the ants to move. We can not add a cell to the occupied zone without ants crossing that cell. The second case is invalid because it would create a cell with more than one ant in the cell. The third case is invalid because it needs that 2 ants are already in the cell, which is not permitted. The fourth case is invalid because the problem states that 2 ants can not pass the same border.

The tree below shows the whole process for (n = 2) considering only valid moves. Every node is an incomplete board and their children are linked by lines. Every step is a row in the graph. The cell that we'll add to our zone in the next step in marked with a red border. As expected there are only 2 ways to assemble the final board:

Lets do some steps for the case of (n = 4):

There are invalid nodes that are discarded like nodes 4.2 and 6.8, and some nodes that are duplicated and we consolidate in one like 6.6. Every parent can have at most 2 children, some parents have 1 or no children so we could have better estimated the number of options per cell as 1.5 instead of 2 and our wild guessing of the number of final boards would be (1.5^(n^2)) instead of (2^(n^2)). We could start coding the solution sketched up to this point. However there are some observations that would help us to simplify the solution.

The first observation looking at the above graph is that in every step not all the cells are required to deduce the next board, all the action is happening in the border between the zone and the empty board, so we could ignore all the board cells except the cells at the zone frontier (the ones marked with red at the right):

The second observation is more tricky and easy to miss. It comes from the realization that for every iteration it really doesn't matter if the arrows go inside or leave our zone from the bottom or the right border. The result is the same:

So we reduce our possibilities for every cell as EMPTY (no ants crossing the border), IN (an ant going inside the occupied zone), OUT (an ant leaving the zone), IN+OUT (2 ants passing the cell border). This reduces the above graph to this:

The code for generating the next step can be deduced following the graph below:

Additionally, we'll need to check for valid ranges and avoiding to create invalid cells, like for example: we can't add arrows to the right if we are in the last column, or arrows to the bottom if we are in the last row, or an arrow to the bottom if there is already an arrow with the same type there. The script below shows the steps for (n = 4):

How much time would take this algorithm to find the answer? Every cell has 4 options, there are (n) cells in the border, so in every step would be a maximum of (4^n) nodes, there are (n^2) steps (one step for every cell) so we could guess it would take (n^2)*(4^n) steps to find the answer (if we use a hash data container to look for duplicated nodes in constant time). For (n = 10) this is 100*4^10 (nearly 10^8). We can finish this in C in less than a second! This is an impressive improvement compared to awaiting 1300 days.

I hope that with this explanation you are ready to code the solution for yourself. However, if that is not the case, there is not helping but sitting with a pencil and paper and trying by hand the above steps. The little fella below approves: