131 lines
3.3 KiB
Python
131 lines
3.3 KiB
Python
|
from collections import deque
|
||
|
|
from pprint import pprint
|
||
|
|
|
||
|
|
NORTH = 1
|
||
|
|
EAST = 2
|
||
|
|
SOUTH = 4
|
||
|
|
WEST = 8
|
||
|
|
|
||
|
|
ROOT = 0
|
||
|
|
IN_PARENS = 1
|
||
|
|
SKIPPING = 2
|
||
|
|
|
||
|
|
start_pos = 200, 200
|
||
|
|
grid = [[0] * start_pos[0] * 2 for _ in range(start_pos[1] * 2)]
|
||
|
|
|
||
|
|
min_x, max_x = start_pos
|
||
|
|
min_y, max_y = start_pos
|
||
|
|
|
||
|
|
|
||
|
|
def print_grid(x_=None, y_=None):
|
||
|
|
for y in range(min_y, max_y + 1):
|
||
|
|
for x in range(min_x, max_x + 1):
|
||
|
|
print(end="@")
|
||
|
|
print(end="-" if grid[y][x] & NORTH else "@")
|
||
|
|
print("#")
|
||
|
|
|
||
|
|
for x in range(min_x, max_x + 1):
|
||
|
|
print(end="|" if grid[y][x] & WEST else "@")
|
||
|
|
if (x, y) == start_pos:
|
||
|
|
print(end="X")
|
||
|
|
elif x == x_ and y == y_:
|
||
|
|
print(end=".")
|
||
|
|
else:
|
||
|
|
print(end=" ")
|
||
|
|
print("@")
|
||
|
|
print("@" * ((max_x - min_x) * 2 + 3))
|
||
|
|
|
||
|
|
|
||
|
|
def parse_input(inp):
|
||
|
|
global min_x, max_x, min_y, max_y
|
||
|
|
|
||
|
|
# print(inp, end="\n\n")
|
||
|
|
# print("\033[2J\033[;H")
|
||
|
|
stack = [(0, start_pos[0], start_pos[1])]
|
||
|
|
while stack:
|
||
|
|
# print("===================================")
|
||
|
|
# print(stack, end=" -> ")
|
||
|
|
start, x, y = stack.pop()
|
||
|
|
# print(start)
|
||
|
|
|
||
|
|
depth = 0
|
||
|
|
skip_to_end = False
|
||
|
|
for i in range(start, len(inp)):
|
||
|
|
c = inp[i]
|
||
|
|
|
||
|
|
if depth == 0 and not skip_to_end:
|
||
|
|
# print(f"{depth} {inp[:i]}\033[4;3{depth+1}m{inp[i]}\033[0m{inp[i+1:]} ({x:>2},{y:>2}) -> ", end="")
|
||
|
|
|
||
|
|
if c == "N": grid[y][x] |= NORTH; y -= 1; grid[y][x] |= SOUTH
|
||
|
|
elif c == "E": grid[y][x] |= EAST; x += 1; grid[y][x] |= WEST
|
||
|
|
elif c == "S": grid[y][x] |= SOUTH; y += 1; grid[y][x] |= NORTH
|
||
|
|
elif c == "W": grid[y][x] |= WEST; x -= 1; grid[y][x] |= EAST
|
||
|
|
|
||
|
|
if x < min_x: min_x = x
|
||
|
|
if x > max_x: max_x = x
|
||
|
|
if y < min_y: min_y = y
|
||
|
|
if y > max_y: max_y = y
|
||
|
|
|
||
|
|
# print(f"({x:>2},{y:>2})")
|
||
|
|
# print_grid(x, y)
|
||
|
|
# print()
|
||
|
|
|
||
|
|
|
||
|
|
if c == "(" and not skip_to_end:
|
||
|
|
if depth == 0:
|
||
|
|
stack.append((i + 1, x, y))
|
||
|
|
depth += 1
|
||
|
|
elif c == "|" and not skip_to_end:
|
||
|
|
if depth == 1:
|
||
|
|
stack.append((i + 1, x, y))
|
||
|
|
elif depth == 0:
|
||
|
|
skip_to_end = True
|
||
|
|
elif c == ")":
|
||
|
|
depth -= 1
|
||
|
|
if depth == -1:
|
||
|
|
skip_to_end = False
|
||
|
|
break
|
||
|
|
|
||
|
|
# print()
|
||
|
|
# print("\033[0;0H", end="")
|
||
|
|
# print_grid()
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
def bfs():
|
||
|
|
pos = start_pos
|
||
|
|
|
||
|
|
queue = deque([(pos, 0)])
|
||
|
|
seen = set()
|
||
|
|
lengths = []
|
||
|
|
max_len = 0
|
||
|
|
long_paths = 0
|
||
|
|
|
||
|
|
while queue:
|
||
|
|
(x, y), depth = queue.popleft()
|
||
|
|
if (x, y) in seen:
|
||
|
|
continue
|
||
|
|
seen.add((x, y))
|
||
|
|
|
||
|
|
if depth > max_len:
|
||
|
|
max_len = depth
|
||
|
|
if depth >= 1000:
|
||
|
|
long_paths += 1
|
||
|
|
|
||
|
|
if grid[y][x] & WEST: queue.append(((x - 1, y), depth + 1))
|
||
|
|
if grid[y][x] & EAST: queue.append(((x + 1, y), depth + 1))
|
||
|
|
if grid[y][x] & NORTH: queue.append(((x, y - 1), depth + 1))
|
||
|
|
if grid[y][x] & SOUTH: queue.append(((x, y + 1), depth + 1))
|
||
|
|
|
||
|
|
print("part 1:", max_len)
|
||
|
|
print("part 2:", long_paths)
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
inp = input()
|
||
|
|
parse_input(inp[1:-1])
|
||
|
|
bfs()
|
||
|
|
|
||
|
|
|
||
|
|
main()
|