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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
import intcode
import heapq as heap
import collections
import queue
import time
size = 2
def draw(board, droid=None, path=None, visited=None):
min_x=max_x=min_y=max_y = 0
for p in board:
min_x = min(p[0], min_x)
max_x = max(p[0], max_x)
min_y = min(p[1], min_y)
max_y = max(p[1], max_y)
s = ""
for y in range(min_y-1, max_y+2):
s += "\n"
for x in range(min_x-1, max_x+2):
point = (x, y)
if droid is not None and point == droid:
s += "D"*size
elif path is not None and point in path:
s += "\u2591"*size
elif visited is not None and point in visited:
s += "."*size
elif point in board:
s += ("\u2588" if board[point] == "#" else " ")*size
else:
s += "."*size
return s
def dist(a, b):
return abs(a[0] - b[0]) + abs(a[1] -b[1])
def neighbours(p):
''' Return all neighbours to p in a tuple '''
return [(p[0]+1, p[1]), (p[0]-1, p[1]), \
(p[0], p[1]+1), (p[0], p[1]-1)]
def get_path(p_start, p_end, board):
#print("get_path", p_start, p_end)
'''
Return a path as a deque between p_start and p_end given some board-state
The path is guaranteed valid but not guaranteed the shortest
'''
if p_start == p_end:
# already at destination, no path
return collections.deque()
visited = set()
h = []
heap.heappush(h, (0, p_start, collections.deque()))
while True:
cur = heap.heappop(h)
for n in neighbours(cur[1]):
if n == p_end:
# done
cur[2].append(n)
return cur[2]
if n in visited:
continue
if n not in board:
# unknown point
continue
if board[n] == "#":
# wall
continue
new_path = collections.deque(cur[2])
new_path.append(n)
visited.add(n)
heap.heappush(h, (dist(p_start, n), n, new_path))
def get_short_path(start, end, board):
'''
Return the shortest path between start and end given some board-state
The path is guaranteed valid and the shortest available
'''
if start == end:
return collections.deque()
visited = set()
h = []
heap.heappush(h, (0, start, collections.deque()))
while True:
cur = heap.heappop(h)
for n in neighbours(cur[1]):
if n == end:
cur[2].append(n)
return cur[2]
if n in visited:
continue
if n not in board:
continue
if board[n] == "#":
continue
new_path = collections.deque(cur[2])
new_path.append(n)
visited.add(n)
#print(draw(board, path=new_path, visited=visited))
#time.sleep(0.01)
heap.heappush(h, (cur[0] + 1, n, new_path))
cur_x = cur_y = 0
stack = collections.deque()
stack.append((0,0))
path = collections.deque()
board = {}
oxygen = (0,0)
f = open("../input/15", "r").readlines()
c = intcode.Computer([int(x) for x in f[0].split(",")])
auto = True
steps = 0
while not c.SIG_HALT:
if auto and len(stack) == 0:
print("stack empty")
break
c.step()
if c.SIG_INPUT:
direction = 0
prev_x, prev_y = cur_x, cur_y
if auto:
if len(path) == 0:
# find new path
for n in neighbours((cur_x, cur_y)):
if n not in stack and n not in board:
stack.append(n)
next = stack.pop()
path = get_path((cur_x, cur_y), next, board)
next_step = path.popleft()
if next_step[1] == cur_y-1:
direction = 1
cur_y -= 1
elif next_step[1] == cur_y+1:
direction = 2
cur_y += 1
elif next_step[0] == cur_x-1:
direction = 3
cur_x -= 1
elif next_step[0] == cur_x+1:
direction = 4
cur_x += 1
else:
print("invalid path")
break
else: # manual
next_step = input()
if next_step == "w":
direction = 1
cur_y -= 1
elif next_step == "s":
direction = 2
cur_y += 1
elif next_step == "a":
direction = 3
cur_x -= 1
elif next_step == "d":
direction = 4
cur_x += 1
else:
continue
c.input = direction
steps += 1
c.SIG_INPUT = False
if c.SIG_OUTPUT:
# time.sleep(0.075)
# print(draw(board, droid=(cur_x, cur_y)))
if c.output == 0:
board[(cur_x, cur_y)] = "#"
cur_x, cur_y = prev_x, prev_y
elif c.output == 1:
board[(cur_x, cur_y)] = "."
elif c.output == 2:
board[(cur_x, cur_y)] = "O"
print("found oxygen at", (cur_x, cur_y))
oxygen = (cur_x, cur_y)
else:
break
c.output = None
c.SIG_OUTPUT = False
if not auto:
print(draw(board, (cur_x, cur_y)))
print(draw(board))
print(draw(board, path=get_path((0,0), oxygen, board)))
print(draw(board, path=get_short_path((0,0), oxygen, board)))
print(len(get_short_path((0,0), oxygen, board)))
print(steps)
|
