Merge pull request #9287 from Util/c248

Add TWC 248 solutions by Bruce Gray (in Raku only).

2 files changed, 130 insertions, 0 deletions

diff --git a/challenge-248/bruce-gray/raku/ch-1.raku b/challenge-248/bruce-gray/raku/ch-1.raku
new file mode 100644
index 0000000000..7077ef3fec
--- /dev/null
+++ b/challenge-248/bruce-gray/raku/ch-1.raku
@@ -0,0 +1,104 @@
+# Distance from nearest Left, from nearest Right, minimum of the two.
+# O(3N), but something about it is slowing it down.
+sub task1_three_linear_scans ( Str $letter, Str $s ) {
+    my @sc = $s.comb;
+
+    my $distance; # Used for side effects within two .map()'s.
+    my &f = { $distance = 0 if $_ eq $letter; $distance++ };
+
+    $distance = Inf; my @L = @sc.map(&f);
+    $distance = Inf; my @R = @sc.reverse.map(&f).reverse;
+
+    return @L »min« @R;
+}
+
+# Lots of participants used variations of this algorithm.
+# It is potentially a poor performer, O(N²)?, depending on the 
+# number of times the letter occurs; 1K string with
+# 10% $letter would be 100K comparisons.
+multi sub infix:<absdiff> (\a, \b) { ( a - b ).abs }
+sub task1_compare_to_all ( Str $letter, Str $s ) {
+    my @pos = $s.indices($letter);
+
+    return map { [min] $_ «absdiff« @pos }, ^$s.chars;
+}
+
+# More intricate, but could be wildly more efficient.
+# Directly generates the whole result in a continuous single Seq.
+sub task1_pyramid ( Str $letter, Str $s ) {
+    # Except for the head&tail, distances always form a pyramid,
+    # either flat-top (1 2 3 4 4 3 2 1) or pointy (1 2 3 4 3 2 1).
+    sub pyramid ( (Int $z1, Int $z2) ) {
+        my $n = $z2 - $z1 - 1;
+        my $m = $n div 2;
+        my @c = 1 .. $m;
+        return |0, |@c, |($m + 1 if $n !%% 2), |@c.reverse;
+    }
+
+    my @pos = $s.indices($letter)
+        or return Inf xx $s.chars;
+
+    # Looks faster, but that big last flatten kills performance,
+    # and limits us to 65K array.
+    # return map |*,
+    #     (1..@pos.head).reverse,
+    #     |@pos.rotor(2 => -1).map(&pyramid),
+    #     0, (1 .. ($s.chars - @pos.tail - 1));
+
+    return gather {
+        .take for reverse 1..@pos.head;
+        .take for |@pos.rotor(2 => -1).map({ |.&pyramid });
+        .take for 0 .. ($s.chars - @pos.tail - 1);
+    }
+}
+
+
+constant $hamlet = 'What a piece of work is a man! how noble in reason! how infinite in faculties! in form and moving how express and admirable! in action how like an angel! in apprehension how like a god! the beauty of the world, the paragon of animals!';
+constant @tests =
+    ( 'e', 'loveleetcode' , [3,2,1,0,1,0,0,1,2,2,1,0] ),
+    ( 'b', 'aaab'         , [3,2,1,0] ),
+
+    ( 'c', 'aaab'         , [Inf xx 4] ),
+
+    # Extra tests from mark-anderson
+    ( 'e', 'eabcde'       , [0,1,2,2,1,0] ),
+    ( 'e', 'eabcdf'       , [0,1,2,3,4,5] ),
+    ( 'e', 'abecd'        , [2,1,0,1,2] ),
+    ( 'e', 'abcefg'       , [3,2,1,0,1,2] ),
+    ( 'e', 'eeeabecefeeg' , [0,0,0,1,1,0,1,0,1,0,0,1] ),
+
+    ( 'a', $hamlet        , [2,1,0,1,1,0,1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1,0,1,1,0,1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,11,10,9,8,7,6,5,4,3,2,1,0,1,2,1,0,1,2,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,0,1,1,0,1,2,3,4,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,11,10,9,8,7,6,5,4,3,2,1,0,1,0,1,2,3,4,3,2,1,0,1,2,1,0,1,2,3] ),
+    ( 'e', $hamlet        , [9,8,7,6,5,4,3,2,1,0,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,2,1,0,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,1,0,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,0,1,2,3,4,5,6,7,6,5,4,3,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,1,0,1,2,3,4,5,5,4,3,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] ),
+    ( 'i', $hamlet        , [8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0,1,1,0,1,0,1,2,1,0,1,2,3,4,4,3,2,1,0,1,2,2,1,0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,4,5,6,7,6,5,4,3,2,1,0,1,2,3,4,5,6,5,4,3,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5] ),
+    ( 'o', $hamlet        , [13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,1,0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0,1,2,1,0,1,2,3,4,5,6,5,4,3,2,1,0,1,2,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,4,5,6,7,7,6,5,4,3,2,1,0,1,1,0,1,2,3,4,5,6,7,8,9,10] ),
+    ( 'u', $hamlet        , [71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40] ),
+    ( 'W', $hamlet        , [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233] ),
+    ( 'h', $hamlet        , [1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,3,2,1,0,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,6,5,4,3,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21] ),
+    ( 's', $hamlet        , [22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1] ),
+    ( '!', $hamlet        , [29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0] ),
+    ( ' ', $hamlet        , [4,3,2,1,0,1,0,1,2,3,2,1,0,1,1,0,1,2,2,1,0,1,1,0,1,0,1,2,2,1,0,1,2,1,0,1,2,3,2,1,0,1,1,0,1,2,3,4,3,2,1,0,1,2,1,0,1,2,3,4,4,3,2,1,0,1,1,0,1,2,3,4,5,5,4,3,2,1,0,1,1,0,1,2,2,1,0,1,2,1,0,1,2,3,3,2,1,0,1,2,1,0,1,2,3,4,3,2,1,0,1,2,1,0,1,2,3,4,5,5,4,3,2,1,0,1,1,0,1,2,3,3,2,1,0,1,2,1,0,1,2,2,1,0,1,1,0,1,2,3,3,2,1,0,1,1,0,1,2,3,4,5,6,6,5,4,3,2,1,0,1,2,1,0,1,2,2,1,0,1,0,1,2,2,1,0,1,2,1,0,1,2,3,3,2,1,0,1,1,0,1,2,1,0,1,2,3,3,2,1,0,1,2,1,0,1,2,3,4,3,2,1,0,1,1,0,1,2,3,4,5,6,7,8] ),
+;
+my @subs =
+    :&task1_three_linear_scans,
+    :&task1_compare_to_all,
+    :&task1_pyramid,
+;
+use Test; plan @tests * @subs;
+for @subs -> ( :key($sub_name), :value(&task1) ) {
+    for @tests -> ( $in_letter, $in_str, @expected ) {
+        my @got = task1($in_letter, $in_str);
+        is-deeply @got, @expected, "$sub_name - $in_letter, {$in_str.substr(0,4)}";
+    }
+}
+
+my $huge = $hamlet x 10_000;
+for @subs -> ( :key($sub_name), :value(&task1) ) {
+    my $t = now;
+
+    my $junk = task1( ' ', $huge ) for ^10;
+
+    say now - $t, ' ', $sub_name;
+}
+# 33.797148952 task1_three_linear_scans
+#  8.153342333 task1_compare_to_all
+#  0.915972521 task1_pyramid
diff --git a/challenge-248/bruce-gray/raku/ch-2.raku b/challenge-248/bruce-gray/raku/ch-2.raku
new file mode 100644
index 0000000000..8e0744aa1b
--- /dev/null
+++ b/challenge-248/bruce-gray/raku/ch-2.raku
@@ -0,0 +1,26 @@
+sub task2_semicolon ( @m ) {
+    return @m.keys.skip.map: -> \r {
+        @m[0].keys.skip.map: -> \c {
+            @m[r-1,r ; c-1,c].sum
+        }
+    }
+}
+sub task2_stream ( @m ) {
+    return @m.map( *.rotor(2 => -1)».sum )
+             .rotor(2 => -1)
+             .map: { [»+«] .list };
+}
+
+
+my @tests =
+    ( ((1,2,3,4),(5,6,7,8),(9,10,11,12))        , ((14,18,22),(30,34,38))   ),
+    ( ((1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)) , ((2,1,0),(1,2,1),(0,1,2)) ),
+;
+my @subs = :&task2_semicolon, :&task2_stream;
+use Test; plan @tests * @subs;
+for @subs -> ( :key($sub_name), :value(&task2) ) {
+    for @tests -> ( @in, @expected ) {
+        my @got = task2(@in);
+        is-deeply @got».List, @expected, "$sub_name - @in[0]";
+    }
+}