Matrix Rotation ♻️
A Deep Dive
Every now and then, I encounter a problem that requires that I rotate a 2-dimensional array.
Behold, the effects of a 90-degree clockwise matrix rotation:[ [
[1,2,3], [7,4,1],
[4,5,6], ---> [8,5,2],
[7,8,9], [9,6,3],
] ]
This is useful when you want to operate on both the rows and columns of a matrix. The rows are easy; they’re just the child arrays, and you can map/filter/whatever. By rotating, you can turn the columns into simple arrays as well.
This is a surprisingly common problem. I encountered it last year when writing a sudoku-validator. More recently, I came across a Snail Sort challenge.
My solution from last year wasn’t great, though — let’s take some time and see if we can come up with something better :)
The Original Solution
I have to admit, after not having seen it for a while, it took me a bit to figure out what was happening here. We’re going to use it as the starting point for this refactor, so let’s unpack it.
The inner map, on line 3, goes through each row of the matrix, and selects 1 character from each array. For example:
const matrix = [
[1,2,3],
[4,5,6],
[7,8,9],
];const index = 1;matrix.map(row => row[index]) // -> [2, 5, 8]
Essentially, this map extracts a single column from a matrix, converting it into a row.
The outer map iterates through each item in the first row, but we don’t even care about the item itself; we just need the index.
This index gets passed to the inner map, so that it runs once per column. This simplified, hardcoded version should make it clear:
const matrix = [
[1,2,3],
[4,5,6],
[7,8,9],
];const indices = [0, 1, 2];indices.map(index => (
matrix.map(row => row[index])
));
The first time the inner map runs, we end up with [1, 4, 7]. The second time, the aforementioned [2, 5, 8]. Finally, [3, 6, 9]. Shove them into an array, and we wind up with:
[ [
[1,2,3], [1,4,7],
[4,5,6], -> [2,5,8],
[7,8,9], [3,6,9],
]; ];
Work Needed
This is a good starting point, but there are some problems with this implementation.
- The first issue I have with this code is it’s not super clear; just look at how much explanation was required to make sense of it!
- Another problem is this code only allows us to move clockwise. What if we want to move counter-clockwise? Our solution should let us move in either direction.
- Last, but certainly not least, is that the solution is wrong. Keen observers will have noticed that this matrix isn’t actually rotated, it’s flipped across a diagonal axis. Instead of turning the box on its side, we’ve flipped it over.
That last problem is the most significant, so let’s tackle it first.
It turns out the answer is quite simple: We just need to reverse the matrix before flipping it!
Even more confusingly, if we rotate the matrix after running our flipMatrix function, the matrix is rotated counter-clockwise:
What the hell is going on here? Why does this work?
Understanding the motion
I need to place a huge disclaimer here; I probably don’t have any business explaining this stuff. I do not have a math background and I’ve only been fiddling with this for a little while.
Imagine if you have a playing card. With one finger on the top left corner and another on the bottom right, you flip it over across its diagonal axis. The card will wind up on its side, and of course be backwards. This is equivalent to what happens when we run our initial version of the function.
Then, imagine if you flip the card over its horizontal axis. The card would now be facing frontwards, and the end result is that the card has been rotated counter-clockwise.
Had we flipped the card over its vertical axis first, and then over the same diagonal axis, the card will rotate clockwise:
How does this relate?
In our code, the horizontal-axis flip is akin to reversing the matrix:
[ [
[1,2,3], matrix.reverse() [7,8,9],
[4,5,6], ---> [4,5,6],
[7,8,9], [1,2,3],
] ]And, because we know that our flipMatrix method acts as a diagonal axis flip, we can derive that:
- Reversing the matrix before the flip will yield a clockwise rotation.
- Reversing the matrix after the flip will yield a counter-clockwise rotation.
This is a powerful idea, and it allows us to compose all 4 variants without duplicating our core logic:
Further Refactoring
We’ve solved the most critical issue, and we’ve created generalized permutations for other use-cases. Our new solution has introduced a new issue, though.
When we pass our functions a `matrix` argument, it’s a reference to an array that exists outside that function. Array#reverse is mutative, and it transforms that array.
This is very bad, because it’s an unintended side effect. We don’t want to mess with the input itself, we just want to use it to create the desired output.
Let’s try making a composable reverse function that does not mutate the array.
Neat; we’ve solved the mutative issue. The only issue left is the code clarity issue. Let’s continue down this functional path, and see if we can make it more intuitive.
Building Blocks
Let’s assemble a small toolkit of functional building blocks we can use to solve this problem.
These blocks are great for a few reasons, but what makes them shine here is their semantic value. By naming a small piece of code, our solution becomes declarative; we no longer need to figure out what matrix[0].map is about.
Here’s what it looks like:
We create a range of values for our matrix rows, map over those indexes, and pluck that index from each row in the matrix.
Conclusion
Programming is all about problem-solving, and often a problem can be broken into multiple, smaller problems. These smaller problems are often pretty generic, and their solutions can be reused.
The more problems you solve, the bigger your toolkit gets, and the more likely it is that when you encounter a new problem, you’ll already have solutions in your pocket that can take you most of the way there.
This is especially true with functional programming, where a library of tiny utility functions can be used to tackle an incredibly vast array of complex problems.
To Be Continued?
Functional programming is fairly new to me; I can’t help but feel like there’s still room for improvement with this solution!
If any FP gurus have suggestions, please let me know :)
