day_12.livemd

2022 Day 12

Mix.install([:kino])

Input

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

Code

Module

defmodule Puzzle do
  def part_one(input) do
    input
    |> process_input()
    |> make_nodes()
    |> find_path()
  end

  def part_two(input) do
    input
    |> process_input()
    |> make_nodes()
    |> find_path_down()
  end

  defp find_path({nodes, start, goal}) do
    # state = {explored, frontier, unexplored}
    explored = Map.put(%{}, start, %{parent: nil, step: 0})
    state = {explored, [start], nodes -- [start]}

    explore(state, goal, nodes)
  end

  defp find_path_down({nodes, _, goal}) do
    # start with the goal and go backwards
    explored = Map.put(%{}, goal, %{parent: nil, step: 0})
    state = {explored, [goal], nodes -- [goal]}

    explore_down(state, nodes)
  end

  defp explore({explored, [goal | _], _unexplored}, goal, _) do
    IO.puts("YOU MADE IT!")

    # IO.inspect(%{
    #   explored: length(Map.keys(explored)),
    #   unexplored: length(unexplored)
    # })

    explored[goal][:step]
  end

  defp explore({explored, [], []}, _, _) do
    IO.puts("YOU HAVE DIED OF DYSENTERY")
    explored
  end

  defp explore({explored, [current | frontier], unexplored}, goal, nodes) do
    step = explored[current][:step] + 1

    neighbors =
      neighbors(current, nodes)
      |> Enum.reject(fn node -> node in frontier or node in Map.keys(explored) end)

    newly_explored =
      Enum.reduce(neighbors, explored, fn node, acc ->
        Map.put(acc, node, %{
          parent: current,
          step: step
        })
      end)

    new_frontier =
      frontier
      |> Enum.concat(neighbors)

    # TODO A* Algorithm with heuristic sorting
    # |> Enum.sort_by(&elem(&1, 3))

    explore(
      {newly_explored, new_frontier, unexplored -- neighbors},
      goal,
      nodes
    )
  end

  defp explore_down({explored, [{_, _, 97, _} = node | _], _}, _) do
    IO.puts("YOU FOUND THE NEW STARTING POINT!")
    explored[node][:step]
  end

  defp explore_down({explored, [current | frontier], unexplored}, nodes) do
    step = explored[current][:step] + 1

    neighbors =
      neighbors(current, nodes, :down)
      |> Enum.reject(fn node -> node in frontier or node in Map.keys(explored) end)

    newly_explored =
      Enum.reduce(neighbors, explored, fn node, acc ->
        Map.put(acc, node, %{
          parent: current,
          step: step
        })
      end)

    new_frontier =
      frontier
      |> Enum.concat(neighbors)

    explore_down(
      {newly_explored, new_frontier, unexplored -- neighbors},
      nodes
    )
  end

  defp neighbors({x, y, z, _h}, nodes, direction \\ :up) do
    elevation_filter =
      if direction == :up do
        fn nodes, z ->
          Enum.reject(nodes, &(elem(&1, 2) > z + 1))
        end
      else
        fn nodes, z ->
          Enum.reject(nodes, &(elem(&1, 2) < z - 1))
        end
      end

    # up down left right
    [
      {x, y - 1},
      {x, y + 1},
      {x - 1, y},
      {x + 1, y}
    ]
    |> Enum.map(&find_node(&1, nodes))
    |> Enum.reject(&is_nil/1)
    |> elevation_filter.(z)
  end

  defp make_nodes(rows) do
    x_max = length(List.first(rows)) - 1
    y_max = length(rows) - 1

    goal_xy = find_xy(69, rows)
    goal_xyz = Tuple.append(goal_xy, 122)
    start_xy = find_xy(83, rows)

    nodes =
      for x <- 0..x_max, y <- 0..y_max do
        z = get_height({x, y}, rows)
        {x, y, z, heuristic({x, y, z}, goal_xyz)}
      end

    start = find_node(start_xy, nodes)
    goal = find_node(goal_xy, nodes)

    {nodes, start, goal}
  end

  defp find_node({x, y}, nodes) do
    Enum.find(nodes, fn {xf, yf, _, _} -> x == xf and y == yf end)
  end

  defp valid_xy?({x, y}, rows) do
    cond do
      x < 0 or y < 0 ->
        false

      x == length(List.first(rows)) ->
        false

      y == length(rows) ->
        false

      true ->
        true
    end
  end

  defp get_height({x, y}, rows) do
    value =
      valid_xy?({x, y}, rows) and
        Enum.at(rows, y) |> Enum.at(x)

    case value do
      false -> nil
      69 -> 122
      83 -> 97
      _ -> value
    end
  end

  defp find_xy(value, rows) do
    y = Enum.find_index(rows, fn row -> value in row end)
    x = Enum.find_index(Enum.at(rows, y), &(&1 == value))

    {x, y}
  end

  defp heuristic(xyz, goal_xyz) do
    {x1, y1, z1} = xyz
    {x2, y2, z2} = goal_xyz

    # 3D Manhattan distance
    abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)
  end

  defp process_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&String.to_charlist/1)
  end
end

Evaluate

part_1 =
  input
  |> Kino.Input.read()
  |> Puzzle.part_one()

part_2 =
  input
  |> Kino.Input.read()
  |> Puzzle.part_two()

{part_1, part_2}

Test

ExUnit.start(autorun: false)

defmodule PuzzleTest do
  use ExUnit.Case, async: true

  setup do
    input = ~s(
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
)

    {:ok, input: input}
  end

  test "part_one", %{input: input} do
    assert Puzzle.part_one(input) == 31
  end

  test "part_two", %{input: input} do
    assert Puzzle.part_two(input) == 29
  end
end

ExUnit.run()