From 6aa5c270464f36c0fb846c3dfd8b95db8dc2fa66 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Tue, 5 Apr 2022 21:25:55 +0100 Subject: - Added guest contributions by Eric Cheung. --- challenge-159/eric-cheung/python/ch-1.py | 65 +++++++++++++++++++++++++++++ challenge-159/eric-cheung/python/ch-2.py | 70 ++++++++++++++++++++++++++++++++ 2 files changed, 135 insertions(+) create mode 100755 challenge-159/eric-cheung/python/ch-1.py create mode 100755 challenge-159/eric-cheung/python/ch-2.py (limited to 'challenge-159/eric-cheung/python') diff --git a/challenge-159/eric-cheung/python/ch-1.py b/challenge-159/eric-cheung/python/ch-1.py new file mode 100755 index 0000000000..84e4d54b07 --- /dev/null +++ b/challenge-159/eric-cheung/python/ch-1.py @@ -0,0 +1,65 @@ +## Remarks +## https://www.geeksforgeeks.org/farey-sequence/ + +## Python3 program to print +## Farey Sequence of given order + +## Class for fraction x / y (a term in farey sequence) +class Term: + + ## Constructor to initialize + ## x and y in x / y + def __init__(self, x, y): + self.x = x + self.y = y + + +## GCD of a and b +def gcd(a, b): + if b == 0: + return a + + return gcd(b, a % b) + +## Function to print +## Farey sequence of order n +def farey(n): + + ## Create a vector to store terms of output + v = [] + + ## One by one find and store all terms except 0 / 1 and n / n which are known + for i in range(1, n + 1): + for j in range(i + 1, n + 1): + + ## Checking whether i and j are in lowest term + if gcd(i, j) == 1: + v.append(Term(i, j)) + + ## Sorting the term of sequence + for i in range(len(v)): + for j in range(i + 1, len(v)): + if (v[i].x * v[j].y > v[j].x * v[i].y): + v[i], v[j] = v[j], v[i] + + ## Explicitly printing first term + print("0 / 1", end = " ") + + ## Printing other terms + for i in range(len(v)): + print("%d/%d" % (v[i].x, v[i].y), end = " ") + + ## explicitly printing last term + print("1/1") + + +# Driver Code +if __name__ == "__main__": + ## n = 5 ## Example 1: + ## n = 7 ## Example 2: + n = 4 ## Example 3: + + print("Farey sequence of order %d is" % n) + farey(n) + +## This code is contributed by sanjeev2552 diff --git a/challenge-159/eric-cheung/python/ch-2.py b/challenge-159/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..4e19c591df --- /dev/null +++ b/challenge-159/eric-cheung/python/ch-2.py @@ -0,0 +1,70 @@ +## Remarks +## https://www.geeksforgeeks.org/program-mobius-function/ + +## Python program to evaluate +## Mobius def M(N) = 1 if N = 1 +## M(N) = 0 if any prime factor of N is contained twice +## M(N) = (-1) ^ (no of distinct prime factors) + + +import math + + +## def to check if n is prime or not +def isPrime(n) : + + if (n < 2) : + return False + + for i in range(2, n + 1) : + if (n % i == 0) : + return False + + i = i * i + + return True + + +def mobius(n) : + + p = 0 + + ## Handling 2 separately + if (n % 2 == 0) : + + n = int(n / 2) + p = p + 1 + + ## If 2^2 also divides N + if (n % 2 == 0) : + return 0 + + ## Check for all other prime factors + for i in range(3, int(math.sqrt(n)) + 1) : + + ## If i divides n + if (n % i == 0) : + + n = int(n / i) + p = p + 1 + + ## If i ^ 2 also divides N + if (n % i == 0) : + return 0 + + i = i + 2 + + if(p % 2 == 0) : + return -1 + + return 1 + +## Driver Code +## N = 5 ## Example: 1 +## N = 10 ## Example: 2 +N = 20 ## Example: 3 + +print ("Mobius defs M(N) at N = {} is: {}\n" . format(N, mobius(N))); + + +## This code is contributed by Manish Shaw (manishshaw1) -- cgit From 6e220136f3cd0b6189d3ea501127ae7b8531b0c6 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Mon, 11 Apr 2022 19:25:14 +0100 Subject: - Added guest contributions by Eric Cheung. --- challenge-159/eric-cheung/python/ch-1.py | 98 +++++++++++++++++--------------- challenge-159/eric-cheung/python/ch-2.py | 87 ++++++++++------------------ 2 files changed, 81 insertions(+), 104 deletions(-) (limited to 'challenge-159/eric-cheung/python') diff --git a/challenge-159/eric-cheung/python/ch-1.py b/challenge-159/eric-cheung/python/ch-1.py index 84e4d54b07..82de733403 100755 --- a/challenge-159/eric-cheung/python/ch-1.py +++ b/challenge-159/eric-cheung/python/ch-1.py @@ -1,65 +1,71 @@ ## Remarks -## https://www.geeksforgeeks.org/farey-sequence/ +## https://rosettacode.org/wiki/Four_is_magic#Python -## Python3 program to print -## Farey Sequence of given order +from collections import OrderedDict + +numbers = {1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine'} -## Class for fraction x / y (a term in farey sequence) -class Term: +numbers = OrderedDict(sorted(numbers.items(), key = lambda t: t[0], reverse = True)) - ## Constructor to initialize - ## x and y in x / y - def __init__(self, x, y): - self.x = x - self.y = y +def string_representation(i: int) -> str: + """ + Return the english string representation of an integer + """ + if i == 0: + return "zero" + words = ['negative'] if i < 0 else [] -## GCD of a and b -def gcd(a, b): - if b == 0: - return a + working_copy = abs(i) - return gcd(b, a % b) + for key, value in numbers.items(): + if key <= working_copy: + times = int(working_copy / key) + + if key >= 100: + words.append(string_representation(times)) -## Function to print -## Farey sequence of order n -def farey(n): + words.append(value) + working_copy -= times * key - ## Create a vector to store terms of output - v = [] + if working_copy == 0: + break + + return " ".join(words) - ## One by one find and store all terms except 0 / 1 and n / n which are known - for i in range(1, n + 1): - for j in range(i + 1, n + 1): - ## Checking whether i and j are in lowest term - if gcd(i, j) == 1: - v.append(Term(i, j)) +def next_phrase(i: int): + """ + Generate all the phrases + """ + while not i == 4: # Generate phrases until four is reached + str_i = string_representation(i) + len_i = len(str_i) - ## Sorting the term of sequence - for i in range(len(v)): - for j in range(i + 1, len(v)): - if (v[i].x * v[j].y > v[j].x * v[i].y): - v[i], v[j] = v[j], v[i] + yield str_i, "is", string_representation(len_i) - ## Explicitly printing first term - print("0 / 1", end = " ") + i = len_i + + ## The Last Phrase + yield string_representation(i), "is", "magic" + + +def magic(i: int) -> str: + phrases = [] - ## Printing other terms - for i in range(len(v)): - print("%d/%d" % (v[i].x, v[i].y), end = " ") + for phrase in next_phrase(i): + phrases.append(" ".join(phrase)) - ## explicitly printing last term - print("1/1") + return f'{", ".join(phrases)}.'.capitalize() -# Driver Code -if __name__ == "__main__": - ## n = 5 ## Example 1: - ## n = 7 ## Example 2: - n = 4 ## Example 3: +## Driver Code + +## nInput = 5 ## Example 1: +## nInput = 7 ## Example 2: +nInput = 6 ## Example 3: + +strMsg = magic(nInput) - print("Farey sequence of order %d is" % n) - farey(n) +print (strMsg) -## This code is contributed by sanjeev2552 diff --git a/challenge-159/eric-cheung/python/ch-2.py b/challenge-159/eric-cheung/python/ch-2.py index 4e19c591df..220bf69b97 100755 --- a/challenge-159/eric-cheung/python/ch-2.py +++ b/challenge-159/eric-cheung/python/ch-2.py @@ -1,70 +1,41 @@ ## Remarks -## https://www.geeksforgeeks.org/program-mobius-function/ +## https://www.geeksforgeeks.org/equilibrium-index-of-an-array/ -## Python program to evaluate -## Mobius def M(N) = 1 if N = 1 -## M(N) = 0 if any prime factor of N is contained twice -## M(N) = (-1) ^ (no of distinct prime factors) +## Python Program to Find Equilibrium Index of an Array +## Function to Find the Equilibrium Index +def equilibrium(arr): + leftsum = 0 + rightsum = 0 -import math + n = len(arr) + ## Check for Indexes one by one until an equilibrium index is found + for i in range(n): + leftsum = 0 + rightsum = 0 -## def to check if n is prime or not -def isPrime(n) : + ## Get Left Sum + for j in range(i): + leftsum = leftsum + arr[j] - if (n < 2) : - return False + ## Get Right Sum + for j in range(i + 1, n): + rightsum = rightsum + arr[j] - for i in range(2, n + 1) : - if (n % i == 0) : - return False - - i = i * i - - return True - - -def mobius(n) : - - p = 0 - - ## Handling 2 separately - if (n % 2 == 0) : - - n = int(n / 2) - p = p + 1 - - ## If 2^2 also divides N - if (n % 2 == 0) : - return 0 - - ## Check for all other prime factors - for i in range(3, int(math.sqrt(n)) + 1) : - - ## If i divides n - if (n % i == 0) : - - n = int(n / i) - p = p + 1 - - ## If i ^ 2 also divides N - if (n % i == 0) : - return 0 - - i = i + 2 - - if(p % 2 == 0) : - return -1 - - return 1 + ## If Left Sum and Right Sum are same, then we are done + if leftsum == rightsum: + return i + + ## return -1 if no equilibrium index is found + return -1 + ## Driver Code -## N = 5 ## Example: 1 -## N = 10 ## Example: 2 -N = 20 ## Example: 3 +arr = [1, 3, 5, 7, 9] ## Example 1: +## arr = [1, 2, 3, 4, 5] ## Example 2: +## arr = [2, 4, 2] ## Example 3: -print ("Mobius defs M(N) at N = {} is: {}\n" . format(N, mobius(N))); +print (equilibrium(arr)) - -## This code is contributed by Manish Shaw (manishshaw1) +## This code is contributed by Abhishek Sharama -- cgit