aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-096/paulo-custodio/basic/ch-1.bas57
-rw-r--r--challenge-096/paulo-custodio/basic/ch-2.bas138
-rw-r--r--challenge-096/paulo-custodio/c/ch-1.c59
-rw-r--r--challenge-096/paulo-custodio/c/ch-2.c164
-rw-r--r--challenge-096/paulo-custodio/cpp/ch-1.cpp42
-rw-r--r--challenge-096/paulo-custodio/cpp/ch-2.cpp150
-rw-r--r--challenge-096/paulo-custodio/forth/ch-1.fs81
-rw-r--r--challenge-096/paulo-custodio/forth/ch-2.fs153
-rw-r--r--challenge-096/paulo-custodio/perl/ch-1.pl22
-rw-r--r--challenge-096/paulo-custodio/perl/ch-2.pl114
-rw-r--r--challenge-096/paulo-custodio/perl/ch-2a.pl60
-rw-r--r--challenge-096/paulo-custodio/python/ch-1.py20
-rw-r--r--challenge-096/paulo-custodio/python/ch-2.py101
-rw-r--r--challenge-096/paulo-custodio/test.pl67
14 files changed, 1228 insertions, 0 deletions
diff --git a/challenge-096/paulo-custodio/basic/ch-1.bas b/challenge-096/paulo-custodio/basic/ch-1.bas
new file mode 100644
index 0000000000..4d3951e8db
--- /dev/null
+++ b/challenge-096/paulo-custodio/basic/ch-1.bas
@@ -0,0 +1,57 @@
+' Challenge 096
+'
+' TASK #1 › Reverse Words
+' Submitted by: Mohammad S Anwar
+' You are given a string $S.
+'
+' Write a script to reverse the order of words in the given string. The string
+' may contain leading/trailing spaces. The string may have more than one space
+' between words in the string. Print the result without leading/trailing spaces
+' and there should be only one space between words.
+'
+' Example 1:
+' Input: $S = "The Weekly Challenge"
+' Output: "Challenge Weekly The"
+
+function join_args() as string
+ dim text as string
+ dim i as integer
+
+ i = 1
+ do while command(i)<>""
+ text &= trim(command(i))+" "
+ i += 1
+ loop
+ join_args = trim(text)
+end function
+
+sub split_text(words() as string, text as string)
+ dim p as integer
+
+ redim preserve words(0)
+ text = trim(text)
+ p = instr(text, " ")
+ do while p > 0
+ redim preserve words(ubound(words)+1)
+ words(ubound(words)) = left(text, p-1)
+ text = trim(mid(text, p+1))
+ p = instr(text, " ")
+ loop
+ 'store last segment
+ redim preserve words(ubound(words)+1)
+ words(ubound(words)) = text
+end sub
+
+sub print_reverse(words() as string)
+ dim i as integer
+
+ for i = ubound(words) to 1 step -1
+ print words(i);" ";
+ next i
+ print
+end sub
+
+dim words() as string
+split_text words(), join_args()
+print_reverse words()
+
diff --git a/challenge-096/paulo-custodio/basic/ch-2.bas b/challenge-096/paulo-custodio/basic/ch-2.bas
new file mode 100644
index 0000000000..b4eb1fa7b6
--- /dev/null
+++ b/challenge-096/paulo-custodio/basic/ch-2.bas
@@ -0,0 +1,138 @@
+' Challenge 096
+'
+' TASK #2 › Edit Distance
+' Submitted by: Mohammad S Anwar
+' You are given two strings $S1 and $S2.
+'
+' Write a script to find out the minimum operations required to convert $S1
+' into $S2. The operations can be insert, remove or replace a character. Please
+' check out Wikipedia page for more information.
+'
+' Example 1:
+' Input: $S1 = "kitten"; $S2 = "sitting"
+' Output: 3
+'
+' Operation 1: replace 'k' with 's'
+' Operation 2: replace 'e' with 'i'
+' Operation 3: insert 'g' at the end
+' Example 2:
+' Input: $S1 = "sunday"; $S2 = "monday"
+' Output: 2
+'
+' Operation 1: replace 's' with 'm'
+' Operation 2: replace 'u' with 'o'
+'
+' NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+' from which the operations can be deduced
+
+const E as integer = 1
+const S as integer = 2
+const SE as integer = 3
+
+function min(a as integer, b as integer) as integer
+ if a < b then
+ min = a
+ else
+ min = b
+ end if
+end function
+
+function min3(a as integer, b as integer, c as integer) as integer
+ min3 = min(a, min(b, c))
+end function
+
+sub wag_fish_dist(a as string, b as string)
+ dim i as integer, j as integer, stp as integer, subst_cost as integer
+ dim min_dr as integer, min_delta as integer, dr as integer, delta as integer
+
+ ' define a table where d(i,j) is the Levenshtein distance between
+ ' first i chars of a and first j chars of b
+ dim d(len(a)+1, len(b)+1) as integer
+
+ ' source prefixes can be transformed into empty string by dropping chars
+ for i = 1 to len(a)
+ d(i,0) = i
+ next i
+
+ ' target prefixes can be reached from empty source prefix by inserting chars
+ for j = 1 to len(b)
+ d(0,j) = j
+ next j
+
+ ' flood-fill the rest of the table
+ for j = 1 to len(b)
+ for i = 1 to len(a)
+ if mid(a,i,1) = mid(b,j,1) then
+ subst_cost = 0
+ else
+ subst_cost = 1
+ end if
+ d(i,j) = min3(d(i-1,j)+1, _ ' deletion
+ d(i,j-1)+1, _ ' insertion
+ d(i-1,j-1)+subst_cost) ' substitution
+ next i
+ next j
+
+ ' distance is in lower bottom cell
+ print trim(str(d(len(a),len(b))))
+
+ ' traverse the minimum path
+ i = 0: j = 0
+ do while i < len(a) or j < len(b)
+ dr = 0: delta = 0: min_dr = 0: min_delta = len(a)+len(b)
+
+ ' search shortest path in priority SE, E, S
+ if i < len(a) and j < len(b) then
+ dr = SE: delta = d(i+1,j+1) - d(i,j)
+ min_dr = dr: min_delta = delta
+ end if
+ if j < len(b) then
+ dr = E: delta = d(i,j+1) - d(i,j)
+ if delta < min_delta then
+ min_dr = dr: min_delta = delta
+ end if
+ end if
+ if i < len(a) then
+ dr = S: delta = d(i+1,j) - d(i,j)
+ if delta < min_delta then
+ min_dr = dr: min_delta = delta
+ end if
+ end if
+
+ ' apply shortest path and show steps
+ select case min_dr
+ case SE
+ i += 1: j += 1
+ if mid(a,i,1) <> mid(b,j,1) then
+ stp += 1
+ print "Operation"; stp; ": replace '"; _
+ mid(a,i,1); "' with '"; mid(b,j,1); "'"
+ end if
+ case E
+ j += 1
+ stp += 1
+ if j = len(b) then
+ print "Operation"; stp; ": insert '"; _
+ mid(b,j,1); "' at end"
+ else
+ print "Operation"; stp; ": insert '"; _
+ mid(b,j,1); "' at position"; j
+ end if
+ case S
+ i += 1
+ stp += 1
+ if i = len(a) then
+ print "Operation"; stp; ": insert '"; _
+ mid(a,i,1); "' at end"
+ else
+ print "Operation"; stp; ": insert '"; _
+ mid(a,i,1); "' at position"; i
+ end if
+ case else
+ assert(false)
+ end select
+ loop
+end sub
+
+
+wag_fish_dist command(1), command(2)
diff --git a/challenge-096/paulo-custodio/c/ch-1.c b/challenge-096/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..93d55b1329
--- /dev/null
+++ b/challenge-096/paulo-custodio/c/ch-1.c
@@ -0,0 +1,59 @@
+/*
+Challenge 096
+
+TASK #1 › Reverse Words
+Submitted by: Mohammad S Anwar
+You are given a string $S.
+
+Write a script to reverse the order of words in the given string. The string
+may contain leading/trailing spaces. The string may have more than one space
+between words in the string. Print the result without leading/trailing spaces
+and there should be only one space between words.
+
+Example 1:
+Input: $S = "The Weekly Challenge"
+Output: "Challenge Weekly The"
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+void* check_mem(void* p) {
+ if (!p) {
+ fputs("Out of memory", stderr);
+ exit(EXIT_FAILURE);
+ }
+ return p;
+}
+
+int main(int argc, char* argv[]) {
+ // concatenate all args
+ char* text = check_mem(strdup(""));
+ for (int i = 1; i < argc; i++) {
+ text = check_mem(realloc(text, strlen(text)+strlen(argv[i])+2));
+ strcat(text, argv[i]);
+ strcat(text, " ");
+ }
+
+ // build list of words
+ char** words = NULL;
+ size_t num_words = 0;
+ const char* sep = " ";
+ char* word = strtok(text, sep);
+ while (word) {
+ words = check_mem(realloc(words, ++num_words * sizeof(char*)));
+ words[num_words-1] = word;
+
+ word = strtok(NULL, sep);
+ }
+
+ // print words in reverse order
+ for (int i = num_words-1; i >= 0; i--)
+ printf("%s ", words[i]);
+ printf("\n");
+
+ // free memory
+ free(text);
+ free(words);
+}
diff --git a/challenge-096/paulo-custodio/c/ch-2.c b/challenge-096/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..718bb6018d
--- /dev/null
+++ b/challenge-096/paulo-custodio/c/ch-2.c
@@ -0,0 +1,164 @@
+/*
+Challenge 096
+
+TASK #2 › Edit Distance
+Submitted by: Mohammad S Anwar
+You are given two strings $S1 and $S2.
+
+Write a script to find out the minimum operations required to convert $S1
+into $S2. The operations can be insert, remove or replace a character. Please
+check out Wikipedia page for more information.
+
+Example 1:
+Input: $S1 = "kitten"; $S2 = "sitting"
+Output: 3
+
+Operation 1: replace 'k' with 's'
+Operation 2: replace 'e' with 'i'
+Operation 3: insert 'g' at the end
+Example 2:
+Input: $S1 = "sunday"; $S2 = "monday"
+Output: 2
+
+Operation 1: replace 's' with 'm'
+Operation 2: replace 'u' with 'o'
+
+NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+ from which the operations can be deduced
+*/
+
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+void* check_mem(void* p) {
+ if (!p) {
+ fputs("Out of memory", stderr);
+ exit(EXIT_FAILURE);
+ }
+ return p;
+}
+
+int min(int a, int b) {
+ return (a < b) ? a : b;
+}
+
+int min3(int a, int b, int c) {
+ return min(a, min(b, c));
+}
+
+enum { DIR_NONE, DIR_E, DIR_S, DIR_SE };
+
+void wag_fis_dist(const char* a, const char* b) {
+ int len_a = strlen(a);
+ int len_b = strlen(b);
+
+ // define a table where d[i][j] is the Levenshtein distance between
+ // first i chars of a and first j chars of b
+ int** d = check_mem(calloc(len_a+1, sizeof(int*)));
+ for (int i = 0; i <= len_a; i++)
+ d[i] = check_mem(calloc(len_b+1, sizeof(int)));
+
+ // source prefixes can be transformed into empty string by dropping chars
+ for (int i = 1; i <= len_a; i++)
+ d[i][0] = i;
+
+ // target prefixes can be reached from empty source prefix by inserting chars
+ for (int j = 1; j <= len_b; j++)
+ d[0][j] = j;
+
+ // flood-fill the rest of the table
+ for (int j = 1; j <= len_b; j++) {
+ for (int i = 1; i <= len_a; i++) {
+ int subst_cost = (a[i-1] == b[j-1]) ? 0 : 1;
+ d[i][j] = min3(d[i-1][j]+1, // deletion
+ d[i][j-1]+1, // insertion
+ d[i-1][j-1]+subst_cost); // substitution
+ }
+ }
+
+ // distance is in lower bottom cell
+ printf("%d\n", d[len_a][len_b]);
+
+ // traverse the minimum path
+ int i = 0, j = 0, step = 0;
+ while (i < len_a || j < len_b) {
+ int min_dir = DIR_NONE, min_delta = INT_MAX;
+ int dir, delta;
+
+ // search shortest path in priority SE, E, S
+ if (i < len_a && j < len_b) {
+ dir = DIR_SE;
+ delta = d[i+1][j+1] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ if (j < len_b) {
+ dir = DIR_E;
+ delta = d[i][j+1] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ if (i < len_a) {
+ dir = DIR_S;
+ delta = d[i+1][j] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ // apply shortest path and show steps
+ switch (min_dir) {
+ case DIR_SE:
+ i++; j++;
+ if (a[i-1] != b[j-1]) {
+ printf("Operation %d: replace '%c' with '%c'\n",
+ ++step, a[i-1], b[j-1]);
+ }
+ break;
+ case DIR_E:
+ j++;
+ if (j == len_b)
+ printf("Operation %d: insert '%c' at end\n",
+ ++step, b[j-1]);
+ else
+ printf("Operation %d: insert '%c' at position %d\n",
+ ++step, b[j-1], j);
+ break;
+ case DIR_S:
+ i++;
+ if (i == len_a)
+ printf("Operation %d: delete '%c' at end\n",
+ ++step, a[i-1]);
+ else
+ printf("Operation %d: delete '%c' at position %d\n",
+ ++step, a[i-1], i);
+ break;
+ default:
+ assert(0);
+ }
+ }
+
+ // free memory
+ for (int i = 0; i <= len_a; i++)
+ free(d[i]);
+ free(d);
+}
+
+int main(int argc, char* argv[]) {
+ if (argc != 3) {
+ fputs("Usage: ch-2 s1 s2", stderr);
+ return EXIT_FAILURE;
+ }
+
+ wag_fis_dist(argv[1], argv[2]);
+}
diff --git a/challenge-096/paulo-custodio/cpp/ch-1.cpp b/challenge-096/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..34f4d79c73
--- /dev/null
+++ b/challenge-096/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,42 @@
+/*
+Challenge 096
+
+TASK #1 › Reverse Words
+Submitted by: Mohammad S Anwar
+You are given a string $S.
+
+Write a script to reverse the order of words in the given string. The string
+may contain leading/trailing spaces. The string may have more than one space
+between words in the string. Print the result without leading/trailing spaces
+and there should be only one space between words.
+
+Example 1:
+Input: $S = "The Weekly Challenge"
+Output: "Challenge Weekly The"
+*/
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <sstream>
+
+int main(int argc, char* argv[]) {
+ // concatenate all args
+ std::string text;
+ for (int i = 1; i < argc; i++) {
+ text += argv[i];
+ text += " ";
+ }
+
+ // build list of words
+ std::vector<std::string> words;
+ std::istringstream iss(text);
+ std::string word;
+ while (iss >> word)
+ words.push_back(word);
+
+ // print words in reverse order
+ for (auto it = words.rbegin(); it != words.rend(); ++it)
+ std::cout << *it << " ";
+ std::cout << std::endl;
+}
diff --git a/challenge-096/paulo-custodio/cpp/ch-2.cpp b/challenge-096/paulo-custodio/cpp/ch-2.cpp
new file mode 100644
index 0000000000..4e545c85a5
--- /dev/null
+++ b/challenge-096/paulo-custodio/cpp/ch-2.cpp
@@ -0,0 +1,150 @@
+/*
+Challenge 096
+
+TASK #2 › Edit Distance
+Submitted by: Mohammad S Anwar
+You are given two strings $S1 and $S2.
+
+Write a script to find out the minimum operations required to convert $S1
+into $S2. The operations can be insert, remove or replace a character. Please
+check out Wikipedia page for more information.
+
+Example 1:
+Input: $S1 = "kitten"; $S2 = "sitting"
+Output: 3
+
+Operation 1: replace 'k' with 's'
+Operation 2: replace 'e' with 'i'
+Operation 3: insert 'g' at the end
+Example 2:
+Input: $S1 = "sunday"; $S2 = "monday"
+Output: 2
+
+Operation 1: replace 's' with 'm'
+Operation 2: replace 'u' with 'o'
+
+NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+ from which the operations can be deduced
+*/
+
+#include <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+#include <cassert>
+#include <climits>
+
+int min3(int a, int b, int c) {
+ return std::min(a, std::min(b, c));
+}
+
+enum class Dir { None, E, S, SE };
+
+void wag_fis_dist(const std::string& a, const std::string& b) {
+ size_t len_a = a.size();
+ size_t len_b = b.size();
+
+ // define a table where d[i][j] is the Levenshtein distance between
+ // first i chars of a and first j chars of b
+ std::vector<std::vector<int>> d;
+ d.resize(len_a+1);
+ for (size_t i = 0; i <= len_a; i++) {
+ d[i].resize(len_b+1);
+ }
+
+ // source prefixes can be transformed into empty string by dropping chars
+ for (size_t i = 1; i <= len_a; i++)
+ d[i][0] = i;
+
+ // target prefixes can be reached from empty source prefix by inserting chars
+ for (size_t j = 1; j <= len_b; j++)
+ d[0][j] = j;
+
+ // flood-fill the rest of the table
+ for (size_t j = 1; j <= len_b; j++) {
+ for (size_t i = 1; i <= len_a; i++) {
+ int subst_cost = (a[i-1] == b[j-1]) ? 0 : 1;
+ d[i][j] = min3(d[i-1][j]+1, // deletion
+ d[i][j-1]+1, // insertion
+ d[i-1][j-1]+subst_cost); // substitution
+ }
+ }
+
+ // distance is in lower bottom cell
+ std::cout << d[len_a][len_b] << std::endl;
+
+ // traverse the minimum path
+ size_t i = 0, j = 0, step = 0;
+ while (i < len_a || j < len_b) {
+ Dir min_dir = Dir::None, dir;
+ int min_delta = INT_MAX, delta;
+
+ // search shortest path in priority SE, E, S
+ if (i < len_a && j < len_b) {
+ dir = Dir::SE;
+ delta = d[i+1][j+1] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ if (j < len_b) {
+ dir = Dir::E;
+ delta = d[i][j+1] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ if (i < len_a) {
+ dir = Dir::S;
+ delta = d[i+1][j] - d[i][j];
+ if (delta < min_delta) {
+ min_dir = dir;
+ min_delta = delta;
+ }
+ }
+
+ // apply shortest path and show steps
+ switch (min_dir) {
+ case Dir::SE:
+ i++; j++;
+ if (a[i-1] != b[j-1]) {
+ std::cout << "Operation " << ++step << ": replace '"
+ << a[i-1] << "' with '" << b[j-1] << "'" << std::endl;
+ }
+ break;
+ case Dir::E:
+ j++;
+ if (j == len_b)
+ std::cout << "Operation " << ++step << ": insert '"
+ << b[j-1] << "' at end" << std::endl;
+ else
+ std::cout << "Operation " << ++step << ": insert '"
+ << b[j-1] << "' at position " << j << std::endl;
+ break;
+ case Dir::S:
+ i++;
+ if (i == len_a)
+ std::cout << "Operation " << ++step << ": delete '"
+ << a[i-1] << "' at end" << std::endl;
+ else
+ std::cout << "Operation " << ++step << ": delete '"
+ << a[i-1] << "' at position " << i << std::endl;
+ break;
+ default:
+ assert(0);
+ }
+ }
+}
+
+int main(int argc, char* argv[]) {
+ if (argc != 3) {
+ std::cerr << "Usage: ch-2 s1 s2" << std::endl;
+ return EXIT_FAILURE;
+ }
+
+ wag_fis_dist(argv[1], argv[2]);
+}
diff --git a/challenge-096/paulo-custodio/forth/ch-1.fs b/challenge-096/paulo-custodio/forth/ch-1.fs
new file mode 100644
index 0000000000..d325b88fed
--- /dev/null
+++ b/challenge-096/paulo-custodio/forth/ch-1.fs
@@ -0,0 +1,81 @@
+#! /usr/bin/env gforth
+
+\ Challenge 096
+\
+\ TASK #1 > Reverse Words
+\ Submitted by: Mohammad S Anwar
+\ You are given a string $S.
+\
+\ Write a script to reverse the order of words in the given string. The string
+\ may contain leading/trailing spaces. The string may have more than one space
+\ between words in the string. Print the result without leading/trailing spaces
+\ and there should be only one space between words.
+\
+\ Example 1:
+\ Input: $S = "The Weekly Challenge"
+\ Output: "Challenge Weekly The"
+
+\ trim spaces from start of string
+: trim_start ( addr len -- addr len )
+ BEGIN
+ DUP 0= IF EXIT THEN \ exit if lenth is zero
+ OVER C@ BL = IF \ if starts with space
+ 1 /STRING \ remove first char
+ ELSE
+ EXIT \ no more spaces
+ THEN
+ AGAIN ;
+
+\ trim spaces from start and end of string
+: trim ( addr len -- addr len )
+ trim_start -TRAILING ;
+
+
+\ clear counted string at PAD
+: clear_pad ( -- )
+ 0 PAD C! ;
+
+\ concatenate string to PAD, output as counted string
+: append_pad ( addr len -- )
+ PAD COUNT + ( src len dest ) \ get address of char after string
+ 2DUP + >R ( R: end of joined string )
+ SWAP CMOVE \ copy string
+ R> PAD 1+ - PAD C! ; \ store new length
+
+\ concatenate args from command line to one string in PAD
+: join_args ( -- )
+ clear_pad
+ BEGIN NEXT-ARG DUP 0> WHILE \ while input argument
+ trim append_pad \ trim argument and cat
+ s" " append_pad \ cat one space
+ REPEAT 2DROP
+ PAD COUNT -TRAILING SWAP 1- C! ; \ remove ending spaces
+
+\ split a string by blanks
+\ stores result in dictionary and reclaims memory
+: split ( addr len -- tokens count )
+ HERE >R \ save dictionary pointer
+ BEGIN
+ trim \ trim start and end spaces
+ 2DUP 2, \ save rest of string; length will be
+ \ adjusted later
+ s" " SEARCH ( addr-space len-rest f-found )
+ WHILE \ while found space
+ DUP NEGATE HERE 2 CELLS - +! \ adjust last token length
+ REPEAT 2DROP \ drop string
+ R> HERE OVER - ( addr-tokens size-bytes )
+ DUP NEGATE ALLOT \ reclaim dictionary
+ 2 CELLS / ; ( tokens count )
+
+\ print the reversed list of tokens
+: .tokens ( tokens count -- )
+ SWAP OVER 2 CELLS * + SWAP ( addr-end count )
+ 0 ?DO \ for each token
+ 2 CELLS -
+ DUP 2@ TYPE SPACE
+ LOOP DROP ;
+
+join_args \ join arguments to PAD
+PAD COUNT split \ split by spaces
+.tokens CR \ print in reverse order
+BYE
diff --git a/challenge-096/paulo-custodio/forth/ch-2.fs b/challenge-096/paulo-custodio/forth/ch-2.fs
new file mode 100644
index 0000000000..1ecbbf62c3
--- /dev/null
+++ b/challenge-096/paulo-custodio/forth/ch-2.fs
@@ -0,0 +1,153 @@
+#! /usr/bin/env gforth
+
+\ Challenge 096
+\
+\ TASK #2 > Edit Distance
+\ Submitted by: Mohammad S Anwar
+\ You are given two strings $S1 and $S2.
+\
+\ Write a script to find out the minimum operations required to convert $S1
+\ into $S2. The operations can be insert, remove or replace a character. Please
+\ check out Wikipedia page for more information.
+\
+\ Example 1:
+\ Input: $S1 = "kitten"; $S2 = "sitting"
+\ Output: 3
+\
+\ Operation 1: replace 'k' with 's'
+\ Operation 2: replace 'e' with 'i'
+\ Operation 3: insert 'g' at the end
+\ Example 2:
+\ Input: $S1 = "sunday"; $S2 = "monday"
+\ Output: 2
+\
+\ Operation 1: replace 's' with 'm'
+\ Operation 2: replace 'u' with 'o'
+\
+\ NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+\ from which the operations can be deduced
+
+
+\ collect arguments - strings a and b
+NEXT-ARG CONSTANT len_a CONSTANT a
+NEXT-ARG CONSTANT len_b CONSTANT b
+
+\ get string char by index (1..N)
+: a[]@ ( index -- char )
+ a + 1- C@ ;
+
+: b[]@ ( index -- char )
+ b + 1- C@ ;
+
+\ build array len_a+1 rows, len_b+1 cols
+CREATE d
+len_a 1+ len_b 1+ * CELLS ALLOT
+
+\ index array
+: d[] ( i j -- addr )
+ SWAP len_b 1+ * + CELLS
+ d + ;
+
+\ init array to zeros
+: clear_d ( -- )
+ len_a 1+ 0 ?DO
+ len_b 1+ 0 ?DO
+ 0 J I d[] !
+ LOOP
+ LOOP ;
+
+\ init source column
+: init_source ( -- )
+ len_a 1+ 1 ?DO
+ i i 0 d[] !
+ LOOP ;
+
+\ init target row
+: init_target ( -- )
+ len_b 1+ 1 ?DO
+ i 0 i d[] !
+ LOOP ;
+
+\ flood-fill table
+: flood_fill ( -- )
+ len_b 1+ 1 ?DO
+ len_a 1+ 1 ?DO
+ i 1- j d[] @ 1+ \ deletion
+ i j 1- d[] @ 1+ \ insertion
+ i 1- j 1- d[] @ \ substitution
+ i a[]@ j b[]@ <> IF 1+ THEN
+ MIN MIN
+ i j d[] !
+ LOOP
+ LOOP ;
+
+\ output number without space
+: .num ( n -- )
+ 0 U.R ;
+
+\ output step
+0 VALUE step
+: show_operation ( -- )
+ step 1+ TO step
+ ." Operation " step .num ." : " ;
+
+\ traverse minimum path
+: traverse_path ( -- )
+ 0 0 { i j } \ starting point
+ BEGIN i len_a < j len_b < OR WHILE
+ 0 { min_dir } len_a len_b + { min_delta }
+ 0 { dir } 0 { delta }
+
+ \ search shortest path in priority SE (D), E, S
+ i len_a < j len_b < AND IF
+ 'D' TO dir
+ i 1+ j 1+ d[] @ i j d[] @ - TO delta
+ delta min_delta < IF
+ dir TO min_dir
+ delta TO min_delta
+ THEN
+ THEN
+
+ j len_b < IF
+ 'E' TO dir
+ i j 1+ d[] @ i j d[] @ - TO delta
+ delta min_delta < IF
+ dir TO min_dir
+ delta TO min_delta
+ THEN
+ THEN
+
+ i len_a < IF
+ 'S' TO dir
+ i 1+ j d[] @ i j d[] @ - TO delta
+ delta min_delta < IF
+ dir TO min_dir
+ delta TO min_delta
+ THEN
+ THEN
+
+ \ apply shortest path and show steps
+ min_dir 'D' = IF
+ i 1+ TO i
+ j 1+ TO j
+ i a[]@ j b[]@ <> IF
+ show_operation ." replace '" i a[]@ EMIT ." ' with '" j b[]@ EMIT ." '" CR
+ THEN
+ ELSE min_dir 'E' = IF
+ j 1+ TO j
+ show_operation ." insert '" j b[]@ EMIT ." ' at "
+ j len_b = IF ." end" ELSE ." position " j .num THEN CR
+ ELSE min_dir 'S' = IF
+ i 1+ TO i
+ show_operation ." delete '" i a[]@ EMIT ." ' at "
+ j len_b = IF ." end" ELSE ." position " i .num THEN CR
+ THEN THEN THEN
+ REPEAT ;
+
+: wag_fis_dist ( -- )
+ clear_d init_source init_target flood_fill
+ len_a len_b d[] @ . CR \ show distance
+ traverse_path ;
+
+wag_fis_dist
+BYE
diff --git a/challenge-096/paulo-custodio/perl/ch-1.pl b/challenge-096/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..dac87ee172
--- /dev/null
+++ b/challenge-096/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,22 @@
+#!/usr/bin/env perl
+
+# Challenge 096
+#
+# TASK #1 › Reverse Words
+# Submitted by: Mohammad S Anwar
+# You are given a string $S.
+#
+# Write a script to reverse the order of words in the given string. The string
+# may contain leading/trailing spaces. The string may have more than one space
+# between words in the string. Print the result without leading/trailing spaces
+# and there should be only one space between words.
+#
+# Example 1:
+# Input: $S = "The Weekly Challenge"
+# Output: "Challenge Weekly The"
+
+use strict;
+use warnings;
+use 5.030;
+
+say join ' ', reverse split ' ', "@ARGV";
diff --git a/challenge-096/paulo-custodio/perl/ch-2.pl b/challenge-096/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..577366f8f3
--- /dev/null
+++ b/challenge-096/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,114 @@
+#!/usr/bin/env perl
+
+# Challenge 096
+#
+# TASK #2 › Edit Distance
+# Submitted by: Mohammad S Anwar
+# You are given two strings $S1 and $S2.
+#
+# Write a script to find out the minimum operations required to convert $S1
+# into $S2. The operations can be insert, remove or replace a character. Please
+# check out Wikipedia page for more information.
+#
+# Example 1:
+# Input: $S1 = "kitten"; $S2 = "sitting"
+# Output: 3
+#
+# Operation 1: replace 'k' with 's'
+# Operation 2: replace 'e' with 'i'
+# Operation 3: insert 'g' at the end
+# Example 2:
+# Input: $S1 = "sunday"; $S2 = "monday"
+# Output: 2
+#
+# Operation 1: replace 's' with 'm'
+# Operation 2: replace 'u' with 'o'
+
+# NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+# from which the operations can be deduced
+
+use strict;
+use warnings;
+use 5.030;
+use List::Util 'min';
+
+use Data::Dump 'dump';
+
+wag_fis_dist(@ARGV);
+
+sub wag_fis_dist {
+ my($a, $b) = @_;
+
+ # define a table where d[i,j] is the Levenshtein distance between
+ # first i chars of $a and first j chars of $b
+ my @d;
+ $d[0][0] = 0;
+
+ # source prefixes can be transformed into empty string by dropping chars
+ $d[$_][0] = $_ for (1 .. length($a));
+
+ # target prefixes can be reached from empty source prefix by inserting chars
+ $d[0][$_] = $_ for (1 .. length($b));
+
+ # flood-fill the rest of the table
+ for my $j (1 .. length($b)) {
+ for my $i (1 .. length($a)) {
+ my $subst_cost =
+ (substr($a,$i-1,1) eq substr($b,$j-1,1)) ? 0 : 1;
+ $d[$i][$j] = min($d[$i-1][$j]+1, # deletion
+ $d[$i][$j-1]+1, # insertion
+ $d[$i-1][$j-1]+$subst_cost); # substitution
+ }
+ }
+
+ # distance is in lower bottom cell
+ say $d[length($a)][length($b)];
+
+ # traverse the minimum path
+ my($i, $j, $step) = (0,0,0);
+ while ($i < length($a) || $j < length($b)) {
+ my($min_dir, $min_delta) = ('', 1e10);
+ my($dir, $delta);
+
+ # search shortest path in priority SE, E, S
+ if ($i < length($a) && $j < length($b)) {
+ ($dir, $delta) = ("SE", $d[$i+1][$j+1] - $d[$i][$j]);
+ ($min_dir, $min_delta) = ($dir, $delta) if $delta < $min_delta;
+ }
+
+ if ($j < length($b)) {
+ ($dir, $delta) = ("E", $d[$i][$j+1] - $d[$i][$j]);
+ ($min_dir, $min_delta) = ($dir, $delta) if $delta < $min_delta;
+ }
+
+ if ($i < length($a)) {
+ ($dir, $delta) = ("S", $d[$i+1][$j] - $d[$i][$j]);
+ ($min_dir, $min_delta) = ($dir, $delta) if $delta < $min_delta;
+ }
+
+ # apply shortest path and show steps
+ if ($min_dir eq "SE") {
+ ($i, $j) = ($i+1, $j+1);
+ my $from = substr($a,$i-1,1);
+ my $to = substr($b,$j-1,1);
+ if ($from ne $to) {
+ say "Operation ", ++$step, ": replace '$from' with '$to'";
+ }
+ }
+ elsif ($min_dir eq "E") {
+ ($i, $j) = ($i, $j+1);
+ my $add = substr($b,$j-1,1);
+ say "Operation ", ++$step, ": insert '$add' ",
+ ($j==length($b)) ? "at end" : "at position $j";
+ }
+ elsif ($min_dir eq "S") {
+ ($i, $j) = ($i+1, $j);
+ my $del = substr($a,$i-1,1);
+ say "Operation ", ++$step, ": delete '$del' ",
+ ($i==length($a)) ? "at end" : "at position $i";
+ }
+ else {
+ die $min_dir;
+ }
+ }
+}
diff --git a/challenge-096/paulo-custodio/perl/ch-2a.pl b/challenge-096/paulo-custodio/perl/ch-2a.pl
new file mode 100644
index 0000000000..9d253572aa
--- /dev/null
+++ b/challenge-096/paulo-custodio/perl/ch-2a.pl
@@ -0,0 +1,60 @@
+#!/usr/bin/env perl
+
+# Challenge 096
+#
+# TASK #2 › Edit Distance
+# Submitted by: Mohammad S Anwar
+# You are given two strings $S1 and $S2.
+#
+# Write a script to find out the minimum operations required to convert $S1
+# into $S2. The operations can be insert, remove or replace a character. Please
+# check out Wikipedia page for more information.
+#
+# Example 1:
+# Input: $S1 = "kitten"; $S2 = "sitting"
+# Output: 3
+#
+# Operation 1: replace 'k' with 's'
+# Operation 2: replace 'e' with 'i'
+# Operation 3: insert 'g' at the end
+# Example 2:
+# Input: $S1 = "sunday"; $S2 = "monday"
+# Output: 2
+#
+# Operation 1: replace 's' with 'm'
+# Operation 2: replace 'u' with 'o'
+
+# NOTE: the Levenshtein Distance algorithm only computes distance, does not output
+# the edit steps
+
+use strict;
+use warnings;
+use 5.030;
+use List::Util 'min';
+
+# avoid repeated recursive calls of lev_dist
+# for the Example 1 reduces from 29737 to 56 calls!
+use Memoize;
+memoize('lev_dist');
+
+say lev_dist(@ARGV);
+
+
+sub lev_dist {
+ my($a, $b) = @_;
+
+ if ($a eq '') {
+ return length($b);
+ }
+ elsif ($b eq '') {
+ return length($a);
+ }
+ else {
+ my $ch1_diff = substr($a,0,1) ne substr($b,0,1) ? 1 : 0;
+ return min(
+ lev_dist(substr($a, 1), $b)+1, # deletion
+ lev_dist($a, substr($b, 1))+1, # insertion
+ lev_dist(substr($a, 1), substr($b, 1))+$ch1_diff # substitution
+ );
+ }
+}
diff --git a/challenge-096/paulo-custodio/python/ch-1.py b/challenge-096/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..6702aaed4f
--- /dev/null
+++ b/