# Rectangle class

** **ASSIGNMENT 5

**********************************************

PART 1

**********************************************

For this part, you will be solving some problems and implementing the solutions. For this part, yourgoal is to design and implement solutions that are as fast as possible, and to analyze these solutions aswell. You will submit two files:

a5_part1_xxxxxx.py needs to contain the functions you are asked to write for each question.

a5_part1_xxxxxx.txtneeds to contain, for each function, a rough analysis of its running time in termsof n (where n is the length of the input list a, i.e. n=len(a)) and where n=10,000. For example, if yourfunction looks like this:

def riddle(a):

s=0

for x in a:

for y in a:

s = s+ x*y

return s

Then you would write: This function has two nested for loops. The inner loop executes 10,000 times foreach step of the outer loop, which also executes 10,000 times. Therefore, this function performsroughly 10,000*10,000=100,000,000 operations. If your function uses Python’s sort() method orPython’s sorted() function to sort the list a, just say that that function call does about 140,000operations (since Python’s sort does roughly n log_2 n operations).

Alternatively, you can write your analysis in terms of general n. Thus for the above

function riddle, one would say that its running time is O(n^2).

In all of the questions below you may assume that a,is a list containing numbers.

1a) Write a function, largest_34(a), that returns the sum of the 3rd and 4th largest values in

the list a. For simplicity, you may assume that the numbers in the list aare all distinct and that the lista has at least 4 elements. For example:

>>> largest_34([1000, 1, 100, 2, 99, 200, -100])

199

1b) Write a function, largest_third(a), that computes the sum of the len(a)//3 of the

largest values in the list a. For simplicity, you may assume that the numbers in the list aare all distinctand that the list a has at least 3 elements.

1c) Write a function, third_at_least(a), that returns a value in a that occurs at least

len(a)//3 + 1 times. If no such element exists in a, then this function returns None. If more than

one such element exists, you should return the smaller one. For simplicity, you may assume that thelist a has at least 4 elements.

1d) Write a function, sum_tri(a,x), that takes a list , a, as input and returns True if there

exists indices i, j and k (where i and j and k are not necessarily distinct) such that a[i]+a[j]+a[k]=x.

Otherwise it returns False. For example, if a=[1, 5, 8, 2, 6, 55, 90] and x=103, then sum_tri(a, x)

would return True since a[1]+a[2]+a[6]=5+8+90=103. If a=[-1, 1, 5, 8, 2, 6] and x=-3, sum_tri(a, x)would return True since a[0]+a[0]+a[0]=-1+ -1 + -1 = -3. If a=[-10,2] and x=-18, sum_tri(a, x) wouldreturn True since a[0]+a[0]+a[1]=-10+-10+2=18. If a=[1, 1, 5, 8, 2, 6] and x=1000 would return False,since there are not indices i, j and k such that a[i]+a[j]+a[k]=1000.

ASSIGNMENT 5

**********************************************

PART 2

**********************************************

For this part, you are provided with 3 files: a5_part2_xxxxxx.py, a5_part2_testing_given.txt and

drawings_part2.pdf

File a5_part2_xxxxxx.py already contains a class Point that we developed in class. For this part, youwill need to develop and add two more classes to a5_part2_xxxxxx.py: class Rectangle and classCanvas.

To understand how they should be designed and how they should behave, you must study in detail thetest cases provided in a3_part2_testing_given.txt. These tests are your main resource in understandingwhat methods your two classes should have and what their input parameters are.

===========================================================

Details about the two classes:

===========================================================

Class Rectangle represents a 2D (axis-parallel) rectangle that a user can draw on a computer screen.

Think of a computer screen as a plane where each position has an x and a y coordinate.

The data (i.e. attributes) that each object of type Rectangle should have (and that should be

initialized in the constructor, i.e., __init__ method of the class Rectangle) are:

* two Points: the first point representing the bottom left corner of the rectangle and the secondrepresenting the top right corner of the rectangle; and,

* the color of the rectangle

Note that the two points (bottom left and top right) completely determine (the axis parallel) rectangleand its position in the plane. There is no default rectangle.

The __init__ method of Rectangle (that is called by the constructor Rectangle) will take two objects oftype Point as input and a string for the color). You may assume that the first Point (passed to theconstructor, i.e. __init__) will always have smaller than or equal x coordinate than the x coordinate ofthe second Point and smaller than or equal y coordinate than the y coordinate of the second Point.

