Advent 2022 - Day 12

Mix.install([
  {:kino, github: "livebook-dev/kino"},
  {:libgraph, "~> 0.7"}
])

Setup

Last year, path finding is what got me stuck, therefore I am taking the easy path this year and reaching for libgraph out the gate :)

input = Kino.Input.textarea("Please paste your input file:")

grid =
  input
  |> Kino.Input.read()
  |> String.split("\n")
  |> Enum.map(&String.graphemes/1)

Utils

defmodule GridToGraph do
  def real_value(x) do
    case x do
      "S" -> "a"
      "E" -> "z"
      x -> x
    end
  end

  def can_navigate(_a, nil), do: false

  def can_navigate(a, b) do
    a = real_value(a) |> String.to_charlist() |> hd()
    b = real_value(b) |> String.to_charlist() |> hd()

    a + 1 >= b
  end

  def parse(grid) do
    x_len = length(Enum.at(grid, 0)) - 1
    y_len = length(grid) - 1
    nil_row = List.duplicate(nil, y_len)

    edges =
      for y <- 0..y_len do
        prev_row = if y - 1 < 0, do: nil_row, else: Enum.at(grid, y - 1, nil_row)
        row = Enum.at(grid, y, nil_row)
        next_row = Enum.at(grid, y + 1, nil_row)

        for x <- 0..x_len do
          cur = Enum.at(row, x)

          top = Enum.at(prev_row, x)
          bottom = Enum.at(next_row, x)
          right = Enum.at(row, x + 1)
          left = if x - 1 < 0, do: nil, else: Enum.at(row, x - 1)

          from = {x, y}

          [
            {can_navigate(cur, top), from, {x, y - 1}},
            {can_navigate(cur, bottom), from, {x, y + 1}},
            {can_navigate(cur, right), from, {x + 1, y}},
            {can_navigate(cur, left), from, {x - 1, y}}
          ]
          |> Enum.filter(fn {can_nav, _a, _b} -> can_nav end)
          |> Enum.map(fn {_can_nav, a, b} -> Graph.Edge.new(a, b, label: cur) end)
        end
        |> List.flatten()
      end
      |> List.flatten()

    Graph.new() |> Graph.add_edges(edges)
  end
end

graph = GridToGraph.parse(grid)

edges = Graph.edges(graph)

s =
  edges
  |> Enum.find(fn edge -> Map.get(edge, :label) == "S" end)
  |> then(&Map.get(&1, :v1))

e =
  edges
  |> Enum.find(fn edge -> Map.get(edge, :label) == "E" end)
  |> then(&Map.get(&1, :v1))

{s, e}

Part 1

Graph.Pathfinding.dijkstra(graph, s, e) |> Enum.count() |> then(&(&1 - 1))

Part 2

s =
  edges
  |> Enum.filter(fn edge ->
    label = Map.get(edge, :label)
    label == "S" || label == "a"
  end)
  |> Enum.map(&Map.get(&1, :v1))
  |> MapSet.new()
  |> MapSet.to_list()
  |> Enum.map(fn point ->
    result = Graph.Pathfinding.dijkstra(graph, point, e)

    if result != nil do
      result |> Enum.count() |> then(&(&1 - 1))
    else
      nil
    end
  end)
  |> Enum.filter(&(&1 != nil))
  |> Enum.min()