aoc/2023/10/solution.py

#!/usr/bin/python3
import sys

directions = {
    'north': (-1, 0),
    'east': (0, 1),
    'south': (1, 0),
    'west': (0, -1),
}

pipes = {
    '.': [],
    '|': [directions['north'], directions['south']],
    '-': [directions['east'], directions['west']],
    'L': [directions['north'], directions['east']],
    'J': [directions['north'], directions['west']],
    '7': [directions['south'], directions['west']],
    'F': [directions['south'], directions['east']],
    'S': [directions['north'], directions['east'], directions['south'], directions['west']],
}

def print_grid(grid, format_int=False):
    for line in grid:
        if format_int:
            print(' '.join(['{:2d}'.format(n) for n in line]))
        else:
            print(line)
    rows = len(grid)
    cols = len(grid[0])
    print(f'{cols}x{rows} grid ({cols - 2}x{rows - 2} without pad)')

def construct_grid(f):
    grid = []
    for line in map(str.strip, f):
        grid.append(f'.{line}.')

    empty_line = '.' * len(grid[0])
    grid.insert(0, empty_line)
    grid.append(empty_line)

    return grid

def find_start(grid):
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            if grid[row][col] == 'S':
                return (row, col)
    return (-1, -1)

def connected(grid, start, end):
    start_row = start[0]
    start_col = start[1]
    end_row = end[0]
    end_col = end[1]
    start_char = grid[start_row][start_col]
    end_char = grid[end_row][end_col]
    for start_pipe_off_r, start_pipe_off_c in pipes[start_char]:
        if end_row == start_row + start_pipe_off_r and end_col == start_col + start_pipe_off_c:
            for end_pipe_off_r, end_pipe_off_c in pipes[end_char]:
                if start_row == end_row + end_pipe_off_r and start_col == end_col + end_pipe_off_c:
                    return True
    return False

def get_valid_neighbors(grid, nodes):
    valid = set()
    for row, col in nodes:
        for off_r in range(-1, 2):
            for off_c in range(-1, 2):
                if abs(off_r) + abs(off_c) != 1:
                    continue
                #if connected(grid[row][col], grid[row + off_r][col + off_c]):
                if connected(grid, (row, col), (row + off_r, col + off_c)):
                    valid.add((row + off_r, col + off_c))
    return valid

def get_connected_outside(distances, outsides, bounds):
    connected = set()
    min_row, max_row, min_col, max_col = bounds
    for row, col in outsides:
        for off_r in range(-1, 2):
            for off_c in range(-1, 2):
                row_t = row + off_r
                col_t = col + off_c
                if row_t < min_row or row_t >= max_row:
                    continue
                if col_t < min_col or col_t >= max_col:
                    continue
                if distances[row_t][col_t] > 0:
                    continue
                connected.add((row_t, col_t))
    return connected

def get_connected_inside(distances, outside):
    inside = [[0 for col in row] for row in distances]
    for row in range(len(inside)):
        for col in range(len(inside[row])):
            if distances[row][col] == 0 and outside[row][col] == 0:
                inside[row][col] = 1
    return inside

