## ~noelle/aoc-2021

90a5019ec943b211a58c0a3e91404d4b4155f196 — Noelle Leigh 2 years ago
15_2 wip
2 files changed, 185 insertions(+), 0 deletions(-)

A 15/puzzle_2.py
A 15/puzzle_2_beta.py
A 15/puzzle_2.py => 15/puzzle_2.py +132 -0
@@ 0,0 1,132 @@
"""
Solution for AoC 2021 15 Puzzle 2
cat input.txt | python puzzle_2.py
"""
import heapq
import sys
from dataclasses import dataclass, field
from typing import NamedTuple
Coords = tuple[int, int]
@dataclass(order=False)
class Node:
x: int
y: int
risk: int
risk_from_start: int = sys.maxsize
neighbors: set[Coords] = field(default_factory=set)
def __lt__(self, other: "Node"):
return self.risk_from_start < other.risk_from_start
def __le__(self, other: "Node"):
return self.risk_from_start <= other.risk_from_start
def __gt__(self, other: "Node"):
return self.risk_from_start > other.risk_from_start
def __ge__(self, other: "Node"):
return self.risk_from_start >= other.risk_from_start
Graph = dict[Coords, Node]
def wrap_risk(value):
return (value % 10) + (value // 10)
def make_graph(base_tile: list[list[int]]) -> Graph:
tile_height = len(base_tile)
tile_width = len(base_tile[0])
# Create disconnected set of nodes
nodes: Graph = {}
for tile_row_index in range(5):
for tile_col_index in range(5):
for row_index, row in enumerate(base_tile):
for col_index, risk in enumerate(row):
real_row_index = row_index + (tile_row_index * tile_width)
real_col_index = col_index + (tile_col_index * tile_height)
real_risk = wrap_risk(risk + tile_row_index + tile_col_index)
real_risk = real_risk if real_risk else 1
nodes[(real_row_index, real_col_index)] = Node(
x=real_col_index, y=real_row_index, risk=real_risk
)
# Connect nodes
for key, node in nodes.items():
row_index, col_index = key
neighbor_keys = [
# North
(row_index - 1, col_index),
# East
(row_index, col_index + 1),
# South
(row_index + 1, col_index),
# West
(row_index, col_index - 1),
]
for neighbor_key in neighbor_keys:
if neighbor_key in nodes:
return nodes
class Point(NamedTuple):
x: int
y: int
def dijkstra(graph: Graph, start: Coords, end: Coords) -> int:
"""
Return the most risk-averse path from start to end on a map along with its cost.
Refs:
- https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Algorithm
- https://www.udacity.com/blog/2021/10/implementing-dijkstras-algorithm-in-python.html
"""
unvisited_coords = set(graph)
graph[start].risk = 0
graph[start].risk_from_start = 0
heap = []
heapq.heappush(heap, graph[start])
while unvisited_coords:
current_coords = min(unvisited_coords, key=lambda coords: graph[coords].risk_from_start)
current_node = graph[current_coords]
for neighbor_coords in current_node.neighbors & unvisited_coords:
new_risk_from_start = graph[neighbor_coords].risk + graph[current_coords].risk_from_start
if new_risk_from_start < graph[neighbor_coords].risk_from_start:
graph[neighbor_coords].risk_from_start = new_risk_from_start
unvisited_coords.remove(current_coords)
return graph[end].risk_from_start
def print_map(graph: Graph):
for coords in sorted(graph):
row_index, col_index = coords
if col_index == 0 and row_index > 0:
sys.stdout.write("\n")
sys.stdout.write(str(graph[coords].risk))
sys.stdout.write("\n")
if __name__ == "__main__":
cave_map = list(
map(
lambda line: list(
map(
lambda val: int(val),
line.strip(),
)
),
sys.stdin,
)
)
graph = make_graph(cave_map)
start = min(graph, key=lambda key: sum(key))
end = max(graph, key=lambda key: sum(key))
# print_map(graph)
total_risk = dijkstra(graph, start, end)
sys.stdout.write(str(total_risk))

A 15/puzzle_2_beta.py => 15/puzzle_2_beta.py +53 -0
@@ 0,0 1,53 @@
import sys
from typing import TextIO
FACTOR = 5
return list(
map(
lambda line: list(map(lambda val: int(val), line.strip())),
input_,
)
)
def wrap_risk(value):
return (value % 10) + (value // 10)
def expand_tile(input_tile: list[list[int]], factor: int):
tile_height = len(input_tile)
tile_width = len(input_tile[0])
tile_map = list(
map(
lambda _: list(
map(
lambda _: None,
range(factor * tile_width),
)
),
range(factor * tile_height),
)
)
for tile_row_index in range(factor):
for tile_col_index in range(factor):
for row_index, row in enumerate(input_tile):
for col_index, risk in enumerate(row):
new_row_index = row_index + (tile_row_index * tile_height)
new_col_index = col_index + (tile_col_index * tile_width)
new_risk = wrap_risk(risk + tile_row_index + tile_col_index)
tile_map[new_row_index][new_col_index] = new_risk
return tile_map
def print_map(tile_map: list[list[int]]):
print("\n".join(map(lambda row: "".join(map(lambda val: str(val), row)), tile_map)))
if __name__ == "__main__":