Merge remote-tracking branch 'upstream/master'

3 files changed, 170 insertions, 20 deletions

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 3e029bbb01..29b27ddfda 100644
--- a/challenge-096/paulo-custodio/test.pl
+++ b/challenge-096/paulo-custodio/test.pl
@@ -5,30 +5,34 @@ use warnings;
 use 5.030;
 use Test::More;
 
-compile(         "gcc     c/ch-1.c   -o     c/ch-1");
-compile(         "g++   cpp/ch-1.cpp -o   cpp/ch-1");
-compile(         "fbc basic/ch-1.bas -o basic/ch-1");
+# hack so that output redirection works in msys
+my $LUA = $^O eq "msys" ? "lua.exe" : "lua";
+
+run("gcc     c/ch-1.c   -o     c/ch-1");
+run("g++   cpp/ch-1.cpp -o   cpp/ch-1");
+run("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";
+    is capture(    "perl perl/ch-1.pl  $in"), "$out\n";
+    is capture(     "$LUA lua/ch-1.lua $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";
 
-compile("gcc     c/ch-2.c   -o     c/ch-2");
-compile("g++   cpp/ch-2.cpp -o   cpp/ch-2");
-compile("fbc basic/ch-2.bas -o basic/ch-2");
+run("gcc     c/ch-2.c   -o     c/ch-2");
+run("g++   cpp/ch-2.cpp -o   cpp/ch-2");
+run("fbc basic/ch-2.bas -o basic/ch-2");
 
 for (["kitten sitting" => <<END],
 3
@@ -43,17 +47,17 @@ 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;
+    is capture(    "perl perl/ch-2.pl  $in"), $out;
+    is capture(     "$LUA lua/ch-2.lua $in"), $out;
+    is capture( "gforth forth/ch-2.fs  $in"), $out;
+    is capture("python python/ch-2.py  $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`;
@@ -61,7 +65,7 @@ sub capture {
     return $out;
 }
 
-sub compile {
+sub run {
     my($cmd) = @_;
     ok 0==system($cmd), $cmd;
 }