Matrix/Grid Traversal

A common kdb interview question is to traverse a matrix (or grid) in kdb.

Let's take a look at how that can be achieved.

The Matrix

Assume you have a 3 by 3 matrix e.g.:

1 1 1

1 1 1

1 1 1

How many paths are there from the top left position (0,0) to the bottom right position (2,2) if you can only move right or down?

Because this is a small matrix, we can work it out visually:

There are 6 paths.

The traditional solution to this problem uses recursion. You can see the recursive solution to this problem using other languages here.

The key action at each stage of recursion is going to be to move either one step to the right or one step down. If we escape the boundary of the grid, stop and exit this recursion loop. If we reach the final destination, return a value to indicate that this is a valid path.

Recursive solution

Mark Kelly on stackoverflow has the best recursion solution:

f:{ 

// When you reach a wall, there is only one way to corner so return valid path 

if[any 1=(x;y);:1]; 

// Otherwise spawn 2 paths - one up, one right

:.z.s[x-1;y] + .z.s[x;y-1] 

 };

f[3;3]

The first thing to note is that the solution starts at the bottom right and works backwards. This allows the function to always end at '1' rather than having to end at a number that changes with the size of the matrix. 

Additionally, the solution recognises that once you hit a wall, there is only one valid way to go. Rather than waste time working out all of the invalid paths, it immediately returns as a valid path.

Iterative solution

However, in the world of kdb, recursion should rarely be used. q is a vector based programming language and works best when iterating over vectors - this is what separates it from most other languages. The traditional recursion solution for this problem might suit other languages but it doesn't suit kdb. 

At this point you may be wondering how it is possible to get the answer for this problem iteratively. This is where some prior mathematical/computer science knowledge is useful, as there are two well known other methods for solving this puzzle: dynamic programming and combinatorics. Please see these two pages for further explanations.

Here is one possible iterative solution:

gridTraverse:{

 gridPoints: reverse raze (til x),\:/: (til y);

 last {[res;curr]

  if[not 0=curr[0];res[(curr[0]-1;curr[1])]+:res[curr]];

  if[not 0=curr[1];res[(curr[0];curr[1]-1)]+:res[curr]];

  res

 }/[(enlist first gridPoints)!(enlist 1);gridPoints]

 };

In this solution, each grid point is iterated over along with a results dictionary. The results dictionary keeps track of the number of paths that have passed through each grid point. 

Each new grid point 'inherits' the result number of the previous grid point, such that when [0, 0] is arrived at, the result value for it contains the accumulated number of unique paths that passed through all the grid points to get there.

Performance comparison with the recursive solution:

q)\ts f[14;14]

15238 1664

q)\ts gridTraverse[14;14]

2 20384

Comments