RabbitFarm
2021-09-05
A Platform for Every Departing Sub-Matrix
The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.
Part 1
You are given m x n binary matrix having 0 or 1. Write a script to find out maximum sub-matrix having only 0.
Solution
use strict;
use warnings;
use Tree::Suffix;
sub maximum_sub_matrix{
my @matrix = @_;
my @sub_matrix;
my %indices;
my @indices_maximum;
my $indices_previous = "";
my $indices_current = "";
my $tree = new Tree::Suffix();
for my $i (0 .. @matrix - 1){
$indices_current = "";
for my $j (0 .. @{$matrix[0]} - 1){
$indices_current .= $j if $matrix[$i][$j] == 0;
$indices_current .= "x" if $matrix[$i][$j] == 1;
}
$tree->insert($indices_current);
for my $n (2 .. @{$matrix[0]}){
for my $s ($tree->longest_common_substrings(1, $n)){
if(!$indices{$s}){
$indices{$s} = [$i - 1, $i];
}
else{
push @{$indices{$s}}, $i - 1, $i;
}
}
}
$tree->remove($indices_previous) if $indices_previous;
$indices_previous = $indices_current;
}
for my $s (keys %indices){
my $max_area = -1;
my @indices = sort {$a <=> $b} do {my %seen; grep { !$seen{$_}++} @{$indices{$s}}};
unless($indices[0] < 0){
my $area = 0;
my $count = 0;
for(my $i = 0; $i <= @indices - 1; $i++){
$count++;
$area += length($s) if $i == 0;
$area += length($s) if $i > 0 && $indices[$i] == $indices[$i - 1] + 1;
do{$area = 0; $count = 0} if $i > 0 && $indices[$i] != $indices[$i - 1] + 1;
}
if($area >= $max_area){
$max_area = $area;
push @indices_maximum, [$s, $count];
}
}
}
for (0 .. $indices_maximum[0][1] - 1){
push @sub_matrix, [(0) x length($indices_maximum[0][0])];
}
return @sub_matrix;
}
MAIN:{
my @sub_matrix = maximum_sub_matrix(
[1, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0]
);
for my $row (@sub_matrix){
print "[" . join(" ", @{$row}) . "]\n";
}
}
Sample Run
$ perl perl/ch-1.pl
[0 0]
[0 0]
[0 0]
$ perl perl/ch-1.pl
[0 0 0]
[0 0 0]
Notes
At first this seemed like a very similar Dynamic Programming style approach like the one used in Challenge 117 would be suitable. The idea being to start with the top row and the track in a hash all the different possible submatrices that arise as we work downwards in the matrix. While this is definitely a DP problem tracking the possible submatrices in this way is completely inefficient! Unlike the problem of Challenge 117 in which the possible paths descending the triangle are all completely known and predictable, here a lot of extra work needs to be done.
In order to determine overlap between the zeroes in successive rows of the matrix the rows
are converted to strings and then the common substrings are computed using Tree::Suffix.
Because we are looking for any possible overlap we need to repeat the common substring
search for different lengths. The process to do this is a bit cumbersome, but it does
work! So, at least the solution I had in mind ended up working but it's all so convoluted.
Clearly more elegant solutions exist. One positive feature here though is that multiple
maximum sized submatrices can be identified. In the example output you can see that two
solutions exist, both with an "area" of six. Here which one gets shown is just based on
the random ordering of the keys in %indices
, but determining all solutions could be
easily done. Since this was not part of the original challenge it was left undone.
Part 2
You are given a list of intervals. Write a script to determine conflicts between the intervals.
Solution
use strict;
use warnings;
use Date::Parse;
use Heap::MinMax;
sub number_platforms{
my($arrivals, $departures) = @_;
my $platforms = 0;
my $heap = new Heap::MinMax();
$heap->insert(str2time(shift @{$departures}));
for my $i (0 .. @{$departures}){
$platforms++ if str2time($arrivals->[$i]) < $heap->min();
$heap->pop_min() if str2time($arrivals->[$i]) >= $heap->min();
$heap->insert(str2time($departures->[$i]));
}
return $platforms;
}
MAIN:{
print number_platforms(
["11:20", "14:30"],
["11:50", "15:00"]
) . "\n";
print number_platforms(
["10:20", "11:00", "11:10", "12:20", "16:20", "19:00"],
["10:30", "13:20", "12:40", "12:50", "20:20", "21:20"],
) . "\n";
}
Sample Run
$ perl perl/ch-2.pl
1
3
Notes
First, all times have to be converted to something numeric and so Date::Parse's str2time
is used to convert the times to Unix epoch timestamps.
Heaps are not usually something I commonly use, even for these challenge problems they never seem to be convenient. Here though is a pretty standard use of a Heap! Here the use of a Heap allows for easy access to the next departure time. If a train arrives before the next departure, increase the number of platforms.
References
posted at: 23:59 by: Adam Russell | path: /perl | permanent link to this entry