Mercurial > lbo > hg > aoc22
view 2022/12/12.jl @ 47:55b04c1490ac
Day 07 Part 1
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Thu, 07 Dec 2023 21:16:16 +0100 |
parents | 05ddc45b4210 |
children |
line wrap: on
line source
import DataStructures: PriorityQueue, enqueue!, dequeue!; const test_input = "12/test_input.txt"; const input = "12/input.txt"; const START = -1; const END = -2; const MAX_DIFF = 1; function read_map(fh::IOStream)::Matrix{Int} lines = readlines(fh); m = zeros(Int, length(lines), length(lines[1])); for (i, line) in enumerate(lines) for (j, char) in enumerate(line) m[i,j] = char - 'a'; if char == 'E' m[i,j] = END; elseif char == 'S' m[i,j] = START; end end end m end function find_start_end(m::Matrix{Int})::Tuple{CartesianIndex, CartesianIndex} findnext((==)(START), m, CartesianIndex((1,1))), findnext((==)(END), m, CartesianIndex((1,1))) end function reconstruct_path(parents::Matrix{CartesianIndex{2}}, start::CartesianIndex, endd::CartesianIndex)::Vector{CartesianIndex} v = Vector{CartesianIndex}(); current = endd; while current != start push!(v, current); current = parents[(current)]; end reverse!(v); v end function find_path(m::Matrix{Int}; start::Union{Nothing, CartesianIndex}=nothing)::Vector{CartesianIndex} s, e = find_start_end(m); if !isnothing(start) s = start; end current_best = zeros(Int, size(m)) .+ 10000; parents = [CartesianIndex((-1,-1)) for i = 1:size(m, 1), j = 1:size(m, 2)]; top = PriorityQueue{Tuple{CartesianIndex,Int}, Int}(); enqueue!(top, (s, 0), 0); valid(x) = x[1] > 0 && x[1] <= size(m, 1) && x[2] > 0 && x[2] <= size(m, 2); while length(top) > 0 (cb, dist) = dequeue!(top); for mov in [(0,1),(0,-1),(1,0),(-1,0)] nb = cb + CartesianIndex(mov); if !valid(nb) continue end if m[nb] == END && m[cb] >= 24 parents[nb] = cb; return reconstruct_path(parents, s, nb) elseif m[nb] == END || (m[nb]-m[cb]) > 1 continue; end if current_best[nb] > dist + 1 current_best[nb] = dist + 1; parents[nb] = cb; enqueue!(top, (nb, dist + 1), dist + 1); end end end [] end function find_any_shortest_path(m::Matrix{Int})::Vector{Int} positions = findall(x -> x == START || x == 0, m); lengths = [length(find_path(m; start=p)) for p in positions]; sort!(lengths); lengths end open(input; read=true) do fh m = read_map(fh); for c in eachrow(m) println(c); end @time p = find_path(m); println("PART 1: Path $p with length $(length(p))"); println("PART 2: All path lengths are $(find_any_shortest_path(m))"); end