1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#!/usr/bin/env python3
# import numpy as np
from functools import reduce
from re import findall
from copy import deepcopy
from collections import defaultdict
import sys
# filename = "in/day24.ref"
filename = "in/day24.pzl"
data = open(filename).read()
lines = [line for line in data.rstrip('\n').split('\n')]
# print(lines)
D = dict()
for y,line in enumerate(lines):
for x,val in enumerate(line):
if val != '.':
D[(y,x)] = val
def get_max(D):
min_y = 1000
max_y = 0
min_x = 1000
max_x = 0
for y,x in D:
min_y = min(min_y, y)
max_y = max(max_y, y)
min_x = min(min_x, x)
max_x = max(max_x, x)
return min_y, max_y, min_x, max_x
def print_grid(D, P):
min_y, max_y, min_x, max_x = get_max(D)
for y in range(min_y, max_y + 1):
for x in range(min_x, max_x + 1):
if (y,x) in P:
print('E',end='')
elif (y,x) in D:
print(D[(y,x)][0],end='')
else:
print('.', end='')
print()
print()
print()
min_y, max_y, min_x, max_x = get_max(D)
start_x = 1
end_x = max_x - 1
def get_next_D(D):
Dn = defaultdict(list)
for (y,x) in D:
for val in D[(y,x)]:
if val == '#':
Dn[(y,x)].append('#')
elif val == '>':
nx = x + 1
if nx == max_x:
nx = 1
Dn[(y,nx)].append('>')
elif val == '<':
nx = x - 1
if nx == 0:
nx = max_x - 1
Dn[(y,nx)].append('<')
elif val == 'v':
ny = y + 1
if ny == max_y:
ny = 1
Dn[(ny,x)].append('v')
elif val == '^':
ny = y - 1
if ny == 0:
ny = max_y - 1
Dn[(ny,x)].append('^')
return Dn
def dfs(Dstart, Pstart, Pend):
P = Pstart
D = Dstart
it = 0
for _ in range(1000):
it += 1
Pn = set()
D = get_next_D(D)
for y,x in P:
for dy,dx in [0,0], [1,0], [-1,0], [0,1], [0,-1]:
if 0 <= y+dy <= max_y and 0 <= x+dx <= max_x:
if (y+dy, x+dx) not in D:
Pn.add((y+dy,x+dx))
P = Pn
# print_grid(D, P)
# print(P)
for (y,x) in P:
if (y,x) in Pend:
return D, it
Pstart = set()
Pstart.add((0,1))
Pend = set()
Pend.add((max_y, max_x-1))
D, t1 = dfs(D, Pstart, Pend)
D, t2 = dfs(D, Pend, Pstart)
D, t3 = dfs(D, Pstart, Pend)
res1 = t1
res2 = t1 + t2 + t3
print('res1:', res1)
print('res2:', res2)
|
