My (attempted) solutions to the 2022 Advent of Code
Log | Files | Refs | README

day_12.jl (2725B)

```      1 #!/usr/bin/env julia
4 using Graphs
5
6 example = readlines(IOBuffer("""
7     Sabqponm
8     abcryxxl
9     accszExk
10     acctuvwj
11     abdefghi"""))
12 input = readlines("data/day_12.txt")
13
14 function parse_input(input::Vector{<:AbstractString})
15     # Transpose this back
16     heightmap = permutedims(hcat(split.(input, "")...))
17
18     # Save the start and end location and set them to heights
19     startpoint = findfirst(==("S"), heightmap)
20     endpoint = findfirst(==("E"), heightmap)
21     heightmap[startpoint] = "a"
22     heightmap[endpoint] = "z"
23
24     # Convert to integers and return the map along with the starting and ending
25     # point coordinates
26     (
27         map(x->x>"Z" ? x[1]-'a' : x[1]-'A', heightmap),
28         startpoint,
29         endpoint
30     )
31 end
32
33 function makegraph(heightmap::AbstractMatrix)
34     height, width = size(heightmap)
35     g = DiGraph(height*width)
36     # I wanted to do this elegantly, but meh, just going to brute-force
37     # indexing.
38     for (i, ind) = enumerate(CartesianIndices(heightmap))
39         if ind[1] < height
40             if heightmap[ind] + 1 >= heightmap[ind[1]+1, ind[2]]
41                 add_edge!(g, i, i+1)
42             end
43             if heightmap[ind[1]+1, ind[2]] + 1 >= heightmap[ind]
44                 add_edge!(g, i+1, i)
45             end
46         end
47         if ind[2] < width
48             if heightmap[ind] + 1 >= heightmap[ind[1], ind[2]+1]
49                 add_edge!(g, i, i+height)
50             end
51             if heightmap[ind[1], ind[2]+1] + 1 >= heightmap[ind]
52                 add_edge!(g, i+height, i)
53             end
54         end
55     end
56     g
57 end
58
59 function pathdist(g::AbstractGraph, v_source::Int, v_dest::Int)
60     dijkstra_shortest_paths(g, [v_source]).dists[v_dest]
61 end
62
63 function pathdist(g::AbstractGraph, v_source::CartesianIndex{2},
64                   v_dest::CartesianIndex{2}, heightmap::AbstractMatrix)
65     height, width = size(heightmap)
66     source_ind = v_source[1] + (v_source[2]-1)*height
67     dest_ind =   v_dest[1]   + (v_dest[2]-1)  *height
68     pathdist(g, source_ind, dest_ind)
69 end
70
71 function pathdist(g::AbstractGraph, v_source::Vector{CartesianIndex{2}},
72                   v_dest::CartesianIndex{2}, heightmap::AbstractMatrix)
73     map(x->pathdist(g, x, v_dest, heightmap), v_source)
74 end
75
76 function part_1(input)
77     heightmap, v_source, v_dest = parse_input(input)
78     pathdist(makegraph(heightmap), v_source, v_dest, heightmap)
79 end
80 @assert part_1(example) == 31
81 @info part_1(input)
82
83 function part_2(input)
84     heightmap, _, v_dest = parse_input(input)
85     v_source = findall(heightmap .== 0)
86     minimum(pathdist(makegraph(heightmap), v_source, v_dest, heightmap))
87 end
88 @assert part_2(example) == 29
89 @info part_2(input)
```