Merge remote-tracking branch 'upstream/master'

68 files changed, 481718 insertions, 60 deletions

diff --git a/challenge-111/abigail/README.md b/challenge-111/abigail/README.md
index f73efb55cd..b9e45903c7 100644
--- a/challenge-111/abigail/README.md
+++ b/challenge-111/abigail/README.md
@@ -1,44 +1,34 @@
-# Solutions by Asbigail
-## [Valid Phone Number Formats](https://perlweeklychallenge.org/blog/perl-weekly-challenge-110/#TASK1)
-
-> You are given a text file.
-> 
-> Write a script to display all valid phone numbers in the given text file.
-
-### Acceptable Phone Number Formats
-
-~~~~
-+nn  nnnnnnnnnn
-(nn) nnnnnnnnnn
-nnnn nnnnnnnnnn
-~~~~
-
-### Input File
-~~~~
-0044 1148820341
- +44 1148820341
-  44-11-4882-0341
-(44) 1148820341
-  00 1148820341
-~~~~
-
-### Output
-~~~~
-0044 1148820341
- +44 1148820341
-(44) 1148820341
-~~~~
+# Solutions by Abigail
+## [Search Matrix](https://perlweeklychallenge.org/blog/perl-weekly-challenge-111/#TASK1)
 
-### Notes
-The examples show we should not take the specification as a specification;
-just a rough guideline. According to the specification, 
-" +44 1148820341" fails the criteria not once, but twice: it contains
-a leading space (not allowed in the specification), and it has only a
-single space between the '+44' part and the rest, where the specification
-requires two.
+> You are given 5x5 matrix filled with integers such that each row is
+> sorted from left to right and the first integer of each row is greater
+> than the last integer of the previous row.
+>
+> Write a script to find a given integer in the matrix using an
+> efficient search algorithm.
 
-We therefore conclude the examples just contain random spaces, and we
-can completly ignore any white space in the input.
+### Notes
+This challenge confuses me. We're basically asked to find a number
+in a sorted list. Which in languages without hashes one would solve
+with binary search (yielding an O (log N) solution), and in languages
+with hashes you'd use a hash (yielding an O (1) (expected) time solution).
+Sure, the hash takes linear preprocessing time, but since we're asked
+to write a script, we're spending linear time reading in the data
+anyway.
+
+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.
+
+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.
+
+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.
 
 ### Solutions
 * [AWK](awk/ch-1.awk)
@@ -51,33 +41,44 @@ can completly ignore any white space in the input.
 * [Ruby](ruby/ch-1.rb)
 
 ### Blog
-[Perl Weekly Challenge 110: Valid Phone Numbers](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-110-1.html)
 
-## [Transpose File](https://perlweeklychallenge.org/blog/perl-weekly-challenge-110/#TASK2)
+## [Ordered Letters](https://perlweeklychallenge.org/blog/perl-weekly-challenge-111/#TASK2)
+
+> Given a word, you can sort its letters alphabetically (case insensitive).
+> For example, 'beekeeper' becomes 'beeeeekpr' and 'dictionary' becomes
+> 'acdiinorty'.
+>
+> Write a script to find the longest English words that don't change when
+> their letters are sorted.
+
+### Notes
+We will grep the words from standard input which don't change
+if they are sorted; these are the words which match the pattern
+/^a*b*c*...z*$/i. We keep track of the longest word.
+
+If course, there does not have to be a unique word. It will depend
+on the word list used to search in. For instance, three different
+word list I used give different results:
 
-> You are given a text file.
-> 
-> Write a script to transpose the contents of the given file.
+    infochimps.com     /usr/share/dict/words     enable.lst
+    --------------     ---------------------     ----------
+                                     Adelops
+          aegilops
+                                     alloquy
+                                     beefily        beefily
+                                     begorry
+                                     billowy        billowy
+                                     egilops
 
-### Input File
-~~~~
-name,age,sex
-Mohammad,45,m
-Joe,20,m
-Julie,35,f
-Cristina,10,f
-~~~~
+Only one of them has a unique longest word.
 
-### Output
-~~~~
-name,Mohammad,Joe,Julie,Cristina
-age,45,20,35,10
-sex,m,m,f,f
-~~~~
+We will be reading a word list from standard input, and write
+the longest word where the letters are in alphabetical order
+to standard output. In case of ties, we print the first one found.
 
 
 ### Solutions
-* [AWK](awk/ch-2.awk)
+* [GNU AWK](awk/ch-2.gawk)
 * [Bash](bash/ch-2.sh)
 * [C](c/ch-2.c)
 * [Lua](lua/ch-2.lua)
@@ -87,5 +88,4 @@ sex,m,m,f,f
 * [Ruby](ruby/ch-2.rb)
 
 ### Blog
-[Perl Weekly Challenge 110: Transpose File](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-110-2.html)
 
