advent_of_code_2021/day15/part2.py

import argparse
import functools
from typing import List, NamedTuple, Set, Tuple
import sys

parser = argparse.ArgumentParser()
parser.add_argument("ifile", type=argparse.FileType('r'))
args = parser.parse_args()

board = [[int(char) for char in line.strip()] for line in args.ifile.readlines()]


def expandMap(board: List[List[int]]) -> List[List[int]]:
    map: List[List[int]] = []

    # build the top 'bar' of the map
    for line in board:
        clone = list(line)

        for repeat in range(0, 4):
            for index in range(0, len(line)):
                curr = clone[index + len(line) * repeat]
                if curr == 9:
                    curr = 1
                else:
                    curr += 1
                clone.append(curr)
        map.append(clone)

    for repeat in range(0, 4):
        for line_index in range(0, len(board)):
            line = []
            for col in range(0, len(map[0])):
                curr = map[len(board) * repeat + line_index][col]
                if curr == 9:
                    curr = 1
                else:
                    curr += 1
                line.append(curr)
            map.append(line)

    return map


def printMap(board: List[List[int]]):
    for line in board:
        print("".join(map(str, line)))

MAX_VAL = 10000000000000000000
expanded_map = expandMap(board)
# expanded_map = board
max_x_pos = len(expanded_map[0]) - 1
max_y_pos = len(expanded_map) - 1
sys.setrecursionlimit(2 * (max_x_pos + max_y_pos + 20))

class Point(NamedTuple):
    x: int
    y: int

best_by_pos = [[MAX_VAL for pos in line] for line in expanded_map]
best_by_pos[0][0] = 0
traversed = [[False for pos in line] for line in expanded_map]
CURR_BEST = MAX_VAL

def lowerNode(costMap: List[List[int]], first: Point, second: Point):
    if costMap[first.y][first.x] < costMap[second.y][second.x]:
        return first
    else:
        return second

def nodeSearch(untraversedSet: List[Point], currentCostMap: List[List[int]], edgeCosts: List[List[int]]):
    pos = functools.reduce(functools.partial(lowerNode,  currentCostMap), untraversedSet[1:], untraversedSet[0])
    untraversedSet.remove(pos)

    if currentCostMap[pos.y][pos.x] == MAX_VAL:
        print("FAILED")
        sys.exit()

    if pos.x == max_x_pos and pos.y == max_y_pos:
        print(currentCostMap[pos.y][pos.x])
        sys.exit(1)

    # for each neighbor, consider costs

    consider = [
        Point(pos.x + 1, pos.y),
        Point(pos.x - 1, pos.y),
        Point(pos.x, pos.y - 1),
        Point(pos.x, pos.y + 1)
    ]

    for other in consider:
        if 0 <= other.x <= max_x_pos and 0 <= other.y <= max_y_pos and not traversed[other.y][other.x]:
            currentCostMap[other.y][other.x] = min(currentCostMap[other.y][other.x], currentCostMap[pos.y][pos.x] + edgeCosts[other.y][other.x])
            if other not in untraversedSet:
                untraversedSet.append(other)

    traversed[pos.y][pos.x] = True


todo = [Point(0, 0)]

while len(todo) != 0:
    nodeSearch(todo, best_by_pos, expanded_map)

for line in traversed:
    print("".join(map(lambda x: "*" if x else " ", line)))