Class Rectangle should have 13 methods. In particular, in addition to the constructor (i.e. __init__method) and three methods that override python’s object methods (and make your class user friendlyas suggested by the test cases), your class should contain the following 9 methods:

get_bottom_left, get_top_right, get_color, reset_color, get_perimeter, get_area, move, intersects,and contains.

Here is a description of three of those methods whose job may not be obvious from the test cases.

* Method move: given numbers dx and dy this method moves the calling rectangle by dx in the xdirection and by dy in the y-direction. This method should not change directly the coordinates of thetwo corners of the calling rectangle, but must instead call move method from the Point class.

ASSIGNMENT 5

* Method intersects: returns True if the calling rectangle intersects the given rectangle and Falseotherwise. Definition: two rectangles intersect if they have at least one point in common, otherwisethey do not intersect.

* Method contains: given an x and a y coordinate of a point, this method tests if that point is inside ofthe calling rectangle. If yes it returns True and otherwise False. (A point on the boundary of therectangle is considered to be inside).

==========================================================================

Class Canvas represents a collection of Rectangles. It has 8 methods. In addition, to the constructor(i.e. __init__ method) and two methods that override python’s object methods (and make your classuser friendly as suggested by the test cases), your class should contain 5 more methods:

add_one_rectangle, count_same_color, total_perimeter, min_enclosing_rectangle, and common_point.

Here is a description of those methods whose job may not be obvious from the test cases.

* The method total_perimeter: returns the sum of the perimeters of all the rectangles in the callingcanvas. To compute total perimeter do not compute a perimeter of an individual rectangle in the bodyof total_perimeter method. Instead use get_perimeter method from the Rectangle class.

* Method min_enclosing_rectangle: calculates the minimum enclosing rectangle that contains all therectangles in the calling canvas. It returns an object of type Rectangle of any color you prefer. To findminimum enclosing rectangle you will need to find the minimum x coordinate of all rectangles, themaximum x coordinate for all rectangles, the minimum y coordinate and the maximum y coordinate ofall rectangles.

* Method common_point: returns True if there exists a point that intersects all rectangles in the callingcanvas.

**********************************************

PART 3

**********************************************

Implement a recursive python function digit_sum(n) to calculate the sum of all digits of the

given non-negative integer n.

Then, implement a recursive python function to compute the digital root digital_root(n) of the

given integer n. Your function must use the digit_sumfunction.

The digital root of a number is calculated by taking the sum of all of the digits in a number,

and repeating the process with the resulting sum until only a single digit remains. For

example, if you start with 1969, you must first add 1+9+6+9 to get 25. Since the value 25 has

more than a single digit, you must repeat the operation to obtain 7 as a final answer.

Your function digital_root(n) must use digit_sumfunction. Place both functions in the same file

a5_part3_xxxxxx.py.

ASSIGNMENT 5

**********************************************

BONUS

**********************************************

To get the bonus or parts of it, you will need to redo some parts of Assignment 4 but by designing andusing objects with a small change that when creating a network, you will need to read 2 files, one as inAssignment 4, and one containing user IDs and theirnames. As before you have astarter code in a5_bonus_xxxxxx.py.Your code must go inside of that file in clearly indicated spaces.

As always you cannot erase of modify any parts of the given code except for word “pass”.

**a5_part2_xxxxxx.py**

class Point:

‘class that represents a point in the plane’

def __init__(self, xcoord=0, ycoord=0):

”’ (Point,number, number) -> None

initialize point coordinates to (xcoord, ycoord)”’

self.x = xcoord

self.y = ycoord

defsetx(self, xcoord):

”’ (Point,number)->None

Sets x coordinate of point to xcoord”’

self.x = xcoord

defsety(self, ycoord):

”’ (Point,number)->None

Sets y coordinate of point to ycoord”’

self.y = ycoord

def get(self):

”'(Point)->tuple

Returns a tuple with x and y coordinates of the point”’

return (self.x, self.y)

def move(self, dx, dy):

”'(Point,number,number)->None

changes the x and y coordinates by dx and dy”’

self.x += dx

self.y += dy

def __eq__(self, other):

”'(Point,Point)->bool

Returns True if self and other have the same coordinates”’

returnself.x == other.x and self.y == other.y

def __repr__(self):

”'(Point)->str

Returns canonical string representation Point(x, y)”’

return ‘Point(‘+str(self.x)+’,’+str(self.y)+’)’

def __str__(self):

”'(Point)->str

Returns nice string representation Point(x, y).

In this case we chose the same representation as in __repr__”’

return ‘Point(‘+str(self.x)+’,’+str(self.y)+’)’

