commit 9411152faa02ad1b7a725723db3403a1cfc5cba7
parent 7c60dc832da2f4653548bc80334d1a6849f9a93c
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Wed, 14 Dec 2022 19:14:10 -0800
Non-working solution to day 12, part 1.
A Graphs.jl implementation of the solution that should work, but its
broken and producing weird results for the puzzle input (but not the
example). I'm committing this because I might abandon it and write an
algorithm from scratch, but this is my first time working with Graphs.jl
and it seems like useful reference code to have around.
Diffstat:
| A | src/day_12.jl | | | 73 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 73 insertions(+), 0 deletions(-)
diff --git a/src/day_12.jl b/src/day_12.jl
@@ -0,0 +1,73 @@
+#!/usr/bin/env julia
+# https://adventofcode.com/2022/day/12
+using AdventOfCode
+using Graphs
+
+example = readlines(IOBuffer("""
+ Sabqponm
+ abcryxxl
+ accszExk
+ acctuvwj
+ abdefghi"""))
+input = readlines("data/day_12.txt")
+
+function parse_input(input::Vector{<:AbstractString})
+ # Transpose this back
+ heightmap = permutedims(hcat(split.(input, "")...))
+
+ # Save the start and end location and set them to heights
+ startpoint = findfirst(==("S"), heightmap)
+ endpoint = findfirst(==("E"), heightmap)
+ heightmap[startpoint] = "a"
+ heightmap[endpoint] = "z"
+
+ # Convert to integers and return the map along with the starting and ending
+ # point coordinates
+ (
+ map(x->x>"Z" ? x[1]-'a' : x[1]-'A', heightmap),
+ startpoint,
+ endpoint
+ )
+end
+
+function makegraph(heightmap::AbstractMatrix)
+ height, width = size(heightmap)
+ g = Graph(height*width)
+ # I wanted to do this elegantly, but meh, just going to brute-force
+ # indexing.
+ for (i, ind) = enumerate(CartesianIndices(heightmap))
+ if ind[1] < height &&
+ abs(heightmap[ind] - heightmap[ind[1]+1, ind[2]]) <= 1
+ add_edge!(g, i, i+1)
+ end
+ if ind[2] < width &&
+ abs(heightmap[ind] - heightmap[ind[1], ind[2]+1]) <= 1
+ add_edge!(g, i, i+height)
+ end
+ end
+ g
+end
+
+function pathdist(g::AbstractGraph, v_source::Int, v_dest::Int)
+ dijkstra_shortest_paths(g, [v_source]).dists[v_dest]
+end
+
+function pathdist(g::AbstractGraph, v_source::CartesianIndex{2},
+ v_dest::CartesianIndex{2}, heightmap::AbstractMatrix)
+ height, width = size(heightmap)
+ source_ind = v_source[1] + (v_source[2]-1)*height
+ dest_ind = v_dest[1] + (v_dest[2]-1) *height
+ pathdist(g, source_ind, dest_ind)
+end
+
+function part_1(input)
+ heightmap, v_source, v_dest = parse_input(input)
+ pathdist(makegraph(heightmap), v_source, v_dest, heightmap)
+end
+@assert part_1(example) == 31
+@info part_1(input)
+
+function part_2(input)
+ nothing
+end
+@info part_2(input)
