Merge remote-tracking branch 'upstream/master'

6 files changed, 303 insertions, 63 deletions

diff --git a/challenge-092/paulo-custodio/basic/ch-1.bas b/challenge-092/paulo-custodio/basic/ch-1.bas
index 1e042022ff..bfaafba85f 100644
--- a/challenge-092/paulo-custodio/basic/ch-1.bas
+++ b/challenge-092/paulo-custodio/basic/ch-1.bas
@@ -4,7 +4,7 @@
 ' Submitted by: Mohammad S Anwar
 ' You are given two strings $A and $B.
 '
-' Write a script to check if the given strings are Isomorphic. Print 1 if they 
+' Write a script to check if the given strings are Isomorphic. Print 1 if they
 ' are otherwise 0.
 '
 ' Example 1:
@@ -18,30 +18,30 @@
 ' Output: 0
 
 function isomorphic(a as string, b as string) as integer
-	dim mapping(256) as integer, mapped(256) as integer
-	dim i as integer, ac as integer, bc as integer
-	
-	if a="" or len(a)<>len(b) then
-		isomorphic = 0: exit function
-	end if
-		
-	for i=1 to len(a)
-		ac = asc(mid(a,i,1))
-		bc = asc(mid(b,i,1))
-		if mapping(ac)=0 then			' a is new
-			if mapped(bc)<>0 then		' b already mapped to some other a
-				isomorphic = 0: exit function
-			else 						' store mapping
-				mapping(ac) = bc
-				mapped(bc) = 1
-			end if
-		else							' a already occurred
-			if mapping(ac)<>bc then		' previous mapping is different
-				isomorphic = 0: exit function
-			end if
-		end if
-	next
-	isomorphic = 1
+    dim mapping(256) as integer, mapped(256) as integer
+    dim i as integer, ac as integer, bc as integer
+
+    if a="" or len(a)<>len(b) then
+        isomorphic = 0: exit function
+    end if
+
+    for i=1 to len(a)
+        ac = asc(mid(a,i,1))
+        bc = asc(mid(b,i,1))
+        if mapping(ac)=0 then           ' a is new
+            if mapped(bc)<>0 then       ' b already mapped to some other a
+                isomorphic = 0: exit function
+            else                        ' store mapping
+                mapping(ac) = bc
+                mapped(bc) = 1
+            end if
+        else                            ' a already occurred
+            if mapping(ac)<>bc then     ' previous mapping is different
+                isomorphic = 0: exit function
+            end if
+        end if
+    next
+    isomorphic = 1
 end function
 
-print trim(str(isomorphic(command(1), command(2))))
\ No newline at end of file
+print trim(str(isomorphic(command(1), command(2))))
diff --git a/challenge-092/paulo-custodio/basic/ch-2.bas b/challenge-092/paulo-custodio/basic/ch-2.bas
index a974817a64..dc292b2769 100644
--- a/challenge-092/paulo-custodio/basic/ch-2.bas
+++ b/challenge-092/paulo-custodio/basic/ch-2.bas
@@ -19,46 +19,46 @@
 redim shared timeline(1) as Boolean
 
 sub fill_timeline()
-	dim i as integer, j as integer, p as integer, bg as integer, ed as integer
-	i=1
-	do while command(i)<>""
-		' parse begin,end
-		p=instr(command(i),",")
-		if p=0 then error 5
-		bg=val(command(i))
-		ed=val(mid(command(i),p+1))
-		' resize timeline if needed
-		if 2*ed>ubound(timeline) then
-			redim preserve timeline(2*ed+2)
-		end if
-		
-		' fill interval
-		for j=2*bg to 2*ed
-			timeline(j)=true
-		next
-		i=i+1
-	loop
+    dim i as integer, j as integer, p as integer, bg as integer, ed as integer
+    i=1
+    do while command(i)<>""
+        ' parse begin,end
+        p=instr(command(i),",")
+        if p=0 then error 5
+        bg=val(command(i))
+        ed=val(mid(command(i),p+1))
+        ' resize timeline if needed
+        if 2*ed>ubound(timeline) then
+            redim preserve timeline(2*ed+2)
+        end if
+
+        ' fill interval
+        for j=2*bg to 2*ed
+            timeline(j)=true
+        next
+        i=i+1
+    loop
 end sub
 
 sub print_timeline()
