NxM Paths Matrix Problem

Photo by Chris Ried on Unsplash

Background:

Instructions:

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.

Process:

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.

0x0 Matrix

That’s awesome. Phew. Except I’m really no closer to a general answer.

1x1 Matrix

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.

2x2 Matrix

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:

2x2 Matrix to 2x2 Point and Edge Diagram

We see here there are 2 paths, so a 2x2 Matrix gives a result of 2.

More General Matrices, First Calculations

In more math-y terms, the answers are symmetrical:

f(2,3) = f(3,2)

2x3 Matrix to 2x3 Point and Edge Diagram

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:

It got hard to calculate after this…

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:

4x3 Matrix in Tree Diagram Format

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.

This is not quite right.

So I wrote it out in a matrix (to go back to that) and that sparked an idea:

Kinda thinking in circles here.

Could this problem be solved with recursion?

Investigations into Recursion

I quickly noticed the following:

3x2 Matrix is just a 2x2 Matrix with some extra options as shown:

3x2 = 2x2 + some other stuff

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:

Aha! Getting somewhere.

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

The 2 options to start a 3x3 matrix are: L to a 3x2, or R to a 2x3.

3x3 = 2x3 + 3x2

But a 2x3 matrix is the same (in terms of # of paths) as a 3x2 matrix.

In math:

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.

Two Solutions

f(N,M):

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.

You can find the code snippets here.

Extensions

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?

Mind. Blown.

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.

Brendan is a Mechanical Designer at Nymi, and blogs about startups, mental models and why hardware is hard here. He’s a Venture for Canada alumni, coffee aficionado, and cookbook collector. He’s learning python.

Mechanical Designer. Hardware Enthusiast. VFC 2015 Alumni.