131 lines
2.6 KiB
Python
131 lines
2.6 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
import random
|
||
|
|
from collections import defaultdict
|
||
|
|
import sys
|
||
|
|
|
||
|
|
sys.setrecursionlimit(15000)
|
||
|
|
|
||
|
|
|
||
|
|
no_slippery = True
|
||
|
|
|
||
|
|
|
||
|
|
PATH = 1
|
||
|
|
FOREST = 2
|
||
|
|
SLOPE_NORTH = 3
|
||
|
|
SLOPE_EAST = 4
|
||
|
|
SLOPE_SOUTH = 5
|
||
|
|
SLOPE_WEST = 6
|
||
|
|
|
||
|
|
|
||
|
|
map = []
|
||
|
|
|
||
|
|
with open("input.txt", "r") as f:
|
||
|
|
for line in f:
|
||
|
|
row = []
|
||
|
|
for char in line.strip():
|
||
|
|
tile = None
|
||
|
|
if char == ".":
|
||
|
|
tile = PATH
|
||
|
|
if char == "#":
|
||
|
|
tile = FOREST
|
||
|
|
if char == "^":
|
||
|
|
tile = SLOPE_NORTH
|
||
|
|
if char == ">":
|
||
|
|
tile = SLOPE_EAST
|
||
|
|
if char == "v":
|
||
|
|
tile = SLOPE_SOUTH
|
||
|
|
if char == "<":
|
||
|
|
tile = SLOPE_WEST
|
||
|
|
row.append(tile)
|
||
|
|
|
||
|
|
map.append(row)
|
||
|
|
|
||
|
|
|
||
|
|
def find_path(row):
|
||
|
|
for i, tile in enumerate(row):
|
||
|
|
if tile == PATH:
|
||
|
|
return i
|
||
|
|
|
||
|
|
|
||
|
|
start = (0, find_path(map[0]))
|
||
|
|
goal = (len(map) - 1, find_path(map[-1]))
|
||
|
|
|
||
|
|
|
||
|
|
def valid_next_step(destination, illegal_slope):
|
||
|
|
global no_slippery
|
||
|
|
(y, x) = destination
|
||
|
|
try:
|
||
|
|
tile = map[y][x]
|
||
|
|
|
||
|
|
if no_slippery:
|
||
|
|
return tile not in [FOREST]
|
||
|
|
else:
|
||
|
|
return tile not in [illegal_slope, FOREST]
|
||
|
|
except:
|
||
|
|
return False
|
||
|
|
|
||
|
|
|
||
|
|
def possible_directions(coords):
|
||
|
|
(y, x) = coords
|
||
|
|
tile = map[y][x]
|
||
|
|
|
||
|
|
if tile == FOREST:
|
||
|
|
raise Exception("Cannot be in a forest!")
|
||
|
|
|
||
|
|
if not no_slippery:
|
||
|
|
if tile == SLOPE_NORTH:
|
||
|
|
return [(y - 1, x)]
|
||
|
|
if tile == SLOPE_EAST:
|
||
|
|
return [(y, x + 1)]
|
||
|
|
if tile == SLOPE_SOUTH:
|
||
|
|
return [(y + 1, x)]
|
||
|
|
if tile == SLOPE_WEST:
|
||
|
|
return [(y, x - 1)]
|
||
|
|
|
||
|
|
steps = [
|
||
|
|
((y - 1, x), SLOPE_SOUTH),
|
||
|
|
((y, x + 1), SLOPE_WEST),
|
||
|
|
((y + 1, x), SLOPE_NORTH),
|
||
|
|
((y, x - 1), SLOPE_EAST),
|
||
|
|
]
|
||
|
|
|
||
|
|
valid_destinations = []
|
||
|
|
|
||
|
|
for destination, illegal_slope in steps:
|
||
|
|
if valid_next_step(destination, illegal_slope):
|
||
|
|
valid_destinations.append(destination)
|
||
|
|
|
||
|
|
return valid_destinations
|
||
|
|
|
||
|
|
|
||
|
|
longest_path = -1
|
||
|
|
|
||
|
|
memo = defaultdict(lambda: -1)
|
||
|
|
|
||
|
|
|
||
|
|
def walk(path, length, position):
|
||
|
|
global longest_path
|
||
|
|
|
||
|
|
if length < memo[position]:
|
||
|
|
return
|
||
|
|
|
||
|
|
if position == goal:
|
||
|
|
if length > longest_path:
|
||
|
|
longest_path = length
|
||
|
|
print("NEW BEST", longest_path)
|
||
|
|
return
|
||
|
|
|
||
|
|
cool = possible_directions(position)
|
||
|
|
random.shuffle(cool)
|
||
|
|
for next_position in cool:
|
||
|
|
if next_position not in path:
|
||
|
|
next_path = dict(path)
|
||
|
|
next_path[position] = True
|
||
|
|
walk(next_path, length + 1, next_position)
|
||
|
|
|
||
|
|
|
||
|
|
walk({}, 0, start)
|
||
|
|
|
||
|
|
print(longest_path)
|