-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday15.jl
41 lines (34 loc) · 1.09 KB
/
day15.jl
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
using DataStructures
m = vcat(map(eachline("data/day15.txt")) do line
transpose(parse.(Int, split(line, "")))
end...)
function dijk(m)
src = CartesianIndex(1, 1)
dst = CartesianIndex(size(m)...) # bottom-right corner
queue = PriorityQueue{CartesianIndex, Int}()
dist = fill(typemax(Int), size(m)...)
queue[src] = dist[src] = 0
while !isempty(queue)
this = dequeue!(queue)
for (dx, dy) ∈ [(-1, 0), (1, 0), (0, -1), (0, 1)]
next = this + CartesianIndex(dx, dy)
if checkbounds(Bool, m, next)
ndist = dist[this] + m[next]
if ndist < dist[next]
queue[next] = dist[next] = ndist
end
end
end
if dist[dst] < typemax(Int)
break
end
end
return dist[dst]
end
# Part 1 - What is the lowest total risk of any path from the top left to the bottom right?
println("part1 = ", dijk(m))
# Part 2 - Using the full map, what is the lowest total risk of any path from the top left to the bottom right?
m2 = hcat([m .+ i for i ∈ 0:4]...)
m2 = vcat([m2 .+ i for i ∈ 0:4]...)
m2[m2 .>= 10] .-= 9
println("part2 = ", dijk(m2))