#def get_connected_inside(grid):
    #inside = [[0 for col in row] for row in grid]
    #north_south_rays = [[0 for col in row] for row in grid]
    #east_west_rays = [[0 for col in row] for row in grid]
    #south_north_rays = [[0 for col in row] for row in grid]
    #west_east_rays = [[0 for col in row] for row in grid]
    #for row in range(1, len(inside)):
        #for col in range(len(inside[row])):
            #if grid[row - 1][col] != '.':
                #north_south_rays[row][col] = north_south_rays[row - 1][col] + 1
            #else:
                #north_south_rays[row][col] = north_south_rays[row - 1][col]
    #for row in range(len(inside)):
        #for col in range(1, len(inside[row])):
            #if grid[row][col - 1] != '.':
                #west_east_rays[row][col] = west_east_rays[row][col - 1] + 1
            #else:
                #west_east_rays[row][col] = west_east_rays[row][col - 1]
    #for row in range(len(inside) - 1):
        #for col in range(len(inside[row])):
            #if grid[row + 1][col] != '.':
                #south_north_rays[row][col] = south_north_rays[row + 1][col] + 1
            #else:
                #south_north_rays[row][col] = south_north_rays[row + 1][col]
    #for row in range(len(inside)):
        #for col in range(1, len(inside[row])):
            #if grid[row][col - 1] != '.':
                #west_east_rays[row][col] = west_east_rays[row][col - 1] + 1
            #else:
                #west_east_rays[row][col] = west_east_rays[row][col - 1]
    #rays = [[0 for col in row] for row in grid]
    #for row in range(len(inside)):
        #for col in range(len(inside[row])):
            #rays[row][col] = west_east_rays[row][col] + north_south_rays[row][col]
    #print_grid(west_east_rays)
    #print_grid(north_south_rays)
    #print_grid(rays)
    #return inside

def part1():
    print('part 1')
    grid = construct_grid(sys.stdin)
    print_grid(grid)
    start = find_start(grid)
    print(f'start is {start}')
    distances = [[0 for col in row] for row in grid]
    distances[start[0]][start[1]] = 1
    print_grid(distances)
    processed = set()
    nodes = set([start])
    while len(nodes) > 0:
        old = nodes.copy()
        for row, col in old:
            neighbors = get_valid_neighbors(grid, old)
            for row_n, col_n in neighbors:
                if (row_n, col_n) not in processed:
                    nodes.add((row_n, col_n))
                    if distances[row_n][col_n] != 0:
                        distances[row_n][col_n] = min(distances[row_n][col_n], distances[row][col] + 1)
                    else:
                        distances[row_n][col_n] = distances[row][col] + 1
            processed.add((row, col))
            nodes.remove((row, col))
    print_grid(distances)
    maximum = 0
    for row in distances:
        for col in row:
            maximum = max(maximum, col)
    print(f'max is {maximum - 1}')

def part2():
    print('part 2')
    grid = construct_grid(sys.stdin)
    print_grid(grid)
    start = find_start(grid)
    print(f'start is {start}')
    distances = [[0 for col in row] for row in grid]
    distances[start[0]][start[1]] = 1
    print_grid(distances)
    processed = set()
    nodes = set([start])
    while len(nodes) > 0:
        old = nodes.copy()
        for row, col in old:
            neighbors = get_valid_neighbors(grid, old)
            for row_n, col_n in neighbors:
                if (row_n, col_n) not in processed:
                    nodes.add((row_n, col_n))
                    if distances[row_n][col_n] != 0:
                        distances[row_n][col_n] = min(distances[row_n][col_n], distances[row][col] + 1)
                    else:
                        distances[row_n][col_n] = distances[row][col] + 1
            processed.add((row, col))
            nodes.remove((row, col))
    print_grid(distances, format_int=True)
    maximum = 0
    for row in distances:
        for col in row:
            maximum = max(maximum, col)
    print(f'max is {maximum - 1}')

    outside_grid = [[0 for col in row] for row in distances]
    processed = set()
    outsides = set([(1, 1)])
    bounds = (0, len(distances), 0, len(distances[0]))
    while len(outsides) > 0:
        old = outsides.copy()
        for row, col in old:
            neighbors = get_connected_outside(distances, outsides, bounds)
            #print(old, neighbors)
            for row_n, col_n in neighbors:
                if (row_n, col_n) not in processed:
                    outside_grid[row_n][col_n] = 1
                    outsides.add((row_n, col_n))
            processed.add((row, col))
            outsides.remove((row, col))
    #print_grid(outside_grid, format_int=True)

    inside_grid = get_connected_inside(distances, outside_grid)
    #print_grid(inside_grid, format_int=True)

    total = 0
    for row in inside_grid:
        total += sum(row)
    print(f'total of {total} inside tiles')

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