From c402c40f216b437ab1aba13793d493eb25cbfd14 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Mon, 25 Jan 2021 20:07:40 +0000 Subject: Replace tabs by spaces so that indentation looks correct --- challenge-096/paulo-custodio/basic/ch-1.bas | 73 +++++---- challenge-096/paulo-custodio/basic/ch-2.bas | 198 ++++++++++++------------ challenge-096/paulo-custodio/c/ch-1.c | 72 ++++----- challenge-096/paulo-custodio/c/ch-2.c | 230 ++++++++++++++-------------- challenge-096/paulo-custodio/cpp/ch-1.cpp | 42 ++--- challenge-096/paulo-custodio/cpp/ch-2.cpp | 212 ++++++++++++------------- challenge-096/paulo-custodio/forth/ch-1.fs | 108 ++++++------- challenge-096/paulo-custodio/forth/ch-2.fs | 198 ++++++++++++------------ challenge-096/paulo-custodio/perl/ch-1.pl | 10 +- challenge-096/paulo-custodio/perl/ch-2.pl | 160 +++++++++---------- challenge-096/paulo-custodio/perl/ch-2a.pl | 40 ++--- challenge-096/paulo-custodio/python/ch-1.py | 10 +- challenge-096/paulo-custodio/python/ch-2.py | 138 ++++++++--------- challenge-096/paulo-custodio/test.pl | 52 +++---- 14 files changed, 771 insertions(+), 772 deletions(-) (limited to 'challenge-096') 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 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 @@ -34,131 +34,131 @@ NOTE: the Wagner-Fischer Distance algorithm builds a table of distances #include 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 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 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 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 @@ -35,116 +35,116 @@ NOTE: the Wagner-Fischer Distance algorithm builds a table of distances #include 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> 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> 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) { + 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 index d325b88fed..88f75e7542 100644 --- a/challenge-096/paulo-custodio/forth/ch-1.fs +++ b/challenge-096/paulo-custodio/forth/ch-1.fs @@ -5,77 +5,77 @@ \ 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" \ 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_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 ; +: trim ( addr len -- addr len ) + trim_start -TRAILING ; \ clear counted string at PAD -: clear_pad ( -- ) - 0 PAD C! ; +: 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 - +: 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 +: 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 ) - +: 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 ; +: .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 +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 index 1ecbbf62c3..85543ee453 100644 --- a/challenge-096/paulo-custodio/forth/ch-2.fs +++ b/challenge-096/paulo-custodio/forth/ch-2.fs @@ -5,27 +5,27 @@ \ 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 \ collect arguments - strings a and b @@ -33,121 +33,121 @@ 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@ ; +: a[]@ ( index -- char ) + a + 1- C@ ; -: b[]@ ( index -- char ) - b + 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 + ; +: 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 ; +: 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_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 ; +: 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 ; +: 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 ; +: .num ( n -- ) + 0 U.R ; \ output step 0 VALUE step -: show_operation ( -- ) - step 1+ TO step - ." Operation " step .num ." : " ; +: 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 ; +: 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 index 86015899e2..82ccb706d1 100644 --- a/challenge-096/paulo-custodio/perl/ch-1.pl +++ b/challenge-096/paulo-custodio/perl/ch-1.pl @@ -5,12 +5,12 @@ # 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" diff --git a/challenge-096/paulo-custodio/perl/ch-2.pl b/challenge-096/paulo-custodio/perl/ch-2.pl index 829d33c12d..5d1b0be743 100644 --- a/challenge-096/paulo-custodio/perl/ch-2.pl +++ b/challenge-096/paulo-custodio/perl/ch-2.pl @@ -5,27 +5,27 @@ # 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 use strict; use warnings; @@ -37,78 +37,78 @@ 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; - } - } + 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 index 13452e254d..fb0fe511fa 100644 --- a/challenge-096/paulo-custodio/perl/ch-2a.pl +++ b/challenge-096/paulo-custodio/perl/ch-2a.pl @@ -5,22 +5,22 @@ # 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' @@ -41,20 +41,20 @@ 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 - ); - } + 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 index 6702aaed4f..704a9e3c57 100644 --- a/challenge-096/paulo-custodio/python/ch-1.py +++ b/challenge-096/paulo-custodio/python/ch-1.py @@ -5,12 +5,12 @@ # 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" diff --git a/challenge-096/paulo-custodio/python/ch-2.py b/challenge-096/paulo-custodio/python/ch-2.py index 20d75882e1..b949c7765a 100644 --- a/challenge-096/paulo-custodio/python/ch-2.py +++ b/challenge-096/paulo-custodio/python/ch-2.py @@ -5,97 +5,97 @@ # 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 import sys def wag_fis_dist(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 - d = [ [ 0 for j in range(0, len(b)+1) ] for i in range(0, len(a)+1) ] - - # source prefixes can be transformed into empty string by dropping chars - for i in range(1, len(a)+1): - d[i][0] = i + # define a table where d[i,j] is the Levenshtein distance between + # first i chars of a and first j chars of b + d = [ [ 0 for j in range(0, len(b)+1) ] for i in range(0, len(a)+1) ] + + # source prefixes can be transformed into empty string by dropping chars + for i in range(1, len(a)+1): + d[i][0] = i + + # target prefixes can be reached from empty source prefix by inserting chars + for j in range(1, len(b)+1): + d[0][j] = j + + # flood-fill the rest of the table + for j in range(1, len(b)+1): + for i in range(1, len(a)+1): + subst_cost = 0 if a[i-1] == b[j-1] else 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 + print(d[len(a)][len(b)]) + + # traverse the minimum path + i, j, step = 0, 0, 0 + while i < len(a) or j < len(b): + min_dir, min_delta = '', 1e10 + + # search shortest path in priority SE, E, S + if i < len(a) and j < len(b): + dir, delta = "SE", d[i+1][j+1] - d[i][j] + if delta < min_delta: + min_dir, min_delta = dir, delta + + if j < len(b): + dir, delta = "E", d[i][j+1] - d[i][j] + if delta < min_delta: + min_dir, min_delta = dir, delta - # target prefixes can be reached from empty source prefix by inserting chars - for j in range(1, len(b)+1): - d[0][j] = j - - # flood-fill the rest of the table - for j in range(1, len(b)+1): - for i in range(1, len(a)+1): - subst_cost = 0 if a[i-1] == b[j-1] else 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 + if i < len(a): + dir, delta = "S", d[i+1][j] - d[i][j] + if delta < min_delta: + min_dir, min_delta = dir, delta - # distance is in lower bottom cell - print(d[len(a)][len(b)]) - - # traverse the minimum path - i, j, step = 0, 0, 0 - while i < len(a) or j < len(b): - min_dir, min_delta = '', 1e10 - - # search shortest path in priority SE, E, S - if i < len(a) and j < len(b): - dir, delta = "SE", d[i+1][j+1] - d[i][j] - if delta < min_delta: - min_dir, min_delta = dir, delta - - if j < len(b): - dir, delta = "E", d[i][j+1] - d[i][j] - if delta < min_delta: - min_dir, min_delta = dir, delta - - if i < len(a): - dir, delta = "S", d[i+1][j] - d[i][j] - if delta < min_delta: - min_dir, min_delta = dir, delta - - # apply shortest path and show steps - if min_dir == "SE": - i, j = i+1, j+1 - frm, to = a[i-1], b[j-1] - if frm != to: - step += 1 - print(f"Operation {step}: replace '{frm}' with '{to}'") - elif min_dir == "E": - i, j = i, j+1 - add = b[j-1] - step += 1 - at = "at end" if j == len(b) else f"at position {j}" - print(f"Operation {step}: insert '{add}' {at}") - elif min_dir == "S": - i, j = i+1, j - dl = a[i-1] - step += 1 - at = "at end" if i == len(a) else f"at position {i}" - print(f"Operation {step}: delete '{dl}' {at}") - else: - assert 0 + # apply shortest path and show steps + if min_dir == "SE": + i, j = i+1, j+1 + frm, to = a[i-1], b[j-1] + if frm != to: + step += 1 + print(f"Operation {step}: replace '{frm}' with '{to}'") + elif min_dir == "E": + i, j = i, j+1 + add = b[j-1] + step += 1 + at = "at end" if j == len(b) else f"at position {j}" + print(f"Operation {step}: insert '{add}' {at}") + elif min_dir == "S": + i, j = i+1, j + dl = a[i-1] + step += 1 + at = "at end" if i == len(a) else f"at position {i}" + print(f"Operation {step}: delete '{dl}' {at}") + else: + assert 0 a, b = tuple(sys.argv[1:3]) wag_fis_dist(a, b) diff --git a/challenge-096/paulo-custodio/test.pl b/challenge-096/paulo-custodio/test.pl index 3848a26842..3e029bbb01 100644 --- a/challenge-096/paulo-custodio/test.pl +++ b/challenge-096/paulo-custodio/test.pl @@ -10,21 +10,21 @@ compile( "g++ cpp/ch-1.cpp -o cpp/ch-1"); compile( "fbc basic/ch-1.bas -o basic/ch-1"); for (["The Weekly Challenge" => "Challenge Weekly The"], - ["' Perl and Raku are part of the same family '" => - "family same the of part are Raku and Perl"]) { - my($in, $out) = @$_; - - is capture( "perl perl/ch-1.pl $in"), "$out\n"; - is capture("python python/ch-1.py $in"), "$out\n"; - is capture( "gforth forth/ch-1.fs $in"), "$out\n"; - is capture( "c/ch-1 $in"), "$out\n"; - is capture( "cpp/ch-1 $in"), "$out\n"; - is capture( "basic/ch-1 $in"), "$out\n"; + ["' Perl and Raku are part of the same family '" => + "family same the of part are Raku and Perl"]) { + my($in, $out) = @$_; + + is capture( "perl perl/ch-1.pl $in"), "$out\n"; + is capture("python python/ch-1.py $in"), "$out\n"; + is capture( "gforth forth/ch-1.fs $in"), "$out\n"; + is capture( "c/ch-1 $in"), "$out\n"; + is capture( "cpp/ch-1 $in"), "$out\n"; + is capture( "basic/ch-1 $in"), "$out\n"; } -is capture("perl perl/ch-2a.pl kitten sitting"), "3\n"; -is capture("perl perl/ch-2a.pl sunday monday"), "2\n"; +is capture("perl perl/ch-2a.pl kitten sitting"), "3\n"; +is capture("perl perl/ch-2a.pl sunday monday"), "2\n"; compile("gcc c/ch-2.c -o c/ch-2"); compile("g++ cpp/ch-2.cpp -o cpp/ch-2"); @@ -41,27 +41,27 @@ END Operation 1: replace 's' with 'm' Operation 2: replace 'u' with 'o' END - my($in, $out) = @$_; - - is capture( "perl perl/ch-2.pl $in"), $out; - is capture("python python/ch-2.py $in"), $out; - is capture( "gforth forth/ch-2.fs $in"), $out; - is capture( "c/ch-2 $in"), $out; - is capture( "cpp/ch-2 $in"), $out; - is capture( "basic/ch-2 $in"), $out; + my($in, $out) = @$_; + + is capture( "perl perl/ch-2.pl $in"), $out; + is capture("python python/ch-2.py $in"), $out; + is capture( "gforth forth/ch-2.fs $in"), $out; + is capture( "c/ch-2 $in"), $out; + is capture( "cpp/ch-2 $in"), $out; + is capture( "basic/ch-2 $in"), $out; } done_testing; sub capture { - my($cmd) = @_; - my $out = `$cmd`; - $out =~ s/[ \r\t]*\n/\n/g; - return $out; + my($cmd) = @_; + my $out = `$cmd`; + $out =~ s/[ \r\t]*\n/\n/g; + return $out; } sub compile { - my($cmd) = @_; - ok 0==system($cmd), $cmd; + my($cmd) = @_; + ok 0==system($cmd), $cmd; } -- cgit From 5cf0f14f20bc569c1336bd578805bf9f7e3a5654 Mon Sep 17 00:00:00 2001 From: Paulo Custodio Date: Tue, 26 Jan 2021 00:40:22 +0000 Subject: Add Lua solution to 096 --- challenge-096/paulo-custodio/lua/ch-1.lua | 30 ++++++++ challenge-096/paulo-custodio/lua/ch-2.lua | 116 ++++++++++++++++++++++++++++++ challenge-096/paulo-custodio/test.pl | 72 ++++++++++--------- 3 files changed, 184 insertions(+), 34 deletions(-) create mode 100644 challenge-096/paulo-custodio/lua/ch-1.lua create mode 100644 challenge-096/paulo-custodio/lua/ch-2.lua (limited to 'challenge-096') diff --git a/challenge-096/paulo-custodio/lua/ch-1.lua b/challenge-096/paulo-custodio/lua/ch-1.lua new file mode 100644 index 0000000000..a278af7a23 --- /dev/null +++ b/challenge-096/paulo-custodio/lua/ch-1.lua @@ -0,0 +1,30 @@ +#!/usr/bin/env lua + +--[[ +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" +--]] + +-- concatenate all words (to be able to split multiple spaces) +text = "" +for i=1,#arg do text = text..arg[i].." "; end + +-- spit by spaces, store in reverse order +words = {} +for word in string.gmatch(text, "([^%s]+)") do + table.insert(words, 1, word) +end + +io.write(table.concat(words, " "), "\n") diff --git a/challenge-096/paulo-custodio/lua/ch-2.lua b/challenge-096/paulo-custodio/lua/ch-2.lua new file mode 100644 index 0000000000..7a3d59a8f9 --- /dev/null +++ b/challenge-096/paulo-custodio/lua/ch-2.lua @@ -0,0 +1,116 @@ +#!/usr/bin/env lua + +--[[ +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 +--]] + +function wag_fis_dist(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 + local d = {} + + -- source prefixes can be transformed into empty string by dropping chars + for i=0,#a do + d[i] = {} + d[i][0] = i + end + + -- target prefixes can be reached from empty source prefix by inserting chars + for j=0,#b do + d[0][j] = j + end + + -- flood-fill the rest of the table + for j=1,#b do + for i=1,#a do + local subst_cost = 0 + if string.sub(a,i,i) ~= string.sub(b,j,j) then subst_cost = 1; end + d[i][j] = math.min(d[i-1][j]+1, -- deletion + d[i][j-1]+1, -- insertion + d[i-1][j-1]+subst_cost) -- substitution + end + end + + -- distance is in lower bottom cell + io.write(d[#a][#b], "\n") + + -- traverse the minimum path + local i, j, step = 0, 0, 0 + while i < #a or j < #b do + local dir, delta, min_dir, min_delta = 0,0,0,#a+#b + + -- search shortest path in priority SE, E, S + if i < #a and j < #b then + dir, delta = 'SE', d[i+1][j+1] - d[i][j] + if delta < min_delta then min_dir, min_delta = dir, delta; end + end + if j < #b then + dir, delta = 'E', d[i][j+1] - d[i][j] + if delta < min_delta then min_dir, min_delta = dir, delta; end + end + if i < #a then + dir, delta = 'S', d[i+1][j] - d[i][j] + if delta < min_delta then min_dir, min_delta = dir, delta; end + end + + -- apply shortest path and show steps + if min_dir == 'SE' then + i, j = i+1, j+1 + if string.sub(a,i,i) ~= string.sub(b,j,j) then + step = step+1 + io.write("Operation ", step, ": replace '", + string.sub(a,i,i), "' with '", + string.sub(b,j,j), "'\n") + end + elseif min_dir == 'E' then + j = j+1 + step = step+1 + if j == #b then + io.write("Operation ", step, ": insert '", + string.sub(b,j,j), "' at end\n") + else + io.write("Operation ", step, ": insert '", + string.sub(b,j,j), "' at position ", j, "\n") + end + elseif min_dir == 'S' then + i = i+1 + step = step+1 + if i == #a then + io.write("Operation ", step, ": insert '", + string.sub(a,i,i), "' at end\n") + else + io.write("Operation ", step, ": insert '", + string.sub(a,i,i), "' at position ", i, "\n") + end + else + assert(false, "invalid direction") + end + end +end + +wag_fis_dist(arg[1], arg[2]) diff --git a/challenge-096/paulo-custodio/test.pl b/challenge-096/paulo-custodio/test.pl index 3848a26842..5205bccf3c 100644 --- a/challenge-096/paulo-custodio/test.pl +++ b/challenge-0