aoc/2022/12/solution.py

#!/usr/bin/python3
import sys
from queue import Queue

def print_grid(grid, as_chr=False):
    for row in grid:
        for col in row:
            print(chr(col) if as_chr else f'{col} ', end='')
        print()

def find_start(grid, start):
    for y, row in enumerate(grid):
        for x, col in enumerate(row):
            if col == ord(start):
                return (x, y)
    return (-1, -1)

def part1():
    start = chr(ord('a') - 1)
    end = chr(ord('z') + 1)
    grid = [[ord(c) for c in line.strip().replace('S', start).replace('E', end)] for line in sys.stdin]
    visited = [[False for col in row] for row in grid]
    steps = [[sys.maxsize for col in row] for row in grid]
    print_grid(grid, True)

    start_x, start_y = find_start(grid, start)
    max_x, max_y = len(grid[0]), len(grid)

    queue = Queue(0)
    #visited[start_y][start_x] = True
    queue.put((start_x, start_y))
    steps[start_y][start_x] = 0
    visited[start_y][start_x] = True
    while not queue.empty():
        x, y = queue.get()
        #print(x, y, chr(grid[y][x]))
        for ox, oy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x + ox, y + oy
            # skipping conditions
            if nx < 0 or ny < 0 or nx >= max_x or ny >= max_y:
                continue
            if grid[ny][nx] == ord(end):
                steps[ny][nx] = min(steps[ny][nx], steps[y][x] + 1)
                print(f'steps {steps[ny][nx]}')
            if visited[ny][nx]:
                #print(chr(grid[y][x]), chr(grid[ny][nx]))
                continue
            if grid[ny][nx] > grid[y][x] + 1:
                continue
            visited[ny][nx] = True
            steps[ny][nx] = min(steps[ny][nx], steps[y][x] + 1)
            queue.put((nx, ny))
    #print_grid(steps)

# worst pathfinding code of my life
# utterly lazy
def part2():
    end = chr(ord('z') + 1)
    grid = [[ord(c) for c in line.strip().replace('E', end)] for line in sys.stdin]
    print_grid(grid, True)

    max_x, max_y = len(grid[0]), len(grid)
    starts = [[(x, y) for x, c in enumerate(row) if c == ord('a')] for y, row in enumerate(grid)]
    min_steps = []
    for row in starts:
        for start_x, start_y in row:
            #print(start_x, start_y)
            visited = [[False for col in row] for row in grid]
            steps = [[sys.maxsize for col in row] for row in grid]
            queue = Queue(0)
            #visited[start_y][start_x] = True
            queue.put((start_x, start_y))
            steps[start_y][start_x] = 0
            visited[start_y][start_x] = True
            while not queue.empty():
                x, y = queue.get()
                #print(x, y, chr(grid[y][x]))
                for ox, oy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx, ny = x + ox, y + oy
                    # skipping conditions
                    if nx < 0 or ny < 0 or nx >= max_x or ny >= max_y:
                        continue
                    if grid[ny][nx] == ord(end):
                        steps[ny][nx] = min(steps[ny][nx], steps[y][x] + 1)
                        min_steps.append(steps[ny][nx])
                        print(f'steps {steps[ny][nx]}')
                    if visited[ny][nx]:
                        #print(chr(grid[y][x]), chr(grid[ny][nx]))
                        continue
                    if grid[ny][nx] > grid[y][x] + 1:
                        continue
                    visited[ny][nx] = True
                    steps[ny][nx] = min(steps[ny][nx], steps[y][x] + 1)
                    queue.put((nx, ny))
            #print_grid(steps)
    print(min(min_steps))

if sys.argv[1] in '1':
    part1()
else:
    part2()