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
|
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:
if board[point] == "#":
s += "\u2588" * size
elif board[point] == "S":
s += "\u2591" * size
else:
s += " " * size
else:
s += "." * size
return s
def neighbours(p):
return [(p[0]+1, p[1]), (p[0]-1, p[1]), \
(p[0], p[1]+1), (p[0], p[1]-1)]
def get_path(start, end, board):
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)] = "S"
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(len(get_path((0,0), oxygen, board)))
print(steps)
|
