def readfile(input_file):
with open(input_file) as inp:
return inp.read().rstrip('\n')
testinput = """ A
A
#######.#########
#######.........#
#######.#######.#
#######.#######.#
#######.#######.#
##### B ###.#
BC...## C ###.#
##.## ###.#
##...DE F ###.#
##### G ###.#
#########.#####.#
DE..#######...###.#
#.#########.###.#
FG..#########.....#
###########.#####
Z
Z"""
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"))
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 """)
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)
find_path2(readfile("AoC/input20.txt"))