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:
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:
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:
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.