PWC 242 Flip the Script

Perl Weekly Challenge Task 2, "Flip Matrix", asks the musical question, "Can you teach a matrix some basic gymnastics?"

You are given n x n binary matrix.
Write a script to flip the given matrix as below.
a) Reverse each row
b) Invert each member

Example 1

Input: @matrix = ([1, 1, 0], [1, 0, 1], [0, 0, 0])
Output: ([1, 0, 0], [0, 1, 0], [1, 1, 1])

1 1 0  -reverse-->  0 1 1  -invert--> 1 0 0
1 0 1               1 0 1             0 1 0
0 0 0               0 0 0             1 1 1

Example 2

Input: @matrix = ([1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0])
Output: ([1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0])

1 1 0 0  -reverse--> 0 0 1 1  -invert--> 1 1 0 0
1 0 0 1              1 0 0 1             0 1 1 0
0 1 1 1              1 1 1 0             0 0 0 1
1 0 1 0              0 1 0 1             1 0 1 0

Peregrination

Many programming challenges have nuanced restrictions that lead to clever solutions. What have we here? Is it relevant that the matrix is square? How is limiting to binary digits going to help? The examples show that some rows don't change when both operations are applied; is that something that can be exploited?

Is this a math problem?

Reversing the rows of a matrix can be done by multiplying the matrix by a "reverse diagonal" matrix:

| a b c |   | 0 0 1 |   | c b a |
| d e f | X | 0 1 0 | = | f e d |
| g h i |   | 1 0 0 |   | i h g |

That's a concise mathematical formulation, but computationally, matrix multiplication doesn't scale well. Is there a clever theorem based on using the transpose of a diagonal matrix or something about the symmetry of the result? Probably, but I don't have enough linear algebra at the top of my brain to help me with a solution.

Is this a C problem?

If we were to treat the rows as binary numbers, is there a clever bit-twiddling hack for reversing the bits of an integer? Of course there is. But that's going to divert us more to C or maybe assembler than Perl, and it's also going to give us an implicit limit to row length (not that we're going to come up against that for the purposes of this task).

Is this a string problem?

If we were to treat the rows as strings, we can swap 0s and 1s with the translate function, tr/01/10/. That might lead to a quick solution.

Nah, it's a Perl problem.

Okay, so what do we have on hand in Perl? Well, there's the reverse function for reversing the elements of a list -- how convenient. Let's go for an obvious answer. We'll loop over the rows, reverse each one, and invert the values, exactly as the problem states.

sub flipMatrix($m)
{
    my @result;
    for my $row ( $m->@* )
    {
        push @result, [ map { $_ == 1 ? 0 : 1 } reverse $row->@* ];
    }
    return \@result;
}

We're taking the input argument matrix $m to actually be a reference to an array of array references. The loop builds a new set of array references, copying the elements while inverting and reversing.

There are many ways to turn a 1 into a 0 and vice versa. This one gets points for obvious, at least to me.

This solution has the advantage that (a) it works, and (b) it leaves the original matrix unchanged. On the other hand, it doubles the space required and spends extra time allocating memory and copying lists. Could we do something more efficient?

Reversing in place

If we're willing to modify the array, we can save memory allocation and speed up the process by reversing the rows in place. Reversing a list in place is a common exercise in data structures classes. It involves running a pair of indexes from opposite ends of the list toward each other while swapping elements. We can interject the bit inversion while we're at it.

sub flipMatrix($m)
{
    for my $row ( $m->@* )
    {
        for ( my ($front, $back) = (0, $row->$#*); $front <= $back ; $front++, $back-- )
        {
            $row->@[$front, $back] = map { ( $_ + 1 ) & 1 } $row->@[$back, $front];
        }
    }
    return $m;
}

A bit of unusual syntax here is $row->$#*. It's the last index of the array, derived from postfix dereferencing. The "classic Perl" syntax would be $#{$row}. As a Perl newcomer, I always had a hard time remembering that, probably because I made the mistake of thinking of $# as a special variable, when it's really more useful to think of it as an operator.

The swap step here is using Perl's array slice feature to move both elements in what looks like simultaneous operations. I've used a different way to invert bits in this function, based on incrementing the least significant bit and then masking off all the other bits.

What about that string idea?

The temptation to use character translation is hanging out there, so let's see what it looks like if we treat the rows as strings instead of numbers.

sub flipMatrix_S($m)
{
    my @result;
    for my $row ( $m->@* )
    {
        (my $s = reverse qq($row->@*)) =~ tr/01/10/;
        push @result, [ split(" ", $s) ];
    }
    return \@result;
}

Here we're going to pay the cost of converting to and from string representations, but it still looks reasonably clear and efficient. Let's take the operations apart.

• qq($row->@*) -- $row is a reference to an array, and $row->@* is postfix derefencing notation for getting all the elements of the row. Putting that inside double quotes would interpolate the elements, with a space between. I'm using the qq() double-quote operator here to emphasize that I'm depending on string interpolation (double quotes would be easy to overlook). Of course, it's only clearly readable if qq looks familiar.
• (my $s = reverse "$row->@*") -- reverse works on strings as well as lists, doing exactly what we need here. We're going to assign that to a variable, so that we can apply the tr operator.
• (my $s ...) =~ tr/01/10/ -- this translates every 0 to 1 and vice versa.
• split(" ", $s) -- we have to pay the cost to convert the string back to a list
• [ split... ] -- and we're creating a reference to that list
• push @result, ... -- which we can save in the @result array.

No wagering please

So given that we have three solutions, which one is fast? My intuition says that the one that modifies the array in place should be good. Copying the rows in order to modify them probably introduces a fair amount of behind-the-scenes memory allocation that could be significant, compared to doing it in place.

These functions are small enough that we can put them into a file, with slightly different names, and apply the Benchmark module to compare them. Benchmark::cmpthese is an easy way to run code blocks and see their relative performance.

sub flipMatrix($m)   { ... } # Modify in place
sub flipMatrix_B($m) { ... } # Use builtin reverse
sub flipMatrix_S($m) { ... } # Use string operations

use Benchmark qw/:all/;

cmpthese(500000, {
        'my reverse'      => sub { flipMatrix(...) },
        'builtin reverse' => sub { flipMatrix_B(...) },
        'string tr'       => sub { flipMatrix_S(...) },
});

When this runs, it outputs a table showing relative performance, from slowest to fastest.

                    Rate       string tr      my reverse builtin reverse
string tr       303030/s              --            -18%            -41%
my reverse      370370/s             22%              --            -28%
builtin reverse 515464/s             70%             39%              --

I was right about string conversion overhead, but once again, my intuition about what's efficient is proven to be as bad as ever -- using the builtin reverse is significantly faster, even though it involves making list copies. Good thing I measured.