1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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)
|
