aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-074/paulo-custodio/perl/ch-1.pl2
-rw-r--r--challenge-074/paulo-custodio/perl/ch-2.pl32
-rw-r--r--challenge-074/paulo-custodio/python/ch-1.py45
-rw-r--r--challenge-074/paulo-custodio/python/ch-2.py54
-rw-r--r--challenge-075/paulo-custodio/perl/ch-1.pl2
-rw-r--r--challenge-075/paulo-custodio/perl/ch-2.pl2
-rw-r--r--challenge-075/paulo-custodio/python/ch-1.py47
-rw-r--r--challenge-075/paulo-custodio/python/ch-2.py77
-rw-r--r--challenge-146/paulo-custodio/perl/ch-1.pl2
-rw-r--r--challenge-146/paulo-custodio/python/ch-1.py11
-rw-r--r--challenge-146/paulo-custodio/python/ch-2.py42
-rw-r--r--challenge-147/paulo-custodio/perl/ch-1.pl2
-rw-r--r--challenge-147/paulo-custodio/perl/ch-2.pl2
-rw-r--r--challenge-147/paulo-custodio/python/ch-1.py36
-rw-r--r--challenge-147/paulo-custodio/python/ch-2.py43
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})")
generated by cgit (git 2.34.1) at 2026-07-01 10:38:35 +0000