- Added solutions by Colin Crain.

4 files changed, 369 insertions, 0 deletions

diff --git a/challenge-079/colin-crain/perl/ch-1.pl b/challenge-079/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..4d54252938
--- /dev/null
+++ b/challenge-079/colin-crain/perl/ch-1.pl
@@ -0,0 +1,122 @@
+#! /opt/local/bin/perl
+#
+#       count_set_match.pl
+#
+#       TASK #1 › Count Set Bits
+#         Submitted by: Mohammad S Anwar
+#         You are given a positive number $N.
+# 
+#         Write a script to count the total number of set bits of the binary
+#         representations of all numbers from 1 to $N and return
+#         $total_count_set_bit % 1000000007.
+# 
+#         Example 1:
+#         Input: $N = 4
+# 
+#         Explanation: First find out the set bit counts of all numbers 
+#             i.e. 1, 2, 3 and 4.
+# 
+#             Decimal: 1
+#             Binary: 001
+#             Set Bit Counts: 1
+# 
+#             Decimal: 2
+#             Binary: 010
+#             Set Bit Counts: 1
+# 
+#             Decimal: 3
+#             Binary: 011
+#             Set Bit Counts: 2
+# 
+#             Decimal: 4
+#             Binary: 100
+#             Set Bit Counts: 1
+# 
+#             Total set bit count: 1 + 1 + 2 + 1 = 5
+# 
+#         Output: Your script should print `5` as `5 % 1000000007 = 5`.
+#         Example 2:
+#         Input: $N = 3
+# 
+#         Explanation: First find out the set bit counts of all numbers 
+#             i.e. 1, 2 and 3.
+# 
+#             Decimal: 1
+#             Binary: 01
+#             Set Bit Count: 1
+# 
+#             Decimal: 2
+#             Binary: 10
+#             Set Bit Count: 1
+# 
+#             Decimal: 3
+#             Binary: 11
+#             Set Bit Count: 2
+# 
+#             Total set bit count: 1 + 1 + 2 = 4
+# 
+#         Output: Your script should print `4` as `4 % 1000000007 = 4`.
+# 
+#         method:
+#             The way I see it, there are three parts to this task. Over a loop
+#             of values, we need to first create a binary representation of a
+#             number, then count and sum the 1s present in those values. For the
+#             third and seemingly, puzzlingly unrelated part, we then modulo the
+#             total by one billion and seven.
+# 
+#             In weeks past, we've found easy ways to convert decimal to binary.
+#             For the counting the 1s step, this is the same as summing every
+#             digit, as these, being binary, are only going to be either 1 or 0.
+#             Breaking the digit string into a list of elements and then summing
+#             these accomplishes this well; after this step the sum is added to
+#             a running total for the sequence of 1 up to the target value.
+# 
+#             As for the modulo phase, a little explanation is in order. The
+#             value 1000000007 is ultimately arbitrary, and is selected because
+#             it:
+#     
+#                 1. is large, but not too large, and
+#                 2. is prime
+#     
+#             Beyond these criteria, there is no meaning behind that specific
+#             choice of number, and 1,000,000,033 would do just as well, or
+#             2,000,000,033. Speaking to the first point, what this selection
+#             does is produce a verifiable, reproducable result that fits into
+#             common integer data types without any risk of overflow.
+# 
+#             This can even be done at every step of a calculation involving
+#             very very large numbers, constructing the correct modulo result
+#             without ever exceeding the range of a 32-bit integer. But then
+#             again there is no requirement here either to process an unusually
+#             big range or for that matter work properly on 32-bit machines. So
+#             even should we wish to include values past 2^32 in our
+#             intermediary steps, the 64-bit norm these day gives us
+#             considerably more range. 
+# 
+#             So we're not going to bother to do that. I do wonder if anyone
+#             will. 
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+use warnings;
+use strict;
+use feature ":5.26";
+
+## ## ## ## ## MAIN:
+
+my $input = shift // 100000;
+my $tot;
+
+for my $i (1..$input) {
+    my $bin = sprintf "%b", $i;
+    my $j = length $bin;
+    while (--$j >= 0 ) {
+        substr( $bin, $j, 1 ) and $tot++;
+    }
+}
+my $out = $tot % 1000000007;
+
+say "out:  $out";
diff --git a/challenge-079/colin-crain/perl/ch-2.pl b/challenge-079/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..3300295a5d
--- /dev/null
+++ b/challenge-079/colin-crain/perl/ch-2.pl
@@ -0,0 +1,103 @@
+#! /opt/local/bin/perl
+#
+#       water_inside_a_duck.pl
+#
+#       TASK #2 › Trapped Rain Water
+#         Submitted by: Mohammad S Anwar
+#         You are given an array of positive numbers @N.
+# 
+#         Write a script to represent it as Histogram Chart and find out how
+#         much water it can trap.
+# 
+#         Example 1:
+#         Input: @N = (2, 1, 4, 1, 2, 5)
+#         The histogram representation of the given array is as below.
+#              5           #
+#              4     #     #
+#              3     #     #
+#              2 #   #   # #
+#              1 # # # # # #
+#              _ _ _ _ _ _ _
+#                2 1 4 1 2 5
+#         Looking at the above histogram, we can see, it can trap 1 unit of rain
+#         water between 1st and 3rd column. Similary it can trap 5 units of rain
+#         water betweem 3rd and last column.
+# 
+#         Therefore your script should print 6.
+# 
+#         Example 2:
+#         Input: @N = (3, 1, 3, 1, 1, 5)
+#         The histogram representation of the given array is as below.
+#              5           #
+#              4           #
+#              3 #   #     #
+#              2 #   #     #
+#              1 # # # # # #
+#              _ _ _ _ _ _ _
+#                3 1 3 1 1 5
+#         Looking at the above histogram, we can see, it can trap 2 units of
+#         rain water between 1st and 3rd column. Also it can trap 4 units of
+#         rain water between 3rd and last column.
+# 
+#         Therefore your script should print 6.
+# 
+#       method:
+
+#             Water falls from the sky and gathers, so that's where we'll start,
+#             at the top, descending.  As we traverse the range from maximum to minimum, each level
+#             of the histogram is examined and an array is created from the
+#             indices of elements that extend to that height or
+#             beyond. A single result represents the solitary highest point that in
+#             itself cannot contain a volume, but any two adjectant elements in
+#             this array represent a gap that, given the opportunity, will fill
+#             with water. 
+# 
+#             Water is assumed to collect in the spaces between the boundries of
+#             the histogram columns, thus it is the non-inclusive interstitial
+#             gap between a pair of indices that represents an expanse of water
+#             at a depth of one unit. Adjacent indices will simply have a gap of
+#             zero and thus will not fill. For each pair of indices, this is a
+#             volume of water collected. Examining in turn each adjacent pair of
+#             elements in the level array, a running tally gathers the total
+#             volume of water at that level. Repeating this process as we
+#             descend down the histogram, until we arrive at the minimum value,
+#             yields the total valume of water trapped by the whole structure. 
+
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+use warnings;
+use strict;
+use feature ":5.26";
+
+## ## ## ## ## MAIN:
+
+my @input = @ARGV;
+
+@input = (3,6,3,1,1,5) if scalar @ARGV == 0;
+
+my ($min,$max) = (sort {$a-$b} @input)[0,$#input];
+
+say "histogram:\n";
+
+my $vol;
+for my $level (reverse($min..$max)) {
+    my @peaks = grep { $input[$_] >= $level } (0..$#input);
+
+    ## draw the histogram while we're here
+    say "$level ", join ' ', map { $input[$_] >= $level ? '#' : ' ' } (0..$#input);
+
+    while (scalar @peaks > 1) {
+        my $start_idx = shift @peaks;
+        $vol += $peaks[0] - $start_idx - 1;
+    }
+}
+
+## out
+say join ' ', ("-") x (scalar @input + 1);
+say '  ', join ' ', @input;
+
+say "\nvolume: $vol";
diff --git a/challenge-079/colin-crain/raku/ch-1.raku b/challenge-079/colin-crain/raku/ch-1.raku
new file mode 100644
index 0000000000..992f7e1861
--- /dev/null
+++ b/challenge-079/colin-crain/raku/ch-1.raku
@@ -0,0 +1,73 @@
+#!/usr/bin/env perl6
+# 
+#
+#       count-set-match.raku
+# 
+#       TASK #1 › Count Set Bits
+#         Submitted by: Mohammad S Anwar
+#         You are given a positive number $N.
+# 
+#         Write a script to count the total number of set bits of the binary
+#         representations of all numbers from 1 to $N and return
+#         $total_count_set_bit % 1000000007.
+# 
+#         Example 1:
+#         Input: $N = 4
+# 
+#         Explanation: First find out the set bit counts of all numbers 
+#             i.e. 1, 2, 3 and 4.
+# 
+#             Decimal: 1
+#             Binary: 001
+#             Set Bit Counts: 1
+# 
+#             Decimal: 2
+#             Binary: 010
+#             Set Bit Counts: 1
+# 
+#             Decimal: 3
+#             Binary: 011
+#             Set Bit Counts: 2
+# 
+#             Decimal: 4
+#             Binary: 100
+#             Set Bit Counts: 1
+# 
+#             Total set bit count: 1 + 1 + 2 + 1 = 5
+# 
+#         Output: Your script should print `5` as `5 % 1000000007 = 5`.
+#         Example 2:
+#         Input: $N = 3
+# 
+#         Explanation: First find out the set bit counts of all numbers 
+#             i.e. 1, 2 and 3.
+# 
+#             Decimal: 1
+#             Binary: 01
+#             Set Bit Count: 1
+# 
+#             Decimal: 2
+#             Binary: 10
+#             Set Bit Count: 1
+# 
+#             Decimal: 3
+#             Binary: 11
+#             Set Bit Count: 2
+# 
+#             Total set bit count: 1 + 1 + 2 = 4
+# 
+#         Output: Your script should print `4` as `4 % 1000000007 = 4`.
+#
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN (Int $input = 100000) ;
+
+my $tot += .base(2).comb.sum for ^$input;
+
+say "input: $input";
+say "total: ", $tot %= 1000000007;
+
diff --git a/challenge-079/colin-crain/raku/ch-2.raku b/challenge-079/colin-crain/raku/ch-2.raku
new file mode 100644
index 0000000000..e3b5e17c12
--- /dev/null
+++ b/challenge-079/colin-crain/raku/ch-2.raku
@@ -0,0 +1,71 @@
+#!/usr/bin/env perl6
+# 
+#
+#       water_inside_a_duck.raku
+#
+#       TASK #2 › Trapped Rain Water
+#         Submitted by: Mohammad S Anwar
+#         You are given an array of positive numbers @N.
+# 
+#         Write a script to represent it as Histogram Chart and find out how
+#         much water it can trap.
+# 
+#         Example 1:
+#         Input: @N = (2, 1, 4, 1, 2, 5)
+#         The histogram representation of the given array is as below.
+#              5           #
+#              4     #     #
+#              3     #     #
+#              2 #   #   # #
+#              1 # # # # # #
+#              _ _ _ _ _ _ _
+#                2 1 4 1 2 5
+#         Looking at the above histogram, we can see, it can trap 1 unit of rain
+#         water between 1st and 3rd column. Similary it can trap 5 units of rain
+#         water betweem 3rd and last column.
+# 
+#         Therefore your script should print 6.
+# 
+#         Example 2:
+#         Input: @N = (3, 1, 3, 1, 1, 5)
+#         The histogram representation of the given array is as below.
+#              5           #
+#              4           #
+#              3 #   #     #
+#              2 #   #     #
+#              1 # # # # # #
+#              _ _ _ _ _ _ _
+#                3 1 3 1 1 5
+#         Looking at the above histogram, we can see, it can trap 2 units of
+#         rain water between 1st and 3rd column. Also it can trap 4 units of
+#         rain water between 3rd and last column.
+# 
+#         Therefore your script should print 6.
+#
+#
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN (*@input) ;
+
+@input.elems == 0 and @input = 9,12,10,6,8,6,9,6; 
+my $vol;
+say "histogram:\n";
+
+for (@input.min..@input.max).reverse -> $level {
+    my @peaks = @input.keys.grep({ @input[$_] >= $level });
+    $vol += ($_[1] - $_[0] - 1) for @peaks.rotor(2=>-1);
+    
+    ## draw the histogram while we're looping through the levels
+    say $level.fmt("%-2s | "), (^@input).map({ @input[$_] >= $level ?? '##' !! '  ' }).join: ' '; 
+}
+
+## out
+say '---+' ~ '---' x @input.elems;
+say '   | ' ~ @input.map(*.fmt("%-3s")).join ~ "\n";
+
+say "volume: ", $vol;
+