commit c3fc2b38859fe28f21c7c8c196340262c39ed935
parent 23009c3a9747510c0bd7047182e256f372fe073d
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 15 Dec 2019 12:13:26 -0500
Add Julia solution for day 15
Diffstat:
| A | day-15/day-15.jl | | | 237 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 237 insertions(+), 0 deletions(-)
diff --git a/day-15/day-15.jl b/day-15/day-15.jl
@@ -0,0 +1,237 @@
+function computer_step!(program, pc, relative_base, input)
+ # Runs from given pc until completion or next request for input.
+ # Modifies program and pc.
+ # Returns if the program has terminated and the output.
+ output = []
+ function get_param(loc, mode)
+ # Loc is gauranteed to exist.
+ if mode == 0
+ # Position mode.
+ get(program, program[loc] + 1, 0)
+ elseif mode == 1
+ # Immediate mode.
+ program[loc]
+ else
+ # Relative mode.
+ get(program, relative_base + program[loc] + 1, 0)
+ end
+ end
+ function get_res_loc(loc, mode)
+ # Loc is gauranteed to exist.
+ if mode == 0
+ # Position mode.
+ program[loc] + 1
+ else
+ # Relative mode.
+ relative_base + program[loc] + 1
+ end
+ end
+ while true
+ op_code = program[pc] % 100
+ mode_1 = (program[pc] % 1000) ÷ 100
+ mode_2 = (program[pc] % 10000) ÷ 1000
+ mode_3 = (program[pc] % 100000) ÷ 10000
+ if op_code == 1
+ program[get_res_loc(pc + 3, mode_3)] = (
+ get_param(pc + 1, mode_1)
+ + get_param(pc + 2, mode_2)
+ )
+ pc += 4
+ elseif op_code == 2
+ program[get_res_loc(pc + 3, mode_3)] = (
+ get_param(pc + 1, mode_1)
+ * get_param(pc + 2, mode_2)
+ )
+ pc += 4
+ elseif op_code == 3
+ if !isnothing(input)
+ program[get_res_loc(pc + 1, mode_1)] = input
+ input = nothing
+ else
+ return (pc, relative_base, false, output)
+ end
+ pc += 2
+ elseif op_code == 4
+ push!(output, get_param(pc + 1, mode_1))
+ pc += 2
+ elseif op_code == 5
+ if get_param(pc + 1, mode_1) != 0
+ pc = get_param(pc + 2, mode_2) + 1
+ else
+ pc += 3
+ end
+ elseif op_code == 6
+ if get_param(pc + 1, mode_1) == 0
+ pc = get_param(pc + 2, mode_2) + 1
+ else
+ pc += 3
+ end
+ elseif op_code == 7
+ program[get_res_loc(pc + 3, mode_3)] = (
+ get_param(pc + 1, mode_1)
+ < get_param(pc + 2, mode_2)
+ ) ? 1 : 0
+ pc += 4
+ elseif op_code == 8
+ program[get_res_loc(pc + 3, mode_3)] = (
+ get_param(pc + 1, mode_1)
+ == get_param(pc + 2, mode_2)
+ ) ? 1 : 0
+ pc += 4
+ elseif op_code == 9
+ relative_base += get_param(pc + 1, mode_1)
+ pc += 2
+ elseif op_code == 99
+ break
+ else
+ println("Unknown op code: ", op_code)
+ break
+ end
+ end
+ (pc, relative_base, true, output)
+end
+
+function flip(cmd)
+ if cmd == 1
+ 2
+ elseif cmd == 2
+ 1
+ elseif cmd == 3
+ 4
+ else
+ 3
+ end
+end
+
+function move_to_cmd(coord, cmd)
+ if cmd == 1
+ (coord[1], coord[2] + 1)
+ elseif cmd == 2
+ (coord[1], coord[2] - 1)
+ elseif cmd == 3
+ (coord[1] - 1, coord[2])
+ else
+ (coord[1] + 1, coord[2])
+ end
+end
+
+function chart_maze(program)
+ # Chart the maze via DFS
+ program = Dict(enumerate(copy(program)))
+ # Set program state.
+ pc = 1
+ relative_base = 0
+ # DFS to chart the maze.
+ curr_cmds = []
+ curr_path = [(0, 0)]
+ maze_map = Dict((0, 0) => 1)
+ # Start with initial directions.
+ queue = []
+ for cmd in 1:4
+ push!(queue, (1, cmd, move_to_cmd((0, 0), cmd)))
+ end
+ while !isempty(queue)
+ path_len, cmd, coord = pop!(queue)
+ # Check difference between current path and backtrack.
+ if length(curr_path) > path_len
+ # Backtrack
+ for cmd in map(flip, reverse(curr_cmds[path_len:end]))
+ pc, relative_base, _, _ = computer_step!(
+ program, pc, relative_base, cmd
+ )
+ end
+ # Chean up path.
+ resize!(curr_cmds, path_len - 1)
+ # Keep the origin.
+ resize!(curr_path, path_len)
+ end
+ # Move in specified direction.
+ pc, relative_base, _, step_output = computer_step!(
+ program, pc, relative_base, cmd
+ )
+ # Chart the result.
+ maze_map[coord] = step_output[1]
+ # Determine if we proceed in given direction.
+ if step_output[1] != 0
+ # Free space, record and plan next moves.
+ # Otherwise, keep original path.
+ push!(curr_cmds, cmd)
+ push!(curr_path, coord)
+ for next_cmd in 1:4
+ # Only visit uncharted location.
+ target = move_to_cmd(coord, next_cmd)
+ if !haskey(maze_map, target)
+ push!(queue, (path_len + 1, next_cmd, target))
+ end
+ end
+ end
+ end
+ maze_map
+end
+
+function find_min_path(maze_map)
+ # Return shortest path from (0, 0) to space labeled 2.
+ queue = []
+ visited = Dict()
+ push!(queue, (0, (0, 0)))
+ # BFS to find location.
+ while !isempty(queue)
+ path_len, coord = popfirst!(queue)
+ visited[coord] = true
+ dest = get(maze_map, coord, 0)
+ if dest == 1
+ # Explore next stpes.
+ for cmd in 1:4
+ next_coord = move_to_cmd(coord, cmd)
+ if !get(visited, next_coord, false)
+ push!(queue, (path_len + 1, next_coord))
+ end
+ end
+ elseif dest == 2
+ return path_len
+ end
+ end
+end
+
+function calc_fill_time(maze_map)
+ # Computes the fill time for the entire maze.
+ # Find oxygen source.
+ source_coord = collect(filter(v -> maze_map[v] == 2, keys(maze_map)))[1]
+ queue = []
+ filled = Dict()
+ push!(queue, (0, source_coord))
+ max_time = 0
+ # BFS to fill the maze.
+ while !isempty(queue)
+ time, coord = popfirst!(queue)
+ max_time = max(max_time, time)
+ filled[coord] = true
+ if get(maze_map, coord, 0) != 0
+ # Walls can't be filled.
+ # Fill the next area.
+ for cmd in 1:4
+ next_coord = move_to_cmd(coord, cmd)
+ if !get(filled, next_coord, false)
+ push!(queue, (time + 1, next_coord))
+ end
+ end
+ end
+ end
+ max_time
+end
+
+function part_1(input)
+ maze_map = chart_maze(input)
+ find_min_path(maze_map)
+end
+
+function part_2(input)
+ maze_map = chart_maze(input)
+ calc_fill_time(maze_map)
+end
+
+input = map(x -> parse(Int128, x), split(readlines(open("input.txt"))[1], ','))
+
+println("Julia:")
+println("Part 1: ", part_1(input))
+println("Part 2: ", part_2(input))