2024 day16 solve1HEADmaster

1 files changed, 75 insertions, 0 deletions

diff --git a/2024/day16/solve.py b/2024/day16/solve.py
new file mode 100644
index 0000000..92a24f2
--- /dev/null
+++ b/2024/day16/solve.py
@@ -0,0 +1,75 @@
+from bisect import insort

+from typing import Optional

+

+

+class Globals:

+    start_position = None

+    end_position = None

+

+

+class Node:

+    def __init__(self, position: tuple[int, int], previous_node: Optional["Node"], cost: int):

+        self.position = position

+        self.previous_node = previous_node

+        self.cost = cost

+

+        self.estimated_total_cost = cost + abs(Globals.end_position[0] - position[0]) + abs(

+            Globals.end_position[1] - position[1])

+

+

+def is_node_in_list(node_list: list[Node], position: tuple[int, int]):

+    for node in node_list:

+        if node.position == position:

+            return True

+    return False

+

+

+data = []

+with open("input") as f:

+    for line in f:

+        data.append(line.strip())

+

+for row_idx, line in enumerate(data):

+    for col_idx, char in enumerate(line):

+        if char == "S":

+            Globals.start_position = (row_idx, col_idx)

+            if Globals.end_position is not None:

+                break

+        elif char == "E":

+            Globals.end_position = (row_idx, col_idx)

+            if Globals.start_position is not None:

+                break

+    else:

+        continue

+    break

+

+row_count = len(data)

+col_count = len(data[0])

+traveled_to_positions = []

+open_nodes = []

+open_nodes.append(Node(Globals.start_position, None, 0))

+while True:

+    current_node = open_nodes.pop()

+    if current_node.position == Globals.end_position:

+        print(current_node.cost)

+        break

+

+    traveled_to_positions.append(current_node.position)

+    if not current_node.previous_node is None:

+        prev_pos = current_node.previous_node.position

+        forward_dir = (current_node.position[0] - prev_pos[0], current_node.position[1] - prev_pos[1])

+        came_from_dir = (forward_dir[0] * -1, forward_dir[1] * -1)

+    else:

+        came_from_dir = None

+        forward_dir = (0, 1)

+    for direct in ((-1, 0), (1, 0), (0, -1), (0, 1)):

+        if direct == came_from_dir:

+            continue

+

+        is_forward_dir = forward_dir == direct

+

+        new_pos = (current_node.position[0] + direct[0], current_node.position[1] + direct[1])

+        if 0 <= new_pos[0] < row_count and 0 <= new_pos[1] < col_count and data[new_pos[0]][new_pos[1]] != "#" and \

+                new_pos not in traveled_to_positions and not is_node_in_list(open_nodes, new_pos):

+            new_node = Node(new_pos, current_node, current_node.cost + (1 if is_forward_dir else 1001))

+            insort(open_nodes, new_node, key=lambda x: -x.estimated_total_cost)