AoC 2022 Day 12

Mix.install([
  {:kino, "~> 0.7.0"},
  {:kino_vega_lite, "~> 0.1.6"}
])

Input

input_field = Kino.Input.textarea("Puzzle input")

input = Kino.Input.read(input_field)

Part 1

defmodule Heightmap do
  defstruct [:map, :start_point, :end_point, :dim]

  def map_char("S"), do: :start_point
  def map_char("E"), do: :end_point
  def map_char(<>), do: char

  def new(map) do
    {start_point, _} = Enum.find(map, &amp;match?({_, :start_point}, &amp;1))
    {end_point, _} = Enum.find(map, &amp;match?({_, :end_point}, &amp;1))

    dim =
      map
      |> Enum.map(&amp;elem(&amp;1, 0))
      |> Enum.max()

    %Heightmap{
      map: map,
      start_point: start_point,
      end_point: end_point,
      dim: dim
    }
  end

  def neighbours(heightmap, {x, y}) do
    [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]
    |> Enum.filter(&amp;Heightmap.in_bounds?(heightmap, &amp;1))
    |> Enum.map(&amp;Heightmap.get_point(heightmap, &amp;1))
  end

  def get_point(%Heightmap{map: map}, point), do: {point, Map.fetch!(map, point)}

  def in_bounds?(%Heightmap{}, {x, y}) when x < 0 or y < 0, do: false
  def in_bounds?(%Heightmap{dim: {dim_x, dim_y}}, {x, y}) when x > dim_x or y > dim_y, do: false
  def in_bounds?(%Heightmap{}, _), do: true

  def can_move(_from, {_, :start_point}), do: true
  def can_move({_, :start_point}, {_, to}), do: to <= ?a + 1
  def can_move({_, from}, {_, :end_point}), do: from >= ?z - 1
  def can_move({_, :end_point}, _), do: false
  def can_move({_, from}, {_, to}), do: from - to >= -1
end

heightmap =
  input
  |> String.split("\n")
  |> Enum.map(fn line ->
    line
    |> String.codepoints()
    |> Enum.map(&Heightmap.map_char/1)
  end)
  |> Enum.with_index()
  |> Enum.reduce(%{}, fn {line, y}, acc ->
    line
    |> Enum.with_index()
    |> Enum.map(fn {item, x} -> {{x, y}, item} end)
    |> Enum.into(%{})
    |> Map.merge(acc)
  end)
  |> Heightmap.new()

graph = :digraph.new()
{dim_x, dim_y} = heightmap.dim

for x <- 0..dim_x do
  for y <- 0..dim_y do
    :digraph.add_vertex(graph, {x, y})
  end
end

for x <- 0..dim_x do
  for y <- 0..dim_y do
    {coord, _val} = point = Heightmap.get_point(heightmap, {x, y})

    heightmap
    |> Heightmap.neighbours(coord)
    |> Enum.filter(&amp;Heightmap.can_move(point, &amp;1))
    |> Enum.each(fn {target_coord, _} -> :digraph.add_edge(graph, coord, target_coord) end)
  end
end

res = :digraph.get_short_path(graph, heightmap.start_point, heightmap.end_point) |> Enum.count()
res - 1

Part 2

has_path = :digraph_utils.reaching_neighbours([heightmap.end_point], graph) |> MapSet.new()

start_point_candidates =
  heightmap.map
  |> Enum.filter(&match?({_, ?a}, &1))
  |> Enum.map(&elem(&1, 0))
  |> MapSet.new()

valid_candidates = MapSet.intersection(start_point_candidates, has_path)

valid_paths =
  Enum.map(valid_candidates, fn cand ->
    :digraph.get_short_path(graph, cand, heightmap.end_point)
  end)

res =
  valid_paths
  |> Enum.map(&Enum.count/1)
  |> Enum.min()

res - 1