Merge pull request #4843 from adamcrussell/challenge-128

solutions to challenge 128

3 files changed, 106 insertions, 0 deletions

diff --git a/challenge-128/adam-russell/blog.txt b/challenge-128/adam-russell/blog.txt
new file mode 100644
index 0000000000..fe879c6e4f
--- /dev/null
+++ b/challenge-128/adam-russell/blog.txt
@@ -0,0 +1 @@
+http://www.rabbitfarm.com/cgi-bin/blosxom/perl/2021/09/05
diff --git a/challenge-128/adam-russell/perl/ch-1.pl b/challenge-128/adam-russell/perl/ch-1.pl
new file mode 100644
index 0000000000..fbe87eb47e
--- /dev/null
+++ b/challenge-128/adam-russell/perl/ch-1.pl
@@ -0,0 +1,71 @@
+use strict;
+use warnings;
+## 
+# You are given m x n binary matrix having 0 or 1.
+# Write a script to find out maximum sub-matrix having only 0.
+##
+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"; 
+    }  
+} 
diff --git a/challenge-128/adam-russell/perl/ch-2.pl b/challenge-128/adam-russell/perl/ch-2.pl
new file mode 100644
index 0000000000..e53f4b3d6c
--- /dev/null
+++ b/challenge-128/adam-russell/perl/ch-2.pl
@@ -0,0 +1,34 @@
+use strict;
+use warnings;
+##
+# You are given two arrays of arrival and departure 
+# times of trains at a railway station.
+# Write a script to find out the minimum number of 
+# platforms needed so that no train needs to wait.
+##
+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"; 
+}