Second Perl implementation

9 files changed, 109 insertions, 14 deletions

diff --git a/challenge-111/abigail/README.md b/challenge-111/abigail/README.md
index 978fa5fdee..39cfe578f6 100644
--- a/challenge-111/abigail/README.md
+++ b/challenge-111/abigail/README.md
@@ -30,6 +30,9 @@ Only for language lacking hashes/maps/dictionaries/tables, we will
 make use of the fact the input is sorted. For the majority of
 languages, the fact input is sorted does not offer additional benefits.
 
+For Perl, we make two implementations: one based on a hash, the
+other using binary search.
+
 ### Solutions
 * [AWK](awk/ch-1.awk)
 * [Bash](bash/ch-1.sh)
diff --git a/challenge-111/abigail/perl/ch-1.pl b/challenge-111/abigail/perl/ch-1.pl
index 00f6e2502d..ca06d26dea 100644
--- a/challenge-111/abigail/perl/ch-1.pl
+++ b/challenge-111/abigail/perl/ch-1.pl
@@ -14,7 +14,7 @@ use experimental 'lexical_subs';
 #
 
 #
-# Run as: perl ch-1.pl < input-file
+# Run as: perl ch-1.pl [bsearch] < input-file
 #
 
 #
@@ -29,22 +29,72 @@ use experimental 'lexical_subs';
 # Perhaps the intend was a subroutine which takes a matrix and a target
 # number, but that was not what is being asked. The challenge explicitly
 # asks for *a script*, which means we have to spend a linear amount of 
-# time reading data anyway. So, that's what you get.
+# time reading data anyway.
 #
-# The only part where we use the fact we are given a matrix is for the
-# input: the first five lines are assumed to contain the matrix. The
-# rest of the input is taken as numbers to search for.
+# Just to cover our bases, we'll do two implementation. Without arguments,
+# we'll do that fast, hash bases, implementation. If the program is
+# given the 'bsearch' argument, we will make use of a subroutine which
+# takes a 2-d matrix and a target number as parameters, and which uses
+# a bog standard binary search implementation to find out whether the
+# target exists.
 #
 
 my $MATRIX_SIZE = 5;
 
-#
-# Read in a matrix of data
-#
-my %matrix;
-@matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE; 
+my $HASH    = 0;
+my $BSEARCH = 1;
 
-#
-# Print 0/1 depending on whether the given number is in the matrix or not.
-#
-chomp, say exists $matrix {$_} || 0 while <>
+my $TYPE = $HASH;
+   $TYPE = $BSEARCH if @ARGV && $ARGV [0] eq "bsearch";
+
+@ARGV = ();
+
+if ($TYPE == $HASH) {
+    #
+    # Read in a matrix of data
+    #
+    my %matrix;
+    @matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE; 
+
+    #
+    # Print 0/1 depending on whether the given number is in the matrix or not.
+    #
+    chomp, say exists $matrix {$_} || 0 while <>;
+
+    exit;
+}
+
+if ($TYPE == $BSEARCH) {
+    #
+    # Use binary search to find a target value into a sorted set.
+    #
+    my sub bsearch ($matrix, $target) {
+        my ($min, $max) = (0, $MATRIX_SIZE * $MATRIX_SIZE);
+        while ($min < $max) {
+            use integer;
+            my $mid = ($min + $max) / 2;
+            #
+            # To map a 1-d coordinate c to a 2-d pair x, y, we use
+            # x = floor (c / size), y = c % size.
+            # 
+            my $cmp = $$matrix [$mid / $MATRIX_SIZE]
+                               [$mid % $MATRIX_SIZE] <=> $target;
+            if    ($cmp < 0) {$min = $mid + 1}
+            elsif ($cmp > 0) {$max = $mid}
+            else  {return 1}
+        }
+        return (0)
+    }
+
+    #
+    # Read in the matrix
+    #
+    my $matrix = [map {[<> =~ /-?[0-9]+/g]} 1 .. $MATRIX_SIZE];
+
+    #
+    # Check for existence for the rest of the data
+    #
+    say bsearch ($matrix, $_) for <>;
+
+    exit;
+}
diff --git a/challenge-111/abigail/t/ctest.ini b/challenge-111/abigail/t/ctest.ini
index 0c0dfde484..1cfc7fa7ae 100644
--- a/challenge-111/abigail/t/ctest.ini
+++ b/challenge-111/abigail/t/ctest.ini
@@ -7,10 +7,19 @@
 1-1 = Given example

 1-2 = Use large numbers

 1-3 = Use negative numbers

+1-4 = Given example (binary search)

+1-5 = Use large numbers (binary search)

+1-6 = Use negative numbers (binary search)

 2-1 = Enable.lst

 2-2 = /usr/share/dict/words

 2-3 = infochimps.com

 

+[1-4,1-5,1-6]

+skip = Only one implementation

+

+[1-4,1-5,1-6/perl]

+skip = 0

+

 [2-1]

 input_file = /Users/abigail/Words/enable.lst

 

diff --git a/challenge-111/abigail/t/input-1-4 b/challenge-111/abigail/t/input-1-4
new file mode 100644
index 0000000000..fa2f7e3fa1
--- /dev/null
+++ b/challenge-111/abigail/t/input-1-4
@@ -0,0 +1,7 @@
+ 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
+35
+39
diff --git a/challenge-111/abigail/t/input-1-5 b/challenge-111/abigail/t/input-1-5
new file mode 100644
index 0000000000..14b659ea7d
--- /dev/null
+++ b/challenge-111/abigail/t/input-1-5
@@ -0,0 +1,7 @@
+ 1000000  2000000  3000000  5000000  7000000
+ 9000000 11000000 15000000 19000000 20000000
+23000000 24000000 25000000 29000000 31000000
+32000000 33000000 39000000 40000000 42000000
+45000000 47000000 48000000 49000000 50000000
+35000000
+39000000
diff --git a/challenge-111/abigail/t/input-1-6 b/challenge-111/abigail/t/input-1-6
new file mode 100644
index 0000000000..e5dd243924
--- /dev/null
+++ b/challenge-111/abigail/t/input-1-6
@@ -0,0 +1,10 @@
+-9 -7 -5 -3 -2
+ 0 11 15 19 20
+23 24 25 29 31
+32 33 39 40 42
+45 47 48 49 50
+-5
+-1
+0
+1
+11
diff --git a/challenge-111/abigail/t/output-1-4.exp b/challenge-111/abigail/t/output-1-4.exp
new file mode 100644
index 0000000000..0d66ea1aee
--- /dev/null
+++ b/challenge-111/abigail/t/output-1-4.exp
@@ -0,0 +1,2 @@
+0
+1
diff --git a/challenge-111/abigail/t/output-1-5.exp b/challenge-111/abigail/t/output-1-5.exp
new file mode 100644
index 0000000000..0d66ea1aee
--- /dev/null
+++ b/challenge-111/abigail/t/output-1-5.exp
@@ -0,0 +1,2 @@
+0
+1
diff --git a/challenge-111/abigail/t/output-1-6.exp b/challenge-111/abigail/t/output-1-6.exp
new file mode 100644
index 0000000000..33f911e8c0
--- /dev/null
+++ b/challenge-111/abigail/t/output-1-6.exp
@@ -0,0 +1,5 @@
+1
+0
+1
+0
+1