-
Notifications
You must be signed in to change notification settings - Fork 0
/
15.py
104 lines (90 loc) · 3.45 KB
/
15.py
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
import os
inputFile = open(os.path.dirname(__file__) + '/input.txt', 'r')
line = inputFile.read().rstrip()
inputFile.close()
def run(input1, program, i, base):
while 1:
instruction = str(program[i]).zfill(5)
if i + 1 not in program:
program[i + 1] = 0
if i + 2 not in program:
program[i + 2] = 0
if i + 3 not in program:
program[i + 3] = 0
key1 = i + 1 if instruction[2] == '1' else program[i + 1] + base if instruction[2] == '2' else program[i + 1]
key2 = i + 2 if instruction[1] == '1' else program[i + 2] + base if instruction[1] == '2' else program[i + 2]
key3 = i + 3 if instruction[0] == '1' else program[i + 3] + base if instruction[0] == '2' else program[i + 3]
if key1 not in program:
program[key1] = 0
if key2 not in program:
program[key2] = 0
if key3 not in program:
program[key3] = 0
if instruction[-1] == '1':
program[key3] = program[key1] + program[key2]
i += 4
elif instruction[-1] == '2':
program[key3] = program[key1] * program[key2]
i += 4
elif instruction[-1] == '3':
program[key1] = input1
i += 2
elif instruction[-1] == '4':
return program[key1], program, i + 2, base
elif instruction[-1] == '5':
i = program[key2] if program[key1] else i + 3
elif instruction[-1] == '6':
i = i + 3 if program[key1] else program[key2]
elif instruction[-1] == '7':
program[key3] = 1 if program[key1] < program[key2] else 0
i += 4
elif instruction[-1] == '8':
program[key3] = 1 if program[key1] == program[key2] else 0
i += 4
elif instruction[-1] == '9':
base += program[key1]
i += 2
def solve():
program = dict(enumerate(int(i) for i in line.split(',')))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
paths = [((0, 0), program, 0, 0)]
visited = {(0, 0): 1}
new_paths = []
grid = {(0, 0): '.'}
steps = empty = 1
found = 0
# BFS
while len(paths):
for path in paths:
for move in range(1, 5):
direction = directions[move - 1]
pos = (path[0][0] + direction[0], path[0][1] + direction[1])
if pos not in visited:
visited[pos] = 1
output, new_program, new_i, new_base = run(move, dict(path[1]), path[2], path[3])
if output == 2:
if not found:
print(f'Part one: {steps}')
grid[pos] = 'O'
found = 1
elif output == 1:
grid[pos] = '.'
empty += 1
new_paths.append((pos, new_program, new_i, new_base))
else:
grid[pos] = '#'
paths = new_paths[:]
new_paths = []
steps += 1
minutes = 0
while empty > 0:
new_grid = dict(grid)
for i, j in grid:
if grid[(i, j)] == '.':
if grid[(i + 1, j)] == 'O' or grid[(i - 1, j)] == 'O' or grid[(i, j + 1)] == 'O' or grid[(i, j - 1)] == 'O':
new_grid[(i, j)] = 'O'
empty -= 1
grid = new_grid
minutes += 1
print(f'Part two: {minutes}')
solve()