This article is about some programming exercises. If you are a learner and learning Data Stricture and OOP in Python, it may be helpful for you. I am going to solve two problems and try to explain as much as possible. I assume that you know the Python programming basics and OOP basics as well. I got the idea of these two problems from the course Algorithms, Part I in Coursera. 

Problem 1

Develop an algorithm that takes two lists of coordinates and returns their intersection. We need to find the common coordinates in both the lists.

Solution

There are 4 steps to solve this problem

1. Concatenate the two lists and make one list out of two lists.
2. Sort this merged list by x coordinated first and then by y coordinates. So, if there are any common items they will be side by side.
3. Then return duplicate coordinates.

Here is the complete code below. The function ‘concArray’ will concatenate the lists. The function ‘sortList’ will sort the coordinates. The function ‘clash’ will return if two consecutive coordinates are the same.

class Intersection():
    def __init__ (self, sets):
        self.sets = sets

def concArrays(self):
        self.sets = self.sets[0] + self.sets[1]
        return self.sets

def sortList(self):
        self.sets = sorted(self.sets, key=lambda x: x[0])
        return sorted(self.sets, key=lambda x: x[1])

def clash(self):
return [self.sets[i] for i in range(0, len(self.sets)-1) if self.sets[i] == self.sets[i+1]]

Let’s check if the algorithm works properly:

sets = [[(2,4),(5,3),(2,6),(6,2),(4,9)],[(4,9),(10,8),(9,3),(5,3),(1,7)]]
inter = Intersection(sets)
inter.concArrays()
inter.sortList()
print(inter.clash())

It returns [(4, 9), (5, 3)]. If you notice in our sets variable, these are the two common coordinates. As our lists are not too big we can check just by looking at it.

Problem 2

Given a list of n buckets, each containing blue, white or red pebble. Sort them by color in the order of red, white, and blue.

Solution

There might be different ways of solution to it. I am showing two solutions. The first one is using a sorting algorithm. Here I used insertion sort. Any other sorting algorithm will work in the same way.

Here are the steps:

1. Make a dictionary where colors are the keys and values are the integers.
2. In the sorting algorithm, use the values from the dictionary while comparing two colors.

Here is the complete code:

def sortColor(a):
    color = {'red': 1, 'white': 2, 'blue': 3}
    for i in range(1, len(a)):
        value = a[i]
        hole = i
        while (hole > 0) and (color[a[hole -1]]>color[value]):
            a[hole] = a[hole -1]
            hole = hole -1
        a[hole] = value
    return a

Check this algorithm with the following list of colors:

print(sortColor(['red', 'white', 'red', 'blue', 'white', 'blue']))

The output was perfect. Please try it.

I want to show a two-liner solution as well. If you know how to use lambda, this is for you.

def sortColor1(a):
    color = {'red': 1, 'white': 2, 'blue': 3}
    return sorted(a, key=lambda x: a[color[x]], reverse=True)

I hope it was helpful.

Additional reading:

1. Use of Lambda, Map, and Filter in Python.

#programming  #Python #algorithm  #sortingAlgorithm