Add Python solution to challenge 064

5 files changed, 119 insertions, 5 deletions

diff --git a/challenge-064/paulo-custodio/Makefile b/challenge-064/paulo-custodio/Makefile
index ba9a2bf399..9c7316cd76 100644
--- a/challenge-064/paulo-custodio/Makefile
+++ b/challenge-064/paulo-custodio/Makefile
@@ -1,3 +1,5 @@
 all:
 	perl perl/ch-1.pl
 	perl perl/ch-2.pl
+	python3 python/ch-1.py
+	python3 python/ch-2.py
diff --git a/challenge-064/paulo-custodio/perl/ch-1.pl b/challenge-064/paulo-custodio/perl/ch-1.pl
index 5a1197d4a3..e5acc1ebf1 100644
--- a/challenge-064/paulo-custodio/perl/ch-1.pl
+++ b/challenge-064/paulo-custodio/perl/ch-1.pl
@@ -2,11 +2,11 @@
 
 # Challenge 064
 #
-# TASK #1 › Minimum Sum Path
+# TASK #1 > Minimum Sum Path
 # Submitted by: Mohammad S Anwar
 # Reviewed by: Ryan Thompson
 #
-# Given an m × n matrix with non-negative integers, write a script to find a
+# Given an m x n matrix with non-negative integers, write a script to find a
 # path from top left to bottom right which minimizes the sum of all numbers
 # along its path. You can only move either down or right at any point in time.
 #
diff --git a/challenge-064/paulo-custodio/perl/ch-2.pl b/challenge-064/paulo-custodio/perl/ch-2.pl
index e4a4532f3e..5ae8da6e1e 100644
--- a/challenge-064/paulo-custodio/perl/ch-2.pl
+++ b/challenge-064/paulo-custodio/perl/ch-2.pl
@@ -2,7 +2,7 @@
 
 # Challenge 064
 #
-# TASK #2 › Word Break
+# TASK #2 > Word Break
 # Submitted by: Mohammad S Anwar
 #
 # You are given a string $S and an array of words @W.
@@ -32,7 +32,7 @@
 # 0 as none matching word found.
 
 use Modern::Perl;
-use Math::Combinatorics 'combine';
+use Math::Combinatorics 'permute';
 use Test::More;
 
 is word_break("perlweeklychallenge", "weekly", "challenge", "perl"),
@@ -45,7 +45,7 @@ done_testing;
 sub word_break {
     my($S, @W) = @_;
     my $k = scalar(@W);
-    for (combine($k, @W)) {
+    for (permute(@W)) {
         my @words = @$_;
         if (join('', @words) eq $S) {
             return "@W";
diff --git a/challenge-064/paulo-custodio/python/ch-1.py b/challenge-064/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..54982caa27
--- /dev/null
+++ b/challenge-064/paulo-custodio/python/ch-1.py
@@ -0,0 +1,60 @@
+#!/usr/bin/env python3
+
+# Challenge 064
+#
+# TASK #1 > Minimum Sum Path
+# Submitted by: Mohammad S Anwar
+# Reviewed by: Ryan Thompson
+#
+# Given an m x n matrix with non-negative integers, write a script to find a
+# path from top left to bottom right which minimizes the sum of all numbers
+# along its path. You can only move either down or right at any point in time.
+#
+# Example
+# Input:
+#
+# [ 1 2 3 ]
+# [ 4 5 6 ]
+# [ 7 8 9 ]
+# The minimum sum path looks like this:
+#
+# 1?2?3
+#     ?
+#     6
+#     ?
+#     9
+# Thus, your script could output: 21 ( 1 ? 2 ? 3 ? 6 ? 9 )
+
+import unittest
+import sys
+
+def min_sum(m):
+    min_sum = [sys.maxsize]  # Using a list to simulate a global variable
+
+    def min_sum1(sum, r, c, m):
+        rows = len(m)
+        cols = len(m[0])
+        sum += m[r][c]
+        if r == rows - 1 and c == cols - 1:  # reached end
+            if sum < min_sum[0]:
+                min_sum[0] = sum
+        else:
+            if r + 1 < rows:
+                min_sum1(sum, r + 1, c, m)
+            if c + 1 < cols:
+                min_sum1(sum, r, c + 1, m)
+
+    min_sum1(0, 0, 0, m)
+    return min_sum[0]
+
+class TestMinSum(unittest.TestCase):
+    def test_min_sum(self):
+        m = [
+            [1, 2, 3],
+            [4, 5, 6],
+            [7, 8, 9]
+        ]
+        self.assertEqual(min_sum(m), 21)
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/challenge-064/paulo-custodio/python/ch-2.py b/challenge-064/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..12034bea57
--- /dev/null
+++ b/challenge-064/paulo-custodio/python/ch-2.py
@@ -0,0 +1,52 @@
+#!/usr/bin/env perl
+
+# Challenge 064
+#
+# TASK #2 > Word Break
+# Submitted by: Mohammad S Anwar
+#
+# You are given a string $S and an array of words @W.
+#
+# Write a script to find out if $S can be split into sequence of one or more
+# words as in the given @W.
+#
+# Print the all the words if found otherwise print 0.
+#
+# Example 1:
+# Input:
+#
+# $S = "perlweeklychallenge"
+# @W = ("weekly", "challenge", "perl")
+#
+# Output:
+#
+# "perl", "weekly", "challenge"
+# Example 2:
+# Input:
+#
+# $S = "perlandraku"
+# @W = ("python", "ruby", "haskell")
+#
+# Output:
+#
+# 0 as none matching word found.
+
+import itertools
+import unittest
+
+def word_break(S, *W):
+    k = len(W)
+    for words in itertools.permutations(W):
+        if ''.join(words) == S:
+            return ' '.join(W)
+    return "0"
+
+class TestWordBreak(unittest.TestCase):
+    def test_word_break(self):
+        self.assertEqual(word_break("perlweeklychallenge", "weekly", "challenge", "perl"),
+                         "weekly challenge perl")
+        self.assertEqual(word_break("perlandraku", "python", "ruby", "haskell"),
+                         "0")
+
+if __name__ == '__main__':
+    unittest.main()