Merge pull request #5162 from pauloscustodio/devel

Devel

10 files changed, 245 insertions, 15 deletions

diff --git a/challenge-111/paulo-custodio/Makefile b/challenge-111/paulo-custodio/Makefile
new file mode 100644
index 0000000000..c3c762d746
--- /dev/null
+++ b/challenge-111/paulo-custodio/Makefile
@@ -0,0 +1,2 @@
+all:
+	perl ../../challenge-001/paulo-custodio/test.pl
diff --git a/challenge-111/paulo-custodio/python/ch-1.py b/challenge-111/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..44b45019f2
--- /dev/null
+++ b/challenge-111/paulo-custodio/python/ch-1.py
@@ -0,0 +1,78 @@
+#!/usr/bin/env python3
+
+# Challenge 111
+#
+# TASK #1 - Search Matrix
+# Submitted by: Mohammad S Anwar
+# You are given 5x5 matrix filled with integers such that each row is sorted
+# from left to right and the first integer of each row is greater than the
+# last integer of the previous row.
+#
+# Write a script to find a given integer in the matrix using an efficient
+# search algorithm.
+#
+# Example
+#     Matrix: [  1,  2,  3,  5,  7 ]
+#             [  9, 11, 15, 19, 20 ]
+#             [ 23, 24, 25, 29, 31 ]
+#             [ 32, 33, 39, 40, 42 ]
+#             [ 45, 47, 48, 49, 50 ]
+#
+#     Input: 35
+#     Output: 0 since it is missing in the matrix
+#
+#     Input: 39
+#     Output: 1 as it exists in the matrix
+
+import sys
+
+data = [[  1,  2,  3,  5,  7 ],
+        [  9, 11, 15, 19, 20 ],
+        [ 23, 24, 25, 29, 31 ],
+        [ 32, 33, 39, 40, 42 ],
+        [ 45, 47, 48, 49, 50 ]]
+
+def find_col(n, row):
+    l = 0
+    h = len(data[row])-1
+    if n < data[row][0] or n > data[row][-1]:
+        return -1
+    while l < h:
+        m = int((l+h)/2)
+        if n < data[row][m]:
+            h = m-1
+        elif n > data[row][m]:
+            l = m+1
+        else:
+            return m
+    if n != data[row][l]:
+        return -1
+    else:
+        return l
+
+def find_row(n):
+    l = 0
+    h = len(data)-1
+    if n < data[0][0] or n > data[-1][-1]:
+        return -1
+    while l < h:
+        m = int((l+h)/2)
+        if n < data[m][0]:
+            h = m-1
+        elif n > data[m][-1]:
+            l = m+1
+        else:
+            return m
+    return l
+
+def find(n):
+    row = find_row(n)
+    if row < 0:
+        return 0
+    col = find_col(n, row)
+    if col < 0:
+        return 0
+    else:
+        return 1
+
+print(find(int(sys.argv[1])))
diff --git a/challenge-111/paulo-custodio/python/ch-2.py b/challenge-111/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..43aca5f927
--- /dev/null
+++ b/challenge-111/paulo-custodio/python/ch-2.py
@@ -0,0 +1,35 @@
+#!/usr/bin/env python3
+
+# Challenge 111
+#
+# TASK #2 - Ordered Letters
+# Submitted by: E. Choroba
+# Given a word, you can sort its letters alphabetically (case insensitive).
+# For example, "beekeeper" becomes "beeeeekpr" and "dictionary" becomes
+# "acdiinorty".
+#
+# Write a script to find the longest English words that don't change when
+# their letters are sorted.
+
+import fileinput
+import sys
+
+def read_input():
+    lines = []
+    for line in fileinput.input():
+        lines.append(line)
+    return lines
+
+def find_longest(lines):
+    max_len = 0
+    words = []
+    for word in lines:
+        word = word.strip().lower()
+        drow = "".join(sorted(word))
+        if word==drow:
+            max_len = max(max_len, len(word))
+            words.append(word)
+    words = list(filter(lambda x: len(x)==max_len, words))
+    return words
+
+print(" ".join(find_longest(read_input())))
diff --git a/challenge-111/paulo-custodio/test.pl b/challenge-111/paulo-custodio/test.pl
deleted file mode 100755
index ba6c37260b..0000000000
--- a/challenge-111/paulo-custodio/test.pl
+++ /dev/null
@@ -1,4 +0,0 @@
-#!/usr/bin/env perl
-use Modern::Perl;
-use Test::More;
-require '../../challenge-001/paulo-custodio/test.pl';
diff --git a/challenge-112/paulo-custodio/Makefile b/challenge-112/paulo-custodio/Makefile
new file mode 100644
index 0000000000..c3c762d746
--- /dev/null
+++ b/challenge-112/paulo-custodio/Makefile
@@ -0,0 +1,2 @@
+all:
+	perl ../../challenge-001/paulo-custodio/test.pl
diff --git a/challenge-112/paulo-custodio/python/ch-1.py b/challenge-112/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..605de4b538
--- /dev/null
+++ b/challenge-112/paulo-custodio/python/ch-1.py
@@ -0,0 +1,52 @@
+#!/usr/bin/env python3
+
+# Challenge 112
+#
+# TASK #1 - Canonical Path
+# Submitted by: Mohammad S Anwar
+# You are given a string path, starting with a slash '/'.
+#
+# Write a script to convert the given absolute path to the simplified canonical
+# path.
+#
+# In a Unix-style file system:
+#
+# - A period '.' refers to the current directory
+# - A double period '..' refers to the directory up a level
+# - Multiple consecutive slashes ('//') are treated as a single slash '/'
+# The canonical path format:
+#
+# - The path starts with a single slash '/'.
+# - Any two directories are separated by a single slash '/'.
+# - The path does not end with a trailing '/'.
+# - The path only contains the directories on the path from the root directory
+#   to the target file or directory
+# Example
+# Input: "/a/"
+# Output: "/a"
+#
+# Input: "/a/b//c/"
+# Output: "/a/b/c"
+#
+# Input: "/a/b/c/../.."
+# Output: "/a"
+
+import sys
+import re
+
+def canon(path):
+    def replace(srch, rpl, s):
+        while True:
+            s, count = re.subn(srch, rpl, s)
+            if count==0:
+                return s
+
+    path = replace(r"/\./", "/", path)
+    path = replace(r"/\.$", "/", path)
+    path = replace(r"/[^\/\.]+/\.\./", "/", path)
+    path = replace(r"/[^\/\.]+/\.\.$", "/", path)
+    path = re.sub(r"/+", "/", path)
+    path = re.sub(r"/$", "", path)
+    return path
+
+print(canon(sys.argv[1]))
diff --git a/challenge-112/paulo-custodio/python/ch-2.py b/challenge-112/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..952ebe41da
--- /dev/null
+++ b/challenge-112/paulo-custodio/python/ch-2.py
@@ -0,0 +1,39 @@
+#!/usr/bin/env python3
+
+# Challenge 112
+#
+# TASK #2 - Climb Stairs
+# Submitted by: Mohammad S Anwar
+# You are given $n steps to climb
+#
+# Write a script to find out the distinct ways to climb to the top. You are
+# allowed to climb either 1 or 2 steps at a time.
+#
+# Example
+# Input: $n = 3
+# Output: 3
+#
+#     Option 1: 1 step + 1 step + 1 step
+#     Option 2: 1 step + 2 steps
+#     Option 3: 2 steps + 1 step
+#
+# Input: $n = 4
+# Output: 5
+#
+#     Option 1: 1 step + 1 step + 1 step + 1 step
+#     Option 2: 1 step + 1 step + 2 steps
+#     Option 3: 2 steps + 1 step + 1 step
+#     Option 4: 1 step + 2 steps + 1 step
+#     Option 5: 2 steps + 2 steps
+
+import sys
+
+def count(n):
+    if n <= 0:
+        return 0
+    elif 1 <= n <= 2:
+        return n
+    else:
+        return count(n-1)+count(n-2)
+
+print(count(int(sys.argv[1])))
diff --git a/challenge-113/paulo-custodio/perl/ch-1.pl b/challenge-113/paulo-custodio/perl/ch-1.pl
index b9badbba36..5cee958f39 100644
--- a/challenge-113/paulo-custodio/perl/ch-1.pl
+++ b/challenge-113/paulo-custodio/perl/ch-1.pl
@@ -18,14 +18,29 @@
 # Output: 1
 
 use Modern::Perl;
