- Added solutions by Colin Crain.

4 files changed, 458 insertions, 0 deletions

diff --git a/challenge-075/colin-crain/perl/ch-1.pl b/challenge-075/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..acc48f6524
--- /dev/null
+++ b/challenge-075/colin-crain/perl/ch-1.pl
@@ -0,0 +1,100 @@
+#! /opt/local/bin/perl
+#
+#       change_is_gonna_come.pl
+#
+#         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.
+# 
+#         Example:
+#         Input:
+#             @C = (1, 2, 4)
+#             $S = 6
+# 
+#         Output: 6
+#             There are 6 possible ways to make sum 6.
+#                 a) (1, 1, 1, 1, 1, 1)
+#                 b) (1, 1, 1, 1, 2)
+#                 c) (1, 1, 2, 2)
+#                 d) (1, 1, 4)
+#                 e) (2, 2, 2)
+#                 f) (2, 4)
+# 
+#         method:
+#             Recursive routine that diminishes the options available in the
+#             coin bag as the total anount remaining decreases. Builds a
+#             branching tree of coin groupings until no more coins can be used
+#             or remaining amount to be tendered is 0.
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+use warnings;
+use strict;
+use feature ":5.26";
+
+## ## ## ## ## MAIN:
+
+## in
+my $S      = shift @ARGV // 27;
+our @coins = sort { $a <=> $b} @ARGV;
+@coins     = (2,5,10,25) if ! @ARGV;
+our @solutions;
+
+## work
+get_coin_groups($S);
+
+## out
+print_output(\@solutions);
+
+## ## ## ## ## SUBS:
+
+sub get_coin_groups {
+    my ($amt, $group, $bag) = @_;
+    $group //= [];
+    $bag     //= \@coins;
+    
+    ## base case, cashed out
+    if ($amt == 0) {
+        push @solutions, $group;
+        return;
+    }
+    
+    ## limit coin bag to those smaller or equal to the current amount
+    my @coin_bag = grep { $_ <= $amt } $bag->@*;
+    
+    ## edge case, cannot complete group with remaining coins
+    if (@coin_bag == 0) {
+        return;
+    }
+    
+    for my $coin ( @coin_bag ) {        
+        ## limit coin bag to this coin or smaller
+        ## keeps groups ordered and disallows duplicate rearrangements
+        my @smaller_coin_bag = grep { $_ <= $coin } $bag->@*; 
+        get_coin_groups( $amt - $coin, [@$group, $coin], \@smaller_coin_bag );
+    }
+}
+
+sub print_output {
+use Lingua::EN::Inflexion;
+    my ($output, $sum ) = @_;
+    my $count = scalar $output->@*;
+    
+    say<<"__EOD__";
+Input:
+    \@C = (@coins)
+    \$S = $S
+__EOD__
+ 
+    say "Output: $count";
+    my $str = inflect("<#d:$count>There <V:is> <#wnc:$count> possible <N:ways> to make the sum $S.");
+    say $str;
+    
+    my @letter_prefixes = ('a'..'z', 'aa'..'zz');
+    say "\t", shift @letter_prefixes, ')  (', (join ', ', $_->@*), ')' for @solutions;
+
+}
+
diff --git a/challenge-075/colin-crain/perl/ch-2.pl b/challenge-075/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..d09c971d5c
--- /dev/null
+++ b/challenge-075/colin-crain/perl/ch-2.pl
@@ -0,0 +1,139 @@
+#! /opt/local/bin/perl
+#
+#         75_2_windows_wide_open.pl
+#
+#         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 larget rectangle histogram created by the
+#             given array.
+# 
+#             BONUS: Try to print the histogram as shown in the example, if
+#             possible.
+# 
+#         Example 1:
+# 
+#             Input: @A = (2, 1, 4, 5, 3, 7)
+#                  7           #
+#                  6           #
+#                  5       #   #
+#                  4     # #   #
+#                  3     # # # #
+#                  2 #   # # # #
+#                  1 # # # # # #
+#                  _ _ _ _ _ _ _
+#                    2 1 4 5 3 7
+# 
+#             Looking at the above histogram, the largest rectangle (4 x 3) is
+#             formed by columns (4, 5, 3 and 7).
+# 
+#             Output: 12
+# 
+#         Example 2:
+# 
+#             Input: @A = (3, 2, 3, 5, 7, 5)
+#                  7         #
+#                  6         #
+#                  5       # # #
+#                  4       # # #
+#                  3 #   # # # #
+#                  2 # # # # # #
+#                  1 # # # # # #
+#                  _ _ _ _ _ _ _
+#                    3 2 3 5 7 5
+#             Looking at the above histogram, the largest rectangle (3 x 5) is
+#             formed by columns (5, 7 and 5).
+# 
+#         Output: 15
+# 
+#       
+## ## ## ## ##
+# 
+#         method:
+#             The rectangular area under a range is defined by the minimum value
+#             within that range and the width of the span.
+# 
+#             So by looking at each range set within the bounds of the array, we
+#             can find the corresponding minimum; multiplying that by the width
+#             of the window gives us the area of the rectangle.
+# 
+#             We are asked to find the maximum rectangle, but if we wish to
+#             allow for multiple equal areas, outputting all values, we need
+#             to keep all the rectangle data and review it before reporting. We
+#             can keep everything in an array of arrays, with a structure for
+#             [Area, Start, End, Height] and descending sort by area. Take the
+#             first value and compare to the next until it differs; these will
+#             be the maximum rectangles.
+# 
+#             We will choose to not consider a single data point to be a proper
+#             rectangle, more like a line, so in altering the input of example
+#             number 2 to the list (3, 2, 3, 5, 7, 16), the result would still
+#             be 15, being the rectangle with height 5 over (5,7,16), rather
+#             than just the 16 value. It would be easy enough to fudge the
+#             iterators to make it work that way, but I consider it to be a
+#             degenerate and slightly boring case, overly sensitive to outliers
+#             and signal noise. Let's keep it interesting and say rectangles
+#             need at minimum width 2.
+# 
+#                 array 6 14 17 1 20 7 15 5 10 19 16 13
+# 
+#                 rectangle found at:
+#                     start index 4
+#                     end index   11
+#                     height      5
+#                     width       8
+#                     area        40
+# 
+#                 rectangle found at:
+#                     start index 8
+#                     end index   11
+#                     height      10
+#                     width       4
+#                     area        40
+# 
+# 
+# 
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+use warnings;
+use strict;
+use feature ":5.26";
+
+use List::Util qw( min sample );
+
+## ## ## ## ## MAIN:
+
+my @A = sample 12, (1..24);
+my @windows;
+
+for my $start (0..@A-2) {
+    for my $end ($start+1..@A-1) {
+        my $min = min @A[$start..$end];
+        push @windows, [$min*($end-$start+1), $start, $end, $min];
+    }
+} 
+
+my @sorted  = sort { $b->[0] <=> $a->[0]        } @windows;
+my @largest = grep { $_->[0] == $sorted[0]->[0] } @sorted;
+
+say "array (@A)";
+
+for my $rect ( @largest ) {
+    my $width = $rect->[2] - $rect->[1] + 1;
+    say<<__EOD__;
+
+rectangle found at:
+    start index $rect->[1]
+    end index   $rect->[2]
+    height      $rect->[3]
+    width       $width
+    area        $rect->[0]
+__EOD__
+}
+
+
+
diff --git a/challenge-075/colin-crain/raku/ch-1.raku b/challenge-075/colin-crain/raku/ch-1.raku
new file mode 100644
index 0000000000..3c40079d02
--- /dev/null
+++ b/challenge-075/colin-crain/raku/ch-1.raku
@@ -0,0 +1,89 @@
+#!/usr/bin/env perl6
+# 
+#
+#       change_is_gonna_come.raku
+#
+#         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.
+# 
+#         Example:
+#         Input:
+#             @C = (1, 2, 4)
+#             $S = 6
+# 
+#         Output: 6
+#             There are 6 possible ways to make sum 6.
+#                 a) (1, 1, 1, 1, 1, 1)
+#                 b) (1, 1, 1, 1, 2)
+#                 c) (1, 1, 2, 2)
+#                 d) (1, 1, 4)
+#                 e) (2, 2, 2)
+#                 f) (2, 4)
+# 
+#         method:
+#             Recursive routine that diminishes the options available in the
+#             coin bag as the total anount remaining decreases. Builds a
+#             branching tree of coin groupings until no more coins can be used
+#             or remaining amount to be tendered is 0.
+#
+#
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN ($S = 27, *@coins) ;
+
+# cfg
+@coins = (2,5,10,25) if @coins.elems == 0;
+@coins .= sort( { $^a <=> $^b } );
+my @solutions;
+
+# work
+get_coin_groups($S);
+
+# out
+print_output(@solutions);
+
+## ## ## ## ##
+
+sub get_coin_groups ($amt, @group = [], @bag = @coins) {
+
+    ## base case, cashed out
+    $amt == 0 and return @solutions.push: @group;
+
+    ## limit coin bag to those smaller or equal to the current amount
+    my @coin_bag = @bag.grep: { $_ <= $amt } ;
+    
+    ## edge case, cannot complete group with remaining coins
+    @coin_bag == 0 and return;
+
+    for @coin_bag -> $coin {
+        ## limit coin bag to this coin or smaller than this coin
+        ## keeps groups ordered and disallows duplicate rearrangements
+        my @smaller_coin_bag = @bag.grep: { $_ <= $coin } ;
+        get_coin_groups( $amt - $coin, ( |@group, $coin ) , @smaller_coin_bag );
+    }
+}
+
+sub print_output ($output) {
+    my $count = $output.elems;
+    
+    say "Input:\n    \@C = ", @coins;
+    say "    \$S = $S\n";
+    say "Output: $count";
+    say $count == 1 
+        ?? "There is one possible way to make sum $S"
+        !! "There are $count ways to make sum $S";
+        
+    
+    my @letter_prefixes = |('a'..'z'), |('aa'..'zz');
+    say "\t", @letter_prefixes.shift, ') ', $_ for @solutions;
+
+}
+
+
diff --git a/challenge-075/colin-crain/raku/ch-2.raku b/challenge-075/colin-crain/raku/ch-2.raku
new file mode 100644
index 0000000000..589c0ed895
--- /dev/null
+++ b/challenge-075/colin-crain/raku/ch-2.raku
@@ -0,0 +1,130 @@
+#!/usr/bin/env perl6
+# 
+#
+#         75_2_windows_wide_open.raku
+#
+#         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 larget rectangle histogram created by the
+#             given array.
+# 
+#             BONUS: Try to print the histogram as shown in the example, if
+#             possible.
+# 
+#         Example 1:
+# 
+#             Input: @A = (2, 1, 4, 5, 3, 7)
+#                  7           #
+#                  6           #
+#                  5       #   #
+#                  4     # #   #
+#                  3     # # # #
+#                  2 #   # # # #
+#                  1 # # # # # #
+#                  _ _ _ _ _ _ _
+#                    2 1 4 5 3 7
+# 
+#             Looking at the above histogram, the largest rectangle (4 x 3) is
+#             formed by columns (4, 5, 3 and 7).
+# 
+#             Output: 12
+# 
+#         Example 2:
+# 
+#             Input: @A = (3, 2, 3, 5, 7, 5)
+#                  7         #
+#                  6         #
+#                  5       # # #
+#                  4       # # #
+#                  3 #   # # # #
+#                  2 # # # # # #
+#                  1 # # # # # #
+#                  _ _ _ _ _ _ _
+#                    3 2 3 5 7 5
+#             Looking at the above histogram, the largest rectangle (3 x 5) is
+#             formed by columns (5, 7 and 5).
+# 
+#         Output: 15
+# 
+#       
+## ## ## ## ##
+# 
+#         method:
+#             The rectangular area under a range is defined by the minimum value
+#             within that range and the width of the span.
+# 
+#             So by looking at each range set within the bounds of the array, we
+#             can find the corresponding minimum; multiplying that by the width
+#             of the window gives us the area of the rectangle.
+# 
+#             We are asked to find the maximum rectangle, but if we wish to
+#             allow for multiple equal areas, outputting all values, we need
+#             to keep all the rectangle data and review it before reporting. We
+#             can keep everything in an array of arrays, with a structure for
+#             [Area, Start, End, Height] and descending sort by area. Take the
+#             max value and find any others matching; these will
+#             be the maximum rectangles.
+# 
+#             We will choose to not consider a single data point to be a proper
+#             rectangle, more like a line, so in altering the input of example
+#             number 2 to the list (3, 2, 3, 5, 7, 16), the result would still
+#             be 15, being the rectangle with height 5 over (5,7,16), rather
+#             than just the 16 value. It would be easy enough to fudge the
+#             iterators to make it work that way, but I consider it to be a
+#             degenerate and slightly boring case, overly sensitive to outliers
+#             and signal noise. Let's keep it interesting and say rectangles
+#             need at minimum width 2.
+# 
+#                 array 6 14 17 1 20 7 15 5 10 19 16 13
+# 
+#                 rectangle found at:
+#                     start index 4
+#                     end index   11
+#                     height      5
+#                     width       8
+#                     area        40
+# 
+#                 rectangle found at:
+#                     start index 8
+#                     end index   11
+#                     height      10
+#                     width       4
+#                     area        40#
+#
+#
+#       2020 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+unit sub MAIN () ;
+
+## cfg
+my @A = (^24).pick(12);
+my @windows;
+
+## work
+for (^@A.elems).combinations(2) -> ($start, $end) {
+    my $min = @A[$start..$end].min;
+    @windows.push: ($min*($start..$end).elems, $start, $end, $min);
+}
+
+my $max     = @windows.max({$_[0]});
+my @largest = @windows.grep({ $_[0] == $max[0] });
+
+
+## out
+say "array ", @A, "\n";
+for @largest -> @r {
+    my $width = @r[2]-@r[1]+1;
+    
+    say qq:to/__EOD__/;
+        rectangle found at:
+            start index @r[1]
+            end index   @r[2]
+            height      @r[3]
+            width       $width
+            area        @r[0]
+        __EOD__
+}
+