Merge pull request #10906 from pauloscustodio/master

Add Python solutions

15 files changed, 377 insertions, 22 deletions

diff --git a/challenge-074/paulo-custodio/perl/ch-1.pl b/challenge-074/paulo-custodio/perl/ch-1.pl
index a97295a806..04cb491c3f 100644
--- a/challenge-074/paulo-custodio/perl/ch-1.pl
+++ b/challenge-074/paulo-custodio/perl/ch-1.pl
@@ -2,7 +2,7 @@
 
 # Challenge 074
 #
-# TASK #1 › Majority Element
+# TASK #1 > Majority Element
 # Submitted by: Mohammad S Anwar
 # You are given an array of integers of size $N.
 #
diff --git a/challenge-074/paulo-custodio/perl/ch-2.pl b/challenge-074/paulo-custodio/perl/ch-2.pl
index 7c81bac6ab..da34170991 100644
--- a/challenge-074/paulo-custodio/perl/ch-2.pl
+++ b/challenge-074/paulo-custodio/perl/ch-2.pl
@@ -2,7 +2,7 @@
 
 # Challenge 074
 #
-# TASK #2 › FNR Character
+# TASK #2 > FNR Character
 # Submitted by: Mohammad S Anwar
 # You are given a string $S.
 #
@@ -10,23 +10,23 @@
 # -> right) for the given string. Print # if none found.
 #
 # Example 1
-# Input: $S = ‘ababc’
-# Output: ‘abb#c’
-# Pass 1: “a”, the FNR character is ‘a’
-# Pass 2: “ab”, the FNR character is ‘b’
-# Pass 3: “aba”, the FNR character is ‘b’
-# Pass 4: “abab”, no FNR found, hence ‘#’
-# Pass 5: “ababc” the FNR character is ‘c’
+# Input: $S = 'ababc'
+# Output: 'abb#c'
+# Pass 1: "a", the FNR character is 'a'
+# Pass 2: "ab", the FNR character is 'b'
+# Pass 3: "aba", the FNR character is 'b'
+# Pass 4: "abab", no FNR found, hence '#'
+# Pass 5: "ababc" the FNR character is 'c'
 #
 # Example 2
-# Input: $S = ‘xyzzyx’
-# Output: ‘xyzyx#’
-# Pass 1: “x”, the FNR character is “x”
-# Pass 2: “xy”, the FNR character is “y”
-# Pass 3: “xyz”, the FNR character is “z”
-# Pass 4: “xyzz”, the FNR character is “y”
-# Pass 5: “xyzzy”, the FNR character is “x”
-# Pass 6: “xyzzyx”, no FNR found, hence ‘#’
+# Input: $S = 'xyzzyx'
+# Output: 'xyzyx#'
+# Pass 1: "x", the FNR character is "x"
+# Pass 2: "xy", the FNR character is "y"
+# Pass 3: "xyz", the FNR character is "z"
+# Pass 4: "xyzz", the FNR character is "y"
+# Pass 5: "xyzzy", the FNR character is "x"
+# Pass 6: "xyzzyx", no FNR found, hence '#'
 
 use Modern::Perl;
 
