<jupyter_start><jupyter_text>[Day 15: Chiton](https://adventofcode.com/2021/day/15)<jupyter_code>import collections as cl
import dataclasses as dc
from typing import Optional<jupyter_output><empty_output><jupyter_text>Part 1<jupyter_code>example_data = [
    "1163751742",
    "1381373672",
    "2136511328",
    "3694931569",
    "7463417111",
    "1319128137",
    "1359912421",
    "3125421639",
    "1293138521",
    "2311944581",
]
def parse_input(input_data: list[str]) -> list[list[int]]:
    return [list(map(int, row)) for row in input_data]


@dc.dataclass
class Node:
    risk: Optional[int] = None
    best_neighbour: tuple[Optional[int], Optional[int]] = (None, None)
    not_visited: bool = True


def dijkstra(start_coord: tuple[int, int], end_coord: tuple[int, int], risk_map: list[list[int]]) -> list[tuple[int, int]]:
    # get map boundaries
    max_row = len(risk_map) - 1
    max_col = len(risk_map[0]) - 1

    # new nodes have an (implicit) risk of (None: used as infinite), set cost start node to 0
    nodes = cl.defaultdict(Node)
    nodes[start_coord].risk = 0

    # initialize loop
    todo = cl.defaultdict(int)
    best_candidate_coord = start_coord
    while best_candidate_coord != end_coord:
        best_candidate = nodes[best_candidate_coord]

        # visit all non-visited neighbors
        br, bc = best_candidate_coord
        for nr, nc in ((br+1, bc), (br, bc+1), (br-1, bc), (br, bc-1)):
            # only when the coordinates for the neighbor are valid
            if (0 <= nr <= max_row) and (0 <= nc <= max_col):
                neighbor_coord = (nr, nc)
                neighbor = nodes[neighbor_coord]
                if neighbor.not_visited:
                    # do we need to update the risk and best neighbour?
                    new_neighbor_risk = best_candidate.risk + risk_map[nr][nc]
                    if (neighbor.risk is None) or (new_neighbor_risk < neighbor.risk):
                        # update neighbor node
                        neighbor.risk = new_neighbor_risk
                        neighbor.best_neighbour = best_candidate_coord
                        # upsert in todo as well
                        todo[neighbor_coord] = new_neighbor_risk

        # done with best candidate: mark it visited
        best_candidate.not_visited = False

        # get new best candidate (i.e. node with lowest risk so far)
        best_candidate_coord = min(todo, key=todo.get)
        del todo[best_candidate_coord]

    # gather nodes from end back to the start
    route = [best_candidate_coord]
    while best_candidate_coord != start_coord:
        best_candidate_coord = nodes[best_candidate_coord].best_neighbour
        route.append(best_candidate_coord)
    return route[::-1]  # and return in correct order
def part1(input_data: list[str]) -> int:
    risk_map = parse_input(input_data)
    route = dijkstra((0,0), (len(risk_map)-1, len(risk_map[0])-1), risk_map)
    return sum(risk_map[row][col] for row, col in route[1:])
print(f"Check part 1: {part1(example_data) == 40}")
with open(r"..\data\Day 15 input.txt", "r") as fh_in:
    input_data = [line.strip() for line in fh_in]
print(f"Input check: {len(input_data) == 100}")
print(f"Answer part 1: {part1(input_data)}")<jupyter_output>Answer part 1: 390<jupyter_text>Part 2<jupyter_code>def expand_map(initial_map: list[list[int]], factor: int) -> list[list[int]]:
    horizontal_block = []
    for row in initial_map:
        new_row = []
        for i in range(0, factor):
            new_row.extend([col+i if col+i<10 else col+i-9 for col in row])
        horizontal_block.append(new_row)

    new_map = []
    for i in range(0, factor):
        for row in horizontal_block:
            new_map.append([col+i if col+i<10 else col+i-9 for col in row])

    return new_map


def part2(input_data: list[str]) -> int:
    risk_map = expand_map(parse_input(input_data), 5)
    route = dijkstra((0,0), (len(risk_map)-1, len(risk_map[0])-1), risk_map)
    return sum(risk_map[row][col] for row, col in route[1:])
print(f"Check part 2: {part2(example_data) == 315}")
%%time
print(f"Answer part 2: {part2(input_data)}")<jupyter_output>Answer part 2: 2814
Wall time: 10.4 s
{'fraction_non_alphanumeric': 0.11921793037672866, 'fraction_numerical': 0.041726275631855034, 'mean_word_length': 3.022051773729626, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '573715', 'license': 'Unlicense', 'n_tokens_mistral': 1561, 'n_tokens_neox': 1427, 'n_words': 358, 'path': 'src/Day 15 Chiton.ipynb', 'repo_name': 'bh1428/advent_of_code_2021', 'size': '4194'}