diff options
| -rw-r--r-- | challenge-096/abigail/README.md | 1 | ||||
| -rw-r--r-- | challenge-096/abigail/node/ch-2.js | 43 |
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] +} |