Day 12

Setup

https://adventofcode.com/2022/day/12

# Taken from https://blog.danielberkompas.com/2016/04/23/multidimensional-arrays-in-elixir/
defmodule Matrix do
  @moduledoc """
  Helpers for working with multidimensional lists, also called matrices.
  """

  @doc """
  Converts a multidimensional list into a zero-indexed map.

  ## Example

      iex> list = [["x", "o", "x"]]
      ...> Matrix.from_list(list)
      %{0 => %{0 => "x", 1 => "o", 2 => "x"}}
  """
  def from_list(list) when is_list(list) do
    do_from_list(list)
  end

  def contains_point(matrix, %{x: x, y: y}) do
    y >= 0 and y < Enum.count(matrix) and x >= 0 and x < Enum.count(matrix[0])
  end

  # def print(matrix) do
  #   0..(Enum.count(matrix) - 1)
  #   |> Enum.map(fn x -> 
  #     IO.puts("x is " <> inspect(x))
  #     matrix[x] 
  #   end)
  #   |> Enum.map(fn map ->
  #     Map.values(map)
  #   end)
  # end

  defp do_from_list(list, map \\ %{}, index \\ 0)
  defp do_from_list([], map, _index), do: map

  defp do_from_list([h | t], map, index) do
    map = Map.put(map, index, do_from_list(h))
    do_from_list(t, map, index + 1)
  end

  defp do_from_list(other, _, _), do: other

  @doc """
  Converts a zero-indexed map into a multidimensional list.

  ## Example

      iex> matrix = %{0 => %{0 => "x", 1 => "o", 2 => "x"}}
      ...> Matrix.to_list(matrix)
      [["x", "o", "x"]]
  """
  def to_list(matrix) when is_map(matrix) do
    do_to_list(matrix)
  end

  defp do_to_list(matrix) when is_map(matrix) do
    for {_index, value} <- matrix,
        into: [],
        do: do_to_list(value)
  end

  defp do_to_list(other), do: other
end

defmodule Point do
  defstruct x: 0, y: 0
end

defmodule Load do
  def input do
    File.read!(Path.join(Path.absname(__DIR__), "input/12.txt"))
  end
end

defmodule Parse do
  def input(input_str) do
    input_str
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split(&1, "", trim: true))
    |> Matrix.from_list()
  end
end

test_input =
  """
  Sabqponm
  abcryxxl
  accszExk
  acctuvwj
  addefghi
  """
  |> Parse.input()

real_input =
  Load.input()
  |> Parse.input()

defmodule Day12 do
  def all_points(matrix) do
    for x <- 0..(Enum.count(matrix[0]) - 1),
        y <- 0..(Enum.count(matrix) - 1),
        do: %Point{x: x, y: y}
  end

  def point_containing(matrix, character) do
    matrix
    |> all_points
    |> Enum.find(fn point -> matrix[point.y][point.x] == character end)
  end

  def start_point(matrix) do
    point_containing(matrix, "S")
  end

  def end_point(matrix) do
    point_containing(matrix, "E")
  end

  def height(matrix, pos) do
    character =
      case matrix[pos.y][pos.x] do
        "S" -> "a"
        "E" -> "z"
        str -> str
      end

    if is_nil(character) do
      nil
    else
      character
      |> String.to_charlist()
      |> hd
    end
  end

  def neighbor_points(%Point{x: x, y: y}) do
    [
      %Point{x: x - 1, y: y},
      %Point{x: x + 1, y: y},
      %Point{x: x, y: y - 1},
      %Point{x: x, y: y + 1}
    ]
  end

  def search_impl(_, _, [], distances, _) do
    distances
  end

  def search_impl(matrix, visited, [current_pos | to_visit], distances, can_move) do
    visitable_neighbors =
      neighbor_points(current_pos)
      |> Enum.filter(&amp;Matrix.contains_point(matrix, &amp;1))
      |> Enum.filter(fn point -> can_move.(matrix, current_pos, point) end)
      |> Enum.reject(fn point -> MapSet.member?(visited, point) end)
      |> Enum.filter(fn point ->
        distances[point] > distances[current_pos] + 1
      end)

    new_distances =
      visitable_neighbors
      |> Enum.reduce(distances, fn point, acc ->
        Map.put(acc, point, distances[current_pos] + 1)
      end)

    new_visited = MapSet.put(visited, current_pos)

    new_to_visit = to_visit ++ visitable_neighbors

    search_impl(
      matrix,
      new_visited,
      new_to_visit,
      new_distances,
      can_move
    )
  end

  def search(matrix, start, can_move) do
    distance_map =
      matrix
      |> all_points
      |> Enum.reduce(%{}, fn point, acc ->
        Map.put(acc, point, 999)
      end)
      |> Map.put(start, 0)

    search_impl(matrix, MapSet.new(), [start], distance_map, can_move)
  end
end

Part 1

defmodule Part1 do
  def can_move(matrix, a, b) do
    a_height = Day12.height(matrix, a)
    b_height = Day12.height(matrix, b)
    b_height <= a_height + 1
  end

  def solve(input) do
    Day12.search(input, Day12.start_point(input), &amp;Part1.can_move/3)[Day12.end_point(input)]
  end
end

Part1.solve(test_input)

Part1.solve(real_input)

Part 2

defmodule Part2 do
  def can_move(matrix, a, b) do
    a_height = Day12.height(matrix, a)
    b_height = Day12.height(matrix, b)
    a_height <= b_height + 1
  end

  def solve(input) do
    distances = Day12.search(input, Day12.end_point(input), &amp;Part2.can_move/3)

    a_points =
      input
      |> Day12.all_points()
      |> Enum.filter(fn point -> Day12.height(input, point) == ?a end)

    distances
    |> Enum.filter(fn {point, _} -> point in a_points end)
    |> Enum.map(fn {_, distance} -> distance end)
    |> Enum.min()
  end
end

Part2.solve(test_input)

Part2.solve(real_input)