- Added solutions by Colin Crain.

7 files changed, 530 insertions, 0 deletions

diff --git a/challenge-111/colin-crain/blog.txt b/challenge-111/colin-crain/blog.txt
new file mode 100644
index 0000000000..f305f74070
--- /dev/null
+++ b/challenge-111/colin-crain/blog.txt
@@ -0,0 +1 @@
+https://colincrain.com/2021/05/09/are-we-in-the-matrix-get-in-line-friend-get-in-line/
diff --git a/challenge-111/colin-crain/perl/ch-1.pl b/challenge-111/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..7a6a9290c2
--- /dev/null
+++ b/challenge-111/colin-crain/perl/ch-1.pl
@@ -0,0 +1,238 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       are-we-in.pl

+#

+#       Search Matrix

+#         Submitted by: Mohammad S Anwar

+#         You are given 5x5 matrix filled with integers such that each row is

+#         sorted from left to right and the first integer of each row is greater

+#         than the last integer of the previous row.

+# 

+#         Write a script to find a given integer in the matrix using an

+#         efficient search algorithm.

+# 

+#         Example

+# 

+#             Matrix: [  1,  2,  3,  5,  7 ]

+#                     [  9, 11, 15, 19, 20 ]

+#                     [ 23, 24, 25, 29, 31 ]

+#                     [ 32, 33, 39, 40, 42 ]

+#                     [ 45, 47, 48, 49, 50 ]

+# 

+#             Input:  35

+#             Output: 0     since it is missing in the matrix

+# 

+#             Input:  39

+#             Output: 1     as it exists in the matrix

+# 

+#         method: 

+#             we have two nested, sorted datasets. We need to first locate the

+#             correct row that the value may be located in, then search the row

+#             iteslf to look for a matching element. "Efficiency" becomes a

+#             somewhat difficult to interpret term when sorting a through 25

+#             values, as literally any method is likely to be lightning fast.

+#             The overhead for the conditionals in implementing a binary search,

+#             for example, would probably add more operations than saved, over

+#             time.

+# 

+#             As it's unclear exactly where the line of simplicity versus

+#             optimized searching is going to fall, we're going to set up a

+#             variety of methods and see what works best. As the task was quite

+#             clear that we will be working with a set 5×5 matrix we will tune

+#             especially for that, rather than a more general-purpose solution.

+#             

+#         solutions:

+#             1. flatten the matrix and look inside. The first version used

+#             `List::Util::any()` to look through the array because it sounded

+#             fast and the docs promnised it would short-circuit as soon as it

+#             found a match. The docs said because of this it could replace

+#             `grep`. `grep` turned out to be significantly faster. Perl is a

+#             well-tuned machine.

+# 

+#             2. move listwise through the rows until our value is below the

+#             last element, starting from row 0. This method definitively

+#             identifies the value as belonging within a specific row, which can

+#             then be searched. As with the previous example, I started with

+#             `any`, then sped things up significantly using `grep`. As there

+#             are only 5 values, I tried unwinding the `grep` into a cascading

+#             conditional, and got another 10% speed boost.

+# 

+#             3. I tried a very simple divide-and-conquer algorithm, starting at

+#             the middle row and moving either up or down from there. I hit on

+#             using the spaceship operator from `sort`, figuring it would be a

+#             strong target for optimization. By summing the operations of

+#             comparing the target value to the first and last elements of the

+#             middle array, one of the 5 values {-2,-1,0,1,2} will be produced.

+#             The 2 and -2 results mean the selected row is either completely

+#             above or below the target value, and a 0 means the value is above

+#             the lower bound and below the upper — the value is within the row.

+#             Conveniently, the only way to produce a 1 or -1 value is to have a

+#             match with either the upper or lower bound element, allowing us to

+#             return true immediately as we don't need to know which. The

+#             conditionals are aranged to fall through, and should they arrive

+#             at the bottom there are only 3 possible remaining positions that

+#             may match, and these are enumerated with their own conditionals.

+# 

+#             One problem was that should a value lie above one row but below

+#             the next an oscellating state is set up where we move between

+#             checking two rows as the position of the value lies between them.

+#             We need an additional conditional to check for this.

+# 

+#             Despite stripping the control structures and computation to a

+#             minimum I could not get this technique to overtake the simple

+#             row-wise search.

+# 

+#             4. In a last effort to unseat the throne I came up with the

+#             simplest way to divide the row search that I could, with the

+#             smallest amount of extra code. This method starts at the third

+#             row, then moves the seleted row either upwards or downwards from

+#             there. The search within the row remains the same.

+# 

+#             Although this method will locate the correct row in an average

+#             of 2.2 tries, an improvement of the 3 tried of the original, it

+#             ends up running about 10% slower. 

+#             

+#

+#       © 2021 colin crain

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

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+

