Merge pull request #2104 from boblied/master

Solutions for challenge 073

6 files changed, 288 insertions, 42 deletions

diff --git a/challenge-073/bob-lied/README b/challenge-073/bob-lied/README
index be171d638e..64e5cc5a25 100644
--- a/challenge-073/bob-lied/README
+++ b/challenge-073/bob-lied/README
@@ -1,65 +1,53 @@
-Solutions to weekly challenge 72 by Bob Lied.
+Solutions to weekly challenge 73 by Bob Lied.
 
-https://perlweeklychallenge.org/blog/perl-weekly-challenge-072/
+https://perlweeklychallenge.org/blog/perl-weekly-challenge-073/
 
-This week, I would like to add two personal elements to the problem:
-(1) create a template for perl-vim that sets up these weekly challenges
-(includes Test::More, a skeleton for checking ARGV, and whatever else
-is quickly becoming a pattern; and (2) use a github issue in the submission
-process, just to learn more about using git and github.
 
-* TASK #1 > Trailing Zeroes
+* TASK #1 > 
 
 ** Initial thoughts
 
-Too easy, unless I'm missing something.  The result gets a zero on the end every time
-it's multiplied by 10, and since we're doing factorials, that will happen every time N
-rolls past a multiple of 5.  The answer is int(N/5), I think, but I'll need to convince
-myself completely.
-
-We could make it a little tougher by actually calculating N!, and maybe using Memoize
-as an optimization.  And maybe finding out how high N can be until overflow or waiting time
-make it impractical.
+A window of an array implies slices.  Minimum of an array implies List::Util::min.
 
 ** Post Solution Thoughts
 
-Yep, it was really that easy.  I implemented the factorial using Memoize just
-for fun.  The highest number that didn't roll over to floating point was 20!.
+Repeatedly doing the scan for minimum is a lot of extra work.  The cost of
+doing an array of 50 with a window of 3 is minimal, but what about an array
+of 100000 with a window of 200?  So much extra work.  I did a second solution
+with indices that didn't actually take slices.  It's also not necessary to
+find the minimum each time:  as we slide the window right, if it's less than
+the minimum, it becomes the new minimum for as long as it's in the window.
+The only time we need to scan for minimum is when the window slides the
+minimum off the left edge.
 
+I used the task as an excuse to build a slightly more structured program,
+with the solution in a module and a separate test file.
 
 ** Problem Statement
+ # You are given an array of integers @A and sliding window size $S.
+ # Write a script to create an array of min from each sliding window.
 
-You are given a positive integer $N (<= 10).
-
-Write a script to print number of trailing zeroes in $N!.
 
-* TASK #2 > Lines Range
+* TASK #2 > Smallest Neighbor
 
 ** Initial Thoughts
 
-This has come up often enough that I know I've done it in sed and awk; and in
-a pipeline with head and tail.  The flip-flop operator comes to mind, but
-there'll be some experimentation for boundary conditions.  Also some test
-cases for A or B being outside the range of the file or having an empty file.
+There's probably a clever solution involving a reduce() operation, but the
+direct solution of scanning and keeping track of the minimum is probably
+going to be the way to go.
 
 ** Post Solution Thoughts
 
-The hardest part of this turned out to be how to set up tests.  I wanted the
-testing to be self-contained, so I put the test data into __DATA__.  But then
-re-reading that repeatedly for different tests required seeking back to the
-start and also resetting $.  A couple of trips to Google there.
-
-I also wanted to capture the output in a variable and not just print to the
-console.  I knew that a string could be opened as a file handle using a
-reference to the string.  It should have been easy; but I spent a long time
-debugging before I realized that I had typed \&TestResult instead of
-\$TestResult.
+The minimum keeps getting smaller as we move from left to right.  Test sets
+with a zero in the data create ambiguous answers, but there's nothing in the
+specification that says we have to do anything about that.  Negative numbers
+work just fine.
 
 
 ** Problem Statement
-
-You are given a text file name $file and range $A - $B where $A <= $B.
-
-Write a script to display lines range $A and $B in the given file.
-
-(That's A and B inclusive, from the examples.)
+# You are given an array of integers @A.
+# Write a script to create an array that represents the smallest element to the
+# left of each corresponding index.  If none found, then use 0.
+# Example 1:
+# Input: @A = (7,8,3,12,10)
+# Output:     (0,7,0, 3, 3)
diff --git a/challenge-073/bob-lied/perl/MinSlidingWindow.pm b/challenge-073/bob-lied/perl/MinSlidingWindow.pm
new file mode 100644
index 0000000000..693aa931db
--- /dev/null
+++ b/challenge-073/bob-lied/perl/MinSlidingWindow.pm
@@ -0,0 +1,40 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 073 Task #1 > Min Sliding Window
+#=============================================================================
+#
+# You are given an array of integers @A and sliding window size $S.
+# Write a script to create an array of min from each sliding window.
+
+package MinSlidingWindow;
+
+use strict;
+use warnings;
+use feature qw(say);
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw(minSlidingWindow);
+our @EXPORT_OK = qw();
+
+use List::Util qw(min);
+
+sub minSlidingWindow
+{
+    my ($aref, $win) = @_;
+    my @result;
+
+    for my $beg ( 0 .. scalar(@$aref) - $win )
+    {
+        my $min = List::Util::min( @{$aref}[$beg .. $beg+$win-1 ]);
+        push @result, $min;
+    }
+    return \@result;
+}
+
+1;
diff --git a/challenge-073/bob-lied/perl/ch-1.pl b/challenge-073/bob-lied/perl/ch-1.pl
new file mode 100644
index 0000000000..3124daffcf
--- /dev/null
+++ b/challenge-073/bob-lied/perl/ch-1.pl
@@ -0,0 +1,38 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 073 Task #1 > Min Sliding Window
+#=============================================================================
+#
+# You are given an array of integers @A and sliding window size $S.
+# Write a script to create an array of min from each sliding window.
+
+use strict;
+use warnings;
+use feature qw(say);
+
+use Getopt::Long;
+
+use List::Util qw(min);
+
+use lib ".";
+use MinSlidingWindow qw(minSlidingWindow);
+
+
+sub Usage { "Usage: $0 -w SIZE a b c ..." }
+
+my $WinSize;
+GetOptions('winsize:n' => \$WinSize);
+
+die Usage() unless ($WinSize // 0) > 1;
+
+my @A = @ARGV;
+
+die Usage() unless scalar(@A) > $WinSize;
+
+my $answer = minSlidingWindow(\@A, $WinSize);
+say join(", ", @$answer);
diff --git a/challenge-073/bob-lied/perl/ch-1.t b/challenge-073/bob-lied/perl/ch-1.t
new file mode 100644
index 0000000000..97f771be5e
--- /dev/null
+++ b/challenge-073/bob-lied/perl/ch-1.t
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 073 Task #1 > Min Sliding Window
+#=============================================================================
+#
+# You are given an array of integers @A and sliding window size $S.
+# Write a script to create an array of min from each sliding window.
+
+package MinSlidingWindow;
+
+use strict;
+use warnings;
+use feature qw(say);
+
+use lib ".";
+use MinSlidingWindow;
+
+use Test::More;
+
+is_deeply( minSlidingWindow( [0, 1, 2, 3], 2 ), [0,1,2] , "ascending" );
+
+is_deeply( minSlidingWindow( [ 1, 5, 0, 2, 9, 3, 7, 6, 4, 8 ], 3 ), [0,0,0,2,3,3,4,4] );
+
+done_testing();
diff --git a/challenge-073/bob-lied/perl/ch-1a.pl b/challenge-073/bob-lied/perl/ch-1a.pl
new file mode 100644
index 0000000000..361280542b
--- /dev/null
+++ b/challenge-073/bob-lied/perl/ch-1a.pl
@@ -0,0 +1,104 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 073 Task #1 > Min Sliding Window
+#=============================================================================
+#
+# You are given an array of integers @A and sliding window size $S.
+# Write a script to create an array of min from each sliding window.
+#
+# Alternative solution:  try to do as much as possible in one pass, without
+# calculating the minimum of the window every time.
+
+use strict;
+use warnings;
+use feature qw(say);
+
+use Getopt::Long;
+
+sub Usage { "Usage: $0 -w SIZE a b c ..." }
+
+# Return the minimum of an array and the position where the minimum is located.
+sub winMin
+{
+    my @arr = @_;
+
+    my ($min, $where) = ( $arr[0], 0 );
+    ( $arr[$_] < $min ) && (($min, $where) = ($arr[$_], $_)) for 1.. $#arr;
+    return ($min, $where);
+}
+
+sub minSlidingWindow
+{
+    my ($aref, $winSize) = @_;
+
+    # Find value and position of minimum in first window
+    my ($min, $where) = winMin(@{$aref}[0..$winSize-1]);
+
+    my @result = ($min);
+
+    # Step through windows using first and next as boundaries.
+    for ( my $first = 1, my $next = $winSize ; $next < scalar(@$aref) ; $first++, $next++ )
+    {
+        my $val = $aref->[$next];
+
+        # Shift the position of the minimum to the left.  If it shifts
+        # out of the window, find the new window minimum.
+        if ( --$where  < 0 )
+        {
+            ($min, $where) = winMin( @{$aref}[$first..$next] );
+        }
+        elsif ( $val <= $min )
+        {
+            # If the new window is smaller, then that's the min and it's
+            # at the right edge of the window.  No need to hunt for min.
+            ($min, $where) = ($val, $winSize-1)
+        }
+        push @result, $min;
+    }
+
+    return \@result;
+}
+
+sub runTests
+{
+    use Test::More;
+
+    my $min; my $where;
+    ($min, $where) = winMin(1,2,3); is($min, 1);is($where, 0, "minWin first"); 
+    ($min, $where) = winMin(3,1,2); is($min, 1);is($where, 1, "minWin middle"); 
+    ($min, $where) = winMin(3,2,1); is($min, 1);is($where, 2, "minWin last"); 
+    ($min, $where) = winMin(1,1,2); is($min, 1);is($where, 0, "minWin double"); 
+    ($min, $where) = winMin(1,1,1); is($min, 1);is($where, 0, "minWin all same"); 
+
+    is_deeply( minSlidingWindow( [0, 1, 2, 3], 2 ), [0,1,2] , "ascending" );
+
+    is_deeply( minSlidingWindow( [ 1, 5, 0, 2, 9, 3, 7, 6, 4, 8 ], 3 ), [0,0,0,2,3,3,4,4] );
+
+    done_testing();
+}
+
+my $doTest;
+my $WinSize;
+GetOptions('test!' => \$doTest, 'winsize:n' => \$WinSize);
+
+exit(!runTests()) if $doTest;
+
+die Usage() unless ($WinSize // 0) > 1;
+
+my @A = @ARGV;
+
+die Usage() unless scalar(@A) > $WinSize;
+
+my $answer = minSlidingWindow(\@A, $WinSize);
+say join(", ", @$answer);
+
+my @a = map { int(rand(1000)) } ( 1..100000 );
+
+say join(",", @a[0..200]);
+$answer = minSlidingWindow(\@a, 100);
+say join(",", @{$answer}[0..100]);
diff --git a/challenge-073/bob-lied/perl/ch-2.pl b/challenge-073/bob-lied/perl/ch-2.pl
new file mode 100644
index 0000000000..4daed35346
--- /dev/null
+++ b/challenge-073/bob-lied/perl/ch-2.pl
@@ -0,0 +1,47 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-2.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 073 Task #2 > Smallest Neighbour`
+#=============================================================================
+#
+# You are given an array of integers @A.
+# Write a script to create an array that represents the smallest element to the
+# left of each corresponding index.  If none found, then use 0.
+# Example 1:
+# Input: @A = (7,8,3,12,10)
+# Output:     (0,7,0, 3, 3)
+
+use strict;
+use warnings;
+use feature qw(say);
+
+my @A = @ARGV;
+
+sub smallestNeighbor
+{
+    my ($arr) = @_;
+    my @result = (0);   # First result is always zero
+
+    my $smallest = shift(@$arr);
+    while ( scalar(@$arr) )
+    {
+        my $p = shift(@$arr);
+        if ( $smallest < $p )
+        {
+            push @result, $smallest;
+        }
+        else
+        {
+            $smallest = $p;
+            push @result, 0;
+        }
+    }
+
+    return @result;
+}
+
+say "(", join(",", smallestNeighbor(\@A) ), ")";