Day 12: Hill Climbing Algorithm

Mix.install([:kino])

Section

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

grid =
  input
  |> Kino.Input.read()
  |> String.split("\n")
  |> Enum.map(fn line ->
    line
    |> String.to_charlist()
    |> Enum.map(fn
      ?S -> 0
      ?E -> 27
      c -> c - ?a + 1
    end)
  end)
  |> Enum.with_index(0)
  |> Enum.map(fn {row, i} ->
    row
    |> Enum.with_index(0)
    |> Enum.map(fn {col, j} ->
      {{i, j}, col}
    end)
  end)
  |> List.flatten()
  |> Map.new()

start =
  grid
  |> Enum.find_value(fn
    {p, 0} -> p
    _ -> false
  end)

top =
  grid
  |> Enum.find_value(fn
    {p, 27} -> p
    _ -> false
  end)

defmodule BFS do
  def search(grid, path, seen, from \\ -1) do
    {x, y} = current = hd(path)
    h = grid[current]

    seen = Map.put(seen, current, path)

    grid
    |> Map.take([{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}])
    |> Enum.reject(fn {pos, height} ->
      # too high, or known shorter path
      height > h + 1 or (seen[pos] && length(seen[pos]) <= length(path) + 1)
    end)
    |> case do
      [] ->
        # no new nodes the explore, return known shortest paths 
        seen

      list ->
        Enum.reduce(list, seen, fn
          {pos, ^from}, seen ->
            search(grid, [pos], seen, from)

          {pos, _}, seen ->
            search(grid, [pos | path], seen, from)
        end)
    end
  end
end

Part 1

BFS.search(grid, [start], %{})[top] |> Enum.count() |> Kernel.-(1)

Part 2

BFS.search(grid, [start], %{}, 1)[top] |> Enum.count() |> Kernel.-(1)