+our $mat = [  [  1,  2,  3,  5,  7 ],

+              [  9, 11, 15, 19, 20 ],

+              [ 23, 24, 25, 29, 31 ],

+              [ 32, 33, 39, 40, 42 ],

+              [ 45, 47, 48, 49, 50 ]  ];

+

+

+

+sub search_flattened ( $val) {                              ## [1]

+    return (grep {$_ == $val} map {$_->@*} $mat->@*) || '0';

+}

+

+

+sub search_rows ( $val, $row = 0) {                         ## [2]            

+    return 0 if $val > $mat->[-1]->[-1];

+    

+    $row++ while ($val > $mat->[$row]->[-1]);

+    

+    return 1 if (    $val == $mat->[$row]->[0] 

+                  || $val == $mat->[$row]->[1] 

+                  || $val == $mat->[$row]->[2] 

+                  || $val == $mat->[$row]->[3] 

+                  || $val == $mat->[$row]->[4] );

+    return 0;

+}

+

+

+sub search_divide ( $val, $row = 2) {                       ## [3]

+    while (1) {

+        $_ = ($val <=> $mat->[$row]->[0]) + ($val <=> $mat->[$row]->[-1]);

+        if ($_ == -2) {

+            return 0 if ($row == 0) or ($val > $mat->[$row-1]->[-1]);

+            $row--;

+        }

+        elsif ($_ == 2) {

+            return 0 if ($row == $mat->$#*) or ($val < $mat->[$row+1]->[0]);

+            $row++;

+        }

+        elsif ($_) {

+            return 1;

+        }

+        else {

+            return 1 if (   $val == $mat->[$row]->[1] 

+                         || $val == $mat->[$row]->[2] 

+                         || $val == $mat->[$row]->[3] );

+            return 0;

+        }

+    }

+}

+

+sub search_rows_mid ( $val, $row = 2) {                     ## [4]

+    return 0 if $val > $mat->[-1]->[-1] or $val < $mat->[0]->[0] ;

+    

+    $row-- while ($val < $mat->[$row]->[0]);

+    $row++ while ($val > $mat->[$row]->[-1]);

+    

+    return 1 if (    $val == $mat->[$row]->[0] 

+                  || $val == $mat->[$row]->[1] 

+                  || $val == $mat->[$row]->[2] 

+                  || $val == $mat->[$row]->[3] 

+                  || $val == $mat->[$row]->[4] );

+    return 0;

+}

+

+

+

+

+use Test::More;

+

+is search_rows(35), 0, 'ex-1-rows';

+is search_rows(39), 1, 'ex-2-rows';

+

+is search_rows_mid(35), 0, 'ex-1-rows-mid';

+is search_rows_mid(39), 1, 'ex-2-rows-mid';

+

+is search_flattened(35), 0, 'ex-1-flat';

+is search_flattened(39), 1, 'ex-1-flat';

+

+is search_divide(35), 0, 'ex-1-divide';

+is search_divide(39), 1, 'ex-2-divide';

+

+is search_rows(22), 0, 'between-rows-rows';

+is search_rows_mid(22), 0, 'between-rows-rows-mid';

+is search_flattened(22),   0, 'between-rows-flat';

+is search_divide(22),      0, 'between-rows-divide';

+

+is search_rows(51), 0, 'above-top-rows';

+is search_rows_mid(51), 0, 'above-top-rows-mid';

+is search_flattened(51),   0, 'above-top-flat';

+is search_divide(51),      0, 'above-top-divide';

+

+is search_rows(0), 0, 'below-bot-rows';

+is search_rows_mid(0), 0, 'below-bot-rows-mid';

+is search_flattened(0),   0, 'below-bot-flat';

+is search_divide(0),      0, 'below-bot-divide';

+

+is search_rows(-1), 0, 'negative-rows';

+is search_rows_mid(-1), 0, 'negative-rows-mid';

+is search_flattened(-1),   0, 'negative-flat';

+is search_divide(-1),      0, 'negative-divide';

+

+is search_rows(1), 1, 'row1-rows';

+is search_rows_mid(1), 1, 'row1-rows-mid';

+is search_flattened(1),   1, 'row1-flat';

+is search_divide(1),      1, 'row1-divide';

+

+is search_rows(50), 1, 'row5-rows';

+is search_rows_mid(50), 1, 'row5-rows-mid';

+is search_flattened(50),   1, 'row5-flat';

+is search_divide(50),      1, 'row5-divide';

+

+use Benchmark qw( cmpthese );

+

+cmpthese(-3, {

+'row'     => sub { search_rows($_) foreach 0..51; },

+'row-mid' => sub { search_rows_mid($_) foreach 0..51; },

+'flat'    => sub { search_flattened($_) foreach 0..51; },

+'div'     => sub { search_divide($_) foreach 0..51; },

+

+});

+

+done_testing();

+

+=cut

+

+           Rate    flat     div row-mid     row

+flat    13657/s      --    -59%    -68%    -71%

+div     33533/s    146%      --    -21%    -29%

+row-mid 42575/s    212%     27%      --    -10%

+row     47312/s    246%     41%     11%      --

+

+the best way to efficiency is to not execute code

diff --git a/challenge-111/colin-crain/perl/ch-2.pl b/challenge-111/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..081d05ac5b
--- /dev/null
+++ b/challenge-111/colin-crain/perl/ch-2.pl
@@ -0,0 +1,84 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       get-in-line.pl

+#

+#       Ordered Letters

+#         Submitted by: E. Choroba

+# 

+#         Given a word, you can sort its letters alphabetically (case

+#         insensitive). For example, “beekeeper” becomes “beeeeekpr” and

+#         “dictionary” becomes “acdiinorty”.

+# 

+#         Write a script to find the longest English words that don’t change

+#         when their letters are sorted.

+# 

+#         method:

+#             the trick here is not to find an efficient sorting method for the words,

+#             comparing pre and post, but rather to find an eficient manner

+#             of determining whether a word is already sorted, as any word 

+#             requiring any rearangement fails the test. 

+#             

+#             By starting at the front and comparing adjacent pairs of letters

+#             using the `sort` comparison operators, we can avoid sorting the 

+#             words entirely. If in any pair the right letter if lexicographically

+#             smaller than the left, the word fails and me move to the next word 

+#             immediately. 

+#

+#             The longest alphaliteral word I could find anywhere was "aegilops" at 8

+#             letters, being an variant spelling of 'egilops'. The longest in

+#             in any dictionary I had was 7 letters.

+#             

+#             

+#

+#       © 2021 colin crain

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

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+use List::Util qw( max );

+

+my $dict = '/usr/share/dict/words';

+

+open(my $fh, "<", $dict) or die "can't open dict $dict: $!";

+

+my %bag;

+

+for (<$fh>) {

+    s/[\n\r]//g;                    ## general-purpose chomp

+    $_ = lc;                        ## lowercase the word (if in ALLCAPS, for instance)

+    $bag{$_} = length $_ if is_sorted($_);

+}

+

+my $max = max (values %bag);

+say "max length $max\n";

+

+my @longest = sort grep { $bag{$_} == $max } keys %bag;

+

+say $_ for @longest;

+

+

+

+sub is_sorted ($word) {

+    return 0 if length($word) < 3;  ## reject short words

+    for (1 .. length($word)-1) {

+        return 0 if (substr($word, $_-1, 1) cmp substr($word, $_, 1)) == 1 ;

+    }

+    return 1;

+}

+

+

+=cut

+

+max length 7

+

+adelops

+alloquy

+beefily

+begorry

+billowy

+egilops

diff --git a/challenge-111/colin-crain/python/ch-1.py b/challenge-111/colin-crain/python/ch-1.py
new file mode 100644
index 0000000000..e9dad11ff7
--- /dev/null
+++ b/challenge-111/colin-crain/python/ch-1.py
@@ -0,0 +1,66 @@
+#!/usr/bin/env python3

+#

+#

+#       are-we-in.py

+#

+#       Search Matrix

+#         Submitted by: Mohammad S Anwar

+#         You are given 5x5 matrix filled with integers such that each row is

+#         sorted from left to right and the first integer of each row is greater

+#         than the last integer of the previous row.

+# 

+#         Write a script to find a given integer in the matrix using an

+#         efficient search algorithm.

+# 

+#         Example

+# 

+#             Matrix: [  1,  2,  3,  5,  7 ]

+#                     [  9, 11, 15, 19, 20 ]

+#                     [ 23, 24, 25, 29, 31 ]

+#                     [ 32, 33, 39, 40, 42 ]

+#                     [ 45, 47, 48, 49, 50 ]

+# 

+#             Input:  35

+#             Output: 0     since it is missing in the matrix

+# 

+#             Input:  39

+#             Output: 1     as it exists in the matrix

+#

+#

+#

+#       © 2021 colin crain

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

+

+import sys

+

+def inArray(mat, val):

+    if (val > mat[-1][-1]) | (val < mat[0][0]):

+        return False 

+    row = 0

+    while val > mat[row][-1]:

+        row += 1  

+    return val in mat[row]

+   

+   

+

+mat = [[  1,  2,  3,  5,  7 ],

+       [  9, 11, 15, 19, 20 ],

+       [ 23, 24, 25, 29, 31 ],

+       [ 32, 33, 39, 40, 42 ],

+       [ 45, 47, 48, 49, 50 ]] ;

+

+default = 22

+

+if len(sys.argv) == 1:

+    val = default

+else:

+    val = sys.argv[1]

+    

+res = inArray(mat, val)

+

+print(res)

+

+

+

+    

+    

diff --git a/challenge-111/colin-crain/python/ch-2.py b/challenge-111/colin-crain/python/ch-2.py
new file mode 100644
index 0000000000..b7aadfd3b0
--- /dev/null
+++ b/challenge-111/colin-crain/python/ch-2.py
@@ -0,0 +1,48 @@
+#!/usr/bin/env python3

+#

+#

+#       get-in-line.py

+#

+#       Ordered Letters

+#         Submitted by: E. Choroba

+# 

+#         Given a word, you can sort its letters alphabetically (case

+#         insensitive). For example, “beekeeper” becomes “beeeeekpr” and

+#         “dictionary” becomes “acdiinorty”.

+# 

+#         Write a script to find the longest English words that don’t change

+#         when their letters are sorted.

+#

+#

+#

+#       © 2021 colin crain

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

+

+

+dictFile = '/usr/share/dict/words'

+

+def isSorted(word):

+    if len(word) < 3:

+        return False

+    for i in range(1, len(word)):

+        if word[i-1] > word[i]:

+            return False

+    return True

+

+bag = {}

+

+f = open(dictFile, "r")

+for line in f:

+    line = line.rstrip('\r\n').lower()

+    if isSorted(line):

+        bag[line] = len(line)

+f.close

+

+maxLen    = max( v for v in bag.values() )

+longWords = [ w for w in bag if len(w) == maxLen ]

+

+print("longest word length", maxLen, "letters", "\n")

+for word in longWords:

+    print(word)

+

+

diff --git a/challenge-111/colin-crain/raku/ch-1.raku b/challenge-111/colin-crain/raku/ch-1.raku
new file mode 100644
index 0000000000..ba68e0c226
--- /dev/null
+++ b/challenge-111/colin-crain/raku/ch-1.raku
@@ -0,0 +1,47 @@
+#!/usr/bin/env perl6
+#
+#
+#       are-we-in.raku
+#
+#       Search Matrix
+#         Submitted by: Mohammad S Anwar
+#         You are given 5x5 matrix filled with integers such that each row is
+#         sorted from left to right and the first integer of each row is greater
+#         than the last integer of the previous row.
+# 
+#         Write a script to find a given integer in the matrix using an
+#         efficient search algorithm.
+# 
+#         Example
+# 
+#             Matrix: [  1,  2,  3,  5,  7 ]
+#                     [  9, 11, 15, 19, 20 ]
+#                     [ 23, 24, 25, 29, 31 ]
+#                     [ 32, 33, 39, 40, 42 ]
+#                     [ 45, 47, 48, 49, 50 ]
+# 
+#             Input:  35
+#             Output: 0     since it is missing in the matrix
+# 
+#             Input:  39
+#             Output: 1     as it exists in the matrix
+#
+#       method:
+#         In Raku we will output a boolean TRUE/FALSE value
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN (Int $val = 23) ;
+
+our @mat =    [  1,  2,  3,  5,  7 ],
+              [  9, 11, 15, 19, 20 ],
+              [ 23, 24, 25, 29, 31 ],
+              [ 32, 33, 39, 40, 42 ],
+              [ 45, 47, 48, 49, 50 ]  ;
+              
+
+say @mat.first({ $val == any $_.list  })
+        .Bool;
diff --git a/challenge-111/colin-crain/raku/ch-2.raku b/challenge-111/colin-crain/raku/ch-2.raku
new file mode 100644
index 0000000000..cd9566e0e6
--- /dev/null
+++ b/challenge-111/colin-crain/raku/ch-2.raku
@@ -0,0 +1,46 @@
+#!/usr/bin/env perl6
+#
+#
+#       get-in-line.raku
+#
+#       Ordered Letters
+#         Submitted by: E. Choroba
+# 
+#         Given a word, you can sort its letters alphabetically (case
+#         insensitive). For example, “beekeeper” becomes “beeeeekpr” and
+#         “dictionary” becomes “acdiinorty”.
+# 
+#         Write a script to find the longest English words that don’t change
+#         when their letters are sorted.
+#
+#
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN () ;
+
+our $dict = '/usr/share/dict/words';
+
+my %sorted_words = 
+    $dict.IO.lines
+            .map({.lc})
+            .grep({is_sorted($_)}) 
+            .map({ $_ => $_.chars });
+            
+my $longest = %sorted_words.values.max;
+
+say "longest word length $longest\n";
+.say for %sorted_words.keys.grep({%sorted_words{$_} == $longest});
+
+
+sub is_sorted ($word) {
+    return False if $word.chars < 3;
+    for ($word.comb).rotor(2 => -1) -> ($a, $b) {
+        return False if $a cmp $b == 1
+    }
+    return True
+}
+