**a5_bonus_xxxxxx.py**** **

class Person:

# YOUR CODE GOES HERE

pass

class Network:

# YOUR CODE GOES HERE

pass

defget_int():

”’None->int or None”’

num = None

try:

num=int(input(“Enter an integer for a user ID:”).strip())

exceptValueError:

print(“That was not an integer. Please try again.”)

returnnum

defis_valid_file_name():

”’None->str or None”’

file_name = None

try:

file_name=input(“Enter the name of the file: “).strip()

f=open(file_name)

f.close()

exceptFileNotFoundError:

print(“There is no file with that name. Try again.”)

file_name=None

returnfile_name

defget_file_name():

”'()->str”’

file_name=None

whilefile_name==None:

file_name=is_valid_file_name()

returnfile_name

##############################

# main

##############################

print(“Let’s get first file that contains IDs and names:”)

file_name1=get_file_name()

print(“Let’s get the 2nd file that contains pairs of friends as in Assignment 4”)

file_name2=get_file_name()

net=Network(file_name1,file_name2)

print(“Here are all the people in the network, if the network has at most 20 users:”)

iflen(net)<=20:

print(net)

print(“\nLet’s recommend a friend for a user you specify.”)

uid=net.get_uid()

rec=net.recommend(uid)

if rec==None:

print(“We have nobody to recommend for user with ID”, uid, “since he/she is dominating in their connected component”)

else:

print(“For user with ID”, uid,”we recommend the user with ID”,rec)

print(“That is because users”, uid, “and”,rec, “have”, len(net.getCommonFriends(uid,rec)), “common friends and”)

print(“user”, uid, “does not have more common friends with anyone else.”)

print(“\nFinally, you showed interest in knowing common friends of some pairs of users.”)

print(“About 1st user …”)

uid1=net.get_uid()

print(“About 2st user …”)

uid2=net.get_uid()

print(“Here is the list of common friends of”, uid1, “and”, uid2)

common=net.getCommonFriends(uid1,uid2)

for item in common:

print(item, end=” “)** **

**Solution**** **

**a5_part1_xxxxxx.py**

def largest_34(a):

”’ (list)->number ”’

n = 4

# selection sort to find n largest numbers

for i in range(n):

jMax = i

for j in range(i + 1, len(a)):

if a[j] > a[i]: # find the next largest number

jMax = j

a[i], a[jMax] = a[jMax], a[i] # swap

return a[2] + a[3]

deflargest_third(a):

”’ (list) -> number ”’

n = len(a) // 3

a.sort(reverse=True) # ascending order

return sum(a[:n])

defthird_at_least(a):

”’ (list) -> number or None”’

thirds = []

a.sort()

current = a[0]

count = 0 # the number of occurences of current in a

for x in a: # a is sorted

if x == current:

count = count + 1

else:

if count >len(a) // 3:

thirds.append(current)

current = x # change the current number to x

count = 1 # reset count

if thirds: # at most 2 elements

return min(thirds)

else:

return None

defsum_tri(a, x):

”’ (list, int)->bool ”’

a.sort()

for i in range(len(a)):

for j in range(len(a)):

if x – (a[i] + a[j]) in a: # serch the third one

return True

return False # not found** **

**a5_part2_xxxxxx.py**** **

class Point:

‘class that represents a point in the plane’

def __init__(self, xcoord=0, ycoord=0):

”’ (Point,number, number) -> None

initialize point coordinates to (xcoord, ycoord)”’

self.x = xcoord

self.y = ycoord

defsetx(self, xcoord):

”’ (Point,number)->None

Sets x coordinate of point to xcoord”’

self.x = xcoord

defsety(self, ycoord):

”’ (Point,number)->None

Sets y coordinate of point to ycoord”’

self.y = ycoord

def get(self):

”'(Point)->tuple

Returns a tuple with x and y coordinates of the point”’

return (self.x, self.y)

def move(self, dx, dy):

”'(Point,number,number)->None

changes the x and y coordinates by dx and dy”’

self.x += dx

self.y += dy

def __eq__(self, other):

”'(Point,Point)->bool

Returns True if self and other have the same coordinates”’

returnself.x == other.x and self.y == other.y

def __repr__(self):

”'(Point)->str

Returns canonical string representation Point(x, y)”’

return ‘Point(‘+str(self.x)+’,’+str(self.y)+’)’

def __str__(self):

”'(Point)->str

Returns nice string representation Point(x, y).

In this case we chose the same representation as in __repr__”’