-my($N, $D) = @ARGV;
-say represent($N||0, $D||0) ? 1 : 0;
+use Math::Combinatorics;
+use List::Util 'sum';
 
-sub represent {
+sub nums_containing {
     my($n, $d) = @_;
-    my $sum = 0;
+    my @nums;
     for (1..$n) {
-        $sum += $_ if /$d/;
+        push @nums, $_ if /$d/;
+    }
+    return @nums;
+}
+
+sub represent {
+    my($n, $d) = @_;
+    my @nums = nums_containing($n, $d);
+    for my $k (1 .. @nums) {
+        for my $combin (combine($k, @nums)) {
+            return 1 if sum(@$combin) == $n;
+        }
     }
-    return $sum==$n;
+    return 0;
 }
+
+
+my($N, $D) = @ARGV or die "Usage: ch-1.pl N D\n";
+say represent($N, $D) ? 1 : 0;
diff --git a/challenge-113/paulo-custodio/python/ch-1.py b/challenge-113/paulo-custodio/python/ch-1.py
index e544a5ccd8..5c1e781f0c 100644
--- a/challenge-113/paulo-custodio/python/ch-1.py
+++ b/challenge-113/paulo-custodio/python/ch-1.py
@@ -19,13 +19,19 @@
 
 import sys
 import re
+from itertools import combinations
+
+def nums_containing(n, d):
+    nums = list(filter(lambda x: re.search(str(d), str(x)), range(n+1)))
+    return nums
 
 def represent(n, d):
-    sum = 0
-    for i in range(n+1):
-        if re.search(str(d), str(i)):
-            sum += i
-    return sum==n
+    nums = nums_containing(n, d)
+    for k in range(1, len(nums)+1):
+        for combin in combinations(nums, k):
+            if sum(combin) == n:
+                return True
+    return False
 
 if represent(int(sys.argv[1]), int(sys.argv[2])):
     print(1)
diff --git a/challenge-113/paulo-custodio/t/test-1.yaml b/challenge-113/paulo-custodio/t/test-1.yaml
index f3baa5852a..3c31c6f1e8 100644
--- a/challenge-113/paulo-custodio/t/test-1.yaml
+++ b/challenge-113/paulo-custodio/t/test-1.yaml
@@ -8,3 +8,8 @@
   args:     24 7
   input:
   output:   1
+- setup:
+  cleanup:
+  args:     54 7
+  input:
+  output:   1