November 12, 2013

Coding Practice - Spiral traversal of an array

Conceptually, it is convenient to visualize data in several dimensions: e.g. we commonly think of images as 2D and video as 3D. However, at the byte-level, data is just a one-dimensional array of bytes. Going from the conceptual representation to a byte-level representation is known as a traversal.

Traversals are very common in problem areas such as image processing. For example, a simple scanline traversal goes like this:

  1. Start at the top left corner of an image
  2. Keep going right until we reach the right edge of the image
  3. If we’ve reached the bottom right corner, stop. Otherwise, go down one row, start at the very left of the image.
  4. Go to 2.

There are other traversals, such as the Z-curve and the Hilbert curve. While they are more complicated, they reduce the entropy of the resulting sequence, allowing it to be compressed more effectively.

This week’s problem is to implement a slightly unusual traversal. The goal is to traverse matrix elements in a counter-clockwise “spiral” given some starting row and column. Here’s what it looks like:

An example traversal

The image above, as well as the entire problem itself, is taken from @blakeembrey’s excellent coding problem repository.

The solution is pretty straight forward:

  1. Go forward X steps
  2. Turn left
  3. If the traversal is complete, then stop; otherwise go to 1

The only tricky part was to realize how and when X changes. The answer is surprisingly simple: increment X by one after every two turns. Determining the completeness of the traversal is also easy: since you know the dimensions of the matrix you’re traversing, you know how many elements it contains; so stop after you’ve seen that many elements.

Have a look at my solution here.