Day 10: Hoof It
Mix.install([
{:kino, "~> 0.14.2"}
])Input
input = Kino.Input.textarea("Please, paste your input:")defmodule Day10Shared do
def parse(input) do
input
|> Kino.Input.read()
|> String.split("\n")
|> Enum.with_index()
|> Enum.reduce(%{}, fn {line, y}, map ->
line
|> String.codepoints()
|> Enum.with_index()
|> Enum.reduce(map, fn
{".", _}, map ->
map
{char, x}, map ->
Map.put(map, {x, y}, String.to_integer(char))
end)
end)
end
def find(map, level), do: Enum.filter(map, &(elem(&1, 1) == level)) |> Enum.map(&elem(&1, 0))
def build_graph(map) do
Enum.reduce(map, %{}, fn {coord, level}, graph ->
possible_moves =
coord
|> neibs()
|> Enum.filter(fn neib -> Map.get(map, neib, 1337) - level == 1 end)
Map.put(graph, coord, possible_moves)
end)
end
defp neibs({x, y}), do: [{x, y - 1}, {x + 1, y}, {x, y + 1}, {x - 1, y}]
endPart 1
You all arrive at a Lava Production Facility on a floating island in the sky. As the others begin to search the massive industrial complex, you feel a small nose boop your leg and look down to discover a reindeer wearing a hard hat.
The reindeer is holding a book titled “Lava Island Hiking Guide”. However, when you open the book, you discover that most of it seems to have been scorched by lava! As you’re about to ask how you can help, the reindeer brings you a blank topographic map of the surrounding area (your puzzle input) and looks up at you excitedly.
Perhaps you can help fill in the missing hiking trails?
The topographic map indicates the height at each position using a scale from 0 (lowest) to 9 (highest). For example:
0123
1234
8765
9876
Based on un-scorched scraps of the book, you determine that a good hiking trail is as long as possible and has an even, gradual, uphill slope. For all practical purposes, this means that a hiking trail is any path that starts at height 0, ends at height 9, and always increases by a height of exactly 1 at each step. Hiking trails never include diagonal steps - only up, down, left, or right (from the perspective of the map).
You look up from the map and notice that the reindeer has helpfully begun to construct a small pile of pencils, markers, rulers, compasses, stickers, and other equipment you might need to update the map with hiking trails.
A trailhead is any position that starts one or more hiking trails - here, these positions will always have height 0. Assembling more fragments of pages, you establish that a trailhead’s score is the number of 9-height positions reachable from that trailhead via a hiking trail. In the above example, the single trailhead in the top left corner has a score of 1 because it can reach a single 9 (the one in the bottom left).
This trailhead has a score of 2:
...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9
(The positions marked . are impassable tiles to simplify these examples; they do not appear on your actual topographic map.)
This trailhead has a score of 4 because every 9 is reachable via a hiking trail except the one immediately to the left of the trailhead:
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
This topographic map contains two trailheads; the trailhead at the top has a score of 1, while the trailhead at the bottom has a score of 2:
10..9..
2...8..
3...7..
4567654
...8..3
...9..2
.....01Here’s a larger example:
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
This larger example has 9 trailheads. Considering the trailheads in reading order, they have scores of 5, 6, 5, 3, 1, 3, 5, 3, and 5. Adding these scores together, the sum of the scores of all trailheads is 36.
The reindeer gleefully carries over a protractor and adds it to the pile. What is the sum of the scores of all trailheads on your topographic map?
defmodule Day10Part1 do
import Day10Shared
def process(map) do
starts = find(map, 0)
finals = find(map, 9)
graph = build_graph(map)
Enum.reduce(starts, 0, fn start, acc ->
acc + Enum.count(finals, &(bfs(graph, start, &1) == :found))
end)
end
@doc """
Finds the shortest path between two nodes using BFS (Breadth-First Search).
(adapted from one of my Advent of Code 2022 Day 12)
## Parameters
- graph: A map representing the graph's adjacency list
- start: The starting node
- target: The destination node
## Returns
:found or :not_found.
(we can simply change it to return the actual shortest path between start and finish)
## Examples
iex> graph = %{
...> :a => [:b, :c],
...> :b => [:d],
...> :c => [:d],
...> :d => [:e],
...> :e => []
...> }
iex> Day10Part1.bfs(graph, :a, :e)
:found
"""
def bfs(graph, start, target),
do: bfs(graph, [start], target, MapSet.new([start]))
def bfs(_graph, [], _target, _visited),
do: :not_found
def bfs(_graph, [target | _], target, _visited),
do: :found
def bfs(graph, [node | routes], target, visited) do
next = Enum.filter(graph[node], &(!MapSet.member?(visited, &1)))
new_routes = routes ++ next
visited = MapSet.union(visited, MapSet.new(next))
bfs(graph, new_routes, target, visited)
end
end
input |> Day10Shared.parse() |> Day10Part1.process()
# 659 is the right answerPart 2
The reindeer spends a few minutes reviewing your hiking trail map before realizing something, disappearing for a few minutes, and finally returning with yet another slightly-charred piece of paper.
The paper describes a second way to measure a trailhead called its rating. A trailhead’s rating is the number of distinct hiking trails which begin at that trailhead. For example:
.....0.
..4321.
..5..2.
..6543.
..7..4.
..8765.
..9....
The above map has a single trailhead; its rating is 3 because there are exactly three distinct hiking trails which begin at that position:
.....0. .....0. .....0.
..4321. .....1. .....1.
..5.... .....2. .....2.
..6.... ..6543. .....3.
..7.... ..7.... .....4.
..8.... ..8.... ..8765.
..9.... ..9.... ..9....
Here is a map containing a single trailhead with rating 13:
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
This map contains a single trailhead with rating 227 (because there are 121 distinct hiking trails that lead to the 9 on the right edge and 106 that lead to the 9 on the bottom edge):
012345
123456
234567
345678
4.6789
56789.Here’s the larger example from before:
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
Considering its trailheads in reading order, they have ratings of 20, 24, 10, 4, 1, 4, 5, 8, and 5. The sum of all trailhead ratings in this larger example topographic map is 81.
You’re not sure how, but the reindeer seems to have crafted some tiny flags out of toothpicks and bits of paper and is using them to mark trailheads on your topographic map. What is the sum of the ratings of all trailheads?
defmodule Day10Part2 do
import Day10Shared
def process(map) do
starts = find(map, 0)
finals = find(map, 9)
graph = build_graph(map)
Enum.reduce(starts, 0, fn start, total ->
paths_count =
Enum.reduce(finals, 0, fn finish, paths_count ->
all_paths = dfs(graph, start, finish)
paths_count + Enum.count(all_paths)
end)
total + paths_count
end)
end
@doc """
Finds all possible paths between two nodes using DFS (Depth-First Search).
## Parameters
- graph: A map representing the graph's adjacency list
- start: The starting node
- target: The destination node
## Returns
A list of all possible paths from start to target.
## Examples
iex> graph = %{
...> :a => [:b, :c],
...> :b => [:d],
...> :c => [:d],
...> :d => [:e],
...> :e => []
...> }
iex> Day10Part2.dfs(graph, :a, :e)
[
[:a, :b, :d, :e],
[:a, :c, :d, :e]
]
"""
def dfs(graph, start, target) do
graph
|> dfs(start, target, MapSet.new(), [])
|> Enum.map(&Enum.reverse/1)
end
defp dfs(graph, current, target, visited, path) do
# If we've reached the destination, return the current path
if current == target do
[[current | path]]
else
# 0. Prevent revisiting nodes to avoid infinite loops
visited = MapSet.put(visited, current)
# 1. Get neighbors that haven't been visited
# 2. Filter out already visited nodes to prevent cycles
# 3. Recursively explore each unvisited neighbor
graph
|> Map.get(current, [])
|> Enum.filter(fn neighbor -> not MapSet.member?(visited, neighbor) end)
|> Enum.flat_map(fn neighbor ->
dfs(graph, neighbor, target, visited, [current | path])
end)
end
end
end
input |> Day10Shared.parse() |> Day10Part2.process()
# 1463 is the right answer