return ‘Point(‘+str(self.x)+’,’+str(self.y)+’)’

class Rectangle:

‘class that represents a rectangle in the plane’

def __init__(self, bottom_left, top_right, color):

”’ (Rectangle,Point,Point,str) -> None ”’

self.bottom_left = bottom_left

self.top_right = top_right

self.color = color

defget_bottom_left(self):

”’ (Rectangle) -> Point ”’

returnself.bottom_left

defget_top_right(self):

”’ (Rectangle) -> Point ”’

returnself.top_right

defget_color(self):

”’ (Rectangle) ->str ”’

returnself.color

defreset_color(self, color):

”’ (Rectangle,str) -> None ”’

self.color = color

defget_perimeter(self):

”’ (Rectangle) -> number”’

xlen = self.top_right.x – self.bottom_left.x

ylen = self.top_right.y – self.bottom_left.y

return 2 * (ylen + xlen)

defget_area(self):

”’ (Rectangle) -> number”’

xlen = self.top_right.x – self.bottom_left.x

ylen = self.top_right.y – self.bottom_left.y

returnylen * xlen

def move(self, dx, dy):

”’ (Rectangle,number,number) -> None”’

self.bottom_left.move(dx, dy)

self.top_right.move(dx, dy)

def intersects(self, other):

”’ (Rectangle,Rectangle) ->bool”’

this_xlen = self.top_right.x – self.bottom_left.x

this_ylen = self.top_right.y – self.bottom_left.y

other_xlen = other.top_right.x – other.bottom_left.x

other_ylen = other.top_right.y – other.bottom_left.y

bound_xlen = max(self.top_right.x, other.top_right.x) – min(self.bottom_left.x, other.bottom_left.x)

bound_ylen = max(self.top_right.y, other.top_right.y) – min(self.bottom_left.y, other.bottom_left.y)

returnbound_xlen<= this_xlen + other_xlen and bound_ylen<= this_ylen + other_ylen

def contains(self, x, y):

”’ (Rectangle,number,number) ->bool”’

returnself.bottom_left.x<= x <= self.top_right.x and self.bottom_left.y<= y <= self.top_right.y

def __str__(self):

”’ (Rectangle) ->str”’

return (“I am a ” + self.color + ” rectangle with bottom left corner at (” +

str(self.bottom_left.x) + “, ” + str(self.bottom_left.y) + “) and top right corner at (” +

str(self.top_right.x) + “, ” + str(self.top_right.x) + “).”)

def __repr__(self):

”’ (Rectangle) ->str”’

return “Rectangle(” + repr(self.bottom_left) + “,” + repr(self.top_right) + “,'” + self.color + “‘)”

def __eq__(self, other):

”’ (Rectangle,Rectangle) ->bool”’

return ((self.bottom_left, self.top_right) == (other.bottom_left, other.top_right)

andself.color == other.color)

class Canvas:

‘class that represents a collection of Rectangles’

def __init__(self):

”’ (Canvas) -> None ”’

self.rectangles = []

defadd_one_rectangle(self, r):

”’ (Canvas,Rectangle) -> None ”’

self.rectangles.append(r)

defcount_same_color(self, color):

”’ (Canvas,str) ->int ”’

return sum(1 for r in self.rectangles if r.color == color)

deftotal_perimeter(self):

”’ (Canvas) -> number ”’

return sum(r.get_perimeter() for r in self.rectangles)

defmin_enclosing_rectangle(self):

”’ (Canvas) -> Rectangle ”’

bottom = min(r.get_bottom_left().y for r in self.rectangles)

left = min(r.get_bottom_left().x for r in self.rectangles)

top = max(r.get_top_right().y for r in self.rectangles)

right = max(r.get_top_right().x for r in self.rectangles)

return Rectangle(Point(left, bottom), Point(right, top), ‘red’)

defcommon_point(self):

”’ (Canvas) ->bool ”’

return all(r1.intersects(r2) for r1 in self.rectangles

for r2 in self.rectangles)

def __len__(self):

”’ (Canvas) ->int ”’

returnlen(self.rectangles)

def __repr__(self):

”’ (Canvas) ->str ”’

return ‘Canvas(‘ + self.rectangles + ‘)’** **

**a5_part3_xxxxxx.py**

defdigit_sum(n):

”’ (int)->int ”’

if n < 10:

return n

else:

returndigit_sum(n//10) + n % 10

defdigital_root(n):

”’ (int)->int ”’

if n < 10:

return n

else:

returndigital_root(digit_sum(n))