PWC 053 › Matrix Rotation

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is as follows:

Write a script to rotate the following matrix by given 90/180/270 degrees clockwise.

[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]

At first glance, I thought this was a simple matrix transpose, which is what you get when you swap the rows and columns of a matrix. The transposition (^T) of the example matrix would give us:

But the task asks us to rotate clockwise, which would instead give:

We still have to swap the rows and columns; they are just in a different order that we’ll address later.

The task does say “rotate the following matrix,” seeming to imply that we only need to handle this one, specific input. I decided to support arbitrary matrix shapes. Any whole number height/width will work.

Perl

No matter what we do, we need to change every row and column, so the best we can do is O(n²) time.

I do a standard matrix transpose, but I reverse the input rows first. This cancels out the horizontal mirroring after the matrix is transposed:

sub rotate_cw {
    my @A = reverse @{$_[0]};
    my @T;
    for my $x (0..$#A) {
        $T[$_][$x] = $A[$x][$_] for 0..$#{$A[0]};
    }
    \@T;
}

That takes care of the single clockwise rotation. The 180- and counter-clockwise (or anti-clockwise) rotations can be done in terms of rotate_cw:

sub rotate180    { rotate90_cw( rotate90_cw (@_) ) }
sub rotate_ccw   { rotate90_cw( rotate180(   @_) ) }

Note that rotate_ccw is not equivalent to a standard matrix transpose! Remember, the clockwise rotation we’re doing is the mirror image of a transpose, not a rotation in the opposite direction.

Implementing rotate_180 and rotate_ccw as custom functions would be faster by a factor of 2 or 3 respectively. However, the code would be very similar to rotate_cw, so I decided this way was a little less boring. If I was going for speed, I’d probably use XS.

I added a few test cases to check various matrix shapes, including 1×N and M×1.

Raku

Had we been asked to do a standard matrix transformation, the Raku code is a single operator:

[Z] @A

To get a clockwise rotation instead, as with the Perl solution, it’s very easy to simply reverse the input rows:

[Z] @A.reverse

These two rotations almost work perfectly. Unfortunately, 1×N matrices misbehave. Given \(\begin{pmatrix}
1 & 2
\end{pmatrix}\), it would return \(\begin{pmatrix}
2 & 1
\end{pmatrix}\), but I would expect \(\begin{pmatrix}
1 \\
2
\end{pmatrix}\). The error occurs because of list flattening. There are a few ways to fix this, but in order to keep the inputs reasonably flexible, I opted to simply use a multi sub to define a special case for the 1×N matrices. All together, rotate-cw looks like this:

multi sub rotate-cw(@A) { [Z] @A.reverse }
multi sub rotate-cw(@A where !*[0].isa("List")) { @A.map: { [$_] } }

The 180 and ccw subs, again, can be done with repeated calls to rotate-cw:

sub rotate180(@A)    { rotate-cw( rotate-cw(@A) ) }
sub rotate-ccw(@A)   { rotate180( rotate-cw(@A) ) }

Here are a few of the test cases, to give you a sense of what the inputs and outputs look like:

is-deeply rotate-cw((1,2; 3,4; 5,6)), (5,3,1; 6,4,2); # MxN
is-deeply rotate-cw((1,2,3)), ([1],[2],[3]); # 1xM

Of course, non-numeric arguments work just as well (true of the Perl version, as well):

is-deeply rotate-cw(('a','b','c'; 'd','e','f')), ('d','a'; 'e','b'; 'f','c');