Advent of Code 2021 - Day 15

Learning Questions & Discussions Coding Challenges
1

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

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

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

2

Here is my solution:

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

1 Like
3

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
4

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
5

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)

      Graph.add_edges(graph, nbs)
    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
6

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 :man_facepalming:

1 Like
7

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
8

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. :smiley:

2 Likes
9

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
10