This is my response to The Weekly Challenge #298.
m x n binary matrix with 0 and
1 only.
1's
and return it’s area.
Input: @matrix = ([1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0])
Output: 4
Two maximal square found with same size marked as 'x':
[1, 0, 1, 0, 0]
[1, 0, x, x, 1]
[1, 1, x, x, 1]
[1, 0, 0, 1, 0]
[1, 0, 1, 0, 0]
[1, 0, 1, x, x]
[1, 1, 1, x, x]
[1, 0, 0, 1, 0]
Input: @matrix = ([0, 1],
[1, 0])
Output: 1
Two maximal square found with same size marked as 'x':
[0, x]
[1, 0]
[0, 1]
[x, 0]
Input: @matrix = ([0])
Output: 0
This is a mutation of Challenge #128.1: Maximum Sub-Matrix, except that we looked for zeroes then, and the result must be a square this time.
Brute force, together with some cleverness, should do the trick.
File: maximal-square
#! /usr/bin/env raku
unit sub MAIN (Str $matrix = "1 0 1 0 0 | 1 0 1 1 1 | 1 1 1 1 1 | 1 0 0 1 0",
:v(:$verbose)); # [1]
my @matrix = $matrix.split("|")>>.words>>.Numeric; # [2]
die "Illegal characters" unless all(@matrix[*;*]) ~~ 0 | 1; # [3]
die "Uneven row length" unless [==] @matrix>>.elems; # [4]
my $rows = @matrix.elems; # [5]
my $cols = @matrix[0].elems; # [6]
my $max = 0; # [7]
for ^$rows -> $row # [8]
{
for ^$cols -> $col # [9]
{
if @matrix[$row][$col] == 0 # [10]
{
say ": [r:$row,c:$col] - Skipping zero" if $verbose;
next; # [10a]
}
my $max-size = min($rows - $row, $cols - $col); # [11]
say ": [r:$row,c:$col] maxbox: $max-size" if $verbose;
OUTERBOX:
for 1 .. $max-size -> $size # [12]
{
for $row .. $row + $size -1 -> $r # [13]
{
for $col .. $col + $size -1 -> $c # [14]
{
say ": [r:$r,c:$c] -> @matrix[$r][$c]" if $verbose;
last OUTERBOX if @matrix[$r][$c] == 0; # [15]
}
}
say ": Found 1-box $size x $size at [$row,$col]" if $verbose;
$max = max($max, $size * $size) # [16]
}
}
}
say $max; # [17]
[1] Note the «matriux as a string» syntax, used here with the first example as the default value.
[2] Unpack the string into a two dimentional array. The Numeric part
is there to get rid of the undecided IntStr type, which looks pretty bad in
verbose output. (Using int would have coerced non-integer numeric
values to integers, and we do not want that type of errors to slip through
the cracks.)
[3] Ensure that we get the binary digits 0 and 1 only. The all
Junction needs a one dimentional array, which we get with [*;*].
[4] All the matrix rows must have the same length.
[5] Get the number of rows.
[6] Get the number of columns.
[7] The current max value, initially zero.
[8] We are doing this the hard way, by iterating over every position in the matrix (to be used as the upper left hand corner of a square sub matrix). We start with the rows,
[9] then the columns.
[10] Skip the current position [10a] if the cell has a value of zero (as we require a box of 1s).
[11] This is the maximum box size (as length of the sides), given the size of the matrix.
[12] Iterate over all possible box sizes, for the given upper left hand corner of a square. We start with a size of 1, so that we can short circuit this outer loop if we encounter a zero.
[13] Iterate over the rows,
[14] and the columns.
[15] Short circuit the entire loop if we encounter a zero.
[16] We will only get here if we failure to fail (in [15]). That means success. Save the new max value if it is larger than the old one.
[17] Print the result.
Running it:
$ ./maximal-square
4
$ ./maximal-square "0 1 | 1 0"
1
$ ./maximal-square "0"
0
Looking good.
With verbose mode:
$ ./maximal-square -v
: [r:0,c:0] maxbox: 4
: [r:0,c:0] -> 1
: Found 1-box 1 x 1 at [0,0]
: [r:0,c:0] -> 1
: [r:0,c:1] -> 0
: [r:0,c:1] - Skipping zero
: [r:0,c:2] maxbox: 3
: [r:0,c:2] -> 1
: Found 1-box 1 x 1 at [0,2]
: [r:0,c:2] -> 1
: [r:0,c:3] -> 0
: [r:0,c:3] - Skipping zero
: [r:0,c:4] - Skipping zero
: [r:1,c:0] maxbox: 3
: [r:1,c:0] -> 1
: Found 1-box 1 x 1 at [1,0]
: [r:1,c:0] -> 1
: [r:1,c:1] -> 0
: [r:1,c:1] - Skipping zero
: [r:1,c:2] maxbox: 3
: [r:1,c:2] -> 1
: Found 1-box 1 x 1 at [1,2]
: [r:1,c:2] -> 1
: [r:1,c:3] -> 1
: [r:2,c:2] -> 1
: [r:2,c:3] -> 1
: Found 1-box 2 x 2 at [1,2]
: [r:1,c:2] -> 1
: [r:1,c:3] -> 1
: [r:1,c:4] -> 1
: [r:2,c:2] -> 1
: [r:2,c:3] -> 1
: [r:2,c:4] -> 1
: [r:3,c:2] -> 0
: [r:1,c:3] maxbox: 2
: [r:1,c:3] -> 1
: Found 1-box 1 x 1 at [1,3]
: [r:1,c:3] -> 1
: [r:1,c:4] -> 1
: [r:2,c:3] -> 1
: [r:2,c:4] -> 1
: Found 1-box 2 x 2 at [1,3]
: [r:1,c:4] maxbox: 1
: [r:1,c:4] -> 1
: Found 1-box 1 x 1 at [1,4]
: [r:2,c:0] maxbox: 2
: [r:2,c:0] -> 1
: Found 1-box 1 x 1 at [2,0]
: [r:2,c:0] -> 1
: [r:2,c:1] -> 1
: [r:3,c:0] -> 1
: [r:3,c:1] -> 0
: [r:2,c:1] maxbox: 2
: [r:2,c:1] -> 1
: Found 1-box 1 x 1 at [2,1]
: [r:2,c:1] -> 1
: [r:2,c:2] -> 1
: [r:3,c:1] -> 0
: [r:2,c:2] maxbox: 2
: [r:2,c:2] -> 1
: Found 1-box 1 x 1 at [2,2]
: [r:2,c:2] -> 1
: [r:2,c:3] -> 1
: [r:3,c:2] -> 0
: [r:2,c:3] maxbox: 2
: [r:2,c:3] -> 1
: Found 1-box 1 x 1 at [2,3]
: [r:2,c:3] -> 1
: [r:2,c:4] -> 1
: [r:3,c:3] -> 1
: [r:3,c:4] -> 0
: [r:2,c:4] maxbox: 1
: [r:2,c:4] -> 1
: Found 1-box 1 x 1 at [2,4]
: [r:3,c:0] maxbox: 1
: [r:3,c:0] -> 1
: Found 1-box 1 x 1 at [3,0]
: [r:3,c:1] - Skipping zero
: [r:3,c:2] - Skipping zero
: [r:3,c:3] maxbox: 1
: [r:3,c:3] -> 1
: Found 1-box 1 x 1 at [3,3]
: [r:3,c:4] - Skipping zero
4
$ ./maximal-square -v "0 1 | 1 0"
: [r:0,c:0] - Skipping zero
: [r:0,c:1] maxbox: 1
: [r:0,c:1] -> 1
: Found 1-box 1 x 1 at [0,1]
: [r:1,c:0] maxbox: 1
: [r:1,c:0] -> 1
: Found 1-box 1 x 1 at [1,0]
: [r:1,c:1] - Skipping zero
1
$ ./maximal-square -v "0"
: [r:0,c:0] - Skipping zero
0
@intervals, where
$intervals[i] = [starti, endi] and each starti is unique.
i is an interval j
such that startj >= endi and startj is minimized. Please
note that i may equal j.
i. If no right interval exists for interval i,
then put -1 at index i.
Input: @intervals = ([3,4], [2,3], [1,2])
Output: (-1, 0, 1)
There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest
start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest
start that is >= end2 = 2.
Input: @intervals = ([1,4], [2,3], [3,4])
Output: (-1, 2, -1)
There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest
start that is >= end1 = 3.
Input: @intervals = ([1,2])
Output: (-1)
There is only one interval in the collection, so it outputs -1.
Input: @intervals = ([1,4], [2, 2], [3, 4])
Output: (-1, 1, -1)
File: right-interval
#! /usr/bin/env raku
unit sub MAIN (Str $intervals = "3 4 | 2 3 | 1 2", # [1]
:v(:$verbose));
my @intervals = $intervals.split("|")>>.words>>.Numeric; # [2]
die "Illegal characters"
unless all(@intervals[*;*]) ~~ Int; # [3]
die "Interval must have two values only"
unless all(@interval>>.elems) == 2; # [4]
say ": Intervals: { @intervals.raku }" if $verbose;
my %start2index; # [5]
my $index = 0; # [6]
for @intervals -> @interval # [7]
{
die "Interval ends before the start"
if @interval[0] > @interval[1]; # [8]
die "Interval start @interval[0] already used" # [9]
if defined %start2index{@interval[0]};
%start2index{@interval[0]} = $index; # [10]
$index++; # [11]
}
say ": Start2index: { %start2index.raku }" if $verbose;
my @starts = %start2index.keys.sort; # [12]
say ": Start values: { @starts.raku }" if $verbose;
my @output; # [13]
for @intervals -> @interval # [14]
{
my $end = @interval[1]; # [15]
my @next = @starts.grep: * >= $end; # [16]
@output.push( @next.elems ?? %start2index{@next.first} !! -1); # [17]
}
say "({ @output.join(", ") })"; # [18]
[1] Note the default value; this is the first example.
[2] Turn the input into a two dimentional array.
[3] Ensure that we get Integers only.
[4] Every sub array must have two elements.
[5] The index of each start value (of the pairs) will end up here.
[6] The current index.
[7] Iterate over the intervals.
[8] The start value cannot be higher than the end value.
[9] The start value must be unique.
[10] Note the index of the current start value.
[11] Adjust the index in preparation for the next iteration.
[12] Get the start values of the intervals, in sorted order. (We could
also have used something like: @intervals.map({ $_[0]}).sort }) .)
[13] The result (indices) will end up here.
[14] Iterate over the intervals, for a second time.
[15] Get the end of the current interval.
[16] Get the start values that are equal to or larger than the current end value.
[17] Do we have any elements? If so, take the first one
(with first) and save the corresponding index. if not, save -1.
See docs.raku.org/routine/first for more information about first.
[18] Pretty print the result.
Running it:
$ ./right-interval
(-1, 0, 1)
$ ./right-interval "1 4 | 2 3 | 3 4"
(-1, 2, -1)
$ ./right-interval "1 2"
(-1)
$ ./right-interval "1 4 | 2 2 | 3 4"
(-1, 1, -1)
Looking good.
With verbose mode:
$ ./right-interval -v
: Intervals: [(3, 4), (2, 3), (1, 2)]
: Start2index: {"1" => 2, "2" => 1, "3" => 0}
: Start values: ["1", "2", "3"]
(-1, 0, 1)
$ ./right-interval -v "1 4 | 2 3 | 3 4"
: Intervals: [(1, 4), (2, 3), (3, 4)]
: Start2index: {"1" => 0, "2" => 1, "3" => 2}
: Start values: ["1", "2", "3"]
(-1, 2, -1)
$ ./right-interval -v "1 2"
: Intervals: [(1, 2),]
: Start2index: {"1" => 0}
: Start values: ["1"]
(-1)
$ ./right-interval -v "1 4 | 2 2 | 3 4"
: Intervals: [(1, 4), (2, 2), (3, 4)]
: Start2index: {"1" => 0, "2" => 1, "3" => 2}
: Start values: ["1", "2", "3"]
(-1, 1, -1)
We can avoid -1 in the result, but some or all of the intervals will point back to themselves:
$ ./right-interval -v "1 1 | 2 2 | 3 3"
: Intervals: [(1, 1), (2, 2), (3, 3)]
: Start2index: {"1" => 0, "2" => 1, "3" => 2}
: Start values: ["1", "2", "3"]
(0, 1, 2)
$ ./right-interval -v "1 3 | 2 3 | 3 3"
: Intervals: [(1, 3), (2, 3), (3, 3)]
: Start2index: {"1" => 0, "2" => 1, "3" => 2}
: Start values: ["1", "2", "3"]
(2, 2, 2)
And that's it.