- Added solutions by Colin Crain.

4 files changed, 340 insertions, 0 deletions

diff --git a/challenge-151/colin-crain/perl/ch-1.pl b/challenge-151/colin-crain/perl/ch-1.pl
new file mode 100755
index 0000000000..51bff2479e
--- /dev/null
+++ b/challenge-151/colin-crain/perl/ch-1.pl
@@ -0,0 +1,118 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       no-diving-in-the-shallow-end.pl

+#

+#       Binary Tree Depth

+#         Submitted by: Mohammad S Anwar

+#         You are given binary tree.

+# 

+#         Write a script to find the minimum depth.

+# 

+#         The minimum depth is the number of nodes from the root to the

+#         nearest leaf node (node without any children).

+# 

+#         Example 1:

+# 

+#         Input: '1 | 2 3 | 4 5'

+# 

+#                         1

+#                        / \

+#                       2   3

+#                      / \

+#                     4   5

+# 

+#         Output: 2

+# 

+#         Example 2:

+# 

+#         Input: '1 | 2 3 | 4 *  * 5 | * 6'

+# 

+#                         1

+#                        / \

+#                       2   3

+#                      /     \

+#                     4       5

+#                      \

+#                       6

+#         Output: 3

+# 

+#           method:

+# 

+#             So... the robust way or the easy way? Whichis to say do we

+#             build a tree model, perform a depth-first traversal and note

+#             the depth of each node, keeping a running minimal on all leaf

+#             nodes? Or do we work the serial flat data-structure instead?

+#             In the serial format we have a breath-first order laid out

+#             left-to-right

+# 

+# 

+#             One thing different about this tree challenge is that here

+#             wee are given example input in a breadth-first sreialized

+#             string format. In it, we have levels separated by vertical

+#             pipes, with nodes separated by spaces. Empty nodes are

+#             indicated by asterisks; in this way the segment from the

+#             second example "| 4 *  * 5 |" reveals the thrid level has

+#             four nodes and the middle two are null.

+# 

+#             At the end of the string remaining null nodes to fill out the

+#             level are left inplicit and not signified. Although no

+#             examples exist, the child nodes of a null node would also be

+#             null and so indicated with asterisks, which are necessary to

+#             unambiguously mark individual node placement within the

+#             structure.

+# 

+#             All this amounts to a parsable flat format where the child

+#             nodes have a mathematical relationship to the indices of the

+#             parent: 2n+1 and 2n+2.

+# 

+#             If we traverse the tree from left to right we can check each

+#             node, and, if both children are null we have found a leaf. As

+#             the levels ascend from left-to-right the first leaf found

+#             will have the minimum depth.

+#

+#       © 2022 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use utf8;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+

+

+

+my $input = shift ;

+say mindepth( parse( $input ) ) if defined $input;;

+

+sub parse ( $input ) {

+    return map { $_ eq '*' ? undef : $_ } 

+           grep { $_ ne '|' } 

+           split ' ', $input;

+}

+

+sub mindepth ( @tree ) {

+    my $level = 1 ;

+    my $count = 0 ;

+    

+    for my $idx ( 0 .. $#tree ) {

+        return $level if ( defined $tree[$idx]  

+                            and not defined $tree[$idx * 2 + 1]

+                            and not defined $tree[$idx * 2 + 2] ) ;

+        $level++ and $count = 0 if ++$count == 2 ** ($level-1) ;    

+    }

+}

+

+

+

+use Test::More;

+

+is mindepth( parse('1 | 2 3 | 4 5') ), 2, 'ex-1';

+is mindepth( parse('1 | 2 3 | 4 *  * 5 | * 6') ), 3, 'ex-2';

+is mindepth( parse('A | B C | D E  F G | H I  J L   M N  O P') ), 4, 'deeper';

+is mindepth( parse('X') ), 1, 'root';

+

+

+done_testing();

