|
| 1 | +# -------------------------------- Input data ---------------------------------------- # |
| 2 | +import os, grid, graph, dot, assembly, re, itertools, copy, functools |
| 3 | +from collections import Counter, deque, defaultdict |
| 4 | +from functools import reduce |
| 5 | +import heapq |
| 6 | + |
| 7 | +from compass import * |
| 8 | + |
| 9 | + |
| 10 | +# This functions come from https://github.com/mcpower/adventofcode - Thanks! |
| 11 | +def lmap(func, *iterables): |
| 12 | + return list(map(func, *iterables)) |
| 13 | + |
| 14 | + |
| 15 | +def ints(s: str): |
| 16 | + return lmap(int, re.findall(r"-?\d+", s)) # thanks mserrano! |
| 17 | + |
| 18 | + |
| 19 | +def positive_ints(s: str): |
| 20 | + return lmap(int, re.findall(r"\d+", s)) # thanks mserrano! |
| 21 | + |
| 22 | + |
| 23 | +def floats(s: str): |
| 24 | + return lmap(float, re.findall(r"-?\d+(?:\.\d+)?", s)) |
| 25 | + |
| 26 | + |
| 27 | +def positive_floats(s: str): |
| 28 | + return lmap(float, re.findall(r"\d+(?:\.\d+)?", s)) |
| 29 | + |
| 30 | + |
| 31 | +def words(s: str): |
| 32 | + return re.findall(r"[a-zA-Z]+", s) |
| 33 | + |
| 34 | + |
| 35 | +test_data = {} |
| 36 | + |
| 37 | +test = 1 |
| 38 | +test_data[test] = { |
| 39 | + "input": """############# |
| 40 | +#...........# |
| 41 | +###B#C#B#D### |
| 42 | + #A#D#C#A# |
| 43 | + #########""", |
| 44 | + "expected": ["12521", "Unknown"], |
| 45 | +} |
| 46 | + |
| 47 | +test = "real" |
| 48 | +input_file = os.path.join( |
| 49 | + os.path.dirname(__file__), |
| 50 | + "Inputs", |
| 51 | + os.path.basename(__file__).replace(".py", ".txt"), |
| 52 | +) |
| 53 | +test_data[test] = { |
| 54 | + "input": open(input_file, "r+").read(), |
| 55 | + "expected": ["Unknown", "Unknown"], |
| 56 | +} |
| 57 | + |
| 58 | + |
| 59 | +# -------------------------------- Control program execution ------------------------- # |
| 60 | + |
| 61 | +case_to_test = 1 |
| 62 | +part_to_test = 1 |
| 63 | + |
| 64 | +# -------------------------------- Initialize some variables ------------------------- # |
| 65 | + |
| 66 | +puzzle_input = test_data[case_to_test]["input"] |
| 67 | +puzzle_expected_result = test_data[case_to_test]["expected"][part_to_test - 1] |
| 68 | +puzzle_actual_result = "Unknown" |
| 69 | + |
| 70 | + |
| 71 | +# This was the very first attempt to solve it |
| 72 | +# It tries to parse the input, the run A* on it to find possible movements |
| 73 | +# Basically it's wayyy too slow and buggy |
| 74 | + |
| 75 | + |
| 76 | +# -------------------------------- Actual code execution ----------------------------- # |
| 77 | + |
| 78 | +dot.Dot.sort_value = dot.Dot.sorting_map["xy"] |
| 79 | + |
| 80 | + |
| 81 | +class NewGrid(grid.Grid): |
| 82 | + def text_to_dots(self, text, ignore_terrain="", convert_to_int=False): |
| 83 | + self.dots = {} |
| 84 | + |
| 85 | + y = 0 |
| 86 | + self.amphipods = {} |
| 87 | + self.position_to_rooms = [] |
| 88 | + nb_amphipods = [] |
| 89 | + for line in text.splitlines(): |
| 90 | + for x in range(len(line)): |
| 91 | + if line[x] not in ignore_terrain: |
| 92 | + value = line[x] |
| 93 | + position = x - y * 1j |
| 94 | + |
| 95 | + if value == " ": |
| 96 | + continue |
| 97 | + |
| 98 | + if value in "ABCD": |
| 99 | + self.position_to_rooms.append(position) |
| 100 | + if value in nb_amphipods: |
| 101 | + UUID = value + "2" |
| 102 | + else: |
| 103 | + UUID = value + "1" |
| 104 | + nb_amphipods.append(value) |
| 105 | + self.amphipods[UUID] = dot.Dot(self, position, value) |
| 106 | + |
| 107 | + value = "." |
| 108 | + |
| 109 | + self.dots[position] = dot.Dot(self, position, value) |
| 110 | + # self.dots[position].sort_value = self.dots[position].sorting_map['xy'] |
| 111 | + if value == ".": |
| 112 | + self.dots[position].is_waypoint = True |
| 113 | + y += 1 |
| 114 | + |
| 115 | + |
| 116 | +class StateGraph(graph.WeightedGraph): |
| 117 | + amphipod_state = ["A1", "A2", "B1", "B2", "C1", "C2", "D1", "D2"] |
| 118 | + |
| 119 | + def a_star_search(self, start, end=None): |
| 120 | + """ |
| 121 | + Performs a A* search |
| 122 | +
|
| 123 | + This algorithm is appropriate for "One source, multiple targets" |
| 124 | + It takes into account positive weigths / costs of travelling. |
| 125 | + Negative weights will make the algorithm fail. |
| 126 | +
|
| 127 | + The exploration path is a mix of Dijkstra and Greedy BFS |
| 128 | + It uses the current cost + estimated cost to determine the next element to consider |
| 129 | +
|
| 130 | + Some cases to consider: |
| 131 | + - If Estimated cost to complete = 0, A* = Dijkstra |
| 132 | + - If Estimated cost to complete <= actual cost to complete, it is exact |
| 133 | + - If Estimated cost to complete > actual cost to complete, it is inexact |
| 134 | + - If Estimated cost to complete = infinity, A* = Greedy BFS |
| 135 | + The higher Estimated cost to complete, the faster it goes |
| 136 | +
|
| 137 | + :param Any start: The start vertex to consider |
| 138 | + :param Any end: The target/end vertex to consider |
| 139 | + :return: True when the end vertex is found, False otherwise |
| 140 | + """ |
| 141 | + current_distance = 0 |
| 142 | + frontier = [(0, start, 0)] |
| 143 | + heapq.heapify(frontier) |
| 144 | + self.distance_from_start = {start: 0} |
| 145 | + self.came_from = {start: None} |
| 146 | + self.visited = [tuple(dot.position for dot in start)] |
| 147 | + |
| 148 | + i = 0 |
| 149 | + while frontier: # and i < 5: |
| 150 | + i += 1 |
| 151 | + priority, vertex, current_distance = heapq.heappop(frontier) |
| 152 | + print(len(frontier), priority, current_distance) |
| 153 | + |
| 154 | + neighbors = self.neighbors(vertex) |
| 155 | + if not neighbors: |
| 156 | + continue |
| 157 | + |
| 158 | + for neighbor, weight in neighbors.items(): |
| 159 | + # We've already checked that node, and it's not better now |
| 160 | + if neighbor in self.distance_from_start and self.distance_from_start[ |
| 161 | + neighbor |
| 162 | + ] <= (current_distance + weight): |
| 163 | + continue |
| 164 | + |
| 165 | + if any( |
| 166 | + equivalent_position in self.visited |
| 167 | + for equivalent_position in self.equivalent_positions(neighbor) |
| 168 | + ): |
| 169 | + continue |
| 170 | + |
| 171 | + # Adding for future examination |
| 172 | + priority = current_distance + self.estimate_to_complete(neighbor, end) |
| 173 | + # print (vertex, neighbor, current_distance, priority) |
| 174 | + heapq.heappush( |
| 175 | + frontier, (priority, neighbor, current_distance + weight) |
| 176 | + ) |
| 177 | + |
| 178 | + # Adding for final search |
| 179 | + self.distance_from_start[neighbor] = current_distance + weight |
| 180 | + self.came_from[neighbor] = vertex |
| 181 | + self.visited.append(tuple(dot.position for dot in neighbor)) |
| 182 | + |
| 183 | + if self.state_is_final(neighbor): |
| 184 | + return self.distance_from_start[neighbor] |
| 185 | + |
| 186 | + # print (len(frontier)) |
| 187 | + |
| 188 | + return end in self.distance_from_start |
| 189 | + |
| 190 | + def neighbors(self, state): |
| 191 | + if self.state_is_final(state): |
| 192 | + return None |
| 193 | + |
| 194 | + neighbors = {} |
| 195 | + for i, current_dot in enumerate(state): |
| 196 | + amphipod_code = self.amphipod_state[i] |
| 197 | + dots = self.area_graph.edges[current_dot] |
| 198 | + for dot, cost in dots.items(): |
| 199 | + new_state = list(state) |
| 200 | + new_state[i] = dot |
| 201 | + new_state = tuple(new_state) |
| 202 | + # print ('Checking', amphipod_code, 'moved from', state[i], 'to', new_state[i]) |
| 203 | + if self.state_is_valid(state, new_state, i): |
| 204 | + neighbors[new_state] = ( |
| 205 | + cost * self.amphipods[amphipod_code].movement_cost |
| 206 | + ) |
| 207 | + # print ('Movement costs', cost * self.amphipods[amphipod_code].movement_cost) |
| 208 | + |
| 209 | + return neighbors |
| 210 | + |
| 211 | + def state_is_final(self, state): |
| 212 | + for i, position in enumerate(state): |
| 213 | + amphipod_code = self.amphipod_state[i] |
| 214 | + amphipod = self.amphipods[amphipod_code] |
| 215 | + |
| 216 | + if not position in self.room_to_positions[amphipod.terrain]: |
| 217 | + return False |
| 218 | + return True |
| 219 | + |
| 220 | + def state_is_valid(self, state, new_state, changed): |
| 221 | + # Duplicate = 2 amphipods in the same place |
| 222 | + if len(set(new_state)) != len(new_state): |
| 223 | + # print ('Duplicate amphipod', new_state[changed]) |
| 224 | + return False |
| 225 | + |
| 226 | + # Check amphipod is not in wrong room |
| 227 | + if new_state[i].position in self.position_to_rooms: |
| 228 | + room = self.position_to_rooms[new_state[i].position] |
| 229 | + # print ('Amphipod may be in wrong place', new_state) |
| 230 | + amphipod = self.amphipod_state[i] |
| 231 | + if room == self.amphipods[amphipod].initial_room: |
| 232 | + return True |
| 233 | + else: |
| 234 | + # print ('Amphipod is in wrong place', new_state) |
| 235 | + return False |
| 236 | + |
| 237 | + return True |
| 238 | + |
| 239 | + def estimate_to_complete(self, state, target_vertex): |
| 240 | + distance = 0 |
| 241 | + for i, dot in enumerate(state): |
| 242 | + amphipod_code = self.amphipod_state[i] |
| 243 | + amphipod = self.amphipods[amphipod_code] |
| 244 | + |
| 245 | + if not dot.position in self.room_to_positions[amphipod.terrain]: |
| 246 | + room_positions = self.room_to_positions[amphipod.terrain] |
| 247 | + targets = [self.dots[position] for position in room_positions] |
| 248 | + distance += ( |
| 249 | + min( |
| 250 | + self.area_graph.all_edges[dot][target] |
| 251 | + if target in self.area_graph.all_edges[dot] |
| 252 | + else 10 ** 6 |
| 253 | + for target in targets |
| 254 | + ) |
| 255 | + * amphipod.movement_cost |
| 256 | + ) |
| 257 | + |
| 258 | + return distance |
| 259 | + |
| 260 | + def equivalent_positions(self, state): |
| 261 | + state_positions = [dot.position for dot in state] |
| 262 | + positions = [ |
| 263 | + tuple([state_positions[1]] + [state_positions[0]] + state_positions[2:]), |
| 264 | + tuple( |
| 265 | + state_positions[0:2] |
| 266 | + + [state_positions[3]] |
| 267 | + + [state_positions[2]] |
| 268 | + + state_positions[4:] |
| 269 | + ), |
| 270 | + tuple( |
| 271 | + state_positions[0:4] |
| 272 | + + [state_positions[5]] |
| 273 | + + [state_positions[4]] |
| 274 | + + state_positions[6:] |
| 275 | + ), |
| 276 | + tuple(state_positions[0:6] + [state_positions[7]] + [state_positions[6]]), |
| 277 | + ] |
| 278 | + |
| 279 | + for i in range(4): |
| 280 | + position = tuple( |
| 281 | + state_positions[:i] |
| 282 | + + state_positions[i + 1 : i] |
| 283 | + + state_positions[i + 2 :] |
| 284 | + ) |
| 285 | + positions.append(position) |
| 286 | + |
| 287 | + return positions |
| 288 | + |
| 289 | + |
| 290 | +if part_to_test == 1: |
| 291 | + area_map = NewGrid() |
| 292 | + area_map.text_to_dots(puzzle_input) |
| 293 | + |
| 294 | + position_to_rooms = defaultdict(list) |
| 295 | + room_to_positions = defaultdict(list) |
| 296 | + area_map.position_to_rooms = sorted( |
| 297 | + area_map.position_to_rooms, key=lambda a: (a.real, a.imag) |
| 298 | + ) |
| 299 | + for i in range(4): |
| 300 | + position_to_rooms[area_map.position_to_rooms[2 * i]] = "ABCD"[i] |
| 301 | + position_to_rooms[area_map.position_to_rooms[2 * i + 1]] = "ABCD"[i] |
| 302 | + room_to_positions["ABCD"[i]].append(area_map.position_to_rooms[2 * i]) |
| 303 | + room_to_positions["ABCD"[i]].append(area_map.position_to_rooms[2 * i + 1]) |
| 304 | + # Forbid to use the dot right outside the room |
| 305 | + area_map.dots[area_map.position_to_rooms[2 * i + 1] + 1j].is_waypoint = False |
| 306 | + area_map.position_to_rooms = position_to_rooms |
| 307 | + area_map.room_to_positions = room_to_positions |
| 308 | + |
| 309 | + # print (list(dot for dot in area_map.dots if area_map.dots[dot].is_waypoint)) |
| 310 | + |
| 311 | + for amphipod in area_map.amphipods: |
| 312 | + area_map.amphipods[amphipod].initial_room = area_map.position_to_rooms[ |
| 313 | + area_map.amphipods[amphipod].position |
| 314 | + ] |
| 315 | + area_map.amphipods[amphipod].movement_cost = 10 ** ( |
| 316 | + ord(area_map.amphipods[amphipod].terrain) - ord("A") |
| 317 | + ) |
| 318 | + |
| 319 | + area_graph = area_map.convert_to_graph() |
| 320 | + area_graph.all_edges = area_graph.edges |
| 321 | + area_graph.edges = { |
| 322 | + dot: { |
| 323 | + neighbor: distance |
| 324 | + for neighbor, distance in area_graph.edges[dot].items() |
| 325 | + if distance <= 2 |
| 326 | + } |
| 327 | + for dot in area_graph.vertices |
| 328 | + } |
| 329 | + print(len(area_graph.all_edges)) |
| 330 | + |
| 331 | + # print (area_graph.vertices) |
| 332 | + # print (area_graph.edges) |
| 333 | + |
| 334 | + state_graph = StateGraph() |
| 335 | + state_graph.area_graph = area_graph |
| 336 | + state_graph.amphipods = area_map.amphipods |
| 337 | + state_graph.position_to_rooms = area_map.position_to_rooms |
| 338 | + state_graph.room_to_positions = area_map.room_to_positions |
| 339 | + state_graph.dots = area_map.dots |
| 340 | + |
| 341 | + state = tuple( |
| 342 | + area_map.dots[area_map.amphipods[amphipod].position] |
| 343 | + for amphipod in sorted(area_map.amphipods.keys()) |
| 344 | + ) |
| 345 | + # print ('area_map.amphipods', area_map.amphipods) |
| 346 | + |
| 347 | + print("state", state) |
| 348 | + # print ('equivalent', state_graph.equivalent_positions(state)) |
| 349 | + print("estimate", state_graph.estimate_to_complete(state, None)) |
| 350 | + |
| 351 | + print(state_graph.a_star_search(state)) |
| 352 | + |
| 353 | + # In the example, A is already in the right place |
| 354 | + # In all other cases, 1 anphipod per group has to go to the bottom, so 1 move per amphipod |
| 355 | + |
| 356 | + |
| 357 | +else: |
| 358 | + for string in puzzle_input.split("\n"): |
| 359 | + if string == "": |
| 360 | + continue |
| 361 | + |
| 362 | + |
| 363 | +# -------------------------------- Outputs / results --------------------------------- # |
| 364 | + |
| 365 | +print("Case :", case_to_test, "- Part", part_to_test) |
| 366 | +print("Expected result : " + str(puzzle_expected_result)) |
| 367 | +print("Actual result : " + str(puzzle_actual_result)) |
| 368 | +# Date created: 2021-12-23 08:11:43.693421 |
0 commit comments