# 2022 Day 12
```elixir
Mix.install([:kino])
```
## Input
[](https://livebook.dev/run?url=https%3A%2F%2Fgithub.com%2FballPointPenguin%2Faoc2022%2Fblob%2Fmain%2Fday_12.livemd)
```elixir
input = Kino.Input.textarea("Puzzle Input")
```
## Code
<h3>
Module
</h3>
```elixir
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
```
<h3>
Evaluate
</h3>
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
part_1 =
input
|> Kino.Input.read()
|> Puzzle.part_one()
part_2 =
input
|> Kino.Input.read()
|> Puzzle.part_two()
{part_1, part_2}
```
<h3>
Test
</h3>
<!-- livebook:{"reevaluate_automatically":true} -->
```elixir
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()
```
