Day 12 - Advent of Code 2022

""" day_12_01.py """

# usage: python3 day_12_01.py < input


import sys


def parse(data):
    """ create dictionary of paths """
    def neighbours(point):
        """ calculate valid neighbours """
        def diff(p1, p2):
            """ difference in heights """
            mapping = {'S': 'a', 'E': 'z'}
            x1, y1, x2, y2 = *p1, *p2
            v1 = mapping.get(heights[y1][x1], heights[y1][x1])
            v2 = mapping.get(heights[y2][x2], heights[y2][x2])
            return ord(v1) - ord(v2)

        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        xp, yp = point
        options = [(xp + dx, yp + dy) for dx, dy in deltas]
        x_max, y_max = len(heights[0]), len(heights)
        valid = [(x, y) for x, y in options
                 if x in range(x_max) and y in range(y_max)]
        return [(x, y) for x, y in valid if diff((x, y), (xp, yp)) <= 1]

    heights = [list(row) for row in data.splitlines()]

    output = {}
    for y, row in enumerate(heights):
        for x, value in enumerate(row):
            if value == 'S':
                output['start'] = (x, y)
            elif value == 'E':
                output['end'] = (x, y)
            output[(x, y)] = neighbours((x, y))
    return output


def shortest_path(start, end, data):
    """ calculate shortest path from start to end """
    track = {start: [start]}
    queue = [start]
    while queue:
        latest = queue.pop(0)
        for step in data[latest]:
            if step not in track:
                track[step] = [track[latest], step]
                queue.append(step)
    output = []
    while track[end]:
        output.append(track[end].pop())
        if track[end]:
            track[end] = track[end][0]
    output.reverse()
    return output


paths = parse(sys.stdin.read())
print(len(shortest_path(paths['start'], paths['end'], paths)) - 1)

""" day_12_02.py """

# usage: python3 day_12_02.py < input


import sys


def parse(data):
    """ create dictionary of paths """
    def neighbours(point):
        """ calculate valid neighbours """
        def diff(p1, p2):
            """ difference in heights """
            mapping = {'S': 'a', 'E': 'z'}
            x1, y1, x2, y2 = *p1, *p2
            v1 = mapping.get(heights[y1][x1], heights[y1][x1])
            v2 = mapping.get(heights[y2][x2], heights[y2][x2])
            return ord(v1) - ord(v2)

        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        xp, yp = point
        options = [(xp + dx, yp + dy) for dx, dy in deltas]
        x_max, y_max = len(heights[0]), len(heights)
        valid = [(x, y) for x, y in options
                 if x in range(x_max) and y in range(y_max)]
        return [(x, y) for x, y in valid if diff((x, y), (xp, yp)) <= 1]

    heights = [list(row) for row in data.splitlines()]

    output = {}
    for y, row in enumerate(heights):
        for x, value in enumerate(row):
            if value == 'S':
                output['start'] = (x, y)
            elif value == 'E':
                output['end'] = (x, y)
            if value in ['a', 'S']:
                output['a'] = output.get('a', []) + [(x, y)]
            output[(x, y)] = neighbours((x, y))
    return output


def shortest_path(start, end, data):
    """ calculate shortest path from start to end """
    track = {start: [start]}
    queue = [start]
    while queue:
        latest = queue.pop(0)
        for step in data[latest]:
            if step not in track:
                track[step] = [track[latest], step]
                queue.append(step)
    output = []
    while track.get(end):
        output.append(track[end].pop())
        if track[end]:
            track[end] = track[end][0]
    output.reverse()
    return output


paths = parse(sys.stdin.read())
candidates = [len(shortest_path(start, paths['end'], paths))
              for start in paths['a']]
print(min([i for i in candidates if i > 0]) - 1)