# Advent of Code 2021 - Day 15

This topic is about Day 15 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

The entry code is:
`370884-a6a71927`

Here is my solution:

Runtime for both parts and the examples is less than 4 seconds on my computer.

1 Like

ah, good old pathfinding.

I did in anticipation of this implement a naive priority queue a few days ago, so it came in very handy today.

both parts + tests run in under half a second

1 Like

I love that kind of solution.

Generally I would implement the pathfinding, then sum the risks along that path, but you just solve for the simple integer that is the solution.

1 Like

For anyone else using libgraph — if your solution works for the test input but not for the real input, you should check this issue.

My solution (part 2 is quite slow, ~18s on my machine):

``````defmodule AdventOfCode.Day15 do
def part1(input) do
grid = parse_input(input)
graph = make_graph(grid)
min = {0, 0}
max = grid |> Map.keys() |> Enum.max()

graph
|> Graph.dijkstra(min, max)
|> Enum.drop(1)
|> Enum.map(&Map.get(grid, &1))
|> Enum.sum()
end

def part2(input) do
grid = input |> parse_input() |> expand_grid()
graph = make_graph(grid)
min = {0, 0}
max = grid |> Map.keys() |> Enum.max()

graph
|> Graph.dijkstra(min, max)
|> Enum.drop(1)
|> Enum.map(&Map.get(grid, &1))
|> Enum.sum()
end

def make_graph(grid) do
Enum.reduce(grid, Graph.new(), fn {{x, y}, _w}, graph ->
nbs =
[{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]
|> Enum.map(fn point -> {{x, y}, point, [weight: Map.get(grid, point)]} end)
|> Enum.filter(fn {_, _, [weight: w]} -> w end)

end)
end

def expand_grid(grid) do
max = grid |> Map.keys() |> Enum.max()

grid
|> Enum.flat_map(fn point ->
for x1 <- 0..4, y1 <- 0..4, {x1, y1} != {0, 0} do
replicate_point(point, {x1, y1}, max)
end
end)
|> Enum.into(grid)
end

def replicate_point({{x, y}, w}, {x1, y1}, {max_y, max_x}) do
w = w + x1 + y1
w = if w > 9, do: rem(w, 9), else: w
x = x + (max_x + 1) * x1
y = y + (max_y + 1) * y1

{{x, y}, w}
end

def parse_input(input) do
lines = String.split(input, "\n", trim: true)

for {col, y} <- Enum.with_index(lines),
{row, x} <- Enum.with_index(String.codepoints(col)),
into: %{} do
{{x, y}, String.to_integer(row)}
end
end
end
``````
1 Like

Here’s my solution, using Dijkstra and :gb_sets.
I used this document as a reference.

I spent hours wondering why my solution was so slow, before I realized that in the `neighbors_for(node)` function I iterated each time over all nodes to determine the size of the grid 1 Like

If I’m reading your code correctly, I took essentially the same approach but used a plain Map instead of the balanced tree structure you’ve used. I was also tracking the “seen” points in a list rather than a MapSet. My solution could not solve part 1 for the input without melting my CPU, though it works for the smaller example. I’m going to try stealing your use of :gb_sets and MapSet and see if that fixes my issue. Thanks for sharing this.

2 Likes

I’ve just implemented the whole dijkstra part on my own.
Especiallty for part two not fast at all (took about 20min for the result). But I am happy to have finally solved it. 2 Likes

Mine is very similar to others. I’ve never implemented Dijkstra’s before, so that was kind of fun.
My original solution was just based on Wikipedia’s psuedocode, so part two was horribly slow/naive. I was finding the minimum value from a map of `point -> risk`. So shoutout to @bjorng 's solution which introduced me to `:gb_sets`. Refactored my solution leading to a substantial time improvement (O(min) → <4sec on apple m1)

2 Likes