Merge pull request #4030 from Abigail/abigail/week-111

Abigail/week 111

11 files changed, 219 insertions, 14 deletions

diff --git a/challenge-111/abigail/README.md b/challenge-111/abigail/README.md
index b9e45903c7..39cfe578f6 100644
--- a/challenge-111/abigail/README.md
+++ b/challenge-111/abigail/README.md
@@ -30,12 +30,16 @@ 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)
 * [C](c/ch-1.c)
 * [Lua](lua/ch-1.lua)
 * [Node.js](node/ch-1.js)
+* [Pascal](pascal/ch-1.p)
 * [Perl](perl/ch-1.pl)
 * [Python](python/ch-1.py)
 * [Ruby](ruby/ch-1.rb)
@@ -83,6 +87,7 @@ to standard output. In case of ties, we print the first one found.
 * [C](c/ch-2.c)
 * [Lua](lua/ch-2.lua)
 * [Node.js](node/ch-2.js)
+* [Pascal](pascal/ch-2.p)
 * [Perl](perl/ch-2.pl)
 * [Python](python/ch-2.py)
 * [Ruby](ruby/ch-2.rb)
diff --git a/challenge-111/abigail/pascal/ch-1.p b/challenge-111/abigail/pascal/ch-1.p
new file mode 100644
index 0000000000..b94e34fca9
--- /dev/null
+++ b/challenge-111/abigail/pascal/ch-1.p
@@ -0,0 +1,64 @@
+Program SearchMatrix;
+
+(*                  *)
+(* See ../README.md *)
+(*                  *)
+
+(*                                                        *)
+(* Run as: fpc -och-1.out ch-1.p; ./ch-1.out < input-file *)
+(*                                                        *)
+
+const
+    matrix_size = 5;
+
+type
+    matrix_type = Array [1 .. matrix_size * matrix_size] of Longint;
+
+var
+    matrix:     matrix_type;
+    var i:      Integer;
+    var target: Longint;
+
+(*                                                *)
+(* Use binary search to find 'target' in 'matrix' *)
+(*                                                *)
+function bsearch (matrix: matrix_type; target: Longint) : Integer;
+    var
+        min, mid, max: Integer;
+    begin
+        bsearch := 0;
+        min     := 1;
+        max     := matrix_size * matrix_size + 1;
+        while min < max do
+        begin
+            mid := (min + max) div 2;
+            if matrix [mid] = target then
+            begin
+                bsearch := 1;
+                min     := max;
+            end;
+            if matrix [mid] < target then
+            begin
+                min     := mid + 1;
+            end
+            else begin
+                max     := mid - 1;
+            end
+        end
+    end;
+
+
+begin
+    (* Read in the matrix *)
+    for i := 1 to matrix_size * matrix_size do
+    begin
+        read (matrix [i]);
+    end;
+
+    (* The rest of the input are numbers we want to search *)
+    while not eof () do
+    begin
+        readln  (target);
+        writeln (bsearch (matrix, target));
+    end;
+end.
diff --git a/challenge-111/abigail/pascal/ch-2.p b/challenge-111/abigail/pascal/ch-2.p
new file mode 100644
index 0000000000..d4fcf5919b
--- /dev/null
+++ b/challenge-111/abigail/pascal/ch-2.p
@@ -0,0 +1,44 @@
+Program OrderedLetters;
+
+(*                  *)
+(* See ../README.md *)
+(*                  *)
+
+(*                                                        *)
+(* Run as: fpc -och-2.out ch-2.p; ./ch-2.out < input-file *)
+(*                                                        *)
+
+uses sysutils;
+
+var
+    line, longest: string;
+    ch, prev_ch:   char;
+    valid:         boolean;
+
+begin
+    longest := '';
+    while not eof () do
+    begin
+        readln (line);
+        valid   := true;
+        prev_ch := ' ';   (* Any char less than 'a' will do *)
+
+        (* Iterate over the characters of the lowercased string;        *)
+        (* if the character isn't a lowercase letter, or the character  *)
+        (* is less than the previous, it's not a valid candidate.       *)
+        for ch in lowercase (line) do
+        begin
+            if (ch < 'a') or (ch > 'z') or (ch < prev_ch) then
+            begin
+                valid := false;
+                break;
+            end;
+            prev_ch := ch;
+        end;
+        if valid and (length (line) > length (longest)) then
+        begin
+            longest := line;
+        end;
+    end;
+    writeln (longest);
+end.
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