1import operator
  2
  3class Candy:
  4
  5    def __init__(self, mass, uranium):
  6        self.mass = mass
  7        self.uranium = uranium
  8
  9    def get_uranium_quantity(self):
 10        return self.mass * self.uranium
 11
 12    def get_mass(self):
 13        return self.mass
 14    
 15
 16class Person:
 17
 18    def __init__(self, position):
 19        self.position = position
 20    
 21    def get_position(self):
 22        return self.position
 23    
 24    def set_position(self, new_position):
 25        self.position = new_position
 26
 27
 28class Kid(Person):
 29
 30    CRITICAL_MASS = 20
 31
 32    def __init__(self, position, initiative):
 33        super().__init__(position)
 34        self.initiative = initiative
 35        self._basket = []
 36        self._uranium_sum = 0
 37        self.visited_hosts = []
 38    
 39    def get_initiative(self):
 40        return self.initiative
 41    
 42    def add_candy(self, candy):
 43        self._basket.append(candy)
 44    
 45    def is_critical(self):
 46        self._uranium_sum = 0
 47        for candy in self._basket:
 48            self._uranium_sum += candy.get_uranium_quantity()
 49        return self._uranium_sum > self.CRITICAL_MASS
 50    
 51
 52class Host(Person):
 53    
 54    def __init__(self, position, candies):
 55        super().__init__(position)
 56        self._basket = []
 57        self.treated_kids = list()
 58        self.kids_to_be_treated = list()
 59        self.candies = candies
 60
 61        for candy in self.candies:
 62            self._basket.append(Candy(candy[0], candy[1]))  
 63    
 64    def remove_candy(self, function):
 65        if len(self._basket) == 0:
 66            return None
 67        else:
 68            candy = function(self._basket)
 69            self._basket.remove(candy)
 70            return candy
 71        
 72
 73class FluxCapacitor:
 74
 75    def split_participants(self):
 76        for participant in self.participants:
 77            if type(participant) is Kid:
 78                self._kids.append(participant)
 79            else:
 80                self._hosts.append(participant)
 81
 82    def __init__(self, participants):
 83        self.participants = participants
 84        self.victims = set()
 85        self._kids = []
 86        self._hosts = []
 87        self.split_participants()
 88
 89    def give_Candy(self, kid, host):
 90        max_mass_candy = 0
 91        candy_to_give = Candy(0, 0)
 92        for candy in host._basket:
 93            if candy.get_mass() > max_mass_candy:
 94                max_mass_candy = candy.get_mass()
 95                candy_to_give = candy
 96
 97        if len(host._basket) > 0:
 98            kid.add_candy(candy_to_give)
 99            host._basket.remove(candy_to_give)
100    
101    def take_initiative(self, kid):
102        return kid.get_initiative()
103    
104    def order_kids(self, kids, host):
105        kids.sort(key=self.take_initiative, reverse=True)
106        return kids
107
108    def get_distance(self, kid, host):
109        x_kid, y_kid = kid.get_position()
110        x_host, y_host = host.get_position()
111        return abs(x_kid - x_host) + abs(y_kid - y_host)
112
113    def get_nearest_nonvisited_host(self, kid, visited_hosts):
114        all_distances = dict()
115
116        for host in self._hosts:
117            if host not in visited_hosts:
118                current_distance = self.get_distance(kid, host)
119                all_distances[host] = current_distance
120
121        if len(all_distances) != 0:
122            sorted_distances_to_hosts = sorted(all_distances.items(), key = operator.itemgetter(1))
123            min_distance = sorted_distances_to_hosts[0][1]
124            nearest_hosts = [host for host, distance in sorted_distances_to_hosts if distance == min_distance]
125            if len(nearest_hosts) == 1:
126                return nearest_hosts[0]
127            else:
128                sorted_hosts = sorted(nearest_hosts, key = lambda x: (x.get_position()[0], x.get_position()[1]))
129                return sorted_hosts[0]
130        return None
131
132    def set_kid_to_be_treated_by_host(self, kid, host):
133        kid.visited_hosts.append(host)
134        host.treated_kids.append(kid)
135        host.kids_to_be_treated.append(kid)    
136        kid.set_position(host.get_position())
137
138    def get_victim(self):
139        kids_that_have_visited_everyone = set()
140        hosts_that_have_treated_everyone = set()
141
142        while len(self.victims) == 0:
143            for kid in self._kids:
144                if len(kid.visited_hosts) == len(self._hosts):
145                    kids_that_have_visited_everyone.add(kid)
146                nearest_host = self.get_nearest_nonvisited_host(kid, kid.visited_hosts)
147                if nearest_host != None:
148                    self.set_kid_to_be_treated_by_host(kid, nearest_host)
149
150            for host in self._hosts:
151                if len(host.treated_kids) == len(self._kids):
152                    hosts_that_have_treated_everyone.add(host)
153                ordered_kids = self.order_kids(host.kids_to_be_treated, host)
154
155                for kid in ordered_kids:
156                    self.give_Candy(kid, host)
157                    if kid.is_critical():
158                        self.victims.add(kid)
159                host.kids_to_be_treated = list()
160
161            if len(self.victims) != 0:
162                break
163            if len(kids_that_have_visited_everyone) == len(self._kids) and len(hosts_that_have_treated_everyone) == len(self._hosts):
164                break
165
166        return self.victims or None