diff --git a/challenge-111/abigail/awk/ch-1.awk b/challenge-111/abigail/awk/ch-1.awk
new file mode 100644
index 0000000000..c82c027708
--- /dev/null
+++ b/challenge-111/abigail/awk/ch-1.awk
@@ -0,0 +1,30 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
+BEGIN {
+    MATRIX_SIZE = 5
+}
+
+#
+# Read in the matrix first
+#
+NR <= MATRIX_SIZE {
+    for (i = 1; i <= NF; i ++) {
+        matrix [$i] = 1
+    }
+}
+
+#
+# For the rest, print 1/0 depending on whether the input
+# is in the matrix or not.
+#
+NR > MATRIX_SIZE {
+    print (matrix [$0] ? 1 : 0)
+}
diff --git a/challenge-111/abigail/awk/ch-2.gawk b/challenge-111/abigail/awk/ch-2.gawk
new file mode 100644
index 0000000000..98ac26a066
--- /dev/null
+++ b/challenge-111/abigail/awk/ch-2.gawk
@@ -0,0 +1,33 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-2.gawk < input-file
+#
+
+BEGIN {
+    IGNORECASE = 1
+    longest = ""
+    #
+    # Create a pattern /^a*b*...z*$/
+    #
+    pat = "^"
+    for (i = 97; i <= 122; i ++) {
+        pat = pat sprintf ("%c*", i)
+    }
+    pat = pat "$"
+}
+
+#
+# Match words with letters in lexical order; keep longest.
+#
+match ($0, pat) && length ($0) > length (longest) {
+    longest = $0
+}
+
+END {
+    print longest
+}
diff --git a/challenge-111/abigail/bash/ch-1.sh b/challenge-111/abigail/bash/ch-1.sh
new file mode 100644
index 0000000000..0ef20b5732
--- /dev/null
+++ b/challenge-111/abigail/bash/ch-1.sh
@@ -0,0 +1,29 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-1.sh < input-file
+#
+
+declare -A matrix
+MATRIX_SIZE=5
+
+#
+# Read in the matrix
+#
+for   ((i = 1; i <= $MATRIX_SIZE; i ++))
+do    read -a line
+      for n in ${line[@]}
+      do  matrix[$n]=1
+      done
+done
+
+#
+# Print 1/0 depending or not whether the number is in the matrix
+#
+while read number
+do    echo $((matrix[$number] ? 1 : 0))
+done
diff --git a/challenge-111/abigail/bash/ch-2.sh b/challenge-111/abigail/bash/ch-2.sh
new file mode 100644
index 0000000000..7add8bc05f
--- /dev/null
+++ b/challenge-111/abigail/bash/ch-2.sh
@@ -0,0 +1,30 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-2.sh < input-file
+#
+
+
+set -f
+shopt -s extglob
+
+pat1="*(a)*(b)*(c)*(d)*(e)*(f)*(g)*(h)*(i)*(j)*(k)*(l)*(m)"
+pat2="*(n)*(o)*(p)*(q)*(r)*(s)*(t)*(u)*(v)*(w)*(x)*(y)*(z)"
+
+longest=""
+
+while read line
+do    lower=${line,,}                 # Lower case input
+      left=${lower/#$pat1$pat2/}      # Remove pattern
+                                      # Test whether nothing left,
+                                      # and string larger longest found
+      if   [ "X$left" == "X" -a ${#line} -gt ${#longest} ]
+      then longest=$line
+      fi
+done
+
+echo $longest
diff --git a/challenge-111/abigail/c/ch-1.c b/challenge-111/abigail/c/ch-1.c
new file mode 100644
index 0000000000..a8804c7390
--- /dev/null
+++ b/challenge-111/abigail/c/ch-1.c
@@ -0,0 +1,49 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file
+ */
+
+# define MATRIX_SIZE 5
+# define NR_OF_ELEMENTS (MATRIX_SIZE * MATRIX_SIZE)
+
+static int compare (const void *a, const void *b) {
+    return * (int *) a - * (int *) b;
+}
+
+int main (void) {
+    int * matrix;
+    int   target;
+
+    if ((matrix = (int *) malloc (NR_OF_ELEMENTS * sizeof (int))) == NULL) {
+        perror ("Malloc failed");
+        exit (1);
+    }
+
+    /*
+     * Read in the matrix
+     */
+    for (int i = 0; i < NR_OF_ELEMENTS; i ++) {
+        if (scanf ("%d", &matrix [i]) != 1) {
+            perror ("Scanf failed");
+            exit (1);
+        }
+    }
+
+    /*
+     * Read in the search data, and print 1/0 depending on whether
+     * the read number is in the matrix or not.
+     */
+    while (scanf ("%d", &target) == 1) {
+        printf ("%d\n", bsearch (&target, matrix, NR_OF_ELEMENTS,
+                                  sizeof (int), compare) == NULL ? 0 : 1);
+    }
+
+    return (0);
+}
diff --git a/challenge-111/abigail/c/ch-2.c b/challenge-111/abigail/c/ch-2.c
new file mode 100644
index 0000000000..a677e4cad6
--- /dev/null
+++ b/challenge-111/abigail/c/ch-2.c
@@ -0,0 +1,60 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <stdbool.h>
+# include <ctype.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file
+ */
+
+int main (void) {
+    char *  line         = NULL;
+    size_t  len          =    0;
+    char *  longest      = NULL;
+    size_t  longest_size =    0;
+
+    while (getline (&line, &len, stdin) != -1) {
+        /*
+         * First check whether the word has its characters
+         * in lexical order.
+         */
+        size_t i      = 0;
+        bool in_order = 1;
+        while (line [i] != '\n') {
+            if ((i && tolower (line [i]) < tolower (line [i - 1])) ||
+                !isalpha (line [i])) {
+                in_order = false;
+                break;
+            }
+            i ++;
+        }
+
+        /*
+         * If we have a word with its characters in lexical order, and
+         * it's longer than the longest word found, keep the word.
+         */
+        if (in_order && i > longest_size) {
+            longest_size = i;
+            if ((longest = (char *) realloc (longest, (i + 1) * sizeof (char)))
+                 == NULL) {
+                perror ("Realloc failed");
+                exit (1);
+            }
+            for (size_t j = 0; j <= i; j ++) {  /* Copies the newline as well */
+                longest [j] = line [j];
+            }
+            longest [i + 1] = '\0';
+        }
+    }
+    printf ("%s", longest);
+
+    free (line);
+    free (longest);
+
+    return (0);
+}
diff --git a/challenge-111/abigail/lua/ch-1.lua b/challenge-111/abigail/lua/ch-1.lua
new file mode 100644
index 0000000000..194e55b458
--- /dev/null
+++ b/challenge-111/abigail/lua/ch-1.lua
@@ -0,0 +1,33 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-1.lua < input-file
+--
+
+local MATRIX_SIZE = 5
+
+matrix = {}
+
+-- 
+-- Read in the matrix
+--
+for i = 1, MATRIX_SIZE * MATRIX_SIZE do 
+    matrix [io . read ("*number")] = 1
+end
+
+--
+-- Read in the rest, printing 1/0 depending on
+-- whether the number is present in the matrix or not.
+--
+while true do
+    target = io . read ("*number")
+    if   target == nil then break end
+    if   matrix [target]
+    then print (1)
+    else print (0)
+    end
+end
diff --git a/challenge-111/abigail/lua/ch-2.lua b/challenge-111/abigail/lua/ch-2.lua
new file mode 100644
index 0000000000..6beeb6a979
--- /dev/null
+++ b/challenge-111/abigail/lua/ch-2.lua
@@ -0,0 +1,25 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-2.lua < input-file
+--
+
+local longest = ""
+
+for line in io . lines () do
+    --
+    -- Find words with their letters in lexical order, and which are
+    -- longer than the longest found so far.
+    --
+    if   line : lower ()
+              : find  ("^a*b*c*d*e*f*g*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$")
+         and line : len () > longest : len ()
+    then longest = line
+    end
+end
+
+print (longest)
diff --git a/challenge-111/abigail/node/ch-1.js b/challenge-111/abigail/node/ch-1.js
new file mode 100644
index 0000000000..6e97d03272
--- /dev/null
+++ b/challenge-111/abigail/node/ch-1.js
@@ -0,0 +1,37 @@
+#!/usr/local/bin/node
+
+//
+// See ../README.md
+//
+
+//
+// Run as: node ch-1.js < input-file
+//
+
+let MATRIX_SIZE = 5
+
+//
+// Read in all the numbers, both the matrix and the target numbers
+//
+let numbers = 
+  require      ("fs")
+. readFileSync (0)                     // Read all.
+. toString     ()                      // Turn it into a string.
+. match        (/-?[0-9]+/g)
+
+//
+// Populate the matrix
+//
+let matrix = {}
+for (let i = 0; i < MATRIX_SIZE * MATRIX_SIZE; i ++) {
+    matrix [numbers [i]] = 1
+}
+
+//
+// Check the rest of the numbers whether they're present
+// in the matrix.
+//
+for (let j = MATRIX_SIZE * MATRIX_SIZE; j < numbers . length; j ++) {
+    console . log (matrix [numbers [j]] ? 1 : 0)
+}
+
diff --git a/challenge-111/abigail/node/ch-2.js b/challenge-111/abigail/node/ch-2.js
new file mode 100644
index 0000000000..3d7b301b5d
--- /dev/null
+++ b/challenge-111/abigail/node/ch-2.js
@@ -0,0 +1,23 @@
+#!/usr/local/bin/node
+
+//
+// See ../README.md
+//
+
+//
+// Run as: node ch-2.js < inp