-	dim i as integer
-	redim intervals(0) as integer
-	
-	for i=lbound(timeline) to ubound(timeline)-1
-		if timeline(i)=false and timeline(i+1)=true then
-			redim preserve intervals(ubound(intervals)+1)
-			intervals(ubound(intervals))=int(i/2)+1
-		elseif timeline(i)=true and timeline(i+1)=false then
-			redim preserve intervals(ubound(intervals)+1)
-			intervals(ubound(intervals))=int(i/2)
-		end if
-	next
-	
-	for i=1 to ubound(intervals) step 2
-		print "(";trim(str(intervals(i)));",";trim(str(intervals(i+1)));")";
-		if i+2<ubound(intervals) then print ", ";
-	next
-	print
+    dim i as integer
+    redim intervals(0) as integer
+
+    for i=lbound(timeline) to ubound(timeline)-1
+        if timeline(i)=false and timeline(i+1)=true then
+            redim preserve intervals(ubound(intervals)+1)
+            intervals(ubound(intervals))=int(i/2)+1
+        elseif timeline(i)=true and timeline(i+1)=false then
+            redim preserve intervals(ubound(intervals)+1)
+            intervals(ubound(intervals))=int(i/2)
+        end if
+    next
+
+    for i=1 to ubound(intervals) step 2
+        print "(";trim(str(intervals(i)));",";trim(str(intervals(i+1)));")";
+        if i+2<ubound(intervals) then print ", ";
+    next
+    print
 end sub
 
 ' main
