-
Notifications
You must be signed in to change notification settings - Fork 0
/
task1.py
99 lines (69 loc) · 3.35 KB
/
task1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#Name: Russell Sammut-Bonnici
#ID: 0426299(M)
#Task: 1
import random #used for choosing random pivot
#class for storing pair's details
class Pair:
#initialises product pair
def __init__(self,a,b):
self.a = a
self.b = b
self.product = a*b
#recursive method for sorting pairs by products
def sortByProduct(objList):
#base case for when segment's length is less than or equal to one
if(len(objList)<=1):
return objList
smaller=[] #initialized for storing the smaller segment of the list
equivalent=[] #initialized for storing the element at the pivot
greater=[] #initialized for storing the greater segment of the list
#randomly chosen pivot selected from list of pairs
pivot = objList[random.randint(0,len(objList)-1)]
#for loop to go through the list of pairs
for x in objList:
#when x is less, append to smaller segment
if(x.product < pivot.product):
smaller.append(x)
#when x is at the pivot, store element into equivalent
elif(x.product==pivot.product):
equivalent.append(x)
#when x is greater, append to greater segment
elif(x.product > pivot.product):
greater.append(x)
else:
print("An unknown error has occurred during sorting by Product")
#recursively calls method to work on the smaller and greater segment, then returns on backtracking
return sortByProduct(smaller) + equivalent + sortByProduct(greater)
#method for finding product matches
def findProductMatches(rangeList):
pairList = [] #initialized for storing products pairs and their components
# outer loop for a equivalent
for x in rangeList:
# inner loop for b equivalent
for y in rangeList:
if(y>x): #condition to avoid repeated a*b combinations
pairList.append(Pair(x,y))
pairList = sortByProduct(pairList) #sorts by product using quick sort
i = 0 #initialized index to 0
#goes through every index in the pairList array
while(i<len(pairList)):
#Accesses this during the last iteration when the last index has no matching products. Avoids OutOfIndex exception, iterates to exit loop
if(i==len(pairList)-1):
i+=1
#If pair at index has a unique product, skips cause no matches
elif(pairList[i].product != pairList[i+1].product):
i+=1
#If current pair is seen to have at least one match, access while loop
elif(pairList[i].product == pairList[i+1].product):
print("The pair [%d*%d = %d] matches with"%(pairList[i].a, pairList[i].b, pairList[i].product)),
#traverses through products, displaying the matches until there are no more (stops when at the end)
while(i!=len(pairList)-1 and pairList[i].product == pairList[i+1].product):
print("[%d*%d = %d] and"%(pairList[i+1].a, pairList[i+1].b, pairList[i+1].product)),
i+=1
print(",") #prints comma indicating end of line
#else statement used for unconsidered scenarios
else:
print("Error: something wrong has occurred during printing.")
return 0
print("Matching products from 1 to 1024 are;")
findProductMatches(range(1, 1025)) #or (range(1,26))