diff --git a/challenge-151/colin-crain/perl/ch-2.pl b/challenge-151/colin-crain/perl/ch-2.pl
new file mode 100755
index 0000000000..a12aad87fe
--- /dev/null
+++ b/challenge-151/colin-crain/perl/ch-2.pl
@@ -0,0 +1,118 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       daylight-robbery.pl

+#

+#       Rob The House

+#         Submitted by: Mohammad S Anwar

+#         You are planning to rob a row of houses, always starting with the

+#         first and moving in the same direction. However, you can’t rob

+#         two adjacent houses.

+# 

+#         Write a script to find the highest possible gain that can be

+#         achieved.

+# 

+#         Example 1:

+#             Input: @valuables = (2, 4, 5);

+#             Output: 7

+# 

+#         If we rob house (index=0) we get 2 and then the only house we can

+#         rob is house (index=2) where we have 5. So the total valuables in

+#         this case is (2 + 5) = 7.

+# 

+#         Example 2:

+#             Input: @valuables = (4, 2, 3, 6, 5, 3);

+#             Output: 13

+# 

+#         The best choice would be to first rob house (index=0) then rob

+#         house (index=3) then finally house (index=5). This would give us

+#         4 + 6 + 3 =13.

+# 

+#       method:

+

+#         In this version of the travelling burglar problem, wait, is that

+#         a thing? I thought that was a thing. Oh well, in any case, the

+#         goal here is to optimize our selection along an ordered sequence

+#         governed by a set of rules:

+# 

+#             1. we can ony proceed forward

+#             2. we must skip the next element in any movement.

+#             3. the goal is the highest sum of gathered elements

+#             

+#         There is no further governance on the selection of elements, but

+#         some optimal emergent behavior can be derived to guide us to a

+#         winning strategy. For example, from any element we should move

+#         forward either 2 or 3 positions. We cannot move one, and any

+#         position greater than 3 can be arrived at by some combination of

+#         intermediatary steps: position 4 can be broken down into 2 + 2, 5

+#         as 2 + 3 or 3 + 2. As all values are positive (or at least 0, but

+#         not negative) there is never a downside to adding an intermediate

+#         stopover.

+# 

+#         So 2 or 3 it is.

+# 

+#         After 2 or 3, however, there is a problem with looking ahead, as

+#         the element at position n+4 is always dependant on the choices

+#         made previously, as it can only be arrived at in one specific

+#         manner. Furthermore, this predicate dependancy can be

+#         indefinitely extended to the chain of all 2-separate values,

+#         which can only be achieved by making the 2-selectiomn from the

+#         very beginning. There are two such sequences in every list,

+#         corresponding to the ood- and even-numbered indices, that

+#         maximize the number of elements selected, that can only be

+#         arrived at by making specific mutulaly-exclusive choices at the

+#         beginning of the run.

+# 

+#         In short, in order to sum these sequences, each needs to be

+#         started separately and run through completely, examining every

+#         element. As they may also contain the maximal sum, then therefore

+#         we need to look at every value before we can make the

+#         determination of which pattern maximizes the sum.

+# 

+#         So we need to look at all the patterns first. There's no escaping

+#         that. Or at least the whole list of values. Maybe not every

+#         pattern, actually. But pruniing the search tree will be tricky if

+#         it's even possible.

+# 

+#         It looks like we will need ot look at every pattern of 2- and

+#         3-jumps, starting at either the 0th or 1st position.

+# 

+#         As we are tasked with robbing real imaginary houses along a real

+#         imaginary block we can assume the number of houses to be finite

+#         and not excessively large. But the algorithm will bog down

+#         eventually, just to put that out front. 

+# 

+#         

+#         

+#

+#       © 2022 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use utf8;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+

+

