From 2903da28f2db96e094cfa4e040873b31496e0a02 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Fri, 28 Aug 2020 10:58:51 +0100 Subject: - Sometime copy&paste can be disaster. --- challenge-075/mohammad-anwar/perl/ch-2.pl | 101 +++++++++++++++++++++--------- challenge-075/mohammad-anwar/perl/ch-2.t | 100 ++++++++++++++++++++--------- 2 files changed, 144 insertions(+), 57 deletions(-) diff --git a/challenge-075/mohammad-anwar/perl/ch-2.pl b/challenge-075/mohammad-anwar/perl/ch-2.pl index 7749fa9364..8e962979ad 100755 --- a/challenge-075/mohammad-anwar/perl/ch-2.pl +++ b/challenge-075/mohammad-anwar/perl/ch-2.pl @@ -3,62 +3,107 @@ # # Perl Weekly Challenge - 075 # -# Task #1: Coins Sum +# Task #2: Largest Rectangle Histogram # # https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 # use strict; use warnings; +use List::Util qw(min max); -my $COINS = $ARGV[0] || "1, 2, 4"; -my $SUM = $ARGV[1] || 6; +my $L = $ARGV[0] || "2, 1, 4, 5, 3, 7"; -print "Possible ways to achieve the target: ", - coins_sum(prepare($COINS), $SUM), "\n"; +my $list = prepare($L); +print chart($list), "\n\n"; +print "Largest Rectangle Histogram: ", largest_rectangle_histogram($list), "\n"; # # # METHODS -sub coins_sum { - my ($coins, $sum) = @_; +sub largest_rectangle_histogram { + my ($list) = @_; - my $size = $#$coins; - return 0 if ($size == -1 || $sum <= 0); + my $i = 0; + my $max = 0; + foreach my $n (@$list) { - my $matrix; + my ($left, $right) = (0, 0); + $left = go_left($i, $list) if ($i > 0); + $right = go_right($i, $list) if ($i <= $#$list); - # Sum of 0 can be achieved in one possible way. - $matrix->[$_][0] = 1 for (0 .. $size+1); + my @heights = (@$list)[$i - $left .. $i + $right]; + my $size = min(@heights) * @heights; + $max = $size if ($size > $max); - foreach my $i (0 .. $size) { + $i++; + } - foreach my $j (1 .. $sum) { + return $max; +} - my $include_current = 0; - my $exclude_current = 0; +sub go_left { + my ($i, $list) = @_; - if ($coins->[$i] <= $j) { - $include_current = $matrix->[$i][$j - $coins->[$i]]; - } + my $c = $list->[$i]; + my $j = 0; + while ($i > 0) { + $i--; + last if ($list->[$i] < $c); + $j++; + } - if ($i > 0) { - $exclude_current = $matrix->[$i - 1][$j]; - } + return $j; +} + +sub go_right { + my ($i, $list) = @_; - $matrix->[$i][$j] = $include_current + $exclude_current; + my $c = $list->[$i]; + my $j = 0; + while ($i < $#$list) { + $i++; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub chart { + my ($list) = @_; + + my $max = max(@$list); + my $chart = []; + my $row = 1; + foreach (1..$max) { + my $data = ""; + foreach my $i (0..$#$list) { + if ($row <= $list->[$i]) { + $data .= " #"; + } + else { + $data .= " "; + } } + $row++; + push @$chart, sprintf("%d%s", $_, $data); } - return $matrix->[$size][$sum]; + my ($histogram, $line, $size) = ("", "", " "); + $histogram = join "\n", (reverse @$chart); + $line .= "_ " for (0..$#$list + 1); + $size .= join " ", @$list; + + return join "\n", $histogram, $line, $size; } sub prepare { - my ($coins) = @_; + my ($list) = @_; - if (defined $coins) { - $coins =~ s/\s//g; - return [ split /\,/, $coins ]; + if (defined $list) { + $list =~ s/\s//g; + return [ split /\,/, $list ]; } } diff --git a/challenge-075/mohammad-anwar/perl/ch-2.t b/challenge-075/mohammad-anwar/perl/ch-2.t index c2d32443b5..51ba0dec90 100755 --- a/challenge-075/mohammad-anwar/perl/ch-2.t +++ b/challenge-075/mohammad-anwar/perl/ch-2.t @@ -3,7 +3,7 @@ # # Perl Weekly Challenge - 075 # -# Task #1: Coins Sum +# Task #2: Largest Rectangle Histogram # # https://perlweeklychallenge.org/blog/perl-weekly-challenge-075 # @@ -11,12 +11,10 @@ use strict; use warnings; use Test::More; +use List::Util qw(min max); -is coins_sum(prepare("1, 2"), 5), 3; -is coins_sum(prepare("1, 2, 3"), 5), 5; -is coins_sum(prepare("1, 2, 4"), 6), 6; -is coins_sum(prepare("25, 10, 5"), 30), 5; -is coins_sum(prepare("9, 6, 5, 1"), 11), 6; +is(largest_rectangle_histogram(prepare("2, 1, 4, 5, 3, 7")), 12, "example 1"); +is(largest_rectangle_histogram(prepare("3, 2, 3, 5, 7, 5")), 15, "example 2"); done_testing; @@ -24,44 +22,88 @@ done_testing; # # METHODS -sub coins_sum { - my ($coins, $sum) = @_; +sub largest_rectangle_histogram { + my ($list) = @_; - my $size = $#$coins; - return 0 if ($size == -1 || $sum <= 0); + my $i = 0; + my $max = 0; + foreach my $n (@$list) { - my $matrix; + my ($left, $right) = (0, 0); + $left = go_left($i, $list) if ($i > 0); + $right = go_right($i, $list) if ($i <= $#$list); - # Sum of 0 can be achieved in one possible way. - $matrix->[$_][0] = 1 for (0 .. $size+1); + my @heights = (@$list)[$i - $left .. $i + $right]; + my $size = min(@heights) * @heights; + $max = $size if ($size > $max); - foreach my $i (0 .. $size) { + $i++; + } - foreach my $j (1 .. $sum) { + return $max; +} - my $include_current = 0; - my $exclude_current = 0; +sub go_left { + my ($i, $list) = @_; - if ($coins->[$i] <= $j) { - $include_current = $matrix->[$i][$j - $coins->[$i]]; - } + my $c = $list->[$i]; + my $j = 0; + while ($i > 0) { + $i--; + last if ($list->[$i] < $c); + $j++; + } - if ($i > 0) { - $exclude_current = $matrix->[$i - 1][$j]; - } + return $j; +} + +sub go_right { + my ($i, $list) = @_; - $matrix->[$i][$j] = $include_current + $exclude_current; + my $c = $list->[$i]; + my $j = 0; + while ($i < $#$list) { + $i++; + last if ($list->[$i] < $c); + $j++; + } + + return $j; +} + +sub chart { + my ($list) = @_; + + my $max = max(@$list); + my $chart = []; + my $row = 1; + foreach (1..$max) { + my $data = ""; + foreach my $i (0..$#$list) { + if ($row <= $list->[$i]) { + $data .= " #"; + } + else { + $data .= " "; + } } + $row++; + push @$chart, sprintf("%d%s", $_, $data); } - return $matrix->[$size][$sum]; + my ($histogram, $line, $size) = ("", "", " "); + $histogram = join "\n", (reverse @$chart); + $line .= "_ " for (0..$#$list + 1); + $size .= join " ", @$list; + + return join "\n", $histogram, $line, $size; } sub prepare { - my ($coins) = @_; + my ($list) = @_; - if (defined $coins) { - $coins =~ s/\s//g; - return [ split /\,/, $coins ]; + if (defined $list) { + $list =~ s/\s//g; + return [ split /\,/, $list ]; } } -- cgit