diff --git a/challenge-074/paulo-custodio/python/ch-1.py b/challenge-074/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..cce27f69b9
--- /dev/null
+++ b/challenge-074/paulo-custodio/python/ch-1.py
@@ -0,0 +1,45 @@
+#!/usr/bin/env python3
+
+# Challenge 074
+#
+# TASK #1 > Majority Element
+# Submitted by: Mohammad S Anwar
+# You are given an array of integers of size $N.
+#
+# Write a script to find the majority element. If none found then print -1.
+#
+# Majority element in the list is the one that appears more than
+# floor(size_of_list/2).
+#
+# Example 1
+# Input: @A = (1, 2, 2, 3, 2, 4, 2)
+# Output: 2, as 2 appears 4 times in the list which is more than floor(7/2).
+#
+# Example 2
+# Input: @A = (1, 3, 1, 2, 4, 5)
+# Output: -1 as none of the elements appears more than floor(6/2).
+
+import sys
+
+def majority_elem(a):
+    # count instances of each element, get max
+    count = {}
+    max_count = 0
+    max_elem = None
+    for x in a:
+        if x in count:
+            count[x] += 1
+        else:
+            count[x] = 1
+
+        if count[x] > max_count:
+            max_count, max_elem = count[x], x
+
+    # check if majority
+    if max_count > int(len(a)/2):
+        return max_elem
+    else:
+        return -1
+
+a = [int(x) for x in sys.argv[1:]]
+print(majority_elem(a))
diff --git a/challenge-074/paulo-custodio/python/ch-2.py b/challenge-074/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..131c393c0e
--- /dev/null
+++ b/challenge-074/paulo-custodio/python/ch-2.py
@@ -0,0 +1,54 @@
+#!/usr/bin/env python3
+
+# Challenge 074
+#
+# TASK #2 > FNR Character
+# Submitted by: Mohammad S Anwar
+# You are given a string $S.
+#
+# Write a script to print the series of first non-repeating character (left
+# -> right) for the given string. Print # if none found.
+#
+# Example 1
+# Input: $S = 'ababc'
+# Output: 'abb#c'
+# Pass 1: "a", the FNR character is 'a'
+# Pass 2: "ab", the FNR character is 'b'
+# Pass 3: "aba", the FNR character is 'b'
+# Pass 4: "abab", no FNR found, hence '#'
+# Pass 5: "ababc" the FNR character is 'c'
+#
+# Example 2
+# Input: $S = 'xyzzyx'
+# Output: 'xyzyx#'
+# Pass 1: "x", the FNR character is "x"
+# Pass 2: "xy", the FNR character is "y"
+# Pass 3: "xyz", the FNR character is "z"
+# Pass 4: "xyzz", the FNR character is "y"
+# Pass 5: "xyzzy", the FNR character is "x"
+# Pass 6: "xyzzyx", no FNR found, hence '#'
+
+import sys
+
+def lnr_char(s):
+    out = ""
+    seen = {}
+    for i in range(len(s)):
+        ch = s[i]
+        if ch in seen:
+            seen[ch] += 1
+        else:
+            seen[ch] = 1
+        found = False
+        for j in range(i+1)[::-1]:
+            ch = s[j]
+            if ch in seen and seen[ch] == 1:
+                out += ch
+                found = True
+                break
+        if not found:
+            out += "#"
+    return out
+
+s = sys.argv[1]
+print(lnr_char(s))
diff --git a/challenge-075/paulo-custodio/perl/ch-1.pl b/challenge-075/paulo-custodio/perl/ch-1.pl
index 390a2f3bd1..680f944ca0 100644
--- a/challenge-075/paulo-custodio/perl/ch-1.pl
+++ b/challenge-075/paulo-custodio/perl/ch-1.pl
@@ -2,7 +2,7 @@
 
 # Challenge 075
 #
-# TASK #1 › Coins Sum
+# TASK #1 > Coins Sum
 # Submitted by: Mohammad S Anwar
 # You are given a set of coins @C, assuming you have infinite amount of each
 # coin in the set.
diff --git a/challenge-075/paulo-custodio/perl/ch-2.pl b/challenge-075/paulo-custodio/perl/ch-2.pl
index 4979fec29f..4549745fe2 100644
--- a/challenge-075/paulo-custodio/perl/ch-2.pl
+++ b/challenge-075/paulo-custodio/perl/ch-2.pl
@@ -2,7 +2,7 @@
 
 # Challenge 075
 #
-# TASK #2 › Largest Rectangle Histogram
+# TASK #2 > Largest Rectangle Histogram
 # Submitted by: Mohammad S Anwar
 # You are given an array of positive numbers @A.
 #
