day-15.jl (6888B)
1 function computer_step!(program, pc, relative_base, input)
2 # Runs from given pc until completion or next request for input.
3 # Modifies program and pc.
4 # Returns if the program has terminated and the output.
5 output = []
6 function get_param(loc, mode)
7 # Loc is gauranteed to exist.
8 if mode == 0
9 # Position mode.
10 get(program, program[loc] + 1, 0)
11 elseif mode == 1
12 # Immediate mode.
13 program[loc]
14 else
15 # Relative mode.
16 get(program, relative_base + program[loc] + 1, 0)
17 end
18 end
19 function get_res_loc(loc, mode)
20 # Loc is gauranteed to exist.
21 if mode == 0
22 # Position mode.
23 program[loc] + 1
24 else
25 # Relative mode.
26 relative_base + program[loc] + 1
27 end
28 end
29 while true
30 op_code = program[pc] % 100
31 mode_1 = (program[pc] % 1000) ÷ 100
32 mode_2 = (program[pc] % 10000) ÷ 1000
33 mode_3 = (program[pc] % 100000) ÷ 10000
34 if op_code == 1
35 program[get_res_loc(pc + 3, mode_3)] = (
36 get_param(pc + 1, mode_1)
37 + get_param(pc + 2, mode_2)
38 )
39 pc += 4
40 elseif op_code == 2
41 program[get_res_loc(pc + 3, mode_3)] = (
42 get_param(pc + 1, mode_1)
43 * get_param(pc + 2, mode_2)
44 )
45 pc += 4
46 elseif op_code == 3
47 if !isnothing(input)
48 program[get_res_loc(pc + 1, mode_1)] = input
49 input = nothing
50 else
51 return (pc, relative_base, false, output)
52 end
53 pc += 2
54 elseif op_code == 4
55 push!(output, get_param(pc + 1, mode_1))
56 pc += 2
57 elseif op_code == 5
58 if get_param(pc + 1, mode_1) != 0
59 pc = get_param(pc + 2, mode_2) + 1
60 else
61 pc += 3
62 end
63 elseif op_code == 6
64 if get_param(pc + 1, mode_1) == 0
65 pc = get_param(pc + 2, mode_2) + 1
66 else
67 pc += 3
68 end
69 elseif op_code == 7
70 program[get_res_loc(pc + 3, mode_3)] = (
71 get_param(pc + 1, mode_1)
72 < get_param(pc + 2, mode_2)
73 ) ? 1 : 0
74 pc += 4
75 elseif op_code == 8
76 program[get_res_loc(pc + 3, mode_3)] = (
77 get_param(pc + 1, mode_1)
78 == get_param(pc + 2, mode_2)
79 ) ? 1 : 0
80 pc += 4
81 elseif op_code == 9
82 relative_base += get_param(pc + 1, mode_1)
83 pc += 2
84 elseif op_code == 99
85 break
86 else
87 println("Unknown op code: ", op_code)
88 break
89 end
90 end
91 (pc, relative_base, true, output)
92 end
93
94 function flip(cmd)
95 if cmd == 1
96 2
97 elseif cmd == 2
98 1
99 elseif cmd == 3
100 4
101 else
102 3
103 end
104 end
105
106 function move_to_cmd(coord, cmd)
107 if cmd == 1
108 (coord[1], coord[2] + 1)
109 elseif cmd == 2
110 (coord[1], coord[2] - 1)
111 elseif cmd == 3
112 (coord[1] - 1, coord[2])
113 else
114 (coord[1] + 1, coord[2])
115 end
116 end
117
118 function chart_maze(program)
119 # Chart the maze via DFS
120 program = Dict(enumerate(copy(program)))
121 # Set program state.
122 pc = 1
123 relative_base = 0
124 # DFS to chart the maze.
125 curr_cmds = []
126 curr_path = [(0, 0)]
127 maze_map = Dict((0, 0) => 1)
128 # Start with initial directions.
129 queue = []
130 for cmd in 1:4
131 push!(queue, (1, cmd, move_to_cmd((0, 0), cmd)))
132 end
133 while !isempty(queue)
134 path_len, cmd, coord = pop!(queue)
135 # Check difference between current path and backtrack.
136 if length(curr_path) > path_len
137 # Backtrack
138 for cmd in map(flip, reverse(curr_cmds[path_len:end]))
139 pc, relative_base, _, _ = computer_step!(
140 program, pc, relative_base, cmd
141 )
142 end
143 # Chean up path.
144 resize!(curr_cmds, path_len - 1)
145 # Keep the origin.
146 resize!(curr_path, path_len)
147 end
148 # Move in specified direction.
149 pc, relative_base, _, step_output = computer_step!(
150 program, pc, relative_base, cmd
151 )
152 # Chart the result.
153 maze_map[coord] = step_output[1]
154 # Determine if we proceed in given direction.
155 if step_output[1] != 0
156 # Free space, record and plan next moves.
157 # Otherwise, keep original path.
158 push!(curr_cmds, cmd)
159 push!(curr_path, coord)
160 for next_cmd in 1:4
161 # Only visit uncharted location.
162 target = move_to_cmd(coord, next_cmd)
163 if !haskey(maze_map, target)
164 push!(queue, (path_len + 1, next_cmd, target))
165 end
166 end
167 end
168 end
169 maze_map
170 end
171
172 function find_min_path(maze_map)
173 # Return shortest path from (0, 0) to space labeled 2.
174 queue = []
175 visited = Dict()
176 push!(queue, (0, (0, 0)))
177 # BFS to find location.
178 while !isempty(queue)
179 path_len, coord = popfirst!(queue)
180 visited[coord] = true
181 dest = get(maze_map, coord, 0)
182 if dest == 1
183 # Explore next stpes.
184 for cmd in 1:4
185 next_coord = move_to_cmd(coord, cmd)
186 if !get(visited, next_coord, false)
187 push!(queue, (path_len + 1, next_coord))
188 end
189 end
190 elseif dest == 2
191 return path_len
192 end
193 end
194 end
195
196 function calc_fill_time(maze_map)
197 # Computes the fill time for the entire maze.
198 # Find oxygen source.
199 source_coord = collect(filter(v -> maze_map[v] == 2, keys(maze_map)))[1]
200 queue = []
201 filled = Dict()
202 push!(queue, (0, source_coord))
203 max_time = 0
204 # BFS to fill the maze.
205 while !isempty(queue)
206 time, coord = popfirst!(queue)
207 max_time = max(max_time, time)
208 filled[coord] = true
209 if get(maze_map, coord, 0) != 0
210 # Walls can't be filled.
211 # Fill the next area.
212 for cmd in 1:4
213 next_coord = move_to_cmd(coord, cmd)
214 if !get(filled, next_coord, false)
215 push!(queue, (time + 1, next_coord))
216 end
217 end
218 end
219 end
220 max_time
221 end
222
223 function part_1(input)
224 maze_map = chart_maze(input)
225 find_min_path(maze_map)
226 end
227
228 function part_2(input)
229 maze_map = chart_maze(input)
230 calc_fill_time(maze_map)
231 end
232
233 input = map(x -> parse(Int128, x), split(readlines(open("input.txt"))[1], ','))
234
235 println("Julia:")
236 println("Part 1: ", part_1(input))
237 println("Part 2: ", part_2(input))