+our @arr = (

+1, 2, 3, 6, 5, 3, 8, 1, 1, 1, 

+2, 3, 6, 5, 3, 8, 1, 1, 1, 2, 

+3, 6, 5, 3, 8, 1, 1, 1, 2, 3, 

+6, 5, 3, 8, 1, 1, 1, 2, 3, 6, 

+5, 3, 8, 1, 1, 1, 2, 3, 6, 5, 

+3, 8, 1, 1, 1, 2, 6, 5, 3, 8 );

+

+

+say lookahead( );

+

+sub lookahead ( $pos = -2, $sum = 0 ) {

+    return $sum if $pos > $#arr;

+    $sum += $arr[ $pos ] if $pos >= 0;

+    my $two   = lookahead( $pos + 2, $sum ) ;

+    my $three = lookahead( $pos + 3, $sum ) ;

+    return $two > $three ? $two : $three ;

+}

+

diff --git a/challenge-151/colin-crain/raku/ch-1.raku b/challenge-151/colin-crain/raku/ch-1.raku
new file mode 100755
index 0000000000..d305cf45e5
--- /dev/null
+++ b/challenge-151/colin-crain/raku/ch-1.raku
@@ -0,0 +1,77 @@
+#!/usr/bin/env perl6
+#
+#
+#       151-1-no-diving-in-the-shallow-end.raku
+#
+#
+#
+#       © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN ( $input = '1 | 2 3 | 4 *  * 5 | * 6' ) ;
+
+say mindepth( parse( $input ) );
+
+sub parse ( $input ) {
+    $input  .split(/\s+/)
+            .grep( * ne '|')
+            .map: {$_ eq '*' ?? Nil !! $_} ;
+}
+
+sub mindepth ( @tree ) {
+    my ( $level, $count ) = ( 1, 0 );
+    for @tree.keys -> $idx {
+        return $level if @tree[$idx].defined 
+                        and not @tree[$idx * 2 + 1].defined 
+                        and not @tree[$idx * 2 + 2].defined ;
+                        
+        $level++ and $count = 0 if ++$count == 2 ** ($level-1);
+    }
+}
+
+use Test;
+
+is mindepth( parse('1 | 2 3 | 4 5') ), 2, 'ex-1';
+is mindepth( parse('1 | 2 3 | 4 *  * 5 | * 6') ), 3, 'ex-2';
+is mindepth( parse('A | B C | D E  F G | H I  J L   M N  O P') ), 4, 'deeper';
+is mindepth( parse('X') ), 1, 'root';
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+# my $input = shift ;
+# say mindepth( parse( $input ) ) if defined $input;;
+# 
+# sub parse ( $input ) {
+#     return map { $_ eq '*' ? undef : $_ } 
+#            grep { $_ ne '|' } 
+#            split ' ', $input;
+# }
+# 
+# sub mindepth ( @tree ) {
+#     my $level = 1 ;
+#     my $count = 0 ;
+#     
+#     for my $idx ( 0 .. $#tree ) {
+#         return $level if ( defined $tree[$idx]  
+#                             and not defined $tree[$idx * 2 + 1]
+#                             and not defined $tree[$idx * 2 + 2] ) ;
+#         $level++ and $count = 0 if ++$count == 2 ** ($level-1) ;    
+#     }
+# }
+# 
diff --git a/challenge-151/colin-crain/raku/ch-2.raku b/challenge-151/colin-crain/raku/ch-2.raku
new file mode 100755
index 0000000000..34340002f3
--- /dev/null
+++ b/challenge-151/colin-crain/raku/ch-2.raku
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl6
+#
+#
+#       daylight-robbery.raku
+#
+#
+#
+#       © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN ( *@arr ) ;
+
+
+## test data
+@arr = 1,2,3,4 if @arr.elems == 0;
+
+say lookahead();
+
+sub lookahead( $pos = -2, $sum is copy = 0) {
+    return $sum if $pos > @arr.end;
+    $pos >= 0 && $sum += @arr[$pos];
+    ( lookahead( $pos + $_, $sum ) for 2, 3 ).max
+}
+
+