diff --git a/challenge-075/paulo-custodio/python/ch-1.py b/challenge-075/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..b86bde2230
--- /dev/null
+++ b/challenge-075/paulo-custodio/python/ch-1.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python3
+
+# Challenge 075
+#
+# TASK #1 > Coins Sum
+# Submitted by: Mohammad S Anwar
+# You are given a set of coins @C, assuming you have infinite amount of each
+# coin in the set.
+#
+# Write a script to find how many ways you make sum $S using the coins from
+# the set @C.
+#
+# Example:
+# Input:
+#     @C = (1, 2, 4)
+#     $S = 6
+#
+# Output: 6
+# There are 6 possible ways to make sum 6.
+# a) (1, 1, 1, 1, 1, 1)
+# b) (1, 1, 1, 1, 2)
+# c) (1, 1, 2, 2)
+# d) (1, 1, 4)
+# e) (2, 2, 2)
+# f) (2, 4)
+
+import sys
+
+def show_coins(want, coins):
+    def show_coins1(want, have, coins, seen):
+        sum_have = sum(have)
+        if sum_have > want:
+            pass            # busted sum
+        elif sum_have == want:
+            out = ", ".join([str(x) for x in sorted(have)])
+            if not out in seen:
+                seen[out] = 1
+                print(out)
+        else:
+            for coin in coins:
+                show_coins1(want, have+[coin], coins, seen)
+
+    show_coins1(want, [], coins, {})
+
+S = int(sys.argv[1])
+C = [int(x) for x in sys.argv[2:]]
+show_coins(S, C)
diff --git a/challenge-075/paulo-custodio/python/ch-2.py b/challenge-075/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..f98bad8242
--- /dev/null
+++ b/challenge-075/paulo-custodio/python/ch-2.py
@@ -0,0 +1,77 @@
+#!/usr/bin/env python3
+
+# Challenge 075
+#
+# TASK #2 > Largest Rectangle Histogram
+# Submitted by: Mohammad S Anwar
+# You are given an array of positive numbers @A.
+#
+# Write a script to find the largest rectangle histogram created by the given
+# array.
+#
+# BONUS: Try to print the histogram as shown in the example, if possible.
+#
+# Example 1:
+#
+# Input: @A = (2, 1, 4, 5, 3, 7)
+#      7           #
+#      6           #
+#      5       #   #
+#      4     # #   #
+#      3     # # # #
+#      2 #   # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        2 1 4 5 3 7
+# Looking at the above histogram, the largest rectangle (4 x 3) is formed by
+# columns (4, 5, 3 and 7).
+#
+# Output: 12
+#
+# Example 2:
+#
+# Input: @A = (3, 2, 3, 5, 7, 5)
+#      7         #
+#      6         #
+#      5       # # #
+#      4       # # #
+#      3 #   # # # #
+#      2 # # # # # #
+#      1 # # # # # #
+#      _ _ _ _ _ _ _
+#        3 2 3 5 7 5
+# Looking at the above histogram, the largest rectangle (3 x 5) is formed by
+# columns (5, 7 and 5).
+#
+# Output: 15
+
+import sys
+
+def make_histogram(a):
+    max_ = max(a)
+    hist = [[0 for c in range(len(a))] for r in range(max_)]
+    for c in range(len(a)):
+        for r in range(max_-1+1):
+            hist[r][c] = False if r >= a[c] else True
+    return hist
+
+def calc_max_area(hist):
+    max_area = 0
+    for r0 in range(len(hist)):
+        for c0 in range(len(hist[0])):
+            if hist[r0][c0]:
+                for height in range(1, len(hist)-r0+1):
+                    for width in range(1, len(hist[0])-c0+1):
+                        all_ones = True
+                        for r in range(r0, r0+height):
+                            for c in range (c0, c0+width):
+                                if not hist[r][c]:
+                                    all_ones = False;
+                        if all_ones:
+                            max_area = max(max_area, width*height)
+    return max_area
+
+n = [int(x) for x in sys.argv[1:]]
+hist = make_histogram(n)
+max_area = calc_max_area(hist)
+print(max_area)
diff --git a/challenge-146/paulo-custodio/perl/ch-1.pl b/challenge-146/paulo-custodio/perl/ch-1.pl
index 756810be2c..db556137e3 100644
--- a/challenge-146/paulo-custodio/perl/ch-1.pl
+++ b/challenge-146/paulo-custodio/perl/ch-1.pl
@@ -2,7 +2,7 @@
 
 # Challenge 146
 #
-# TASK #1 › 10001st Prime Number
+# TASK #1 > 10001st Prime Number
 # Submitted by: Mohammad S Anwar
 # Write a script to generate the 10001st prime number.
 
diff --git a/challenge-146/paulo-custodio/python/ch-1.py b/challenge-146/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..0cee726b6c
--- /dev/null
+++ b/challenge-146/paulo-custodio/python/ch-1.py
@@ -0,0 +1,11 @@
+#!/usr/bin/env python3
+
+# Challenge 146
+#
+# TASK #1 > 10001st Prime Number
+# Submitted by: Mohammad S Anwar
+# Write a script to generate the 10001st prime number.
+
+from sympy import prime
+
+print(prime(10001))
diff --git a/challenge-146/paulo-custodio/python/ch-2.py b/challenge-146/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..a355bd9517
--- /dev/null
+++ b/challenge-146/paulo-custodio/python/ch-2.py
@@ -0,0 +1,42 @@
+#!/usr/bin/env python3
+
+# Challenge 146
+#
+# Consider the following Curious Fraction Tree:
+#
+#
+# Curious Fraction Tree
+#
+#
+# You are given a fraction, member of the tree created similar to the above sample.
+#
+# Write a script to find out the parent and grandparent of the given member.
+#
+# Example 1:
+#     Input: $member = '3/5';
+#     Output: parent = '3/2' and grandparent = '1/2'
+# Example 2:
+#     Input: $member = '4/3';
+#     Output: parent = '1/3' and grandparent = '1/2'
+#
+# Solution:
+# for node a/b, the children are a/(a+b) and (a+b)/b
+
+import sys
+
+def parent(a, b):
+    if a / b < 1:  # a/(a+b)
+        parent_a = a
+        parent_b = abs(b - a)
+    else:  # (a+b)/b
+        parent_a = abs(b - a)
+        parent_b = b
+    return parent_a, parent_b
+
+input_value = sys.argv[1]
+a, b = map(int, input_value.split('/'))
+print(f"{a}/{b} -> ", end="")
+a, b = parent(a, b)
+print(f"{a}/{b} -> ", end="")
+a, b = parent(a, b)
+print(f"{a}/{b}")
diff --git a/challenge-147/paulo-custodio/perl/ch-1.pl b/challenge-147/paulo-custodio/perl/ch-1.pl
index 85b81d6210..76794b7c9b 100644
--- a/challenge-147/paulo-custodio/perl/ch-1.pl
+++ b/challenge-147/paulo-custodio/perl/ch-1.pl
@@ -2,7 +2,7 @@
 
 # Challenge 147
 #
