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

Challenge 128

Date::Parse

Heap::MinMax

Tree::Suffix

posted at: 23:59 by: Adam Russell | path: /perl | permanent link to this entry