I am going to try my best to publish my process (and hopefully, results) to each of the Daily Coding Problems here. I make no claims that I know what I am doing, that I have an efficient answer, or that any of this will make sense. Let’s get started.
There is an N by M matrix of zeroes. Given N and M, write a function to count the number of ways of starting at the top-left corner and getting to the bottom-right corner. You can only move right or down.
For example, given a 2 by 2 matrix, you should return 2, since there are two ways to get to the bottom-right:
- Right, then down
- Down, then right
Given a 5 by 5 matrix, there are 70 ways to get to the bottom-right.
Having not really thought about this at all, I think the best way to start this kind of open-ended problem is to start with the base cases, work through the weird outliers, and then get to the general case.
I’ll try to do that here.
To start this problem, I began with the simplest possible solution — a 0x0 matrix. This might be more of an edge case, but it gave me somewhere to start.
The challenge with this 0x0 matrix is it really doesn’t have any “paths” so to speak, so I set the result to 0. In fact, any Nx0 matrix should have a result of 0.
That’s awesome. Phew. Except I’m really no closer to a general answer.
Next: 1x1 Matrix. There are no paths again, so the answer here is also 0.
Following that, what about a 2x1 Matrix?
I suppose the simple answer is there is 1 path.
3x1? Again, 1 path.
Nx1? A more general solution, but any Nx1 matrix will have 1 path.
Here we start to approach a general case.
The 2x2 Matrix I decided to represent as follows. The matrix can be represented by a 2x2 grid of vertices and edges, as shown:
We see here there are 2 paths, so a 2x2 Matrix gives a result of 2.
More General Matrices, First Calculations
I first started counting the number of paths and quickly discovered there are 3: DRR, RDR, RRD. I noticed a few things quickly here: a 3x2 matrix has the same number of paths as a 2x3 matrix.
In more math-y terms, the answers are symmetrical:
f(2,3) = f(3,2)
I then began to wonder if there was a simple function to calculate the number of paths based on the size of the matrix, ie:
f(N,M) = some weird function
The best way I know to fit that together is to simply calculate the results until it gets pretty ridiculous. I also noticed, that because we are talking about 2 variables producing one number (the number of paths), that would make a whole lot more sense in a table. So I just drew the diagrams and did the calculations all the way up to 4x4:
At this point I realized the path calculations were getting a bit crazy and I was having trouble keeping track of them all, so I turned back to my formula to see if I could get it to match:
f(N,M) = max(N,M)*(min(N,M)-1)
This doesn’t quite work for anything in the 1’s column, but maybe those were exceptions?
This made sense for everything in the 2 column, and eventually for 3x3.
At 4x3 it stopped making sense, so I drew a diagram:
This is just the same path diagram turned 45 degrees to look like at tree (so D,R = R,L) and I wondered if just adding up the number of edges leaving a point would add up, or if there was some kind of calculation here.
Then I thought maybe it was the sum (or some kind of sum-product) of each point minus 1 (I was getting a bit desperate here). None of the math was working quite right.
So I wrote it out in a matrix (to go back to that) and that sparked an idea:
Could this problem be solved with recursion?
Investigations into Recursion
I’ve been solving a lot of other similar problems with recursion lately, so this would not be that different. The key point of something being recursive has to do with a base case, and then a recursive calculation that occurs to generalize each of the next points from there.
I quickly noticed the following:
3x2 Matrix is just a 2x2 Matrix with some extra options as shown:
And another way to show this is that the new 3x2 matrix options are L to the beginning of the 2x2 matrix, or as it happens, R to the 3x1 matrix, as shown below:
Written as an algorithm:
f(3,2) = f(2,2) + f(3,1)
This looks very recursive to me.
A few more tests here: what if we go to 3x3?
General Recursive Case
This is where it gets amazing (and starts to come together).
The 2 options to start a 3x3 matrix are: L to a 3x2, or R to a 2x3.
But a 2x3 matrix is the same (in terms of # of paths) as a 3x2 matrix.
f(3,3) = f(3,2) + f(2,3) = 2 x f(3,2) = 2 x 3 = 6
A testable formula starts to emerge here:
f(N,M) = f(N,M-1) + f(N-1,M)
I try this with a few other points and it seems to work out.
Therefore, the formula is as follows:
if N or M = 0, f(N,M) = 0
if N or M = 1, f(N,M) = 1
else f(N,M) = f(N-1,M) + f(N,M-1)
At this point I had a related thought:
I have been learning about Dijkstra’s algorithm in another project I’m working on, where the way to find the shortest path between to points is to track how long it has taken to get to that path and store that value as the point on the path.
How that relates is: for each cell in an NxM matrix, why not store the result in an NxM matrix?
That’s what I was doing above when calculating the result for each resulting N and M, but why not formalize it?
This would produce a “master” matrix will all the solutions readily available to a given size. If you don’t expect a matrix larger than say, 20x20, you could quickly calculate the result of any matrix with size of 20 or less, store that result, and quickly look up the answer. This, I suppose, would be the “dynamic” result.
The first is the recursive answer:
if N ≤ 0 or M ≤ 0: return 0
if N = 1 or M = 1: return 1
return f(N-1,M) + f(N,M-1)
The second is more complicated in fact, but gives the master table answer:
Generate the table:
size = 20 (for an arbitrarily large size, say 20x20)
for i from 0 to size:
for j from 0 to size:
if i = 0 and j = 0, arr[i][j] = 0
else if i = 1 or j = 1, arr[i][j] = 1
else, arr[i][j] = arr[i-1][j] + arr[i][j-1] **
Return the value:
if N ≤ 0 or M ≤ 0, return 0
else, return arr[N-1][M-1]
**Note: the -1 is to deal with the way the array stores from 0 up to the size
The first answer is much cleaner code, but because it is recursive, is likely to break the system at much higher values (say 20x20). The second answer will work up to very, very high numbers.
What if you had a 3-dimensional array and could move Down, Right or Back? How would that change the problem?
It gets a lot more complicated, but the solution techniques are the same!
Hint: If one of the dimensions = 1, its a 2D problem. Otherwise, you have to consider 3 movements (Right, Down, Back).
Turns out the master table technique gets WAY more crazy. The recursion technique is very, very simple.
What about an N-Dimensional array?
A few final notes:
This was a much easier problem to solve on paper first before writing the code. Having a finished solution in my notebook before typing anything into Sublime was a great choice.