~noelle/aoc-2021

90a5019ec943b211a58c0a3e91404d4b4155f196 — Noelle Leigh 2 years ago 5831f64 main
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:
                node.neighbors.add(neighbor_key)
                nodes[neighbor_key].neighbors.add(key)

    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


def read_input(input_: TextIO):
    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__":
    input_tile = read_input(sys.stdin)
    tile_map = expand_tile(input_tile, FACTOR)
    print_map(tile_map)