Day 12: Hill Climbing Algorithm

Mix.install(heap: "2.0.2")

text = File.read!("Code/aoc.ex/input/2022/12.txt")

Hill Climbing Algorithm

example = """
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
"""

data =
  for {l, x} <- text |> String.split("\n", trim: true) |> Enum.with_index(),
      {c, y} <- l |> String.to_charlist() |> Enum.with_index(),
      into: %{},
      do: {{x, y}, c}

start = data |> Enum.to_list() |> Enum.find(&amp;match?({_, ?S}, &amp;1)) |> elem(0)
finish = data |> Enum.to_list() |> Enum.find(&amp;match?({_, ?E}, &amp;1)) |> elem(0)

data = data |> Map.merge(%{start => ?a, finish => ?z})

defmodule Dijkstra do
  @type item :: term
  @type cost :: number

  @spec shortest_path(item, (item -> [{item, cost}]), ({cost, item} -> boolean)) :: {cost, item}
  def shortest_path(start, neighbors_fn, finish_condition) do
    pq = Heap.new() |> Heap.push({0, start})
    visited = MapSet.new()

    Stream.unfold({pq, visited}, fn {queue, visited} ->
      {{current_cost, node}, queue} = Heap.split(queue)

      if MapSet.member?(visited, node) do
        {nil, {queue, visited}}
      else
        queue =
          for {neighbor, cost} <- neighbors_fn.(node),
              !MapSet.member?(visited, neighbor),
              reduce: queue do
            h -> Heap.push(h, {cost + current_cost, neighbor})
          end

        visited = MapSet.put(visited, node)

        {{current_cost, node}, {queue, visited}}
      end
    end)
    |> Stream.drop(1)
    |> Stream.reject(&amp;is_nil/1)
    |> Enum.find(finish_condition)
  end
end

Part One

Dijkstra.shortest_path(
  start,
  fn {x, y} ->
    for pair <- [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}],
        is_map_key(data, pair),
        Map.get(data, pair) <= Map.get(data, {x, y}) + 1,
        do: {pair, 1}
  end,
  &amp;match?({_cost, ^finish}, &amp;1)
)
|> elem(0)

Part Two

Dijkstra.shortest_path(
  finish,
  fn {x, y} ->
    for pair <- [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}],
        is_map_key(data, pair),
        Map.get(data, {x, y}) <= Map.get(data, pair) + 1,
        do: {pair, 1}
  end,
  fn {_cost, node} -> Map.get(data, node) == ?a end
)
|> elem(0)