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 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-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"; + ["' 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( "$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"; +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" => <