Merge pull request #3357 from Abigail/abigail/week-096

Abigail/week 096

18 files changed, 212 insertions, 93 deletions

diff --git a/challenge-096/abigail/README.md b/challenge-096/abigail/README.md
index d715618651..9e5afd71ff 100644
--- a/challenge-096/abigail/README.md
+++ b/challenge-096/abigail/README.md
@@ -19,17 +19,29 @@ Input: $S = "    Perl and   Raku are  part of the same family  "
 Output: "family same the of part are Raku and Perl"
 ~~~~
 
+### Notes
+
+The challenge isn't quite clear on whether we should output a number
+(the minimal number of operations required), or the actual operations.
+The examples show both -- but separated by a blank line. Previous
+challenges typically use a blank line to separate the required output
+from the explaination on why that it is the correct answer.
+
+We're opting to only print the number of operations, not the actual
+operations.
+
 ### Solutions
 * [AWK](awk/ch-1.awk)
-* [bash](sh/ch-1.sh)
+* [Bash](sh/ch-1.sh)
 * [C](c/ch-1.c)
-* [lua](lua/ch-1.lua)
+* [Lua](lua/ch-1.lua)
 * [Node.js](node/ch-1.js)
 * [Perl](perl/ch-1.pl)
 * [Python](python/ch-1.py)
 * [Ruby](ruby/ch-1.rb)
 
 ### Blog
