advent-of-code/2022/python/day12.py

import shared
import matrix
from dijkstar import Graph, find_path, algorithm


criteria = lambda _cur, _neighbor: _neighbor - _cur <= 1


def build_graph(mx):
    """
    This is the meat of the solution,
    getting the valid neighbors - and then weighing those neighbors as pathable
    - loop through each row/col and then find who that cell can navigate to, ULDR
    - if it can navigate, add an edge
    """
    graph = Graph()
    for y, row in enumerate(mx):
        for x, _ in enumerate(row):
            neighbors = matrix.valid_neighbors(mx, x=x, y=y, criteria=criteria)
            for neighbor in neighbors:
                graph.add_edge((y, x), (neighbor["y"], neighbor["x"]), 1)
    return graph


def part1(mx):
    start = matrix.find_in_matrix(mx, "S")
    end = matrix.find_in_matrix(mx, "E")
    # Now that we got the start/end, fix those to 'a' and 'z' like the instructions said
    mx[start[0]][start[1]] = "a"
    mx[end[0]][end[1]] = "z"
    # Turn the a-z into numbers 0-25
    matrix.apply_to_all(mx, lambda x: ord(x) - ord("a"))

    graph = build_graph(mx)
    path = find_path(graph, start, end)
    print(len(path.nodes) - 1)


def part2(mx):
    end = matrix.find_in_matrix(mx, "E")
    # don't NEED this, because we go from all 'a', but need to replace it still
    s = matrix.find_in_matrix(mx, "S")
    # Now that we got the start/end, fix those to 'a' and 'z' like the instructions said
    mx[s[0]][s[1]] = "a"
    mx[end[0]][end[1]] = "z"
    starts = matrix.find_in_matrix(mx, "a", one=False)

    # Turn the a-z into numbers 0-25
    matrix.apply_to_all(mx, lambda x: ord(x) - ord("a"))
    graph = build_graph(mx)

    paths = []
    # Find the yx of all 'a'
    for start in starts:
        try:
            path = find_path(graph, start, end)
            paths.append(path)
        except algorithm.NoPathError:
            # This 'a' is in a puddle of 'c's, so it's not pathable
            pass
    shortest = min(paths, key=lambda x: x.total_cost)
    # matrix.apply_to_all(mx, lambda x: chr(x+ord('a'))) # Back to letters, single char prettier
    # all_visited = []
    # for p in paths:
    #    all_visited.extend(p.nodes)
    # all_visited = list(set(all_visited))
    # matrix.highlight(mx, red=all_visited, blink_green=shortest.nodes)
    print(shortest.total_cost)


def main():
    mx = matrix.load_matrix_file(shared.get_fname(12), matrix.split_word_to_chr_list)
    with shared.elapsed_timer() as elapsed:
        part1(mx)
        print(elapsed())
    mx = matrix.load_matrix_file(shared.get_fname(12), matrix.split_word_to_chr_list)
    with shared.elapsed_timer() as elapsed:
        part2(mx)
        print(elapsed())


if __name__ == "__main__":
    main()