-# TASK #1 › Truncatable Prime
+# TASK #1 > Truncatable Prime
 # Submitted by: Mohammad S Anwar
 # Write a script to generate first 20 left-truncatable prime numbers in base 10.
 #
diff --git a/challenge-147/paulo-custodio/perl/ch-2.pl b/challenge-147/paulo-custodio/perl/ch-2.pl
index f81f51987d..3f9ad91939 100644
--- a/challenge-147/paulo-custodio/perl/ch-2.pl
+++ b/challenge-147/paulo-custodio/perl/ch-2.pl
@@ -2,7 +2,7 @@
 
 # Challenge 147
 #
-# TASK #2 › Pentagon Numbers
+# TASK #2 > Pentagon Numbers
 # Submitted by: Mohammad S Anwar
 # Write a script to find the first pair of Pentagon Numbers whose sum and
 # difference are also a Pentagon Number.
diff --git a/challenge-147/paulo-custodio/python/ch-1.py b/challenge-147/paulo-custodio/python/ch-1.py
new file mode 100644
index 0000000000..f3982a0174
--- /dev/null
+++ b/challenge-147/paulo-custodio/python/ch-1.py
@@ -0,0 +1,36 @@
+#!/usr/bin/env python3
+
+# Challenge 147
+#
+# TASK #1 > Truncatable Prime
+# Submitted by: Mohammad S Anwar
+# Write a script to generate first 20 left-truncatable prime numbers in base 10.
+#
+# In number theory, a left-truncatable prime is a prime number which, in a given
+# base, contains no 0, and if the leading left digit is successively removed,
+# then all resulting numbers are primes.
+#
+# Example
+# 9137 is one such left-truncatable prime since 9137, 137, 37 and 7 are all
+# prime numbers.
+
+from sympy import isprime, nextprime
+
+def left_truncatable_prime_it():
+    prime = None
+    while True:
+        prime = nextprime(prime) if prime is not None else 2
+        if is_left_truncatable_prime(prime):
+            yield prime
+
+def is_left_truncatable_prime(p):
+    while True:
+        if not isprime(p):
+            return False
+        p = int(str(p)[1:]) if len(str(p)) > 1 else ''
+        if p == '':
+            return True
+
+it = left_truncatable_prime_it()
+out = [next(it) for _ in range(20)]
+print(", ".join(map(str, out)))
diff --git a/challenge-147/paulo-custodio/python/ch-2.py b/challenge-147/paulo-custodio/python/ch-2.py
new file mode 100644
index 0000000000..87ee1d7626
--- /dev/null
+++ b/challenge-147/paulo-custodio/python/ch-2.py
@@ -0,0 +1,43 @@
+#!/usr/bin/env python3
+
+# Challenge 147
+#
+# TASK #2 > Pentagon Numbers
+# Submitted by: Mohammad S Anwar
+# Write a script to find the first pair of Pentagon Numbers whose sum and
+# difference are also a Pentagon Number.
+#
+# Pentagon numbers can be defined as P(n) = n(3n - 1)/2.
+#
+# Example
+# The first 10 Pentagon Numbers are:
+# 1, 5, 12, 22, 35, 51, 70, 92, 117 and 145.
+#
+# P(4) + P(7) = 22 + 70 = 92 = P(8)
+# but
+# P(4) - P(7) = |22 - 70| = 48 is not a Pentagon Number.
+
+limit = 100_000_000
+
+pentagon = [1]
+is_pentagon = {}
+
+def find_pair():
+    is_pentagon_func(limit)  # build pentagon up to N
+    try_ = pentagon.copy()
+    for a in try_:
+        for b in try_:
+            if is_pentagon_func(a + b) and is_pentagon_func(abs(a - b)):
+                return a, b
+    raise Exception("No pair found")
+
+def is_pentagon_func(num):
+    while pentagon[-1] < num:
+        n = len(pentagon) + 1
+        p = n * (3 * n - 1) // 2
+        pentagon.append(p)
+        is_pentagon[p] = True
+    return is_pentagon.get(num, False)
+
+a, b = find_pair()
+print(f"({a},{b})")