+[Perl Weekly Challenge 96: Reverse Words](https://wp.me/pcxd30-mj)
 
 
 ## [Edit Distance](https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/#TASK2)
@@ -62,10 +74,11 @@ Operation 2: replace 'u' with 'o'
 ### Solutions
 * [AWK](awk/ch-2.awk)
 * [C](c/ch-2.c)
-* [lua](lua/ch-2.lua)
+* [Lua](lua/ch-2.lua)
 * [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
 * [Python](python/ch-2.py)
 * [Ruby](ruby/ch-2.rb)
 
 ### Blog
+[Perl Weekly Challenge 96: Edit Distance](https://wp.me/pcxd30-n7)
diff --git a/challenge-096/abigail/awk/ch-1.awk b/challenge-096/abigail/awk/ch-1.awk
index 744c154648..dae5328b5f 100644..100755
--- a/challenge-096/abigail/awk/ch-1.awk
+++ b/challenge-096/abigail/awk/ch-1.awk
@@ -1,3 +1,13 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
 #
 # AWK splits lines on whitespace, making each field available
 # in $1, $2, ..., etc. So, we just print the fields in reverse,
diff --git a/challenge-096/abigail/awk/ch-2.awk b/challenge-096/abigail/awk/ch-2.awk
index 08cebccb4e..9d3c9fb492 100644..100755
--- a/challenge-096/abigail/awk/ch-2.awk
+++ b/challenge-096/abigail/awk/ch-2.awk
@@ -1,3 +1,13 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-2.awk < input-file
+#
+
 #
 # Return the minimum of 3 values
 #
diff --git a/challenge-096/abigail/bash/ch-1.sh b/challenge-096/abigail/bash/ch-1.sh
index 9122fae4e0..65c6e20bdb 100644..100755
--- a/challenge-096/abigail/bash/ch-1.sh
+++ b/challenge-096/abigail/bash/ch-1.sh
@@ -1,3 +1,13 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-1.sh < input-file
+#
+
 #
 # Read in a line from STDIN, split it on whitespace,
 # put the result into an array 'words'
@@ -7,7 +17,7 @@ do
      #
      # Iterate over the words backwards, and print them.
      #
-     for   ((i = ${#words[@]} - 1; i >= 0; i --));
+     for  ((i = ${#words[@]} - 1; i >= 0; i --));
      do   printf "%s" ${words[$i]}
           #
           # Print a newline after the final word; otherwise,
diff --git a/challenge-096/abigail/blog.txt b/challenge-096/abigail/blog.txt
new file mode 100644
index 0000000000..2559e67c32
--- /dev/null
+++ b/challenge-096/abigail/blog.txt
@@ -0,0 +1 @@
+https://wp.me/pcxd30-mj
diff --git a/challenge-096/abigail/blog1.txt b/challenge-096/abigail/blog1.txt
new file mode 100644
index 0000000000..231a6fbbc0
--- /dev/null
+++ b/challenge-096/abigail/blog1.txt
@@ -0,0 +1 @@
+https://wp.me/pcxd30-n7
diff --git a/challenge-096/abigail/c/ch-1.c b/challenge-096/abigail/c/ch-1.c
index 22ebafd404..b01e726173 100644
--- a/challenge-096/abigail/c/ch-1.c
+++ b/challenge-096/abigail/c/ch-1.c
@@ -1,62 +1,56 @@
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ch-1.o < input-file
+ */
+
 # include <stdlib.h>
 # include <stdio.h>
-# include <string.h>
 # include <ctype.h>
 
 int main (void) {
     char *  line    = NULL;
     size_t  len     = 0;
-    size_t  strlen;
+    size_t  ptr;
 
-    while ((strlen = getline (&line, &len, stdin)) != -1) {
-        char * line_ptr = line;
-        size_t end = strlen;
-        size_t begin;
+    while ((ptr = getline (&line, &len, stdin)) != -1) {
         size_t output = 0;
-        while (end > 0) {
+        while (ptr > 0) {
             /*
              * Skip tailing whitespace
              */
-            while (end > 0 && isspace (line [end - 1])) {
-                end --;
+            while (ptr > 0 && isspace (line [ptr - 1])) {
+                ptr --;
             }
 
             /*
-             * 'end' now just after the end of a word, or
+             * 'ptr' is now just after the end of a word, or
              * at the beginning of the string; if the latter,
              * there is nothing left to print.
              */
-
-            if (end <= 0) {
+            if (ptr <= 0) {
                 break;
             }
 
             /*
-             * Find the beginning of a word
+             * Terminate the string just after the newly found word
              */
-            begin = end - 1;
-            while (begin > 0 && !isspace (line [begin - 1])) {
-                begin --;
-            }
+            line [ptr] = '\0';
 
             /*
-             * Extract the word out of the string: allocate memory,
-             * and copy the right part of the input.
+             * Find the beginning of that word
              */
-            char * word;
-            if ((word = malloc ((end - begin + 1) * sizeof (char))) == NULL) {
-                fprintf (stderr, "Out of memory\n");
-                exit (1);
+            while (ptr > 0 && !isspace (line [ptr - 1])) {
+                ptr --;
             }
-            stpncpy (word, line + begin, end - begin);
 
             /*
-             * Print the string, prepended (except the first printed word)
+             * Print the word, prepended (except the first printed word)
              * by a space.
              */
-            printf ("%s%s", output ++ ? " " : "", word);
-
-            end = begin;
+            printf ("%s%s", output ++ ? " " : "", &line [ptr]);
         }
         printf ("\n");
     }
diff --git a/challenge-096/abigail/c/ch-2.c b/challenge-096/abigail/c/ch-2.c
index 73f35b1c0a..0c88bff827 100644
--- a/challenge-096/abigail/c/ch-2.c
+++ b/challenge-096/abigail/c/ch-2.c
@@ -1,3 +1,11 @@
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-2.o ch-2.c; ch-2.o < input-file
+ */
+
 # include <stdlib.h>
 # include <stdio.h>
 # include <string.h>
@@ -20,19 +28,6 @@ size_t min3 (size_t a, size_t b, size_t c) {
 size_t LevenshteinDistance (char * first,  size_t n,
                             char * second, size_t m) {
       
-    /*
-     * If 'first' is the shorter string, swap the two strings.
-     * This reduces the memory usage.
-     */
-    if (n < m) {
-        char * tmp = first;
-        size_t t   = n;
-        first  = second;
-        second = tmp;
-        n      = m;
-        m      = t;
-    }
-
     size_t ** distance;
     if ((distance = malloc ((n + 1) * sizeof (size_t *))) == NULL) {
         fprintf (stderr, "Out of memory\n");
@@ -54,7 +49,7 @@ size_t LevenshteinDistance (char * first,  size_t n,
             /*
              * We only need the previous row; freeing the memory of rows
              * we no longer need, reduces the memory usage from
-             * Theta (n * m) to O (min (n, m))
+             * Theta (n * m) to O (n + m)
              */
             free (distance [i - 1]);
         }
diff --git a/challenge-096/abigail/lua/ch-1.lua b/challenge-096/abigail/lua/ch-1.lua
index 9c4b1de913..c2de0434f6 100644..100755
--- a/challenge-096/abigail/lua/ch-1.lua
+++ b/challenge-096/abigail/lua/ch-1.lua
@@ -1,9 +1,19 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-1.lua < input-file
+--
+
 for line in io . lines () do
     --
     -- Extract words and put them into an array, in reverse.
     --
     local words = {}
-    for str in string . gmatch (line, "[^ ]+") do
+    for str in string . gmatch (line, "[^%s]+") do
         table . insert (words, 1, str)
     end
 
diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua
index 162f06eef0..99058213ca 100644..100755
--- a/challenge-096/abigail/lua/ch-2.lua
+++ b/challenge-096/abigail/lua/ch-2.lua
@@ -1,3 +1,13 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-2.lua < input-file
+--
+
 --
 -- This is an implementation of the Wagner Fischer algorithm, which
 -- calculates the Levenshtein distance.
@@ -7,18 +17,13 @@
 function LevenshteinDistance (first, second)
     local n = first  : len ()
     local m = second : len ()
-    if n < m
-    then
-        first, second = second, first
-        n,     m      = m,      n
-    end
-    distances = {}
+    distance = {}
     for i = 0, n do
-        distances [i] = {}
+        distance [i] = {}
         for j = 0, m do
             if i == 0 or j == 0
             then
-                distances [i] [j] = i + j
+                distance [i] [j] = i + j
             else
                 local cost = 1
                 if string . sub (first,  i, i) ==
@@ -26,10 +31,10 @@ function LevenshteinDistance (first, second)
                 then
                     cost = 0
                 end
-                distances [i] [j] = math . min (
-                    distances [i - 1] [j]     + 1,
-                    distances [i]     [j - 1] + 1,
-                    distances [i - 1] [j - 1] + cost
+                distance [i] [j] = math . min (
+                    distance [i - 1] [j]     + 1,
+                    distance [i]     [j - 1] + 1,
+                    distance [i - 1] [j - 1] + cost
                 )
             end
         end
@@ -37,14 +42,14 @@ function LevenshteinDistance (first, second)
         --
         -- We only need the previous row, so we can return the
         -- memory of rows before that. This reduces the memory
-        -- usage from O (n * m) to O (min (n, m))
+        -- usage from Theta (n * m) to O (n + m)
         --
         if i > 0
         then
-            distances [i - 1] = nil
+            distance [i - 1] = nil
         end
     end
-    return distances [n] [m]
+    return distance [n] [m]
 end
 
 
diff --git a/challenge-096/abigail/node/ch-1.js b/challenge-096/abigail/node/ch-1.js
index b31524a686..994c1e1971 100644..100755
--- a/challenge-096/abigail/node/ch-1.js
+++ b/challenge-096/abigail/node/ch-1.js
@@ -1,15 +1,17 @@
+#!/usr/local/bin/node
+
 //
-// Read STDIN. Split on newlines, filter out empty lines, then call "main".
-//
-  require      ("fs")
-. readFileSync (0)               // Read all.
-. toString     ()                // Turn it into a string.
-. split        ("\n")            // Split on newlines.
-. filter       (_ => _ . length) // Filter out empty lines.
-. map          (_ => console . log (_ . trim    ()        // Remove leading
-                                                          // and trailing
-                                                          // whitespace.
-                                      . split   (/\s+/)   // split ...
-                                      . reverse ()        // reverse ...
-                                      . join    (" ")))   // and recombine.
-;
+// See ../README.md
+//
+
+//
+// Run as: node ch-1.js < input-file
+//
+
+require ('readline')
+. createInterface ({input: process . stdin})
+. on ('line', _ =>
+       console . log (_ . trim    ()        // Remove leading/trailing spaces
+                        . split   (/\s+/)   // Split on white space
+                        . reverse ()        // Reverse the words
+                        . join    (" ")))   // And join them again.
diff --git a/challenge-096/abigail/node/ch-2.js b/challenge-096/abigail/node/ch-2.js
index 8423ab96b8..a9618414a3 100644..100755
--- a/challenge-096/abigail/node/ch-2.js
+++ b/challenge-096/abigail/node/ch-2.js
@@ -1,6 +1,13 @@
+#!/usr/local/bin/node
+
+//
+// See ../README.md
 //
-// Read STDIN. Split on newlines, filter out empty lines, then call "main".
+
 //
+// Run as: node ch-2.js < input-file
+//
+
   require      ("fs")
 . readFileSync (0)               // Read all.
 . toString     ()                // Turn it into a string.
diff --git a/challenge-096/abigail/perl/ch-1.pl b/challenge-096/abigail/perl/ch-1.pl
index ddca656054..ccd4146db5 100644..100755
--- a/challenge-096/abigail/perl/ch-1.pl
+++ b/challenge-096/abigail/perl/ch-1.pl
@@ -1,5 +1,13 @@
 #!/opt/perl/bin/perl
 
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-1.pl < input-file
+#
+
 use 5.032;
 
 use strict;
diff --git a/challenge-096/abigail/perl/ch-2.pl b/challenge-096/abigail/perl/ch-2.pl
index bb58c84569..c84dec7ad1 100644..100755
--- a/challenge-096/abigail/perl/ch-2.pl
+++ b/challenge-096/abigail/perl/ch-2.pl
@@ -1,4 +1,12 @@
+#!/opt/perl/bin/perl
 
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-2.pl < input-file
+#
 
 use 5.032;
 
@@ -12,14 +20,23 @@ use experimental 'lexical_subs';
 use List::Util 'min';
 
 #
+# The challenge isn't quite clear on whether we should output a number
+# (the minimal number of operations required), or the actual operations.
+# The examples show both -- but separated by a blank line. Previous
+# challenges typically use a blank line to separate the required output
+# from the explaination on why that it is the correct answer.
+#
+# We're opting to only print the number of operations, not the actual
+# operations.
+#
+
+#
 # This is an implementation of the Wagner Fischer algorithm, which
 # calculates the Levenshtein distance.
 #
 # See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
 #
 sub LevenshteinDistance ($first, $second) {
-   ($first, $second) = ($second, $first) if length ($first) <
-                                            length ($second);
     my $distance;
     for (my $i = 0; $i <= length ($first); $i ++) {
         for (my $j = 0; $j <= length ($second); $j ++) {
@@ -33,7 +50,7 @@ sub LevenshteinDistance ($first, $second) {
         }
         #
         # We only need the previous row; this reduces the memory
-        # from O (N * M) to O (min (N, M)), where N and M are the
+        # from Theta (N * M) to O (N + M), where N and M are the
         # lengths of the input strings.
         #
         undef $$distance [$i - 1] if $i;
diff --git a/challenge-096/abigail/python/ch-1.py b/challenge-096/abigail/python/ch-1.py
index ddc34e2633..84a1c2618b 100644..100755
--- a/challenge-096/abigail/python/ch-1.py
+++ b/challenge-096/abigail/python/ch-1.py
@@ -1,3 +1,13 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-1.py < input-file
+#
+
 import fileinput
 
 for line in fileinput . input ():
diff --git a/challenge-096/abigail/python/ch-2.py b/challenge-096/abigail/python/ch-2.py
index deaeff14cf..2e24e442f8 100644..100755
--- a/challenge-096/abigail/python/ch-2.py
+++ b/challenge-096/abigail/python/ch-2.py
@@ -1,3 +1,13 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-2.py < input-file
+#
+
 import fileinput
 
 def LevenshteinDistance (first, second):
diff --git a/challenge-096/abigail/ruby/ch-1.rb b/challenge-096/abigail/ruby/ch-1.rb
index 064f780345..588ac76d7c 100644..100755
--- a/challenge-096/abigail/ruby/ch-1.rb
+++ b/challenge-096/abigail/ruby/ch-1.rb
@@ -1,3 +1,13 @@
+#!/usr/bin/ruby
+
+#
+# See ../README.md
+#
+
+#
+# Run as: ruby ch-1.rb < input-file
+#
+
 ARGF . each_line do |_|
-    puts ((_ . split (/\s+/)) . grep (/\S/)) . reverse . join (" ")
+    puts (_ . strip . split (/\s+/)) . reverse . join (" ")
 end
diff --git a/challenge-096/abigail/ruby/ch-2.rb b/challenge-096/abigail/ruby/ch-2.rb
index 65a57bd6d3..b7ea2a3f6b 100644..100755
--- a/challenge-096/abigail/ruby/ch-2.rb
+++ b/challenge-096/abigail/ruby/ch-2.rb
@@ -1,28 +1,34 @@
+#!/usr/bin/ruby
+
+#
+# See ../README.md
+#
+
+#
+# Run as: ruby ch-2.rb < input-file
+#
+
 def LevenshteinDistance (first, second)
     n = first  . length
     m = second . length
-    if n < m
-        first, second = second, first
-        n,     m      = m,      n
-    end
-    distances = []
+    distance = []
     for i in 0 .. n do
-        distances [i] = []
+        distance [i] = []
         for j in 0 .. m do
-            distances [i] [j] = i == 0 || j == 0 ? i + j
-                    : [distances [i - 1] [j]     + 1,
-                       distances [i]     [j - 1] + 1,
-                       distances [i - 1] [j - 1] +
+            distance [i] [j] = i == 0 || j == 0 ? i + j
+                    : [distance [i - 1] [j]     + 1,
+                       distance [i]     [j - 1] + 1,
+                       distance [i - 1] [j - 1] +
                           (first [i - 1] == second [j - 1] ? 0 : 1)] . min
         end
         #
         # Release memory
         #
         if i > 1
-            distances [i - 1] = nil
+            distance [i - 1] = nil
         end
     end
-    return distances [n] [m]
+    return distance [n] [m]
 end
 
 ARGF . each_line do |_|