aboutsummaryrefslogtreecommitdiff
path: root/challenge-096
diff options
context:
space:
mode:
authorPaulo Custodio <pauloscustodio@gmail.com>2021-01-25 20:07:40 +0000
committerPaulo Custodio <pauloscustodio@gmail.com>2021-01-26 00:06:54 +0000
commit3fa58628535d4041c7cc648c005080ca88f18c18 (patch)
tree336fe3cc14f518f05e871ab974cc86a09a2fd8f6 /challenge-096
parent3d3900a2f0f69c54a34683e4e1b5da007b4af9d9 (diff)
downloadperlweeklychallenge-club-3fa58628535d4041c7cc648c005080ca88f18c18.tar.gz
perlweeklychallenge-club-3fa58628535d4041c7cc648c005080ca88f18c18.tar.bz2
perlweeklychallenge-club-3fa58628535d4041c7cc648c005080ca88f18c18.zip
Replace tabs by spaces so that indentation looks correct
Diffstat (limited to 'challenge-096')
-rw-r--r--challenge-096/paulo-custodio/basic/ch-1.bas73
-rw-r--r--challenge-096/paulo-custodio/basic/ch-2.bas198
-rw-r--r--challenge-096/paulo-custodio/c/ch-1.c72
-rw-r--r--challenge-096/paulo-custodio/c/ch-2.c230
-rw-r--r--challenge-096/paulo-custodio/cpp/ch-1.cpp42
-rw-r--r--challenge-096/paulo-custodio/cpp/ch-2.cpp212
-rw-r--r--challenge-096/paulo-custodio/forth/ch-1.fs108
-rw-r--r--challenge-096/paulo-custodio/forth/ch-2.fs198
-rw-r--r--challenge-096/paulo-custodio/perl/ch-1.pl10
-rw-r--r--challenge-096/paulo-custodio/perl/ch-2.pl160
-rw-r--r--challenge-096/paulo-custodio/perl/ch-2a.pl40
-rw-r--r--challenge-096/paulo-custodio/python/ch-1.py10
-rw-r--r--challenge-096/paulo-custodio/python/ch-2.py138
-rw-r--r--challenge-096/paulo-custodio/test.pl52
14 files changed, 771 insertions, 772 deletions
diff --git a/challenge-096/paulo-custodio/basic/ch-1.bas b/challenge-096/paulo-custodio/basic/ch-1.bas
index 4d3951e8db..5000abf57c 100644
--- a/challenge-096/paulo-custodio/basic/ch-1.bas
+++ b/challenge-096/paulo-custodio/basic/ch-1.bas
@@ -1,57 +1,56 @@
' 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
+'
+' 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)
+ 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
+ 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
+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
index b4eb1fa7b6..8d88019f32 100644
--- a/challenge-096/paulo-custodio/basic/ch-2.bas
+++ b/challenge-096/paulo-custodio/basic/ch-2.bas
@@ -1,137 +1,137 @@
' 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
+'
+' 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
+ 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))
+ 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
+ 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
- ' source prefixes can be transformed into empty string by dropping chars
- for i = 1 to len(a)
- d(i,0) = i
- next i
+ ' 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
- ' target prefixes can be reached from empty source prefix by inserting chars
- for j = 1 to len(b)
- d(0,j) = j
- next j
+ ' source prefixes can be transformed into empty string by dropping chars
+ for i = 1 to len(a)
+ d(i,0) = i
+ next i
- ' 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
+ ' target prefixes can be reached from empty source prefix by inserting chars
+ for j = 1 to len(b)
+ d(0,j) = j
+ 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
+ ' 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
- ' 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
+ ' 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
diff --git a/challenge-096/paulo-custodio/c/ch-1.c b/challenge-096/paulo-custodio/c/ch-1.c
index 93d55b1329..d2d57ff088 100644
--- a/challenge-096/paulo-custodio/c/ch-1.c
+++ b/challenge-096/paulo-custodio/c/ch-1.c
@@ -5,9 +5,9 @@ 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
+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:
@@ -20,40 +20,40 @@ Output: "Challenge Weekly The"
#include <string.h>
void* check_mem(void* p) {
- if (!p) {
- fputs("Out of memory", stderr);
- exit(EXIT_FAILURE);
- }
- return 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);
+ // 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
index 718bb6018d..e4dd334e60 100644
--- a/challenge-096/paulo-custodio/c/ch-2.c
+++ b/challenge-096/paulo-custodio/c/ch-2.c
@@ -23,8 +23,8 @@ 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
+NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+ from which the operations can be deduced
*/
#include <assert.h>
@@ -34,131 +34,131 @@ NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
#include <string.h>
void* check_mem(void* p) {
- if (!p) {
- fputs("Out of memory", stderr);
- exit(EXIT_FAILURE);
- }
- return p;
+ if (!p) {
+ fputs("Out of memory", stderr);
+ exit(EXIT_FAILURE);
+ }
+ return p;
}
int min(int a, int b) {
- return (a < b) ? a : b;
+ return (a < b) ? a : b;
}
int min3(int a, int b, int c) {
- return min(a, min(b, 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 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]);
+ 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
index 34f4d79c73..51beeb423f 100644
--- a/challenge-096/paulo-custodio/cpp/ch-1.cpp
+++ b/challenge-096/paulo-custodio/cpp/ch-1.cpp
@@ -5,9 +5,9 @@ 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
+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:
@@ -21,22 +21,22 @@ Output: "Challenge Weekly The"
#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;
+ // 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
index 4e545c85a5..4f4b5a1954 100644
--- a/challenge-096/paulo-custodio/cpp/ch-2.cpp
+++ b/challenge-096/paulo-custodio/cpp/ch-2.cpp
@@ -23,8 +23,8 @@ 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
+NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
+ from which the operations can be deduced
*/
#include <algorithm>
@@ -35,116 +35,116 @@ NOTE: the Wagner-Fischer Distance algorithm builds a table of distances
#include <climits>
int min3(int a, int b, int c) {
- return std::min(a, std::min(b, 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);
- }
- }
+ 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]);
+ if (argc != 3) {