Advent of Code 2022 - Day 12

Day 12: Hill Climbing Algorithm

Description

Utils

defmodule Load do
  def file(path) do
    File.read!(__DIR__ <> path) |> parse()
  end

  def string(value) do
    value |> parse()
  end

  defp parse(value) do
    value |> String.split("\n", trim: true) |> Enum.map(&amp;String.to_charlist/1)
  end
end

Input

input = Load.file("/data/day12.txt")

Part 1

What is the fewest steps required to move from your current position to the location that should get the best signal?

defmodule Part1 do
  @infinity 9_999_999_999_999_999

  def get_point(nodes, value) do
    0..(length(nodes) - 1)
    |> Enum.find_value(fn y ->
      row = nodes |> Enum.at(y)

      x =
        row
        |> Enum.find_index(fn cell ->
          cell == value
        end)

      if x, do: {x, y}, else: nil
    end)
  end

  def create_nodes(grid) do
    height = grid |> Enum.count()
    width = grid |> Enum.at(0) |> Enum.count()

    0..(height - 1)
    |> Enum.reduce(%{}, fn y, nodes ->
      row = grid |> Enum.at(y)

      0..(width - 1)
      |> Enum.reduce(nodes, fn x, nodes ->
        letter = row |> Enum.at(x)
        height = get_height(letter)

        nodes
        |> Map.merge(%{
          {x, y} => %{height: height, distance: @infinity, visited: false, from: nil}
        })
      end)
    end)
  end

  def get_height(letter) do
    case letter do
      83 -> 97
      69 -> 122
      height -> height
    end
  end

  def create_unvisited(grid) do
    height = grid |> Enum.count()
    width = grid |> Enum.at(0) |> Enum.count()

    0..(height - 1)
    |> Enum.flat_map(fn y ->
      0..(width - 1) |> Enum.map(fn x -> {x, y} end)
    end)
  end

  def set_start_point(nodes, start_point) do
    node = nodes |> Map.get(start_point)
    nodes |> Map.merge(%{start_point => %{node | distance: 0}})
  end

  def djikstra(nodes, point, end_point, queue) do
    neighbor_points = nodes |> get_neighbor_points(point)

    queue = (neighbor_points ++ queue) |> Enum.uniq()

    nodes =
      nodes
      |> update_neighbors(neighbor_points, point)
      |> update_node(point, fn node ->
        %{node | visited: true}
      end)

    cond do
      point == end_point ->
        create_path(nodes, [point])

      length(queue) == 0 ->
        []

      true ->
        [next_point | queue] = nodes |> sort_by_distance(queue)
        djikstra(nodes, next_point, end_point, queue)
    end
  end

  defp create_path(nodes, [last_point | _] = path) do
    node = nodes |> Map.get(last_point)

    if node.distance == 0 do
      path
    else
      nodes |> create_path([node.from | path])
    end
  end

  defp get_neighbor_points(nodes, point) do
    {x, y} = point
    current_node = nodes |> Map.get(point)

    neighbor_points = [
      {x, y - 1},
      {x, y + 1},
      {x - 1, y},
      {x + 1, y}
    ]

    neighbor_points
    |> Enum.filter(fn point ->
      nodes |> Map.has_key?(point)
    end)
    |> Enum.reject(fn point ->
      neighbor = nodes |> Map.get(point)
      neighbor.visited
    end)
    |> Enum.filter(fn point ->
      neighbor = nodes |> Map.get(point)
      neighbor.height - current_node.height <= 1
    end)
  end

  defp update_neighbors(nodes, neighbor_points, current_point) do
    neighbor_points
    |> Enum.reduce(nodes, fn point, nodes ->
      nodes |> update_neighbor(point, current_point)
    end)
  end

  defp update_neighbor(nodes, point, current_point) do
    current_node = nodes |> Map.get(current_point)

    nodes
    |> update_node(point, fn node ->
      if current_node.distance + 1 < node.distance do
        %{node | distance: current_node.distance + 1, from: current_point}
      else
        node
      end
    end)
  end

  defp update_node(nodes, point, updater) when is_function(updater) do
    nodes |> Map.update!(point, updater)
  end

  defp sort_by_distance(nodes, queue) do
    queue
    |> Enum.sort(fn point_a, point_b ->
      node_a = nodes |> Map.get(point_a)
      node_b = nodes |> Map.get(point_b)
      node_a.distance < node_b.distance
    end)
  end
end

# S
start_point = input |> Part1.get_point(83)
# E
end_point = input |> Part1.get_point(69)

input
|> Part1.create_nodes()
|> Part1.set_start_point(start_point)
|> Part1.djikstra(start_point, end_point, [])
|> Enum.count()
|> Kernel.-(1)

Result

490

Part 2

What is the fewest steps required to move starting from any square with elevation a to the location that should get the best signal?

defmodule Part2 do
  def get_all_a_points(grid) do
    height = grid |> Enum.count()
    width = grid |> Enum.at(0) |> Enum.count()

    0..(height - 1)
    |> Enum.reduce([], fn y, a_points ->
      0..(width - 1)
      |> Enum.reduce(a_points, fn x, a_points ->
        letter = grid |> Enum.at(y) |> Enum.at(x)

        height = Part1.get_height(letter)

        if height == ?a do
          [{x, y} | a_points]
        else
          a_points
        end
      end)
    end)
  end
end

a_points = input |> Part2.get_all_a_points()

end_point = input |> Part1.get_point(69)

a_points
|> Enum.map(fn start_point ->
  input
  |> Part1.create_nodes()
  |> Part1.set_start_point(start_point)
  |> Part1.djikstra(start_point, end_point, [])
  |> Enum.count()
  |> Kernel.-(1)
end)
|> Enum.reject(&(&1 == -1))
|> Enum.min()

Result

488