diff options
| author | Paulo Custodio <pauloscustodio@gmail.com> | 2021-01-25 20:07:40 +0000 |
|---|---|---|
| committer | Paulo Custodio <pauloscustodio@gmail.com> | 2021-01-26 00:06:54 +0000 |
| commit | 3fa58628535d4041c7cc648c005080ca88f18c18 (patch) | |
| tree | 336fe3cc14f518f05e871ab974cc86a09a2fd8f6 /challenge-096 | |
| parent | 3d3900a2f0f69c54a34683e4e1b5da007b4af9d9 (diff) | |
| download | perlweeklychallenge-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.bas | 73 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/basic/ch-2.bas | 198 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/c/ch-1.c | 72 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/c/ch-2.c | 230 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/cpp/ch-1.cpp | 42 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/cpp/ch-2.cpp | 212 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/forth/ch-1.fs | 108 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/forth/ch-2.fs | 198 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/perl/ch-1.pl | 10 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/perl/ch-2.pl | 160 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/perl/ch-2a.pl | 40 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/python/ch-1.py | 10 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/python/ch-2.py | 138 | ||||
| -rw-r--r-- | challenge-096/paulo-custodio/test.pl | 52 |
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) { |
