103 lines
2.4 KiB
Python
103 lines
2.4 KiB
Python
|
import sys
|
||
|
|
import os
|
||
|
|
sys.path.insert(1, os.path.abspath('../../'))
|
||
|
|
from python_tools.aoc_utils import *
|
||
|
|
import collections as C
|
||
|
|
sys.setrecursionlimit(1000000)
|
||
|
|
|
||
|
|
G = C.defaultdict(list)
|
||
|
|
|
||
|
|
|
||
|
|
def get_starting_pos(input):
|
||
|
|
for ic, i in enumerate(input):
|
||
|
|
for jc, j in enumerate(i):
|
||
|
|
if j == '^':
|
||
|
|
return [ic, jc, -1, 0]
|
||
|
|
|
||
|
|
|
||
|
|
VISITED = {}#C.defaultdict(lambda: False)
|
||
|
|
OBS = C.defaultdict(list)
|
||
|
|
WOULD_VISIT = {}
|
||
|
|
|
||
|
|
def explore_path(pos, input):
|
||
|
|
global VISITED
|
||
|
|
global WOULD_VISIT
|
||
|
|
rot = pos.copy()
|
||
|
|
rot = [pos[0]+pos[2], pos[1]+pos[3], pos[2], pos[3]]
|
||
|
|
if (rot[0] >= len(input) or rot[0] < 0 or
|
||
|
|
rot[1] >= len(input[0]) or rot[1] < 0):
|
||
|
|
return False
|
||
|
|
|
||
|
|
|
||
|
|
if input[rot[0]][rot[1]] == '#':
|
||
|
|
rot = [pos[0], pos[1], pos[3], -pos[2]]
|
||
|
|
|
||
|
|
if tuple(rot) in WOULD_VISIT:
|
||
|
|
return True
|
||
|
|
else:
|
||
|
|
WOULD_VISIT[tuple(rot)] = True
|
||
|
|
return explore_path(rot, input)
|
||
|
|
|
||
|
|
START = 0
|
||
|
|
|
||
|
|
def take_step(pos, input):
|
||
|
|
global G
|
||
|
|
global VISITED
|
||
|
|
global WOULD_VISIT
|
||
|
|
global START
|
||
|
|
next_pos = [pos[0]+pos[2], pos[1]+pos[3], pos[2], pos[3]]
|
||
|
|
# WOULD_VISIT = VISITED.copy()
|
||
|
|
WOULD_VISIT = {}
|
||
|
|
if (next_pos[0] >= len(input) or next_pos[0] < 0 or
|
||
|
|
next_pos[1] >= len(input[0]) or next_pos[1] < 0):
|
||
|
|
return True
|
||
|
|
elif input[next_pos[0]][next_pos[1]] == '#':
|
||
|
|
next_pos = [pos[0], pos[1], pos[3], -pos[2]]
|
||
|
|
else:
|
||
|
|
temp = input[next_pos[0]][next_pos[1]]
|
||
|
|
input[next_pos[0]][next_pos[1]] = '#'
|
||
|
|
rot = [pos[0], pos[1], pos[3], -pos[2]]
|
||
|
|
if explore_path(START, input):
|
||
|
|
# temp = 'O'
|
||
|
|
OBS[*next_pos[0:2]] = [True]
|
||
|
|
input[next_pos[0]][next_pos[1]] = temp
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
G[*next_pos[0:2]].append(next_pos)
|
||
|
|
pos[0] = next_pos[0]
|
||
|
|
pos[1] = next_pos[1]
|
||
|
|
pos[2] = next_pos[2]
|
||
|
|
pos[3] = next_pos[3]
|
||
|
|
return False
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
def part_one(input):
|
||
|
|
global G
|
||
|
|
global OBS
|
||
|
|
global VISITED
|
||
|
|
global START
|
||
|
|
current_position = get_starting_pos(input)
|
||
|
|
START = get_starting_pos(input)
|
||
|
|
G[*current_position[0:2]].append(current_position)
|
||
|
|
while True:
|
||
|
|
VISITED[tuple(current_position)] = True
|
||
|
|
ret = take_step(current_position, input)
|
||
|
|
if ret == True:
|
||
|
|
break
|
||
|
|
print("Part One: ", len(G))
|
||
|
|
print("Part Two: ", len(OBS))
|
||
|
|
# for i in input:
|
||
|
|
# print(i)
|
||
|
|
|
||
|
|
def main():
|
||
|
|
contents = file2listoflists("input.txt")
|
||
|
|
part_one(contents)
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
main()
|
||
|
|
|