Matrix Puzzle From Hell or: How I Learned to Stop Worrying and Love the Patterns

The Stage

About a year ago, Mr. King (@Adkron) posed a math puzzle on our team’s whiteboard first thing one morning.  The problem seemed at the same time very complex and strangely simple.  Amos said that he had found it surfing the web the night before and that it was from some company’s interview or resume-submitting questions.

After several passionate whiteboarding sessions including members of our team, and any poor souls who walked by (I believe Mr. Young falls into this group), no one had a solution.  Eventually the whiteboard was clearred for more “important” work but the puzzle lingered with me.  On several occasions over the past year I have redrawn the matrix on a pad of paper and spent and hour or two trying to decipher the patterns and make sense of the answer tickling at edge of my brain.

This past week, while drifting off to sleep, the puzzle popped back into my head.  After a few moments a number of ideas I had had months before fell together in just the right way for me to FINALLY figure out a solution.  Eureka! (I mentally shouted) and got out of bed to find a piece of paper to work through some more examples and prove myself right.

The Puzzle

Given a 2D matrix such that each cell’s value is defined as follows:

>> The smallest non-negative integer not already present to the “left” or “above” <<

Determine an constant time function ( O(1) ) which given X and Y indices will return the value of the matrix cell at (X,Y).

For the visual people in the crowd, the top left corner or said matrix looks something like this:

First 8x8 cells of matrix puzzle

The picture only shows the top 8×8 of the defined matrix as an example.  We can see that whatever f(x,y) you come up with needs to equal the following example values

f(0,0) = 0
f(1,0) = 1
f(2,0) = 2
f(3,0) = 3
f(3,1) = 2
f(3,2) = 1
……

The real key here is that the solution needs to function in constant time: O(1).  This means that computing the matrix value at (6,3) should be the same cost computationally as computing the matrix value at (10000000,4500005).

Anyone can write a program to compute the whole matrix out to your point (in theory) but can you come up with a better solution? In less than a year?

The Solution

Not just yet.  I will post my thought process and eventual solution soon in a separate post.

** I didn’t think of this puzzle, nor guarantee that I am remembering it correctly **
** If you know who did or have any corrections, please leave a comment  below **