Perl Weekly Challenge 128: Maximum Sub-Matrix

by Abigail

Challenge

You are given m x n binary matrix having 0 or 1.

Write a script to find out maximum sub-matrix having only 0.

Example 1

Input : [ 1 0 0 0 1 0 ]
        [ 1 1 0 0 0 1 ]
        [ 1 0 0 0 0 0 ]

Output: [ 0 0 0 ]
        [ 0 0 0 ]

Example 2

Input : [ 0 0 1 1 ]
        [ 0 0 0 1 ]
        [ 0 0 1 0 ]

Output: [ 0 0 ]
        [ 0 0 ]
        [ 0 0 ]

Discussion

This sounds very familiar! In fact, it's almost identical to week 87:

You are given matrix m x n with 0 and 1.

Write a script to find the largest rectangle containing only 1. Print 0 if none found.

The first difference with this weeks challenge is that in week 87, we were asked to find the largest rectangle containing 1s, while this week we are asked to find the largest rectangle containing 0s.

The second difference is that in week 87, it is somehow possible to not have a smallest sub-rectangle. Judging from the examples, this happens if the largest rectangle is a 1 x 1 rectangle.

Misleading example

The first example is a bit misleading. It claims the output should be

[ 0 0 0 ]
[ 0 0 0 ]

However, the input matrix also contains

[ 0 0 ]
[ 0 0 ]
[ 0 0 ]

which is the same size. So, the output isn't unique!

Solution

One way to solve this is to copy the code from week 87, rip out the special case dealing with a largest rectangle of size 1 x 1, and searching for 0s instead of 1s.

But we won't do that. Instead, we take the input of this week, flip each 1 to 0, and each 0 to 1, feed this to the program of week 87, and from the output, we flip each 1 to a 0.

Note that this takes care of the case if the largest rectangle is of size 1 x 1 — in this case the program from week 87 outputs a 0, which is the 1 x 1 rectangle we need.

Perl

First, we need to find the program from week 87. We do this by using a path starting from the current program, using the FindBin module:

use FindBin;
my $program = "$FindBin::Bin/../../../challenge-087/abigail/perl/ch-2.pl";

Next we run the program, using two pipes: one to feed it input, and one to read its output. The open2 function from IPC::Open2 will do that:

use IPC::Open2;
my $pid = open2 (my $out, my $in, $^X, $program) // die "open failed: $!";

Here $^X is the path to executable (perl) which is running us; we'll use this to run the code of week 87. $out is a handle from which we can read the output of $program, while $in is a handle we can write to, and which will feed into $program.

We now read the input, flip the 0s and 1s, and feed this to $program:

print $in y/01/10/r while <>;

We're done feeding input, so we close the handle:

close $in;

Time to read the out from $program, flipping each 1 to a 0, and writing this to standard output:

print y/1/0/r while <$out>;

And to be a good citizen, we'll reap our child lest it becomes a zombie:

waitpid ($pid, 0);

Find the full program on GitHub.

Please leave any comments as a GitHub issue.