Merge pull request #2161 from LubosKolouch/master

Challenge 075 Task 2 solutions LK Perl Python

2 files changed, 133 insertions, 0 deletions

diff --git a/challenge-075/lubos-kolouch/perl/ch-2.pl b/challenge-075/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..bbf03742ba
--- /dev/null
+++ b/challenge-075/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,71 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use List::Util qw/max/;
+use feature qw/say/;
+# Perl Weekly challenge 075 Task 2 - Largest histogram 
+
+
+sub printHistogram {
+    my $histogram = shift;
+
+    my $hist_max = max(@$histogram);
+    my $out_str;
+
+    for my $i (reverse 1..$hist_max) {
+        $out_str = $i;
+
+        for my $bar (@$histogram) {
+            $out_str .= $bar >= $i? '#' : ' '
+        }
+
+        say $out_str;
+        
+    }
+
+    $out_str = '_';
+    $out_str .= '_' x scalar @$histogram;
+
+    say $out_str;
+
+    $out_str = ' ';
+    $out_str .= $_ for (@$histogram);
+
+    say $out_str;
+}
+
+sub largestRectangle {
+    my $histogram = shift;
+    
+    my @stack;
+    my $max_area = 0;
+    my $index = 0;
+
+    while ($index < scalar @$histogram) {
+        if ( (not @stack) or ($histogram->[$stack[-1]] <= $histogram->[$index]) ) {
+            push @stack, $index;
+            $index ++;
+        } else {
+            my $top_of_stack = pop @stack;
+            my $area = @stack ? $histogram->[$top_of_stack] * ($index - $stack[-1] - 1) : $index;
+
+            $max_area = max($max_area, $area);
+        }
+    }
+
+    while (@stack) {
+            my $top_of_stack = pop @stack;
+            my $area = @stack ? $histogram->[$top_of_stack] * ($index - $stack[-1] - 1) : $index;
+
+            $max_area = max($max_area, $area);
+    }
+    printHistogram($histogram);
+
+    return $max_area;
+}
+
+use Test::More;
+
+is(largestRectangle([2, 1, 4, 5, 3, 7]), 12);
+is(largestRectangle([3, 2, 3, 5, 7, 5]), 15);
+
diff --git a/challenge-075/lubos-kolouch/python/ch-2.py b/challenge-075/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..306bcae7c3
--- /dev/null
+++ b/challenge-075/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,62 @@
+#!/usr/bin/env python
+""" Perl Weekly challenge 075 Task 2 - Largest histogram """
+
+
+def printHistogram(histogram):
+    """ print the histogram """
+
+    hist_max = max(histogram)
+
+    for i in range(hist_max, 0, -1):
+        my_str = str(i)
+
+        for bar in histogram:
+            my_str += '#' if bar >= i else ' '
+
+        print(my_str)
+
+    my_str = '_'
+    for _ in histogram:
+        my_str += '_'
+
+    print(my_str)
+
+    my_str = ' '
+    for item in histogram:
+        my_str += str(item)
+
+    print(my_str)
+
+def largestRectangle(histogram):
+    stack = list()
+    max_area = 0
+    index = 0
+
+    while index < len(histogram):
+        if (not stack) or (histogram[stack[-1]] <= histogram[index]):
+            stack.append(index)
+            index += 1
+        else:
+            top_of_stack = stack.pop()
+            area = (histogram[top_of_stack] * ((index - stack[-1] - 1)
+                 if stack else index))
+
+            max_area = max(max_area, area)
+
+    while stack:
+ 
+        top_of_stack = stack.pop()
+
+        area = (histogram[top_of_stack] * ((index - stack[-1] - 1)
+                if stack else index))
+
+        max_area = max(max_area, area)
+
+    printHistogram(histogram)
+
+    return max_area
+
+
+assert largestRectangle([2, 1, 4, 5, 3, 7]) == 12
+assert largestRectangle([3, 2, 3, 5, 7, 5]) == 15
+