diff --git a/challenge-092/paulo-custodio/lua/ch-1.lua b/challenge-092/paulo-custodio/lua/ch-1.lua
new file mode 100644
index 0000000000..335b640620
--- /dev/null
+++ b/challenge-092/paulo-custodio/lua/ch-1.lua
@@ -0,0 +1,57 @@
+#!/usr/bin/env lua
+
+--[[
+Challenge 092
+
+TASK #1 > Isomorphic Strings
+Submitted by: Mohammad S Anwar
+You are given two strings $A and $B.
+
+Write a script to check if the given strings are Isomorphic. Print 1 if they
+are otherwise 0.
+
+Example 1:
+Input: $A = "abc"; $B = "xyz"
+Output: 1
+Example 2:
+Input: $A = "abb"; $B = "xyy"
+Output: 1
+Example 3:
+Input: $A = "sum"; $B = "add"
+Output: 0
+--]]
+
+function split_string(str)
+    local t = {}
+    string.gsub(str, ".", function(c) table.insert(t,c) end)
+    return t
+end
+
+function isomorphic(a, b)
+    if #a ~= #b then
+        return 0
+    else
+        local a = split_string(a)
+        local b = split_string(b)
+        local mapping = {}
+        local mapped = {}
+
+        for i=1, #a do
+            if mapping[a[i]] == nil then        -- a is new
+                if mapped[b[i]] ~= nil then     -- b already mapped to some other a
+                    return 0
+                else                            -- store mapping
+                    mapping[a[i]] = b[i]
+                    mapped[b[i]] = 1
+                end
+            else                                -- a already occurred
+                if mapping[a[i]] ~= b[i] then   -- previous mapping is different
+                    return 0
+                end
+            end
+        end
+        return 1
+    end
+end
+
+io.write(isomorphic(arg[1], arg[2]))
diff --git a/challenge-092/paulo-custodio/lua/ch-2.lua b/challenge-092/paulo-custodio/lua/ch-2.lua
new file mode 100644
index 0000000000..5df3153e72
--- /dev/null
+++ b/challenge-092/paulo-custodio/lua/ch-2.lua
@@ -0,0 +1,63 @@
+#!/usr/bin/env lua
+
+--[[
+Challenge 092
+
+TASK #2 > Insert Interval
+Submitted by: Mohammad S Anwar
+You are given a set of sorted non-overlapping intervals and a new interval.
+
+Write a script to merge the new interval to the given set of intervals.
+
+Example 1:
+Input $S = (1,4), (8,10); $N = (2,6)
+Output: (1,6), (8,10)
+Example 2:
+Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+Output: (1,2), (3,10)
+Example 3:
+Input $S = (1,5), (7,9); $N = (10,11)
+Output: (1,5), (7,9), (10,11)
+--]]
+
+timeline = {}
+
+function fill_timeline()
+    for i=1,#arg do
+        -- parse begin,end
+        local bg, ed = string.match(arg[i], "(%d+),(%d+)")
+        bg = tonumber(bg)
+        ed = tonumber(ed)
+
+        -- resize timeline if needed
+        while 2*ed >= #timeline do
+            table.insert(timeline, false)
+        end
+
+        -- fill interval
+        for j=2*bg, 2*ed do
+            timeline[j] = true
+        end
+    end
+end
+
+function print_timeline()
+    -- collect intervals
+    local intervals = {}
+    for i=1, #timeline-1 do
+        if timeline[i] == false and timeline[i+1] == true then
+            table.insert(intervals, math.floor(i/2)+1)
+        elseif timeline[i] == true and timeline[i+1] == false then
+            table.insert(intervals, math.floor(i/2))
+        end
+    end
+
+    -- print intervals
+    for i=1, #intervals, 2 do
+        io.write("(",intervals[i],",",intervals[i+1],")")
+        if i+2 < #intervals then io.write(", ") end
+    end
+end
+
+fill_timeline()
+print_timeline()
diff --git a/challenge-092/paulo-custodio/python/ch-1.py b/challenge-092/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..70e334812e
--- /dev/null
+++ b/challenge-092/paulo-custodio/python/ch-1.py
@@ -0,0 +1,42 @@
+#!/usr/bin/env python
+
+# Challenge 092
+#
+# TASK #1 > Isomorphic Strings
+# Submitted by: Mohammad S Anwar
+# You are given two strings $A and $B.
+#
+# Write a script to check if the given strings are Isomorphic. Print 1 if they
+# are otherwise 0.
+#
+# Example 1:
+# Input: $A = "abc"; $B = "xyz"
+# Output: 1
+# Example 2:
+# Input: $A = "abb"; $B = "xyy"
+# Output: 1
+# Example 3:
+# Input: $A = "sum"; $B = "add"
+# Output: 0
+
+import sys
+
+def isomorphic(a,b):
+    if len(a)!=len(b):
+        return 0
+    else:
+        mapping = {}
+        mapped = {}
+        for i in range(0, len(a)):
+            if not a[i] in mapping:         # a is new
+                if b[i] in mapped:          # b already mapped to some other a
+                    return 0
+                else:                       # store mapping
+                    mapping[a[i]] = b[i]
+                    mapped[b[i]] = 1
+            else:                           # a already occurred
+                if mapping[a[i]]!=b[i]:     # previous mapping is different
+                    return 0
+        return 1
+
+print(isomorphic(sys.argv[1], sys.argv[2]))
diff --git a/challenge-092/paulo-custodio/python/ch-2.py b/challenge-092/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..70338a0976
--- /dev/null
+++ b/challenge-092/paulo-custodio/python/ch-2.py
@@ -0,0 +1,78 @@
+#!/usr/bin/env python
+
+# Challenge 092
+#
+# TASK #2 > Insert Interval
+# Submitted by: Mohammad S Anwar
+# You are given a set of sorted non-overlapping intervals and a new interval.
+#
+# Write a script to merge the new interval to the given set of intervals.
+#
+# Example 1:
+# Input $S = (1,4), (8,10); $N = (2,6)
+# Output: (1,6), (8,10)
+# Example 2:
+# Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+# Output: (1,2), (3,10)
+# Example 3:
+# Input $S = (1,5), (7,9); $N = (10,11)
+# Output: (1,5), (7,9), (10,11)
+
+import sys
+
+def add_interval_in_order(intervals, a, b):
+    if len(intervals)==0:
+        intervals.append([a, b])
+    else:
+        for i in range(0, len(intervals)):
+            if b < intervals[i][0]:                 # before, not overlapping
+                intervals = intervals[:i]+[a, b]+intervals[i:]
+                return intervals
+            elif b >= intervals[i][0] and b < intervals[i][1]:  # end within
+                if a < intervals[i][0]:                         # merge start
+                    intervals[i][0] = a
+                return intervals
+            elif b >= intervals[i][1] and a < intervals[i][1]:  # end after, start within
+                intervals[i][1] = b
+                if a < intervals[i][0]:                         # merge start
+                    intervals[i][0] = a
+                return intervals
+        intervals.append([a, b])                                # append to end
+    return intervals
+
+def merge_intervals(intervals):
+    i = 0
+    while i+1 < len(intervals):
+        while i+1 < len(intervals):
+            this = intervals[i]
+            next = intervals[i+1]
+            if this[1] < next[0]:       # not overlapping
+                break                   # next interval
+            else:
+                intervals = intervals[:i]+ \
+                            [[this[0], next[1]]]+ \
+                            intervals[i+2:]     # merge and test again
+        i += 1
+    return intervals
+
+def add_interval(intervals, a, b):
+    intervals = add_interval_in_order(intervals, a, b)
+    intervals = merge_intervals(intervals)
+    return intervals
+
+def add_intervals():
+    intervals = []
+    for i in range(1, len(sys.argv)):
+        a, b = sys.argv[i].split(',')
+        intervals = add_interval(intervals, int(a), int(b))
+    return intervals
+
+def intervals_str(intervals):
+    out = ''
+    for i in range(0, len(intervals)):
+        out += '('+str(intervals[i][0])+','+str(intervals[i][1])+')'
+        if i<len(intervals)-1:
+            out += ', '
+    return out
+
+print(intervals_str(add_intervals()))