Perl solution for week 98, part 2

5 files changed, 79 insertions, 0 deletions

diff --git a/challenge-098/abigail/README.md b/challenge-098/abigail/README.md
index f7d65c3bb7..2d3ffae7bb 100644
--- a/challenge-098/abigail/README.md
+++ b/challenge-098/abigail/README.md
@@ -53,6 +53,7 @@ Output:
 ~~~~
 
 ### Solutions
+* [Perl](perl/ch-1.pl)
 
 ### Blog
 
@@ -89,6 +90,17 @@ Input: @N = (11, 13, 15, 17) and $N = 19
 Output: 4 since the target 19 is missing and should be placed at the index 4.
 ~~~~
 
+### Notes
+We could write a binary search to find the target number in the
+array. This is tempting, as a binary search take O (log N). But
+this is futile. We're also asked to add the target element to the
+array (if not found), and adding an element in the middle of an
+array takes linear time. So, worst case, we're already spending
+linear time. (And to read the array, we're spending linear time
+anyway).
+
+
 ### Solutions
+* [Perl](perl/ch-2.pl)
 
 ### Blog
diff --git a/challenge-098/abigail/perl/ch-2.pl b/challenge-098/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..abe58c903d
--- /dev/null
+++ b/challenge-098/abigail/perl/ch-2.pl
@@ -0,0 +1,58 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-2.pl < input-file
+#
+# Each line is assumed to be a white space separated list of
+# numbers. The first number is the target number (`$N`), the rest of
+# the numbers is the array (`@N`).
+#
+# Now, we could implement a binary search to find the target in
+# O (log N) time, but why bother? We need to read the array, which
+# means we're already spending linear time; furthermore, we have to
+# insert element if not found -- which is a worst case linear time
+# operation anyway. So, we just do a linear scan.
+#
+# Note that we insert $N into @N by adding it to the end, and then
+# sorting -- which is linear in Perl (as the list (@N, $N) is nearly
+# sorted). We then use a goto to go back to the search; this is 
+# guaranteed to succeed.
+#
+
+INPUT: while (<>) {
+    chomp;
+    my ($N, @N) = split ' ';
+  SEARCH:
+    for my $i (keys @N) {
+        if ($N == $N [$i]) {
+            say $i;
+            next INPUT;
+        }
+    }
+
+    #
+    # Not found. Insert by adding to the end and sorting.
+    #
+    @N = sort {$a <=> $b} @N, $N;
+
+    #
+    # Now, do the search again -- this time, it will succeed.
+    #
+    goto SEARCH;
+}
+
+
+__END__
diff --git a/challenge-098/abigail/t/ctest.ini b/challenge-098/abigail/t/ctest.ini
index 502e73267f..a74eb51936 100644
--- a/challenge-098/abigail/t/ctest.ini
+++ b/challenge-098/abigail/t/ctest.ini
@@ -2,3 +2,4 @@
 1-1 = Given example

 1-2 = Different amounts

 1-3 = Interleaf files

+2-1 = Given examples

diff --git a/challenge-098/abigail/t/input-2-1 b/challenge-098/abigail/t/input-2-1
new file mode 100644
index 0000000000..7f2eab05e9
--- /dev/null
+++ b/challenge-098/abigail/t/input-2-1
@@ -0,0 +1,4 @@
+3 1 2 3 4
+6 1 3 5 7
+10 12 14 16 18
+19 11 13 15 17
diff --git a/challenge-098/abigail/t/output-2-1.exp b/challenge-098/abigail/t/output-2-1.exp
new file mode 100644
index 0000000000..c89c0bde15
--- /dev/null
+++ b/challenge-098/abigail/t/output-2-1.exp
@@ -0,0 +1,4 @@
+2
+3
+0
+4