1import math
2from collections import defaultdict
3
4
5class Candy:
6 def __init__(self, mass, uranium):
7 self._mass = mass
8 self._uranium = uranium
9
10 def get_uranium_quantity(self):
11 return self._mass * self._uranium
12
13 def get_mass(self):
14 return self._mass
15
16
17class Person:
18 def __init__(self, position):
19 self._position = position
20
21 def set_position(self, position):
22 self._position = position
23
24 def get_position(self):
25 return self._position
26
27
28class Kid(Person):
29
30 _BOUNDARY = 20
31
32 def __init__(self, position, initiative):
33 super().__init__(position)
34 self._initiative = initiative
35 self._candies = []
36
37 def get_initiative(self):
38 return self._initiative
39
40 def add_candy(self, new_candy):
41 if new_candy:
42 self._candies.append(new_candy)
43
44 def is_critical(self):
45 return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY
46
47
48class Host(Person):
49 def __init__(self, position, candies):
50 super().__init__(position)
51 self._basket = {Candy(*args) for args in candies}
52
53 def remove_candy(self, function):
54 if not self._basket:
55 return None
56
57 retrieved_candy = function(self._basket)
58 self._basket.remove(retrieved_candy)
59
60 return retrieved_candy
61
62 def get_basket(self):
63 return self._basket
64
65
66class FluxCapacitor:
67 def __init__(self, participants):
68 self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)}
69 self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)}
70
71 def get_victim(self):
72 dead_kids = set()
73 roams = len(self._hosts)
74
75 for _ in range(roams):
76 self._roam_around_pripyat()
77
78 for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()):
79 dead_kids.add(dead_kid)
80
81 if dead_kids:
82 return dead_kids
83
84 return None
85
86 def _roam_around_pripyat(self):
87 hosts_and_their_kids = defaultdict(list)
88
89 for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True):
90 hosts_and_their_kids[self._get_closest_host(kid)].append(kid)
91
92 for host, their_kids in hosts_and_their_kids.items():
93 for kid in their_kids:
94 old_key = kid
95
96 kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass())))
97
98 self._hosts[host.get_position()] = host
99 self._kids[kid] = self._kids.pop(old_key)
100
101 def _get_closest_host(self, kid):
102 closest_distance = None
103 current_host = None
104
105 for host in self._hosts.values():
106 if host.get_position() in self._kids[kid]:
107 continue
108
109 distance = math.dist(host.get_position(), kid.get_position())
110 is_closest = False
111
112 if not current_host:
113 is_closest = True
114 else:
115 is_closest |= distance < closest_distance
116 is_closest |= (math.isclose(distance, closest_distance) and
117 (host.get_position()[0] < current_host.get_position()[0]))
118 is_closest |= (math.isclose(distance, closest_distance) and
119 host.get_position()[0] == current_host.get_position()[0] and
120 host.get_position()[1] < current_host.get_position()[1])
121
122 if is_closest:
123 closest_distance = distance
124 current_host = host
125
126 self._kids[kid].add(current_host.get_position())
127 kid.set_position(current_host.get_position())
128
129 return current_host
............
----------------------------------------------------------------------
Ran 12 tests in 0.001s
OK
Атанас Ников
04.11.2023 20:39Оо, много се радвам, благодаря за обратната връзка, апришиейтед : )
|
Георги Кунчев
04.11.2023 20:37Потвърждавам, че сега е ок.
|
Атанас Ников
04.11.2023 20:32За жалост в момента все още търся конкретния случай, който не работи, но се надявам вече да не се получава безкраен цикъл, ако съм хванал проблема.
|
Георги Кунчев
04.11.2023 20:05Мисля, че сам си отговори. Ти имаш тест, който работи. Аз имам тест, който зависва. Ерго -> не е винаги :smile:
|
Атанас Ников
04.11.2023 19:53Мога ли да попитам дали става въпрос за конкретен случай, или изобщо, т.е., дали става някакво разминаване, понеже тестовете, които написах досега, работят (уж) :(
|
Георги Кунчев
04.11.2023 19:43Имаш безкраен цикъл и тестовете ни ще зависнат, т.е. няма да имаш точки. Моля изтествай с реален случай.
|
f | 1 | import math | f | 1 | import math |
2 | from collections import defaultdict | 2 | from collections import defaultdict | ||
3 | 3 | ||||
4 | 4 | ||||
5 | class Candy: | 5 | class Candy: | ||
6 | def __init__(self, mass, uranium): | 6 | def __init__(self, mass, uranium): | ||
7 | self._mass = mass | 7 | self._mass = mass | ||
8 | self._uranium = uranium | 8 | self._uranium = uranium | ||
9 | 9 | ||||
10 | def get_uranium_quantity(self): | 10 | def get_uranium_quantity(self): | ||
11 | return self._mass * self._uranium | 11 | return self._mass * self._uranium | ||
12 | 12 | ||||
13 | def get_mass(self): | 13 | def get_mass(self): | ||
14 | return self._mass | 14 | return self._mass | ||
15 | 15 | ||||
16 | 16 | ||||
17 | class Person: | 17 | class Person: | ||
18 | def __init__(self, position): | 18 | def __init__(self, position): | ||
19 | self._position = position | 19 | self._position = position | ||
20 | 20 | ||||
21 | def set_position(self, position): | 21 | def set_position(self, position): | ||
22 | self._position = position | 22 | self._position = position | ||
23 | 23 | ||||
24 | def get_position(self): | 24 | def get_position(self): | ||
25 | return self._position | 25 | return self._position | ||
26 | 26 | ||||
27 | 27 | ||||
28 | class Kid(Person): | 28 | class Kid(Person): | ||
n | n | 29 | |||
29 | _BOUNDARY = 20 | 30 | _BOUNDARY = 20 | ||
30 | 31 | ||||
31 | def __init__(self, position, initiative): | 32 | def __init__(self, position, initiative): | ||
32 | super().__init__(position) | 33 | super().__init__(position) | ||
n | 33 | n | |||
34 | self._initiative = initiative | 34 | self._initiative = initiative | ||
35 | self._candies = [] | 35 | self._candies = [] | ||
36 | 36 | ||||
37 | def get_initiative(self): | 37 | def get_initiative(self): | ||
38 | return self._initiative | 38 | return self._initiative | ||
39 | 39 | ||||
40 | def add_candy(self, new_candy): | 40 | def add_candy(self, new_candy): | ||
41 | if new_candy: | 41 | if new_candy: | ||
42 | self._candies.append(new_candy) | 42 | self._candies.append(new_candy) | ||
43 | 43 | ||||
44 | def is_critical(self): | 44 | def is_critical(self): | ||
45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | 45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | ||
46 | 46 | ||||
47 | 47 | ||||
48 | class Host(Person): | 48 | class Host(Person): | ||
49 | def __init__(self, position, candies): | 49 | def __init__(self, position, candies): | ||
50 | super().__init__(position) | 50 | super().__init__(position) | ||
n | 51 | n | |||
52 | self._basket = {Candy(*args) for args in candies} | 51 | self._basket = {Candy(*args) for args in candies} | ||
53 | 52 | ||||
54 | def remove_candy(self, function): | 53 | def remove_candy(self, function): | ||
55 | if not self._basket: | 54 | if not self._basket: | ||
56 | return None | 55 | return None | ||
57 | 56 | ||||
58 | retrieved_candy = function(self._basket) | 57 | retrieved_candy = function(self._basket) | ||
59 | self._basket.remove(retrieved_candy) | 58 | self._basket.remove(retrieved_candy) | ||
60 | 59 | ||||
61 | return retrieved_candy | 60 | return retrieved_candy | ||
62 | 61 | ||||
63 | def get_basket(self): | 62 | def get_basket(self): | ||
64 | return self._basket | 63 | return self._basket | ||
65 | 64 | ||||
66 | 65 | ||||
67 | class FluxCapacitor: | 66 | class FluxCapacitor: | ||
68 | def __init__(self, participants): | 67 | def __init__(self, participants): | ||
69 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | 68 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | ||
70 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | 69 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | ||
71 | 70 | ||||
72 | def get_victim(self): | 71 | def get_victim(self): | ||
73 | dead_kids = set() | 72 | dead_kids = set() | ||
74 | roams = len(self._hosts) | 73 | roams = len(self._hosts) | ||
75 | 74 | ||||
76 | for _ in range(roams): | 75 | for _ in range(roams): | ||
77 | self._roam_around_pripyat() | 76 | self._roam_around_pripyat() | ||
78 | 77 | ||||
79 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | 78 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | ||
80 | dead_kids.add(dead_kid) | 79 | dead_kids.add(dead_kid) | ||
81 | 80 | ||||
82 | if dead_kids: | 81 | if dead_kids: | ||
83 | return dead_kids | 82 | return dead_kids | ||
84 | 83 | ||||
85 | return None | 84 | return None | ||
86 | 85 | ||||
87 | def _roam_around_pripyat(self): | 86 | def _roam_around_pripyat(self): | ||
88 | hosts_and_their_kids = defaultdict(list) | 87 | hosts_and_their_kids = defaultdict(list) | ||
89 | 88 | ||||
90 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | 89 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | ||
91 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | 90 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | ||
92 | 91 | ||||
93 | for host, their_kids in hosts_and_their_kids.items(): | 92 | for host, their_kids in hosts_and_their_kids.items(): | ||
94 | for kid in their_kids: | 93 | for kid in their_kids: | ||
95 | old_key = kid | 94 | old_key = kid | ||
96 | 95 | ||||
97 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | 96 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | ||
98 | 97 | ||||
99 | self._hosts[host.get_position()] = host | 98 | self._hosts[host.get_position()] = host | ||
100 | self._kids[kid] = self._kids.pop(old_key) | 99 | self._kids[kid] = self._kids.pop(old_key) | ||
101 | 100 | ||||
102 | def _get_closest_host(self, kid): | 101 | def _get_closest_host(self, kid): | ||
103 | closest_distance = None | 102 | closest_distance = None | ||
104 | current_host = None | 103 | current_host = None | ||
105 | 104 | ||||
106 | for host in self._hosts.values(): | 105 | for host in self._hosts.values(): | ||
107 | if host.get_position() in self._kids[kid]: | 106 | if host.get_position() in self._kids[kid]: | ||
108 | continue | 107 | continue | ||
109 | 108 | ||||
110 | distance = math.dist(host.get_position(), kid.get_position()) | 109 | distance = math.dist(host.get_position(), kid.get_position()) | ||
111 | is_closest = False | 110 | is_closest = False | ||
112 | 111 | ||||
113 | if not current_host: | 112 | if not current_host: | ||
114 | is_closest = True | 113 | is_closest = True | ||
115 | else: | 114 | else: | ||
116 | is_closest |= distance < closest_distance | 115 | is_closest |= distance < closest_distance | ||
117 | is_closest |= (math.isclose(distance, closest_distance) and | 116 | is_closest |= (math.isclose(distance, closest_distance) and | ||
118 | (host.get_position()[0] < current_host.get_position()[0])) | 117 | (host.get_position()[0] < current_host.get_position()[0])) | ||
119 | is_closest |= (math.isclose(distance, closest_distance) and | 118 | is_closest |= (math.isclose(distance, closest_distance) and | ||
120 | host.get_position()[0] == current_host.get_position()[0] and | 119 | host.get_position()[0] == current_host.get_position()[0] and | ||
121 | host.get_position()[1] < current_host.get_position()[1]) | 120 | host.get_position()[1] < current_host.get_position()[1]) | ||
122 | 121 | ||||
123 | if is_closest: | 122 | if is_closest: | ||
124 | closest_distance = distance | 123 | closest_distance = distance | ||
125 | current_host = host | 124 | current_host = host | ||
126 | 125 | ||||
t | 127 | if not current_host: | t | ||
128 | return None | ||||
129 | |||||
130 | self._kids[kid].add(current_host.get_position()) | 126 | self._kids[kid].add(current_host.get_position()) | ||
131 | kid.set_position(current_host.get_position()) | 127 | kid.set_position(current_host.get_position()) | ||
132 | 128 | ||||
133 | return current_host | 129 | return current_host |
Legends | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
|
f | 1 | import math | f | 1 | import math |
2 | from collections import defaultdict | 2 | from collections import defaultdict | ||
3 | 3 | ||||
4 | 4 | ||||
5 | class Candy: | 5 | class Candy: | ||
6 | def __init__(self, mass, uranium): | 6 | def __init__(self, mass, uranium): | ||
7 | self._mass = mass | 7 | self._mass = mass | ||
8 | self._uranium = uranium | 8 | self._uranium = uranium | ||
9 | 9 | ||||
10 | def get_uranium_quantity(self): | 10 | def get_uranium_quantity(self): | ||
11 | return self._mass * self._uranium | 11 | return self._mass * self._uranium | ||
12 | 12 | ||||
13 | def get_mass(self): | 13 | def get_mass(self): | ||
14 | return self._mass | 14 | return self._mass | ||
15 | 15 | ||||
16 | 16 | ||||
17 | class Person: | 17 | class Person: | ||
18 | def __init__(self, position): | 18 | def __init__(self, position): | ||
19 | self._position = position | 19 | self._position = position | ||
20 | 20 | ||||
21 | def set_position(self, position): | 21 | def set_position(self, position): | ||
22 | self._position = position | 22 | self._position = position | ||
23 | 23 | ||||
24 | def get_position(self): | 24 | def get_position(self): | ||
25 | return self._position | 25 | return self._position | ||
26 | 26 | ||||
27 | 27 | ||||
28 | class Kid(Person): | 28 | class Kid(Person): | ||
29 | _BOUNDARY = 20 | 29 | _BOUNDARY = 20 | ||
30 | 30 | ||||
31 | def __init__(self, position, initiative): | 31 | def __init__(self, position, initiative): | ||
32 | super().__init__(position) | 32 | super().__init__(position) | ||
33 | 33 | ||||
34 | self._initiative = initiative | 34 | self._initiative = initiative | ||
35 | self._candies = [] | 35 | self._candies = [] | ||
36 | 36 | ||||
37 | def get_initiative(self): | 37 | def get_initiative(self): | ||
38 | return self._initiative | 38 | return self._initiative | ||
39 | 39 | ||||
40 | def add_candy(self, new_candy): | 40 | def add_candy(self, new_candy): | ||
41 | if new_candy: | 41 | if new_candy: | ||
42 | self._candies.append(new_candy) | 42 | self._candies.append(new_candy) | ||
43 | 43 | ||||
44 | def is_critical(self): | 44 | def is_critical(self): | ||
45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | 45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | ||
46 | 46 | ||||
47 | 47 | ||||
48 | class Host(Person): | 48 | class Host(Person): | ||
49 | def __init__(self, position, candies): | 49 | def __init__(self, position, candies): | ||
50 | super().__init__(position) | 50 | super().__init__(position) | ||
51 | 51 | ||||
52 | self._basket = {Candy(*args) for args in candies} | 52 | self._basket = {Candy(*args) for args in candies} | ||
53 | 53 | ||||
54 | def remove_candy(self, function): | 54 | def remove_candy(self, function): | ||
55 | if not self._basket: | 55 | if not self._basket: | ||
56 | return None | 56 | return None | ||
57 | 57 | ||||
58 | retrieved_candy = function(self._basket) | 58 | retrieved_candy = function(self._basket) | ||
59 | self._basket.remove(retrieved_candy) | 59 | self._basket.remove(retrieved_candy) | ||
60 | 60 | ||||
61 | return retrieved_candy | 61 | return retrieved_candy | ||
62 | 62 | ||||
63 | def get_basket(self): | 63 | def get_basket(self): | ||
64 | return self._basket | 64 | return self._basket | ||
65 | 65 | ||||
66 | 66 | ||||
67 | class FluxCapacitor: | 67 | class FluxCapacitor: | ||
68 | def __init__(self, participants): | 68 | def __init__(self, participants): | ||
69 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | 69 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | ||
70 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | 70 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | ||
71 | 71 | ||||
72 | def get_victim(self): | 72 | def get_victim(self): | ||
73 | dead_kids = set() | 73 | dead_kids = set() | ||
74 | roams = len(self._hosts) | 74 | roams = len(self._hosts) | ||
75 | 75 | ||||
76 | for _ in range(roams): | 76 | for _ in range(roams): | ||
77 | self._roam_around_pripyat() | 77 | self._roam_around_pripyat() | ||
78 | 78 | ||||
79 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | 79 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | ||
80 | dead_kids.add(dead_kid) | 80 | dead_kids.add(dead_kid) | ||
81 | 81 | ||||
82 | if dead_kids: | 82 | if dead_kids: | ||
83 | return dead_kids | 83 | return dead_kids | ||
84 | 84 | ||||
85 | return None | 85 | return None | ||
86 | 86 | ||||
87 | def _roam_around_pripyat(self): | 87 | def _roam_around_pripyat(self): | ||
88 | hosts_and_their_kids = defaultdict(list) | 88 | hosts_and_their_kids = defaultdict(list) | ||
89 | 89 | ||||
90 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | 90 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | ||
91 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | 91 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | ||
92 | 92 | ||||
93 | for host, their_kids in hosts_and_their_kids.items(): | 93 | for host, their_kids in hosts_and_their_kids.items(): | ||
94 | for kid in their_kids: | 94 | for kid in their_kids: | ||
95 | old_key = kid | 95 | old_key = kid | ||
96 | 96 | ||||
97 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | 97 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | ||
98 | 98 | ||||
99 | self._hosts[host.get_position()] = host | 99 | self._hosts[host.get_position()] = host | ||
100 | self._kids[kid] = self._kids.pop(old_key) | 100 | self._kids[kid] = self._kids.pop(old_key) | ||
101 | 101 | ||||
102 | def _get_closest_host(self, kid): | 102 | def _get_closest_host(self, kid): | ||
103 | closest_distance = None | 103 | closest_distance = None | ||
104 | current_host = None | 104 | current_host = None | ||
105 | 105 | ||||
106 | for host in self._hosts.values(): | 106 | for host in self._hosts.values(): | ||
107 | if host.get_position() in self._kids[kid]: | 107 | if host.get_position() in self._kids[kid]: | ||
108 | continue | 108 | continue | ||
109 | 109 | ||||
n | 110 | distance = self._get_euclidean_distance(host.get_position(), kid.get_position()) | n | 110 | distance = math.dist(host.get_position(), kid.get_position()) |
111 | |||||
112 | is_closest = False | 111 | is_closest = False | ||
113 | 112 | ||||
114 | if not current_host: | 113 | if not current_host: | ||
115 | is_closest = True | 114 | is_closest = True | ||
116 | else: | 115 | else: | ||
117 | is_closest |= distance < closest_distance | 116 | is_closest |= distance < closest_distance | ||
118 | is_closest |= (math.isclose(distance, closest_distance) and | 117 | is_closest |= (math.isclose(distance, closest_distance) and | ||
119 | (host.get_position()[0] < current_host.get_position()[0])) | 118 | (host.get_position()[0] < current_host.get_position()[0])) | ||
120 | is_closest |= (math.isclose(distance, closest_distance) and | 119 | is_closest |= (math.isclose(distance, closest_distance) and | ||
121 | host.get_position()[0] == current_host.get_position()[0] and | 120 | host.get_position()[0] == current_host.get_position()[0] and | ||
122 | host.get_position()[1] < current_host.get_position()[1]) | 121 | host.get_position()[1] < current_host.get_position()[1]) | ||
123 | 122 | ||||
124 | if is_closest: | 123 | if is_closest: | ||
125 | closest_distance = distance | 124 | closest_distance = distance | ||
126 | current_host = host | 125 | current_host = host | ||
127 | 126 | ||||
128 | if not current_host: | 127 | if not current_host: | ||
129 | return None | 128 | return None | ||
130 | 129 | ||||
131 | self._kids[kid].add(current_host.get_position()) | 130 | self._kids[kid].add(current_host.get_position()) | ||
132 | kid.set_position(current_host.get_position()) | 131 | kid.set_position(current_host.get_position()) | ||
133 | 132 | ||||
134 | return current_host | 133 | return current_host | ||
t | 135 | t | |||
136 | @staticmethod | ||||
137 | def _get_euclidean_distance(starting_point, ending_point): | ||||
138 | d_x = starting_point[0] - ending_point[0] | ||||
139 | d_y = starting_point[1] - ending_point[1] | ||||
140 | |||||
141 | return math.sqrt(d_x ** 2 + d_y ** 2) |
Legends | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
|
f | 1 | import math | f | 1 | import math |
2 | from collections import defaultdict | 2 | from collections import defaultdict | ||
3 | 3 | ||||
4 | 4 | ||||
5 | class Candy: | 5 | class Candy: | ||
6 | def __init__(self, mass, uranium): | 6 | def __init__(self, mass, uranium): | ||
7 | self._mass = mass | 7 | self._mass = mass | ||
8 | self._uranium = uranium | 8 | self._uranium = uranium | ||
9 | 9 | ||||
10 | def get_uranium_quantity(self): | 10 | def get_uranium_quantity(self): | ||
11 | return self._mass * self._uranium | 11 | return self._mass * self._uranium | ||
12 | 12 | ||||
13 | def get_mass(self): | 13 | def get_mass(self): | ||
14 | return self._mass | 14 | return self._mass | ||
15 | 15 | ||||
16 | 16 | ||||
17 | class Person: | 17 | class Person: | ||
18 | def __init__(self, position): | 18 | def __init__(self, position): | ||
19 | self._position = position | 19 | self._position = position | ||
20 | 20 | ||||
21 | def set_position(self, position): | 21 | def set_position(self, position): | ||
22 | self._position = position | 22 | self._position = position | ||
23 | 23 | ||||
24 | def get_position(self): | 24 | def get_position(self): | ||
25 | return self._position | 25 | return self._position | ||
26 | 26 | ||||
27 | 27 | ||||
28 | class Kid(Person): | 28 | class Kid(Person): | ||
29 | _BOUNDARY = 20 | 29 | _BOUNDARY = 20 | ||
30 | 30 | ||||
31 | def __init__(self, position, initiative): | 31 | def __init__(self, position, initiative): | ||
32 | super().__init__(position) | 32 | super().__init__(position) | ||
33 | 33 | ||||
34 | self._initiative = initiative | 34 | self._initiative = initiative | ||
35 | self._candies = [] | 35 | self._candies = [] | ||
36 | 36 | ||||
37 | def get_initiative(self): | 37 | def get_initiative(self): | ||
38 | return self._initiative | 38 | return self._initiative | ||
39 | 39 | ||||
40 | def add_candy(self, new_candy): | 40 | def add_candy(self, new_candy): | ||
41 | if new_candy: | 41 | if new_candy: | ||
42 | self._candies.append(new_candy) | 42 | self._candies.append(new_candy) | ||
43 | 43 | ||||
44 | def is_critical(self): | 44 | def is_critical(self): | ||
45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | 45 | return sum(map(lambda candy: candy.get_uranium_quantity(), self._candies)) > self._BOUNDARY | ||
46 | 46 | ||||
47 | 47 | ||||
48 | class Host(Person): | 48 | class Host(Person): | ||
49 | def __init__(self, position, candies): | 49 | def __init__(self, position, candies): | ||
50 | super().__init__(position) | 50 | super().__init__(position) | ||
51 | 51 | ||||
52 | self._basket = {Candy(*args) for args in candies} | 52 | self._basket = {Candy(*args) for args in candies} | ||
53 | 53 | ||||
54 | def remove_candy(self, function): | 54 | def remove_candy(self, function): | ||
55 | if not self._basket: | 55 | if not self._basket: | ||
56 | return None | 56 | return None | ||
57 | 57 | ||||
58 | retrieved_candy = function(self._basket) | 58 | retrieved_candy = function(self._basket) | ||
59 | self._basket.remove(retrieved_candy) | 59 | self._basket.remove(retrieved_candy) | ||
60 | 60 | ||||
61 | return retrieved_candy | 61 | return retrieved_candy | ||
62 | 62 | ||||
63 | def get_basket(self): | 63 | def get_basket(self): | ||
64 | return self._basket | 64 | return self._basket | ||
65 | 65 | ||||
66 | 66 | ||||
67 | class FluxCapacitor: | 67 | class FluxCapacitor: | ||
68 | def __init__(self, participants): | 68 | def __init__(self, participants): | ||
69 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | 69 | self._hosts = {participant.get_position(): participant for participant in participants if isinstance(participant, Host)} | ||
70 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | 70 | self._kids = {participant: set() for participant in participants if isinstance(participant, Kid)} | ||
71 | 71 | ||||
72 | def get_victim(self): | 72 | def get_victim(self): | ||
73 | dead_kids = set() | 73 | dead_kids = set() | ||
n | n | 74 | roams = len(self._hosts) | ||
74 | 75 | ||||
n | 75 | while not dead_kids and self._roam_around_pripyat(): | n | 76 | for _ in range(roams): |
77 | self._roam_around_pripyat() | ||||
78 | |||||
76 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | 79 | for dead_kid in filter(lambda kid: kid.is_critical(), self._kids.keys()): | ||
77 | dead_kids.add(dead_kid) | 80 | dead_kids.add(dead_kid) | ||
78 | 81 | ||||
n | 79 | return dead_kids if dead_kids else None | n | 82 | if dead_kids: |
83 | return dead_kids | ||||
84 | |||||
85 | return None | ||||
80 | 86 | ||||
81 | def _roam_around_pripyat(self): | 87 | def _roam_around_pripyat(self): | ||
82 | hosts_and_their_kids = defaultdict(list) | 88 | hosts_and_their_kids = defaultdict(list) | ||
83 | 89 | ||||
84 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | 90 | for kid in sorted(self._kids.keys(), key=lambda current: current.get_initiative(), reverse=True): | ||
85 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | 91 | hosts_and_their_kids[self._get_closest_host(kid)].append(kid) | ||
86 | 92 | ||||
87 | for host, their_kids in hosts_and_their_kids.items(): | 93 | for host, their_kids in hosts_and_their_kids.items(): | ||
n | 88 | if not host and len(their_kids) == len(self._kids): | n | ||
89 | return False | ||||
90 | |||||
91 | if not host: | ||||
92 | continue | ||||
93 | |||||
94 | for kid in their_kids: | 94 | for kid in their_kids: | ||
95 | old_key = kid | 95 | old_key = kid | ||
96 | 96 | ||||
97 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | 97 | kid.add_candy(host.remove_candy(lambda candies: max(candies, key=lambda candy: candy.get_mass()))) | ||
98 | 98 | ||||
99 | self._hosts[host.get_position()] = host | 99 | self._hosts[host.get_position()] = host | ||
100 | self._kids[kid] = self._kids.pop(old_key) | 100 | self._kids[kid] = self._kids.pop(old_key) | ||
t | 101 | t | |||
102 | return True | ||||
103 | 101 | ||||
104 | def _get_closest_host(self, kid): | 102 | def _get_closest_host(self, kid): | ||
105 | closest_distance = None | 103 | closest_distance = None | ||
106 | current_host = None | 104 | current_host = None | ||
107 | 105 | ||||
108 | for host in self._hosts.values(): | 106 | for host in self._hosts.values(): | ||
109 | if host.get_position() in self._kids[kid]: | 107 | if host.get_position() in self._kids[kid]: | ||
110 | continue | 108 | continue | ||
111 | 109 | ||||
112 | distance = self._get_euclidean_distance(host.get_position(), kid.get_position()) | 110 | distance = self._get_euclidean_distance(host.get_position(), kid.get_position()) | ||
113 | 111 | ||||
114 | is_closest = False | 112 | is_closest = False | ||
115 | 113 | ||||
116 | if not current_host: | 114 | if not current_host: | ||
117 | is_closest = True | 115 | is_closest = True | ||
118 | else: | 116 | else: | ||
119 | is_closest |= distance < closest_distance | 117 | is_closest |= distance < closest_distance | ||
120 | is_closest |= (math.isclose(distance, closest_distance) and | 118 | is_closest |= (math.isclose(distance, closest_distance) and | ||
121 | (host.get_position()[0] < current_host.get_position()[0])) | 119 | (host.get_position()[0] < current_host.get_position()[0])) | ||
122 | is_closest |= (math.isclose(distance, closest_distance) and | 120 | is_closest |= (math.isclose(distance, closest_distance) and | ||
123 | host.get_position()[0] == current_host.get_position()[0] and | 121 | host.get_position()[0] == current_host.get_position()[0] and | ||
124 | host.get_position()[1] < current_host.get_position()[1]) | 122 | host.get_position()[1] < current_host.get_position()[1]) | ||
125 | 123 | ||||
126 | if is_closest: | 124 | if is_closest: | ||
127 | closest_distance = distance | 125 | closest_distance = distance | ||
128 | current_host = host | 126 | current_host = host | ||
129 | 127 | ||||
130 | if not current_host: | 128 | if not current_host: | ||
131 | return None | 129 | return None | ||
132 | 130 | ||||
133 | self._kids[kid].add(current_host.get_position()) | 131 | self._kids[kid].add(current_host.get_position()) | ||
134 | kid.set_position(current_host.get_position()) | 132 | kid.set_position(current_host.get_position()) | ||
135 | 133 | ||||
136 | return current_host | 134 | return current_host | ||
137 | 135 | ||||
138 | @staticmethod | 136 | @staticmethod | ||
139 | def _get_euclidean_distance(starting_point, ending_point): | 137 | def _get_euclidean_distance(starting_point, ending_point): | ||
140 | d_x = starting_point[0] - ending_point[0] | 138 | d_x = starting_point[0] - ending_point[0] | ||
141 | d_y = starting_point[1] - ending_point[1] | 139 | d_y = starting_point[1] - ending_point[1] | ||
142 | 140 | ||||
143 | return math.sqrt(d_x ** 2 + d_y ** 2) | 141 | return math.sqrt(d_x ** 2 + d_y ** 2) |
Legends | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|
|
|