day_12.jl (2725B)
1 #!/usr/bin/env julia 2 # https://adventofcode.com/2022/day/12 3 using AdventOfCode 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)