diff options
25 files changed, 594 insertions, 31 deletions
diff --git a/challenge-096/abigail/README.md b/challenge-096/abigail/README.md index a82f466a38..d715618651 100644 --- a/challenge-096/abigail/README.md +++ b/challenge-096/abigail/README.md @@ -1,62 +1,71 @@ # Solution by Abigail -## [Task 1](https://perlweeklychallenge.org/blog/perl-weekly-challenge-095/#TASK1): +## [Reverse Words](https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/#TASK1) -You are given a number `$N`. +You are given a string `$S`. -Write a script to figure out if the given number is Palindrome. -Print `1` if true otherwise `0`. +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. ### Examples ~~~~ -Input: 1221 -Output: 1 +Input: $S = "The Weekly Challenge" +Output: "Challenge Weekly The" -Input: -101 -Output: 0, since -101 and 101- are not the same. - -Input: 90 -Output: 0 +Input: $S = " Perl and Raku are part of the same family " +Output: "family same the of part are Raku and Perl" ~~~~ ### Solutions -* [awk](awk/ch-1.c) +* [AWK](awk/ch-1.awk) +* [bash](sh/ch-1.sh) * [C](c/ch-1.c) -* [Node](node/ch-1.js) +* [lua](lua/ch-1.lua) +* [Node.js](node/ch-1.js) * [Perl](perl/ch-1.pl) * [Python](python/ch-1.py) +* [Ruby](ruby/ch-1.rb) ### Blog -[Perl Weekly Challenge 95, Part 1](https://wp.me/pcxd30-kq) -## [Task 2](https://perlweeklychallenge.org/blog/perl-weekly-challenge-095/#TASK2) +## [Edit Distance](https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/#TASK2) -Write a script to demonstrate `Stack` operations like below: +You are given two strings `$S1` and `$S2`. -* `push($n)` - add $n to the stack -* `pop()` - remove the top element -* `top()` - get the top element -* `min()` - return the minimum element +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](https://en.wikipedia.org/wiki/Edit_distance) for more information. ### Example ~~~~ -my $stack = Stack->new; -$stack->push(2); -$stack->push(-1); -$stack->push(0); -$stack->pop; # removes 0 -print $stack->top; # prints -1 -$stack->push(0); -print $stack->min; # prints -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 +~~~~ + +~~~~ +Input: $S1 = "sunday"; $S2 = "monday" +Output: 2 + +Operation 1: replace 's' with 'm' +Operation 2: replace 'u' with 'o' ~~~~ ### Solutions -* [awk](awk/ch-2.awk) +* [AWK](awk/ch-2.awk) * [C](c/ch-2.c) -* [Node](node/ch-2.js) +* [lua](lua/ch-2.lua) +* [Node.js](node/ch-2.js) * [Perl](perl/ch-2.pl) * [Python](python/ch-2.py) +* [Ruby](ruby/ch-2.rb) ### Blog -[Perl Weekly Challenge 95, Part 2](https://wp.me/pcxd30-ld) diff --git a/challenge-096/abigail/awk/ch-1.awk b/challenge-096/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..744c154648 --- /dev/null +++ b/challenge-096/abigail/awk/ch-1.awk @@ -0,0 +1,10 @@ +# +# AWK splits lines on whitespace, making each field available +# in $1, $2, ..., etc. So, we just print the fields in reverse, +# followed by a space (or a newline after the last/first). +# +{ + for (i = NF; i; i --) { + printf "%s%s", $i, (i == 1 ? "\n" : " "); + } +} diff --git a/challenge-096/abigail/awk/ch-2.awk b/challenge-096/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..08cebccb4e --- /dev/null +++ b/challenge-096/abigail/awk/ch-2.awk @@ -0,0 +1,26 @@ +# +# Return the minimum of 3 values +# +function min (a, b, c) { + return a < b ? a < c ? a : c\ + : b < c ? b : c +} + +# +# This is an implementation of the Wagner Fischer algorithm, which +# calculates the Levenshtein distance. +# +# See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm +# +{ + for (i = 0; i <= length ($1); i ++) { + for (j = 0; j <= length ($2); j ++) { + distance [i, j] = i == 0 || j == 0 ? i + j\ + : min(distance [i - 1, j] + 1, + distance [i, j - 1] + 1, + distance [i - 1, j - 1] +\ + (substr ($1, i, 1) == substr ($2, j, 1) ? 0 : 1)) + } + } + print distance [length ($1), length ($2)] +} diff --git a/challenge-096/abigail/bash/ch-1.sh b/challenge-096/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..9122fae4e0 --- /dev/null +++ b/challenge-096/abigail/bash/ch-1.sh @@ -0,0 +1,21 @@ +# +# Read in a line from STDIN, split it on whitespace, +# put the result into an array 'words' +# +while read -a words +do + # + # Iterate over the words backwards, and print them. + # + for ((i = ${#words[@]} - 1; i >= 0; i --)); + do printf "%s" ${words[$i]} + # + # Print a newline after the final word; otherwise, + # print a space. + # + if (($i == 0)) + then printf "\n" + else printf " " + fi + done +done diff --git a/challenge-096/abigail/c/ch-1.c b/challenge-096/abigail/c/ch-1.c new file mode 100644 index 0000000000..22ebafd404 --- /dev/null +++ b/challenge-096/abigail/c/ch-1.c @@ -0,0 +1,66 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <ctype.h> + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t strlen; + + while ((strlen = getline (&line, &len, stdin)) != -1) { + char * line_ptr = line; + size_t end = strlen; + size_t begin; + size_t output = 0; + while (end > 0) { + /* + * Skip tailing whitespace + */ + while (end > 0 && isspace (line [end - 1])) { + end --; + } + + /* + * 'end' now just after the end of a word, or + * at the beginning of the string; if the latter, + * there is nothing left to print. + */ + + if (end <= 0) { + break; + } + + /* + * Find the beginning of a word + */ + begin = end - 1; + while (begin > 0 && !isspace (line [begin - 1])) { + begin --; + } + + /* + * Extract the word out of the string: allocate memory, + * and copy the right part of the input. + */ + char * word; + if ((word = malloc ((end - begin + 1) * sizeof (char))) == NULL) { + fprintf (stderr, "Out of memory\n"); + exit (1); + } + stpncpy (word, line + begin, end - begin); + + /* + * Print the string, prepended (except the first printed word) + * by a space. + */ + printf ("%s%s", output ++ ? " " : "", word); + + end = begin; + } + printf ("\n"); + } + free (line); + + return (0); +} diff --git a/challenge-096/abigail/c/ch-2.c b/challenge-096/abigail/c/ch-2.c new file mode 100644 index 0000000000..73f35b1c0a --- /dev/null +++ b/challenge-096/abigail/c/ch-2.c @@ -0,0 +1,128 @@ +# include <stdlib.h> +# include <stdio.h> +# include <string.h> +# include <ctype.h> + +/* + * Return the minimum of three size_t values. + */ +size_t min3 (size_t a, size_t b, size_t c) { + return a < b ? a < c ? a : c + : b < c ? b : c; +} + +/* + * This is an implementation of the Wagner Fischer algorithm, which + * calculates the Levenshtein distance. + * + * See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm + */ +size_t LevenshteinDistance (char * first, size_t n, + char * second, size_t m) { + + /* + * If 'first' is the shorter string, swap the two strings. + * This reduces the memory usage. + */ + if (n < m) { + char * tmp = first; + size_t t = n; + first = second; + second = tmp; + n = m; + m = t; + } + + size_t ** distance; + if ((distance = malloc ((n + 1) * sizeof (size_t *))) == NULL) { + fprintf (stderr, "Out of memory\n"); + exit (1); + } + for (size_t i = 0; i <= n; i ++) { + if ((distance [i] = malloc ((m + 1) * sizeof (size_t))) == NULL) { + fprintf (stderr, "Out of memory\n"); + exit (1); + } + for (size_t j = 0; j <= m; j ++) { + distance [i] [j] = i == 0 || j == 0 ? i + j + : min3 (distance [i - 1] [j] + 1, + distance [i] [j - 1] + 1, + distance [i - 1] [j - 1] + + (first [i - 1] == second [j - 1] ? 0 : 1)); + } + if (i) { + /* + * We only need the previous row; freeing the memory of rows + * we no longer need, reduces the memory usage from + * Theta (n * m) to O (min (n, m)) + */ + free (distance [i - 1]); + } + } + size_t out = distance [n] [m]; + free (distance [n]); + free (distance); + return (out); +} + + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t str_len; + + while ((str_len = getline (&line, &len, stdin)) != -1) { + char * line_ptr = line; + /* + * Skip any leading whitespace + */ + while (isspace (*line_ptr)) { + line_ptr ++; + } + /* + * We're now at the start of the first word; + * scan the word, count its length. + */ + char * first = line_ptr; + size_t n = 0; + + while (!isspace (*line_ptr)) { + line_ptr ++; + n ++; + } + + /* + * Terminate the first word, and advance our pointer. + */ + *line_ptr ++ = '\0'; + + /* + * Skip over any subsequent whitespace + */ + while (isspace (*line_ptr)) { + line_ptr ++; + } + + /* + * We're now at the beginning of the second word; + * scan it, and count its length. + */ + char * second = line_ptr; + size_t m = 0; + + while (*line_ptr && !isspace (*line_ptr)) { + line_ptr ++; + m ++; + } + + /* + * Terminate the second word, before any trailing whitespace + */ + *line_ptr ++ = '\0'; + + printf ("%zu\n", LevenshteinDistance (first, n, second, m)); + } + free (line); + + return (0); +} diff --git a/challenge-096/abigail/lua/ch-1.lua b/challenge-096/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..9c4b1de913 --- /dev/null +++ b/challenge-096/abigail/lua/ch-1.lua @@ -0,0 +1,14 @@ +for line in io . lines () do + -- + -- Extract words and put them into an array, in reverse. + -- + local words = {} + for str in string . gmatch (line, "[^ ]+") do + table . insert (words, 1, str) + end + + -- + -- Print the words + -- + io . write (table . concat (words, " "), "\n") +end diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..162f06eef0 --- /dev/null +++ b/challenge-096/abigail/lua/ch-2.lua @@ -0,0 +1,66 @@ +-- +-- This is an implementation of the Wagner Fischer algorithm, which +-- calculates the Levenshtein distance. +-- +-- See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm +-- +function LevenshteinDistance (first, second) + local n = first : len () + local m = second : len () + if n < m + then + first, second = second, first + n, m = m, n + end + distances = {} + for i = 0, n do + distances [i] = {} + for j = 0, m do + if i == 0 or j == 0 + then + distances [i] [j] = i + j + else + local cost = 1 + if string . sub (first, i, i) == + string . sub (second, j, j) + then + cost = 0 + end + distances [i] [j] = math . min ( + distances [i - 1] [j] + 1, + distances [i] [j - 1] + 1, + distances [i - 1] [j - 1] + cost + ) + end + end + + -- + -- We only need the previous row, so we can return the + -- memory of rows before that. This reduces the memory + -- usage from O (n * m) to O (min (n, m)) + -- + if i > 0 + then + distances [i - 1] = nil + end + end + return distances [n] [m] +end + + +for line in io . lines () do + -- + -- Extract words and put them into an array. + -- + local words = {} + index = 0 + for str in string . gmatch (line, "[^ ]+") do + index = index + 1 + words [index] = str + end + + -- + -- Calculate the edit distance, and print the result. + -- + io . write (LevenshteinDistance (words [1], words [2]), "\n") +end diff --git a/challenge-096/abigail/node/ch-1.js b/challenge-096/abigail/node/ch-1.js new file mode 100644 index 0000000000..b31524a686 --- /dev/null +++ b/challenge-096/abigail/node/ch-1.js @@ -0,0 +1,15 @@ +// +// Read STDIN. Split on newlines, filter out empty lines, then call "main". +// + require ("fs") +. readFileSync (0) // Read all. +. toString () // Turn it into a string. +. split ("\n") // Split on newlines. +. filter (_ => _ . length) // Filter out empty lines. +. map (_ => console . log (_ . trim () // Remove leading + // and trailing + // whitespace. + . split (/\s+/) // split ... + . reverse () // reverse ... + . join (" "))) // and recombine. +; diff --git a/challenge-096/abigail/node/ch-2.js b/challenge-096/abigail/node/ch-2.js new file mode 100644 index 0000000000..8423ab96b8 --- /dev/null +++ b/challenge-096/abigail/node/ch-2.js @@ -0,0 +1,44 @@ +// +// Read STDIN. Split on newlines, filter out empty lines, then call "main". +// + require ("fs") +. readFileSync (0) // Read all. +. toString () // Turn it into a string. +. split ("\n") // Split on newlines. +. filter (_ => _ . length) // Filter out empty lines. +. map (_ => console . log (LevenshteinDistance (_ . trim () + . split (/\s+/)))) +; + +// +// This is an implementation of the Wagner Fischer algorithm, which +// calculates the Levenshtein distance. +// +// See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm +// +function LevenshteinDistance (strings) { + let first = strings [0] . split (""); + let second = strings [1] . split (""); + + let distance = []; + + let N = first . length; + let M = second . length; + + for (let i = 0; i <= N; i ++) { + distance [i] = []; + for (let j = 0; j <= M; j ++) { + distance [i] [j] = + i == 0 || j == 0 ? i + j + : Math . min (distance [i - 1] [j] + 1, + distance [i] [j - 1] + 1, + distance [i - 1] [j - 1] + + (first [i - 1] == + second [j - 1] ? 0 : 1)) + } + if (i) { + distance [i - 1] = 0 + } + } + return distance [N] [M] +} diff --git a/challenge-096/abigail/perl/ch-1.pl b/challenge-096/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..ddca656054 --- /dev/null +++ b/challenge-096/abigail/perl/ch-1.pl @@ -0,0 +1,33 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# For the challenge description, see ../README.md +# + +# +# The challenge doesn't describe what a word is, or what to +# do with things which are neither words, nor whitespace, like +# punctuation. +# +# For instance, what should happen to the sentence: +# +# "The Weekly Challenge, Part 1!" +# +# So, we're using the easy way out, and assume anything which isn't +# whitespace to be part of a word. After all, the examples assumen +# all the world is ASCII letters and spaces. +# +# Which makes the excercise too trivial to be called a challenge. +# + +# Extract 'words', reverse the list, and print it. +say join " " => reverse /\S+/g for <>; diff --git a/challenge-096/abigail/perl/ch-2.pl b/challenge-096/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..bb58c84569 --- /dev/null +++ b/challenge-096/abigail/perl/ch-2.pl @@ -0,0 +1,45 @@ + + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +use List::Util 'min'; + +# +# This is an implementation of the Wagner Fischer algorithm, which +# calculates the Levenshtein distance. +# +# See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm +# +sub LevenshteinDistance ($first, $second) { + ($first, $second) = ($second, $first) if length ($first) < + length ($second); + my $distance; + for (my $i = 0; $i <= length ($first); $i ++) { + for (my $j = 0; $j <= length ($second); $j ++) { + $$distance [$i] [$j] = + $i == 0 || $j == 0 ? $i + $j + : min ($$distance [$i - 1] [$j] + 1, + $$distance [$i] [$j - 1] + 1, + $$distance [$i - 1] [$j - 1] + + (substr ($first, $i - 1, 1) eq + substr ($second, $j - 1, 1) ? 0 : 1)) + } + # + # We only need the previous row; this reduces the memory + # from O (N * M) to O (min (N, M)), where N and M are the + # lengths of the input strings. + # + undef $$distance [$i - 1] if $i; + } + $$distance [-1] [-1]; +} + + +say LevenshteinDistance /\S+/g for <>; diff --git a/challenge-096/abigail/python/ch-1.py b/challenge-096/abigail/python/ch-1.py new file mode 100644 index 0000000000..ddc34e2633 --- /dev/null +++ b/challenge-096/abigail/python/ch-1.py @@ -0,0 +1,6 @@ +import fileinput + +for line in fileinput . input (): + words = line . strip () . split () + words . reverse () + print (" " . join (words)) diff --git a/challenge-096/abigail/python/ch-2.py b/challenge-096/abigail/python/ch-2.py new file mode 100644 index 0000000000..deaeff14cf --- /dev/null +++ b/challenge-096/abigail/python/ch-2.py @@ -0,0 +1,21 @@ +import fileinput + +def LevenshteinDistance (first, second): + n = len (first) + m = len (second) + distance = [] + for i in range (n + 1): + distance . append ([]) + for j in range (m + 1): + distance [i] . append (i + j if i == 0 or j == 0 else + min (distance [i - 1] [j] + 1, + distance [i] [j - 1] + 1, + distance [i - 1] [j - 1] + + (0 if first [i - 1] == + second [j - 1] else 1))) + return distance [n] [m] + + +for line in fileinput . input (): + words = line . strip () . split () + print LevenshteinDistance (words [0], words [1]) diff --git a/challenge-096/abigail/ruby/ch-1.rb b/challenge-096/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..064f780345 --- /dev/null +++ b/challenge-096/abigail/ruby/ch-1.rb @@ -0,0 +1,3 @@ +ARGF . each_line do |_| + puts ((_ . split (/\s+/)) . grep (/\S/)) . reverse . join (" ") +end diff --git a/challenge-096/abigail/ruby/ch-2.rb b/challenge-096/abigail/ruby/ch-2.rb new file mode 100644 index 0000000000..65a57bd6d3 --- /dev/null +++ b/challenge-096/abigail/ruby/ch-2.rb @@ -0,0 +1,31 @@ +def LevenshteinDistance (first, second) + n = first . length + m = second . length + if n < m + first, second = second, first + n, m = m, n + end + distances = [] + for i in 0 .. n do + distances [i] = [] + for j in 0 .. m do + distances [i] [j] = i == 0 || j == 0 ? i + j + : [distances [i - 1] [j] + 1, + distances [i] [j - 1] + 1, + distances [i - 1] [j - 1] + + (first [i - 1] == second [j - 1] ? 0 : 1)] . min + end + # + # Release memory + # + if i > 1 + distances [i - 1] = nil + end + end + return distances [n] [m] +end + +ARGF . each_line do |_| + words = (_ . split (/\s+/)) . grep (/\S/) + puts (LevenshteinDistance words [0], words [1]) +end diff --git a/challenge-096/abigail/t/ctest.ini b/challenge-096/abigail/t/ctest.ini new file mode 100644 index 0000000000..5592956f87 --- /dev/null +++ b/challenge-096/abigail/t/ctest.ini @@ -0,0 +1,13 @@ +[names]
+1-1 = Given examples
+2-1 = Given examples
+2-2 = Wikipedia example
+2-3 = Extra whitespace
+
+
+[1-1]
+trim = 0
+
+
+[2-3]
+trim = 0
diff --git a/challenge-096/abigail/t/input-1-1 b/challenge-096/abigail/t/input-1-1 new file mode 100644 index 0000000000..ed78ab1367 --- /dev/null +++ b/challenge-096/abigail/t/input-1-1 @@ -0,0 +1,2 @@ +The Weekly Challenge + Perl and Raku are part of the same family diff --git a/challenge-096/abigail/t/input-2-1 b/challenge-096/abigail/t/input-2-1 new file mode 100644 index 0000000000..cdfe0772e5 --- /dev/null +++ b/challenge-096/abigail/t/input-2-1 @@ -0,0 +1,2 @@ +kitten sitting +sunday monday diff --git a/challenge-096/abigail/t/input-2-2 b/challenge-096/abigail/t/input-2-2 new file mode 100644 index 0000000000..3575a4749f --- /dev/null +++ b/challenge-096/abigail/t/input-2-2 @@ -0,0 +1 @@ +sunday saturday diff --git a/challenge-096/abigail/t/input-2-3 b/challenge-096/abigail/t/input-2-3 new file mode 100644 index 0000000000..80a194e95c --- /dev/null +++ b/challenge-096/abigail/t/input-2-3 @@ -0,0 +1 @@ + hello world diff --git a/challenge-096/abigail/t/output-1-1.exp b/challenge-096/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..a551829850 --- /dev/null +++ b/challenge-096/abigail/t/output-1-1.exp @@ -0,0 +1,2 @@ +Challenge Weekly The +family same the of part are Raku and Perl diff --git a/challenge-096/abigail/t/output-2-1.exp b/challenge-096/abigail/t/output-2-1.exp new file mode 100644 index 0000000000..f1e5eeed2d --- /dev/null +++ b/challenge-096/abigail/t/output-2-1.exp @@ -0,0 +1,2 @@ +3 +2 diff --git a/challenge-096/abigail/t/output-2-2.exp b/challenge-096/abigail/t/output-2-2.exp new file mode 100644 index 0000000000..00750edc07 --- /dev/null +++ b/challenge-096/abigail/t/output-2-2.exp @@ -0,0 +1 @@ +3 diff --git a/challenge-096/abigail/t/output-2-3.exp b/challenge-096/abigail/t/output-2-3.exp new file mode 100644 index 0000000000..b8626c4cff --- /dev/null +++ b/challenge-096/abigail/t/output-2-3.exp @@ -0,0 +1 @@ +4 |