A wedding is being held in a huge conference hall attended by a massive number of people. The organiser has given you a list of people with their location in the conference hall at a certain snapshot. Your task is to find out, in that snapshot, who in that list has disobeyed social distancing measure and mingled with more than 8 people within a …

offenders.py

from typing import List, Tuple
import random

# Question: A wedding is being held in a huge conference hall attended by a massive number of people. The organiser has given you a list of people with their location in the conference hall at a certain snapshot. Your task is to find out, in that snapshot, who in that list has disobeyed social distancing measure and mingled with more than 8 people within a 2-metre radius.

class Person:
    """
    Class represeting a person
    ...

    Attributes
    ----------
    neighbour_matrix: list
        2D list to keep track of a person's neighbours
    id : int
        identification number of a person
    x : float
        x-coordinate of a person's location
    y : float
        y-coordinate of a person's location
    neighbour_count : int
        number of neighbours a person has within a 2 meter radius

    """

    neighbour_matrix = [
        [None] * 20000
    ] * 20000  # Initialised to have be a 20000x20000 empty list

    def __init__(self, id, x, y):
        self.id = int(id[6:])
        self.x = x
        self.y = y
        self.neighbour_count = 0

    def distance_to(self, person) -> float:
        """Function to find the distance between two persons"""
        return ((self.x - person.x) ** 2 + (self.y - person.y) ** 2) ** 0.5

    def is_neighbour(self, person) -> bool:
        """Function to check if two persons are neighbours (are within a n meter radius)"""
        return self.distance_to(person) <= 2


def snapshot(num_people: int = 20000, hall_length: int = 250, hall_breath: int = 300) -> List[Tuple[str, float, float]]:
    """There's 20,000 people in a conference hall of 250m by 300m
    Returns:
        a list of 3-tuple of Person_id, x-coordinate, y-coordinate
    """
    return [(f'Person{i:06}', random.random() * hall_length, random.random() * hall_breath,) for i in range(num_people)]


def bruteforce(persons):
    """
    Function to find the distance between all pairs of persons in the 'persons'
    list, check whether they are in the same 2 meter radius and update the
    neighbour_matrix and neighbour_count.
    """
    for person in persons:
        id1 = person.id
        for person2 in persons:
            id2 = person2.id

            # Ignore persons whose y-cordinates differ by more than 2 meters
            if abs(person.y - person2.y) > 2:
                continue

            # If the 2 persons have not been checked before and they are not the same person then proceed
            if (Person.neighbour_matrix[id1][id2] == None) and (id1 != id2):
                is_neighbour = person.is_neighbour(person2)

                # If the persons are neighbours then add to the both neighbour_counts
                if is_neighbour:
                    person.neighbour_count += 1
                    person2.neighbour_count += 1
                # Store the value of the neighbour check in both cells of the
                # neighbour_matrix to avoid recomputation (if i,j are neighbours then j,i are also neighbours)
                Person.neighbour_matrix[id1][id2] = is_neighbour
                Person.neighbour_matrix[id2][id1] = is_neighbour


def optimize(persons):
    """
    Function optimizing the bruteforce computation using recursion.
    """

    length = len(persons)
    mid = int(length / 2)

    # Obtain the person in the middle of the persons list
    midpoint = persons[mid]

    # If the length of the persons list is <=5 apply bruteforce
    if length <= 5:
        bruteforce(persons)
    else:
        # Create a list of all persons whose y-coodinate is 
        # within 2 metres of the middle person
        mid_section = []

        for person in persons:
            if abs(person.x - midpoint.x) <= 2:
                mid_section.append(person)

        # Sort mid_section by y-coordibates
        mid_section = sorted(mid_section, key=lambda person: person.y)

        # If the length of the persons list > 5, reduce the problem by 
        # splitting the list and applying recursion.
        optimize(persons[0:mid])
        optimize(persons[mid:])
        # Account for persons in the mid_section who haven't been checked
        # due to the split
        bruteforce(mid_section)


def find_offenders(dataset, n):
    """
    Find the list of offenders which are the persons having more 
    than n neighbours and print their (id, neighbour_count)
    """

    # Create a list of Person objects
    persons = []
    for item in dataset:
        persons.append(Person(item[0], item[1], item[2]))

    optimize(persons)

    offenders = []
    for person in persons:
        if person.neighbour_count > n:
            offenders.append((person.id, person.neighbour_count))

    if(len(offenders) == 0):
        print("No offenders")
    else:
        print(sorted(offenders, key=lambda tup: tup[0]))


if __name__ == '__main__':
    find_offenders(sorted(snapshot(), key=lambda tup: tup[1]), 8)