Advent of Code - Day 17
Mix.install([
{:kino_aoc, "~> 0.1"},
{:heap, "~> 3.0.0"}
])Introduction
–> Content
Puzzle
{:ok, puzzle_input} =
KinoAOC.download_puzzle("2023", "17", System.fetch_env!("LB_AOC_SESSION"))Parser
Code - Parser
defmodule Parser do
def parse(input) do
String.split(input, "\n", trim: true)
|> Enum.map(fn line ->
String.split(line, "", trim: true) |> Enum.map(fn string -> String.to_integer(string) end)
end)
end
def parse_to_hash(input) do
String.split(input, "\n", trim: true)
|> Enum.with_index()
|> Enum.map(fn {line, idx} ->
String.split(line, "", trim: true)
|> Enum.with_index()
|> Enum.map(fn {cell, inner_idx} -> {{idx, inner_idx}, String.to_integer(cell)} end)
end)
|> List.flatten()
|> Map.new()
end
endTests - Parser
ExUnit.start(autorun: false)
defmodule ParserTest do
use ExUnit.Case, async: true
import Parser
@input """
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""
@expected [
[2, 4, 1, 3, 4, 3, 2, 3, 1, 1, 3, 2, 3],
[3, 2, 1, 5, 4, 5, 3, 5, 3, 5, 6, 2, 3],
[3, 2, 5, 5, 2, 4, 5, 6, 5, 4, 2, 5, 4],
[3, 4, 4, 6, 5, 8, 5, 8, 4, 5, 4, 5, 2],
[4, 5, 4, 6, 6, 5, 7, 8, 6, 7, 5, 3, 6],
[1, 4, 3, 8, 5, 9, 8, 7, 9, 8, 4, 5, 4],
[4, 4, 5, 7, 8, 7, 6, 9, 8, 7, 7, 6, 6],
[3, 6, 3, 7, 8, 7, 7, 9, 7, 9, 6, 5, 3],
[4, 6, 5, 4, 9, 6, 7, 9, 8, 6, 8, 8, 7],
[4, 5, 6, 4, 6, 7, 9, 9, 8, 6, 4, 5, 3],
[1, 2, 2, 4, 6, 8, 6, 8, 6, 5, 5, 6, 3],
[2, 5, 4, 6, 5, 4, 8, 8, 8, 7, 7, 3, 5],
[4, 3, 2, 2, 6, 7, 4, 6, 5, 5, 5, 3, 3]
]
@expected2 %{
0 => %{
0 => 2,
1 => 4,
2 => 1,
3 => 3,
4 => 4,
5 => 3,
6 => 2,
7 => 3,
8 => 1,
9 => 1,
10 => 3,
11 => 2,
12 => 3
},
1 => %{
0 => 3,
1 => 2,
2 => 1,
3 => 5,
4 => 4,
5 => 5,
6 => 3,
7 => 5,
8 => 3,
9 => 5,
10 => 6,
11 => 2,
12 => 3
},
2 => %{
0 => 3,
1 => 2,
2 => 5,
3 => 5,
4 => 2,
5 => 4,
6 => 5,
7 => 6,
8 => 5,
9 => 4,
10 => 2,
11 => 5,
12 => 4
},
3 => %{
0 => 3,
1 => 4,
2 => 4,
3 => 6,
4 => 5,
5 => 8,
6 => 5,
7 => 8,
8 => 4,
9 => 5,
10 => 4,
11 => 5,
12 => 2
},
4 => %{
0 => 4,
1 => 5,
2 => 4,
3 => 6,
4 => 6,
5 => 5,
6 => 7,
7 => 8,
8 => 6,
9 => 7,
10 => 5,
11 => 3,
12 => 6
},
5 => %{
0 => 1,
1 => 4,
2 => 3,
3 => 8,
4 => 5,
5 => 9,
6 => 8,
7 => 7,
8 => 9,
9 => 8,
10 => 4,
11 => 5,
12 => 4
},
6 => %{
0 => 4,
1 => 4,
2 => 5,
3 => 7,
4 => 8,
5 => 7,
6 => 6,
7 => 9,
8 => 8,
9 => 7,
10 => 7,
11 => 6,
12 => 6
},
7 => %{
0 => 3,
1 => 6,
2 => 3,
3 => 7,
4 => 8,
5 => 7,
6 => 7,
7 => 9,
8 => 7,
9 => 9,
10 => 6,
11 => 5,
12 => 3
},
8 => %{
0 => 4,
1 => 6,
2 => 5,
3 => 4,
4 => 9,
5 => 6,
6 => 7,
7 => 9,
8 => 8,
9 => 6,
10 => 8,
11 => 8,
12 => 7
},
9 => %{
0 => 4,
1 => 5,
2 => 6,
3 => 4,
4 => 6,
5 => 7,
6 => 9,
7 => 9,
8 => 8,
9 => 6,
10 => 4,
11 => 5,
12 => 3
},
10 => %{
0 => 1,
1 => 2,
2 => 2,
3 => 4,
4 => 6,
5 => 8,
6 => 6,
7 => 8,
8 => 6,
9 => 5,
10 => 5,
11 => 6,
12 => 3
},
11 => %{
0 => 2,
1 => 5,
2 => 4,
3 => 6,
4 => 5,
5 => 4,
6 => 8,
7 => 8,
8 => 8,
9 => 7,
10 => 7,
11 => 3,
12 => 5
},
12 => %{
0 => 4,
1 => 3,
2 => 2,
3 => 2,
4 => 6,
5 => 7,
6 => 4,
7 => 6,
8 => 5,
9 => 5,
10 => 5,
11 => 3,
12 => 3
}
}
@expected3 %{
{0, 0} => 2,
{0, 1} => 4,
{0, 2} => 1,
{0, 3} => 3,
{0, 4} => 4,
{0, 5} => 3,
{0, 6} => 2,
{0, 7} => 3,
{0, 8} => 1,
{0, 9} => 1,
{0, 10} => 3,
{0, 11} => 2,
{0, 12} => 3,
{1, 0} => 3,
{1, 1} => 2,
{1, 2} => 1,
{1, 3} => 5,
{1, 4} => 4,
{1, 5} => 5,
{1, 6} => 3,
{1, 7} => 5,
{1, 8} => 3,
{1, 9} => 5,
{1, 10} => 6,
{1, 11} => 2,
{1, 12} => 3,
{2, 0} => 3,
{2, 1} => 2,
{2, 2} => 5,
{2, 3} => 5,
{2, 4} => 2,
{2, 5} => 4,
{2, 6} => 5,
{2, 7} => 6,
{2, 8} => 5,
{2, 9} => 4,
{2, 10} => 2,
{2, 11} => 5,
{2, 12} => 4,
{3, 0} => 3,
{3, 1} => 4,
{3, 2} => 4,
{3, 3} => 6,
{3, 4} => 5,
{3, 5} => 8,
{3, 6} => 5,
{3, 7} => 8,
{3, 8} => 4,
{3, 9} => 5,
{3, 10} => 4,
{3, 11} => 5,
{3, 12} => 2,
{4, 0} => 4,
{4, 1} => 5,
{4, 2} => 4,
{4, 3} => 6,
{4, 4} => 6,
{4, 5} => 5,
{4, 6} => 7,
{4, 7} => 8,
{4, 8} => 6,
{4, 9} => 7,
{4, 10} => 5,
{4, 11} => 3,
{4, 12} => 6,
{5, 0} => 1,
{5, 1} => 4,
{5, 2} => 3,
{5, 3} => 8,
{5, 4} => 5,
{5, 5} => 9,
{5, 6} => 8,
{5, 7} => 7,
{5, 8} => 9,
{5, 9} => 8,
{5, 10} => 4,
{5, 11} => 5,
{5, 12} => 4,
{6, 0} => 4,
{6, 1} => 4,
{6, 2} => 5,
{6, 3} => 7,
{6, 4} => 8,
{6, 5} => 7,
{6, 6} => 6,
{6, 7} => 9,
{6, 8} => 8,
{6, 9} => 7,
{6, 10} => 7,
{6, 11} => 6,
{6, 12} => 6,
{7, 0} => 3,
{7, 1} => 6,
{7, 2} => 3,
{7, 3} => 7,
{7, 4} => 8,
{7, 5} => 7,
{7, 6} => 7,
{7, 7} => 9,
{7, 8} => 7,
{7, 9} => 9,
{7, 10} => 6,
{7, 11} => 5,
{7, 12} => 3,
{8, 0} => 4,
{8, 1} => 6,
{8, 2} => 5,
{8, 3} => 4,
{8, 4} => 9,
{8, 5} => 6,
{8, 6} => 7,
{8, 7} => 9,
{8, 8} => 8,
{8, 9} => 6,
{8, 10} => 8,
{8, 11} => 8,
{8, 12} => 7,
{9, 0} => 4,
{9, 1} => 5,
{9, 2} => 6,
{9, 3} => 4,
{9, 4} => 6,
{9, 5} => 7,
{9, 6} => 9,
{9, 7} => 9,
{9, 8} => 8,
{9, 9} => 6,
{9, 10} => 4,
{9, 11} => 5,
{9, 12} => 3,
{10, 0} => 1,
{10, 1} => 2,
{10, 2} => 2,
{10, 3} => 4,
{10, 4} => 6,
{10, 5} => 8,
{10, 6} => 6,
{10, 7} => 8,
{10, 8} => 6,
{10, 9} => 5,
{10, 10} => 5,
{10, 11} => 6,
{10, 12} => 3,
{11, 0} => 2,
{11, 1} => 5,
{11, 2} => 4,
{11, 3} => 6,
{11, 4} => 5,
{11, 5} => 4,
{11, 6} => 8,
{11, 7} => 8,
{11, 8} => 8,
{11, 9} => 7,
{11, 10} => 7,
{11, 11} => 3,
{11, 12} => 5,
{12, 0} => 4,
{12, 1} => 3,
{12, 2} => 2,
{12, 3} => 2,
{12, 4} => 6,
{12, 5} => 7,
{12, 6} => 4,
{12, 7} => 6,
{12, 8} => 5,
{12, 9} => 5,
{12, 10} => 5,
{12, 11} => 3,
{12, 12} => 3
}
describe "parse/1" do
test "simple example" do
assert parse(@input) == @expected
assert parse_to_hash(@input) == @expected3
end
end
end
ExUnit.run()Part One
Code - Part 1
defmodule PartOne do
def solve(input) do
IO.puts("--- Part One ---")
IO.puts("Result: #{run(input)}")
end
def run(tiles_input), do: run(tiles_input, &part_one_node_filter/3)
def run(tiles_string, node_filter) when is_bitstring(tiles_string),
do: run(Parser.parse_to_hash(tiles_string), node_filter)
def run(tiles, node_filter) do
{result, cost} =
[:right, :down]
|> Enum.map(fn direction ->
a_star(
tiles,
coord_at(tiles, 0, 0, direction, 1),
coord_at(tiles, number_of_rows(tiles) - 1, number_of_columns(tiles) - 1),
node_filter
)
end)
|> Enum.map(fn result -> {result, cost_of_path(result)} end)
|> Enum.min_by(fn {_, cost} -> cost end)
print_output(tiles, result)
cost
end
defp cost_of_path(path) do
path
|> Enum.map(fn node ->
case node do
{_, _, cell} -> cell
{_, _, cell, _, _} -> cell
end
end)
|> Enum.sum()
end
defp print_output(tiles, result_path) do
IO.puts("")
processed_output =
Enum.map(tiles, fn {{row, col}, cell} ->
if Enum.find(result_path, fn res_entry ->
case res_entry do
{res_row, res_col, _} -> {row, col} == {res_row, res_col}
{res_row, res_col, _, _, _} -> {row, col} == {res_row, res_col}
end
end) do
{{row, col}, "."}
else
{{row, col}, cell}
end
end)
Enum.map(0..(number_of_rows(tiles) - 1), fn row ->
Enum.map(0..(number_of_columns(tiles) - 1), fn col ->
Enum.find_value(processed_output, fn {{res_row, res_col}, cell} ->
{res_row, res_col} == {row, col} && cell
end)
end)
|> Enum.join()
|> IO.puts()
end)
end
defp reconstruct_path(came_from, current), do: reconstruct_path(came_from, current, [])
defp reconstruct_path(came_from, current, total_path) do
previous = came_from[current]
if previous do
reconstruct_path(came_from, previous, [current | total_path])
else
total_path
end
end
defmodule Score do
def new, do: %{}
def get(score, node), do: Map.get(score, node, :infinity)
def put(score, node, value), do: Map.put(score, node, value)
end
defp a_star(tiles, start, goal, node_filter) do
{goal_x, goal_y, _goal_cell} = goal
h = fn node ->
case node do
{node_x, node_y, _cost, _direction, _steps} -> goal_x - node_x + (goal_y - node_y)
{node_x, node_y, _cost} -> goal_x - node_x + (goal_y - node_y)
end
end
a_star(tiles, start, goal, h, node_filter)
end
# A* finds a path from start to goal.
# h is the heuristic function. h(n) estimates the cost to reach goal from node n.
# This is a modified version that considers nodes with vectors of
# direction of steps in said direction so far.
defp a_star(tiles, start, goal, h, node_filter) do
# For node n, came_from[n] is the node immediately preceding it on the cheapest path from the start
# to n currently known.
came_from = %{}
# For node n, g_score[n] is the cost of the cheapest path from start to n currently known.
g_score = Score.new()
g_score = Score.put(g_score, start, 0)
# The set of discovered nodes that may need to be (re-)expanded.
# Initially, only the start node is known.
# This is usually implemented as a min-heap or priority queue rather than a hash-set.
open_set = Heap.min()
# For node n, f_score[n] := g_score[n] + h(n). f_score[n] represents our current best guess as to
# how cheap a path could be from start to finish if it goes through n.
initial_f_score_value = h.(start)
open_set = Heap.push(open_set, {initial_f_score_value, start})
a_star(tiles, start, goal, h, open_set, came_from, g_score, node_filter)
end
defp a_star(tiles, start, goal, h, open_set, came_from, g_score, node_filter) do
if !Enum.empty?(open_set) do
# This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
current = node_with_lowest_score(open_set)
if coords_equal?(current, goal) do
reconstructed_path = reconstruct_path(came_from, current)
cost_of_path = cost_of_path(reconstructed_path)
IO.inspect(%{cost_of_path: cost_of_path})
reconstructed_path
else
open_set = Heap.pop(open_set)
{came_from, g_score, open_set} =
Enum.reduce(
neighbors_of_current(tiles, current, node_filter, goal),
{came_from, g_score, open_set},
fn neighbor, {came_from, g_score, open_set} ->
# d(current,neighbor) is the weight of the edge from current to neighbor
# tentative_g_score is the distance from start to the neighbor through current
tentative_g_score = Score.get(g_score, current) + d(current, neighbor)
neighbor_existing_g_score = Score.get(g_score, neighbor)
if neighbor_existing_g_score == :infinity ||
tentative_g_score < neighbor_existing_g_score do
# This path to neighbor is better than any previous one. Record it!
came_from = Map.put(came_from, neighbor, current)
g_score = Score.put(g_score, neighbor, tentative_g_score)
f_score_value = tentative_g_score + h.(neighbor)
open_set = Heap.push(open_set, {f_score_value, neighbor})
{came_from, g_score, open_set}
else
{came_from, g_score, open_set}
end
end
)
a_star(tiles, start, goal, h, open_set, came_from, g_score, node_filter)
end
else
# Open set is empty but goal was never reached
{:error, "Open set is empty but goal was never reached"}
end
end
defp coords_equal?({v1, v2, v3, _v4, _v5}, node2), do: coords_equal?({v1, v2, v3}, node2)
defp coords_equal?(node1, {v1, v2, v3, _v4, _v5}), do: coords_equal?(node1, {v1, v2, v3})
defp coords_equal?(node1, node2), do: node1 == node2
defp node_with_lowest_score(set) do
Heap.root(set) |> elem(1)
end
defp neighbors_of_current(tiles, {x, y, cost}, node_filter, goal_node),
do: neighbors_of_current(tiles, {x, y, cost, nil, 1}, node_filter, goal_node)
defp neighbors_of_current(tiles, node, node_filter, goal_node) do
_neighbors_of_current(tiles, node)
|> Enum.filter(fn neighbor_node -> node_filter.(node, neighbor_node, goal_node) end)
end
defp _neighbors_of_current(tiles, {x, y, _, :right, steps}) do
[
right_from(tiles, x, y, steps + 1),
down_from(tiles, x, y, 1),
up_from(tiles, x, y, 1)
]
end
defp _neighbors_of_current(tiles, {x, y, _, :down, steps}) do
[
down_from(tiles, x, y, steps + 1),
right_from(tiles, x, y, 1),
left_from(tiles, x, y, 1)
]
end
defp _neighbors_of_current(tiles, {x, y, _, :left, steps}) do
[
left_from(tiles, x, y, steps + 1),
down_from(tiles, x, y, 1),
up_from(tiles, x, y, 1)
]
end
defp _neighbors_of_current(tiles, {x, y, _, :up, steps}) do
[
up_from(tiles, x, y, steps + 1),
right_from(tiles, x, y, 1),
left_from(tiles, x, y, 1)
]
end
defp _neighbors_of_current(tiles, {x, y, _, nil, steps}) do
[
down_from(tiles, x, y, steps + 1),
up_from(tiles, x, y, steps + 1),
right_from(tiles, x, y, steps + 1),
left_from(tiles, x, y, steps + 1)
]
end
defp part_one_node_filter(
{_, _, _, _prev_direction, _prev_steps},
{_, _, neighbor_cell, _neighbor_direction, neighbor_steps},
_goal_node
) do
neighbor_cell != nil && neighbor_steps <= 3
end
def up_from(tiles, x, y, steps) do
coord_at(tiles, x - 1, y, :up, steps)
end
def down_from(tiles, x, y, steps) do
coord_at(tiles, x + 1, y, :down, steps)
end
def left_from(tiles, x, y, steps) do
coord_at(tiles, x, y - 1, :left, steps)
end
def right_from(tiles, x, y, steps) do
coord_at(tiles, x, y + 1, :right, steps)
end
defp d(_current, {_, _, neighbor_cost, _, _}), do: neighbor_cost
defp d(_current, {_, _, neighbor_cost}), do: neighbor_cost
def coord_at(tiles, row, column, direction, steps) do
{row, column, Map.get(tiles, {row, column}), direction, steps}
end
def coord_at(tiles, row, column, direction) do
{row, column, Map.get(tiles, {row, column}), direction}
end
def coord_at(tiles, row, column) do
# {row, column, cell_at(tiles, row, column)}
{row, column, Map.get(tiles, {row, column})}
end
def cell_at(tiles, row, column) do
Map.get(tiles, {row, column})
end
defp number_of_rows(tiles) do
{{row, _column}, _cell} = Enum.max_by(tiles, fn {{row, _column}, _cell} -> row end)
row + 1
end
defp number_of_columns(tiles) do
# Enum.count(Map.get(tiles, 0))
{{_row, column}, _cell} = Enum.max_by(tiles, fn {{_row, column}, _cell} -> column end)
column + 1
end
endTests - Part 1
ExUnit.start(autorun: false)
defmodule PartOneTest do
use ExUnit.Case, async: true
import PartOne
@raw_input """
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""
@input Parser.parse_to_hash(@raw_input)
describe "run/1" do
test "main example" do
assert run(@raw_input) == 102
end
end
describe "cell_at/3" do
test "basic examples" do
assert cell_at(@input, 0, 0) == 2
assert cell_at(@input, 0, 1) == 4
assert cell_at(@input, 1, 0) == 3
end
end
describe "coord_at/3" do
test "basic examples" do
assert coord_at(@input, 0, 0) == {0, 0, 2}
assert coord_at(@input, 0, 1) == {0, 1, 4}
assert coord_at(@input, 1, 0) == {1, 0, 3}
assert coord_at(@input, 0, 0, :east) == {0, 0, 2, :east}
assert coord_at(@input, 0, 1, :east) == {0, 1, 4, :east}
assert coord_at(@input, 1, 0, :east) == {1, 0, 3, :east}
end
end
end
ExUnit.run()Solution - Part 1
PartOne.solve(puzzle_input)Part Two
Code - Part 2
defmodule PartTwo do
def solve(input) do
IO.puts("--- Part Two ---")
IO.puts("Result: #{run(input)}")
end
def run(tiles) do
PartOne.run(tiles, &part_two_node_filter/3)
end
defp part_two_node_filter(
{_, _, _, prev_direction, prev_steps},
{neighbor_x, neighbor_y, neighbor_cell, neighbor_direction, neighbor_steps},
{goal_x, goal_y, _}
) do
neighbor_cell != nil &&
((prev_direction != neighbor_direction && prev_steps >= 4) ||
(prev_direction == neighbor_direction && neighbor_steps <= 10)) &&
({neighbor_x, neighbor_y} != {goal_x, goal_y} || prev_steps + 1 >= 4)
end
endTests - Part 2
ExUnit.start(autorun: false)
defmodule PartTwoTest do
use ExUnit.Case, async: true
import PartTwo
@raw_input """
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533
"""
@input Parser.parse(@raw_input)
describe "run/1" do
test "main example" do
assert run(@raw_input) == 94
end
test "another main example" do
raw_input = """
111111111111
999999999991
999999999991
999999999991
999999999991
"""
assert run(raw_input) == 71
end
end
end
ExUnit.run()Solution - Part 2
PartTwo.solve(puzzle_input)