Node solution for week 96, part 2

2 files changed, 44 insertions, 0 deletions

diff --git a/challenge-096/abigail/README.md b/challenge-096/abigail/README.md
index ea55819653..b19e1c3934 100644
--- a/challenge-096/abigail/README.md
+++ b/challenge-096/abigail/README.md
@@ -58,6 +58,7 @@ Operation 2: replace 'u' with 'o'
 ~~~~
 
 ### Solutions
+* [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
 
 ### Blog
diff --git a/challenge-096/abigail/node/ch-2.js b/challenge-096/abigail/node/ch-2.js
new file mode 100644
index 0000000000..03f423b2ec
--- /dev/null
+++ b/challenge-096/abigail/node/ch-2.js
@@ -0,0 +1,43 @@
+//
+// 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 (LevenshteinDistance (_ . split (/\s+/))))
+;
+
+//
+// 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
+//
+function LevenshteinDistance (strings) {
+    let first  = strings [0] . split ("");
+    let second = strings [1] . split ("");
+
+    let distance = [];
+
+    let N = first  . length;
+    let M = second . length;
+
+    for (let i = 0; i <= N; i ++) {
+        distance [i] = [];
+        for (let j = 0; j <= M; j ++) {
+            distance [i] [j] = 
+                i == 0 || j == 0 ? i + j
+              : Math . min (distance [i - 1] [j]     + 1,
+                            distance [i]     [j - 1] + 1,
+                            distance [i - 1] [j - 1] +
+                               (first  [i - 1] ==
+                                second [j - 1] ? 0 : 1))
+        }
+        if (i) {
+            distance [i - 1] = 0
+        }
+    }
+    return distance [N] [M]
+}