Advent of Code Day 20

In [125]:
def readfile(input_file):
    with open(input_file) as inp:
        return inp.read().rstrip('\n')
In [126]:
testinput = """         A           
         A           
  #######.#########  
  #######.........#  
  #######.#######.#  
  #######.#######.#  
  #######.#######.#  
  #####  B    ###.#  
BC...##  C    ###.#  
  ##.##       ###.#  
  ##...DE  F  ###.#  
  #####    G  ###.#  
  #########.#####.#  
DE..#######...###.#  
  #.#########.###.#  
FG..#########.....#  
  ###########.#####  
             Z       
             Z"""
In [127]:
from collections import defaultdict

def find_path(inp):
    contents = [[y for y in x] for x in inp.split("\n")]
    width = len(contents[0]) - 4
    height = len(contents) - 4

    grid = [] # connections
    debug = []
    for y in range(height + 4):
        debug.append([0] * (width + 4))
        grid.append([])
        for x in range(width + 4):
            grid[y].append(set())

    portals = defaultdict(list)

    for y in range(1, height + 3):
        for x in range(1, width + 3):
            if contents[y][x] != '.' and not contents[y][x].isalpha():
                continue

            for ox, oy in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                if contents[y + oy][x + ox] == '.':
                    grid[y][x].add(((x + ox), (y + oy)))

                elif contents[y + oy][x + ox].isalpha() and not contents[y][x].isalpha():
                    portal = None
                    if oy == 0 and ox == 1: 
                        portal = "".join(contents[y][x + 1:x + 3])
                        portals[portal].append((x + ox, y))
                    if oy == 0 and ox == -1: 
                        portal = "".join(contents[y][x - 2:x])
                        portals[portal].append((x + ox, y))
                    if ox == 0 and oy == 1:
                        portal = contents[y + 1][x] + contents[y + 2][x]
                        portals[portal].append((x, y + oy))
                    if ox == 0 and oy == -1:
                        portal = contents[y - 2][x] + contents[y - 1][x]
                        portals[portal].append((x, y + oy))
                    grid[y][x].add(portal)
                    
    visited = set()
    q = [ (next(iter(portals['AA'])), -1) ]
    
    while q:
        (x, y), d = q.pop(0)
        if (x, y) in visited:
            continue
        visited.add((x, y)) 
        debug[y][x] = d

        for conn in grid[y][x]:
            if conn == 'ZZ':
                #for y in debug:
                #    for x in y:
                #        print(" %2d " % x, end="")
                #    print()

                return d

            if isinstance(conn, tuple):
                q.append((conn, d + 1))
            else:
                for pt in portals[conn]:
                    if pt[0] != x and pt[1] != y:
                        q.append((pt, d))

    assert False, "failed"

find_path(testinput)
find_path(readfile("AoC/input20.txt"))
Out[127]:
568
In [128]:
find_path("""                   A               
                   A               
  #################.#############  
  #.#...#...................#.#.#  
  #.#.#.###.###.###.#########.#.#  
  #.#.#.......#...#.....#.#.#...#  
  #.#########.###.#####.#.#.###.#  
  #.............#.#.....#.......#  
  ###.###########.###.#####.#.#.#  
  #.....#        A   C    #.#.#.#  
  #######        S   P    #####.#  
  #.#...#                 #......VT
  #.#.#.#                 #.#####  
  #...#.#               YN....#.#  
  #.###.#                 #####.#  
DI....#.#                 #.....#  
  #####.#                 #.###.#  
ZZ......#               QG....#..AS
  ###.###                 #######  
JO..#.#.#                 #.....#  
  #.#.#.#                 ###.#.#  
  #...#..DI             BU....#..LF
  #####.#                 #.#####  
YN......#               VT..#....QG
  #.###.#                 #.###.#  
  #.#...#                 #.....#  
  ###.###    J L     J    #.#.###  
  #.....#    O F     P    #.#...#  
  #.###.#####.#.#####.#####.###.#  
  #...#.#.#...#.....#.....#.#...#  
  #.#####.###.###.#.#.#########.#  
  #...#.#.....#...#.#.#.#.....#.#  
  #.###.#####.###.###.#.#.#######  
  #.#.........#...#.............#  
  #########.###.###.#############  
           B   J   C               
           U   P   P             """)
Out[128]:
58
In [129]:
def find_path2(inp):
    contents = [[y for y in x] for x in inp.split("\n")]
    width = len(contents[0]) - 4
    height = len(contents) - 4

    grid = [] # connections
    debug = []
    for y in range(height + 4):
        debug.append([0] * (width + 4))
        grid.append([])
        for x in range(width + 4):
            grid[y].append(set())

    portals = {}

    for y in range(1, height + 3):
        for x in range(1, width + 3):
            if contents[y][x] != '.' and not contents[y][x].isalpha():
                continue

            for ox, oy in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
                if contents[y + oy][x + ox] == '.':
                    grid[y][x].add(((x + ox), (y + oy)))

                elif contents[y + oy][x + ox].isalpha() and not contents[y][x].isalpha():
                    portal = None

                    typ = -1 # outer
                    if y + oy >= 2 and y + oy <= height + 1 and x + ox >= 2 and x + ox <= width + 1:
                        typ = 1 # inner

                    if oy == 0 and ox == 1: 
                        portal = "".join(contents[y][x + 1:x + 3])
                        portals[(portal, typ)] = (x + ox, y)
                    if oy == 0 and ox == -1: 
                        portal = "".join(contents[y][x - 2:x])
                        portals[(portal, typ)] = (x + ox, y)
                    if ox == 0 and oy == 1:
                        portal = contents[y + 1][x] + contents[y + 2][x]
                        portals[(portal, typ)] = (x, y + oy)
                    if ox == 0 and oy == -1:
                        portal = contents[y - 2][x] + contents[y - 1][x]
                        portals[(portal, typ)] = (x, y + oy)
                    grid[y][x].add((portal, typ))

    visited = set()
    q = [ (portals[('AA', -1)], -1, 0) ]
    
    while q:
        (x, y), d, l = q.pop(0)
        if (x, y, l) in visited:
            continue
        visited.add((x, y, l)) 
        debug[y][x] = d

        for conn in grid[y][x]:
            if conn == ('ZZ', -1) and l == 0:
                return d

            if not isinstance(conn[0], str):
                q.append((conn, d + 1, l))
            else:
                p, donut = conn
                if (p, -donut) not in portals:
                    continue

                if l == 0 and donut == -1:
                    continue
                elif l != 0 and (p == 'AA' or p == 'ZZ'):
                    continue

                pt = portals[(p, -donut)]
                q.append((pt, d, l + donut))

    for y in debug:
        for x in y:
            print(" %4d " % x, end="")
        print()
    assert False, "failed"

find_path2(testinput)
Out[129]:
26
In [130]:
find_path2(readfile("AoC/input20.txt"))
Out[130]:
6546