diff options
| -rw-r--r-- | challenge-087/lubos-kolouch/perl/ch-2.pl | 85 | ||||
| -rw-r--r-- | challenge-087/lubos-kolouch/python/ch-2.py | 77 |
2 files changed, 162 insertions, 0 deletions
diff --git a/challenge-087/lubos-kolouch/perl/ch-2.pl b/challenge-087/lubos-kolouch/perl/ch-2.pl new file mode 100644 index 0000000000..c8bb288ba0 --- /dev/null +++ b/challenge-087/lubos-kolouch/perl/ch-2.pl @@ -0,0 +1,85 @@ +#!/usr/bin/perl +#=============================================================================== +# +# FILE: ch-2.pl +# +# USAGE: ./ch-2.pl +# +# DESCRIPTION: Perl Weekly Challenge 088 +# Task 2 - Largest Rectangle +# +# AUTHOR: Lubos Kolouch +# CREATED: 11/22/2020 04:34:38 PM +#=============================================================================== + +use strict; +use warnings; +use List::Util qw/min/; + +sub get_rectangle { + my $input = shift; + + my @input_arr = @$input; + + my $x_size = scalar @input_arr; + my $y_size = scalar @{$input_arr[0]}; + + + my $max_x=0; + my $max_y=0; + + # loop through the array + # look if the current element is 1 + # if so, check how far can go in the row and columns + # if the rectangle is largest, save the dimensions + for my $r (0..$x_size - 2) { + for my $c (0..$y_size - 2) { + if ($input_arr[$r][$c]) { + my $size1 = 0; + my $size2 = 0; + + while ($input_arr[$r+$size1][$c]) { + + #scan through the column and see what is the min size + my $y_shift = 1; + $y_shift++ while ($input_arr[$r+$size1][$c+$y_shift]); + + $size2 = $size2 ? min($size2, $y_shift) : $y_shift; + + last if $size2 == 1; + + $size1++; + } + + if (($size1 * $size2) > ($max_x * $max_y)) { + $max_x = $size1; + $max_y = $size2; + } + + } + } + } + + + # print and return the results + unless ($max_x * $max_y > 1) { + print "0\n"; + return 0; + } + + for my $i (0..$max_x-1) { + print '[ '; + for my $j (0..$max_y-1) { + print '1 '; + } + print "]\n"; + } + return [$max_x, $max_y]; +} + +use Test::More; + +is_deeply(get_rectangle([[0,0,0,1,0,0],[1,1,1,0,0,0],[0,0,1,0,0,1],[1,1,1,1,1,0],[1,1,1,1,1,0]]), [2, 5]); +is_deeply(get_rectangle([[1,0,1,0,1,0],[0,1,0,1,0,1],[1,0,1,0,1,0],[0,1,0,1,0,1]]), 0); +is_deeply(get_rectangle([[0,0,0,1,1,1],[1,1,1,1,1,1],[0,0,1,0,0,1],[0,0,1,1,1,1],[0,0,1,1,1,1]]), [2, 4]); +done_testing; diff --git a/challenge-087/lubos-kolouch/python/ch-2.py b/challenge-087/lubos-kolouch/python/ch-2.py new file mode 100644 index 0000000000..f0237ec5fb --- /dev/null +++ b/challenge-087/lubos-kolouch/python/ch-2.py @@ -0,0 +1,77 @@ +#!/bin/env python +""" +#=============================================================================== +# +# FILE: ch-2.py +# +# USAGE: ./ch-2.py +# +# DESCRIPTION: Perl Weekly Challenge 088 +# Task 2 - Largest Rectangle +# +# AUTHOR: Lubos Kolouch +# CREATED: 11/22/2020 04:34:38 PM +#=============================================================================== +""" + + +def get_rectangle(input_arr): + """ Get the largest rectangle """ + max_x = max_y = 0 + + # loop through the array + # look if the current element is 1 + # if so, check how far can go in the row and columns + # if the rectangle is largest, save the dimensions + + for r, row in enumerate(input_arr[:-1]): + for c, item in enumerate(row[:-1]): + + if item: + # print(f"* 1 at {r} {c}") + size1 = size2 = 0 + + while (r+size1 < len(input_arr)) and (input_arr[r+size1][c]): + # print(f" v 1 at {r} {c}") + + # scan through the column and see what is the min size + y_shift = 0 + + while (c+y_shift < len(row)) and (input_arr[r+size1][c+y_shift]): + # print(f" > 1 at {r+size1} {c+y_shift}") + y_shift += 1 + + size2 = min(size2, y_shift) if size2 else y_shift + + if size2 == 1: + break + + size1 += 1 + + if size1 * size2 > max_x * max_y: + max_x = size1 + max_y = size2 + + # print and return the results + if not max_x * max_y > 1: + print("0") + return 0 + + for _ in range(max_x): + row_str = "[ " + + for _ in range(max_y): + row_str += "1 " + + row_str += "]" + print(row_str) + + return (max_x, max_y) + + +assert get_rectangle([[0, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0], [0, 0, 1, 0, 0, 1], + [1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 0]]) == (2, 5) +assert get_rectangle([[1, 0, 1, 0, 1, 0], [0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0], + [0, 1, 0, 1, 0, 1]]) == 0 +assert get_rectangle([[0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1], [0, 0, 1, 0, 0, 1], + [0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1]]) == (2, 4) |