HEADLINE
The week #075 tasks turned out to be a lot trickier than expected. Generally Task #1 is meant for beginners only but this time it was not the case. It wasn’t my plan when I proposed the task. I thought couple of for-loops and job done. But when I actually started working on the task, I realised it wasn’t as simple as I thought initially. But the good thing is, I got to know about Dynamic Programming (DP).
With the power of DP, the task became piece of cake. While working on the task, I got the idea of similar task which I might propose in the coming weeks. The second task Largest Rectangle Histogram was lot fun to work with. Printing the histogram brought back memory from my early programming days.
I was little nervous when working with Swift this time. Having done this for over a month now, I feel much comfortable. Initial plan was to do in Java as well but gave up after lack of time. I will re-visit later as it is ideal to brush up Java syntax.
If you are interested then please checkout my Swift solutions to this week tasks.
1) Coins Sum
2) Largest Rectangle Histogram
YouTube Weekly
I present live coding session of mine for the tasks of the week. Please do comment the video if you have any suggestions. And if you like the video then please consider subscribing my YouTube Channel.
1) Coins Sum
2) Largest Rectangle Histogram
Last but not the least, I would to love hear your view/opinion with regard to anything I do.
Please get in touch with me by email: mohammad.anwar@yahoo.com.
Let me share my solutions to the The Weekly Challenge - 075.
TASK #1 › Coins Sum
Submitted by Mohammad S Anwar
You are given a set of coins @C, assuming you have infinite amount of each coin in the set.
Write a script to find how many ways you make sum $S using the coins from the set @C.
Using the Dynamic Programming (DP) technique, I built the $matrix containing the buildup results. The key cross columns are the coin sum starting with 0 to the desired sum. Similarly across the rows, coins, in ascending order.
For example, if the given coins are 1, 2, 4 and sum is 6, the keys across the columns would be 0, 1, 3, 4, 5, 6 and across the rows would be 1, 2, 4. With the help the two for-loops we built the $matrix. In the end returns the value from the $matrix.
sub coins_sum {
my ($coins, $sum) = @_;
my $size = $#$coins;
return 0 if ($size == -1 || $sum <= 0);
my $matrix;
# Sum of 0 can be achieved in one possible way.
$matrix->[$_][0] = 1 for (0 .. $size+1);
foreach my $i (0 .. $size) {
foreach my $j (1 .. $sum) {
my $include_current = 0;
my $exclude_current = 0;
if ($coins->[$i] <= $j) {
$include_current = $matrix->[$i][$j - $coins->[$i]];
}
if ($i > 0) {
$exclude_current = $matrix->[$i - 1][$j];
}
$matrix->[$i][$j] = $include_current + $exclude_current;
}
}
return $matrix->[$size][$sum];
}
sub prepare {
my ($coins) = @_;
if (defined $coins) {
$coins =~ s/\s//g;
return [ split /\,/, $coins ];
}
}
For Raku version, it is literally translated from the Perl without any special effects except the following one line.
my $_coins = [ $coins.split(',').map({ .Int }) ];
The above line takes a string and split by ,. In the end cast every element as Int.
sub coins-sum(Str $coins is copy, Int $sum) returns Int {
die "ERROR: Invalid coins [$coins].\n"
unless $coins ~~ /^[\s?\-?\d\,?\s?]+$/;
say "Coins: $coins";
$coins ~~ s:g/\s//;
my $_coins = [ $coins.split(',').map({ .Int }) ];
my $size = $_coins.elems;
return 0 if ($size == 0 || $sum <= 0);
my $matrix;
# Sum of 0 can be achieved in one possible way.
$matrix.[$_][0] = 1 for (0 .. $size-1);
for 0 .. $size-1 -> $i {
for 1 .. $sum -> $j {
my Int $include-current = 0;
my Int $exclude-current = 0;
if $_coins.[$i] <= $j {
$include-current = $matrix.[$i][$j - $_coins.[$i]];
}
if $i > 0 {
$exclude-current = $matrix.[$i - 1][$j];
}
$matrix.[$i][$j] = $include-current + $exclude-current;
}
}
return $matrix.[$size-1][$sum];
}
Here we have one-liner solution to the Coins Sum task.
use strict;
use warnings;
my $COINS = $ARGV[0] || "1, 2, 4";
my $SUM = $ARGV[1] || 6;
print "Possible ways to achieve the target: ",
coins_sum(prepare($COINS), $SUM), "\n";
Followed by Raku one-liner with power of MAIN().
use v6.d;
sub MAIN(Str :$COINS = "1, 2, 4", Int :$SUM = 6) {
say "Possible ways to achieve the target: " ~
coins-sum($COINS, $SUM);
}
Because of lack of time, I went for simple unit test.
use strict;
use warnings;
use Test::More;
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;
done_testing;
Raku unit test is as simple as ever.
use Test;
is coins-sum("1, 2", 5), 3, "Coins=[1, 2] Sum=5";
is coins-sum("1, 2, 3", 5), 5, "Coins=[1, 2, 3] Sum=5";
is coins-sum("1, 2, 4", 6), 6, "Coins=[1, 2, 4] Sum=6";
is coins-sum("25, 10, 5", 30), 5, "Coins=[25, 10, 5] Sum=30";
is coins-sum("9, 6, 5, 1", 11), 6, "Coins=[9, 6, 5, 1] Sum=6";
done-testing;
TASK #2 › Largest Rectangle Histogram
Submitted by Mohammad S Anwar
You are given an array of positive numbers @A.
Write a script to find the largest rectangle histogram created by the given array.
BONUS: Try to print the histogram as shown in the example, if possible.
I had so much fun working with Largest Rectangle Histogram task. I dealt the bonus task first as it was easier than the main task. For this I created sub chart(). For the main task, I created sub largest_rectangle_histogram(). The core of the task done inside two helper methods sub go_left() and sub go_right(). I could have merged the two and have just one. But I decided against the idea for readability purpose.
sub largest_rectangle_histogram {
my ($list) = @_;
my $i = 0;
my $max = 0;
foreach my $n (@$list) {
my ($left, $right) = (0, 0);
$left = go_left($i, $list) if ($i > 0);
$right = go_right($i, $list) if ($i <= $#$list);
my @heights = (@$list)[$i - $left .. $i + $right];
my $size = min(@heights) * @heights;
$max = $size if ($size > $max);
$i++;
}
return $max;
}
sub go_left {
my ($i, $list) = @_;
my $c = $list->[$i];
my $j = 0;
while ($i > 0) {
$i--;
last if ($list->[$i] < $c);
$j++;
}
return $j;
}
sub go_right {
my ($i, $list) = @_;
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);
}
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 ($list) = @_;
if (defined $list) {
$list =~ s/\s//g;
return [ split /\,/, $list ];
}
}
Once again, Raku version is literal translation of the above Perl solution with just one special magical line.
my $heights = $list.[$i - $left .. $i + $right];
The above line does list slicing.
sub largest-rectangle-histogram($list where .all ~~ Int) returns Int {
my Int $i = 0;
my Int $max = 0;
for 0 .. $list.elems-1 -> $i {
my (Int $left, Int $right) = (0, 0);
$left = go-left($i, $list) if $i > 0;
$right = go-right($i, $list) if $i < $list.elems;
my $heights = $list.[$i - $left .. $i + $right];
my $size = $heights.min * $heights.elems;
$max = $size if $size > $max;
}
return $max;
}
sub go-left(Int $i is copy, $list where .all ~~ Int) returns Int {
my $c = $list.[$i];
my $j = 0;
while $i > 0 {
$i = $i - 1;
last if $list.[$i] < $c;
$j = $j + 1;
}
return $j;
}
sub go-right(Int $i is copy, $list where .all ~~ Int) returns Int {
my $c = $list.[$i];
my $j = 0;
while $i < $list.elems-1 {
$i += 1;
last if $list.[$i] < $c;
$j += 1;
}
return $j;
}
sub chart($list where .all ~~ Int) returns Str {
my $max = $list.max;
my $chart = [];
my $row = 1;
for 1 .. $max -> $n {
my Str $data = "";
for 0 .. $list.elems-1 -> $i {
if $row <= $list.[$i] {
$data ~= " #";
}
else {
$data ~= " ";
}
}
$row += 1;
$chart.push: sprintf("%d%s", $n, $data);
}
my (Str $histogram, Str $line, Str $size) = ("", "", " ");
$histogram = $chart.reverse.join("\n");
$line ~= "_ " for 0 .. $list.elems;
$size ~= $list.join(" ");
return ($histogram, $line, $size).join("\n");
}
sub prepare(Str $list is copy) {
return unless $list.defined;
die "ERROR: Invalid list [$list].\n"
unless $list ~~ /^[\s?\-?\d\,?\s?]+$/;
$list ~~ s:g/\s//;
return [ $list.split(',').map({ .Int }) ];
}
Simple wrapper around the sub largest_rectangle_histogram() solves the task.
use strict;
use warnings;
use List::Util qw(min max);
my $L = $ARGV[0] || "2, 1, 4, 5, 3, 7";
my $list = prepare($L);
print chart($list), "\n\n";
print "Largest Rectangle Histogram: ", largest_rectangle_histogram($list), "\n";
Raku does the same to get the work done.
use v6.d;
sub MAIN(Str :$LIST = "2, 1, 4, 5, 3, 7") {
my $list = prepare($LIST);
chart($list).say;
say "Largest Rectangle Histogram: " ~
largest-rectangle-histogram($list);
}
Once again, I took the easy route for unit test.
use strict;
use warnings;
use Test::More;
use List::Util qw(min max);
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;
Raku unit test is forever simple and easy to follow.
use Test;
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;
That’s it for this week. Speak to you soon.