Solutions for task 073

6 files changed, 291 insertions, 2 deletions

diff --git a/challenge-073/bob-lied/README b/challenge-073/bob-lied/README
index b8250240d6..64e5cc5a25 100644
--- a/challenge-073/bob-lied/README
+++ b/challenge-073/bob-lied/README
@@ -7,16 +7,47 @@ https://perlweeklychallenge.org/blog/perl-weekly-challenge-073/
 
 ** Initial thoughts
 
+A window of an array implies slices.  Minimum of an array implies List::Util::min.
+
 ** Post Solution Thoughts
 
+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.
 
 
-* TASK #2 > Lines Range
+* TASK #2 > Smallest Neighbor
 
 ** Initial Thoughts
 
+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
 
-** Problem Statement
+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 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) ), ")";