Question

Python question

It is required to make a function

biggest_vert_group(vert)

that consumes vert, which is a list of list of integers containing the coordinates of the consecutive vertices of a polygon. The function should return the size of the largest group of same length edges.

This function must have a big-o runtime of O(n) where n is the length of vert

Example

biggest_vert_group([[0,0],[1,1],[0,2],[-2,3],[-1,2]]) => 3

only library allowed to be imported is math. list comprehensions, sets and/or enumerators are Forbidden from getting used. Mutating passed parameters are also restricted.

Answer 1

Hello dear....

Here is the perfectly working Python 3 program for the given task by following all the conditions. And the runtime of funtion is O(n) where n is the length of vert. I have also written comments for better understaning. Also attached images of output and code for comfort of reading. Hope you will like it.

same_length_edges.py

import math

#function returns the length of edge between  two given vertices
def length_of_edge(a,b):
    #calculate and return length of edge according to the formula
    return math.sqrt( (a[0]-b[0])**2 + (a[1]-b[1])**2 )

#function returns the size of largest group of same length edges
def biggest_vert_group(vert):
    #a dictionary variable to store count of same length edges
    sameLengthEdgesCount = {}
    #prev variable to calculate distance, initialized with last element
    prev = vert[-1]
    #initially taking maximum count = 1
    maxCount = 1
    #traverse though the given list
    for i in vert:
        #calculate the length of edge between current vertex and previous vertex
        length =  length_of_edge(prev, i)
        #if the 'length' is already in sameLengthEdgesCount dictionary
        if(length in sameLengthEdgesCount):
            #increment count for that length
            sameLengthEdgesCount[length] += 1
            #if the count of that length of greater than maxCount
            if(maxCount < sameLengthEdgesCount[length]):
                #update maxcount
                maxCount = sameLengthEdgesCount[length]
        #else add an item with length as key and 1 as value
        else:
            sameLengthEdgesCount[length] = 1
        #make current vertex as prev vertex
        #so that we can use it to calculate length of the edge in next iteration
        prev = i
    #return max count
    return maxCount


#create a list of vertices
vert = [[0,0],[1,1],[0,2],[-2,3],[-1,2]]
#call biggest_vert_group() function with above list and print the returned value
print(biggest_vert_group(vert))

Output:

3 >>

Image of code:

import math 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 #function returns the length of edge between two given vertices def length_of_edge(a,b): #calculate and return length of edge according to the formula return math.sqrt( (a[@]-b[@]) **2 + (a[1]-b[1]) **2 ) #function returns the size of largest group of same length edges def biggest_vert_group(vert): #a dictionary variable to store count of same length edges sameLengthEdgesCount = {} #prev variable to calculate distance, initialized with last element prev = vert[-1] #initially taking maximum count = 1 maxCount = 1 #traverse though the given list for i in vert: #calculate the length of edge between current vertex and previous vertex length = length_of_edge (prev, i) #if the 'length is already in sameLengthEdgesCount dictionary if(length in sameLengthEdgesCount): #increment count for that length sameLengthEdgesCount[length] += 1 #if the count of that length of greater than maxCount if(maxCount <sameLengthEdgesCount[length]): #update maxcount maxCount = sameLengthEdgesCount[length] #else add an item with length as key and 1 as value else: sameLengthEdgesCount[length] = 1 #make current vertex as prev vertex #so that we can use it to calculate length of the edge in next iteration prev = i #return max count return maxCount #create a list of vertices vert = [[0,0],[1,1],[0,2],[-2,3],[-1,2]] #call biggest_vert_group() function with above list and print the returned value print(biggest_vert_group(vert))

(Note: If you lose indentations while copying the code, adjust according to the above image)

Hope you like it.

If you have any doubts ask me in comment section.

If you like my work, please give me a like and feedback. That helps me a lot. Thank you.

All the best.