Advent of Code 2021 - Day 9

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

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

The entry code is:

1 Like

I solved part two with a simple union-find algorithm. Since it finished in less than two seconds on my computer, I didn’t need to do any further optimizations.


For part two I did a sort-of breadth-first search (I think?). Feels a bit messy, but got the job done.
Also, felt my file’s a bit cruft-y with how many small functions I made, but was trying to make things reusable between parts.

1 Like

Here’s my solution: y2021/day_09.ex
For part 2 used bfs

1 Like

A fairly straight-forward flood-filling exercise where one can write either DFS (what I did) or BFS, and as long as you have a set of “seen” you’ll be fine. I did use a Map for the grid, with {x,y} tuples as keys, which let me do things like Map.get(map, point, 9) and effectively treat the outside as walls and thus I avoided writing any code to handle the edges of the map.

Anyhow full code here: aoc/day-09.exs at master · ramuuns/aoc · GitHub

def part_2 do
  grid = parse_input()

  |> Enum.group_by(fn {coord, height} -> end_point(coord, height, grid) end)
  |> Map.delete(nil)
  |> Enum.sort_by(fn {_coord, points} -> length(points) end, :desc)
  |> Enum.take(3)
  |> Enum.reduce(1, fn {_coord, points}, acc -> acc * length(points) end)

I used Enum.group_by with a function end_point/3 which finds the coordinate where smoke ends up, given a starting point. If the height of the starting point is 9, then it goes into the nil group, which is trashed afterwards.

Full solution here

Here is mine:

My solution
It revolves heavily around recursion. I know it can be greatly optimized, but :man_shrugging:

The most interesting part to check given a point all the other points that belong to a basin

  defp find_same_basin(matrix, [point | rest], already_visited) do
    points_to_check =
      |> get_sorrownding(point)
      |> Enum.reject(fn {_, v} -> v == 9 end)
      |> Enum.reject(fn {p, _} -> p in already_visited end)
      |> {p, _} -> p end)

    find_same_basin(matrix, Enum.uniq(rest ++ points_to_check), [point | already_visited])

  defp get_sorrownding(matrix, {row, col}) do
    rows_count = tuple_size(matrix)
    columns_count = tuple_size(elem(matrix, 0))

      {row + 1, col},
      {row - 1, col},
      {row, col + 1},
      {row, col - 1}
    |> Enum.filter(fn {row, col} ->
      row >= 0 && row < rows_count && col >= 0 and col < columns_count
    |> point -> {point, get_value(matrix, point)} end)

OK, this day went smoothly. Probably not the most brilliant solution, but I like it. :slight_smile:

It took me way to much time to come with it, but it works. Overkill over overkill:

Day 9

input =!("day9.txt")
  # ~S[110
  #   101
  #   110]
  |> String.split("\n", trim: true)
  |> Nx.tensor(names: [:y, :x])
  |> Nx.subtract(?0)
  |> Nx.add(1)

{width, height} = shape = Nx.shape(input)
{100, 100}

Task 1

padded = Nx.pad(input, 99, [{0, 0, 0}, {1, 1, 0}])

shifted = Nx.slice_axis(padded, 0, height, :x)

x1 = Nx.less(input, shifted)

shifted = Nx.slice_axis(padded, 2, height, :x)

x2 = Nx.less(input, shifted)

x = Nx.logical_and(x1, x2)

padded = Nx.pad(input, 99, [{1, 1, 0}, {0, 0, 0}])

shifted = Nx.slice_axis(padded, 0, width, :y)

y1 = Nx.less(input, shifted)

shifted = Nx.slice_axis(padded, 2, width, :y)

y2 = Nx.less(input, shifted)

y = Nx.logical_and(y1, y2)

minimas = Nx.logical_and(x, y)

|> Nx.multiply(minimas)
|> Nx.sum()
|> Nx.to_number()

Task 2

|> Nx.equal(10)
|> Nx.logical_not()
|>, 9999)
|> Nx.to_flat_list()
|> Enum.reject(&(&1 == 9999))
|> point -> {div(point, width), rem(point, width)} end)
|> Enum.reduce([], fn {y, x} = point, basins ->
  basin_left = Enum.find_index(basins, &({y, x - 1} in &1))
  basin_up = Enum.find_index(basins, &({y - 1, x} in &1))

  case {basin_left, basin_up} do
    {nil, nil} ->
      [[point]) | basins]

    {idx, nil} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {nil, idx} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {idx, idx} ->
      List.update_at(basins, idx, &MapSet.put(&1, point))

    {idx1, idx2} ->
      {old, basins} = List.pop_at(basins, max(idx1, idx2))

      List.update_at(basins, min(idx1, idx2), &(&1 |> MapSet.union(old) |> MapSet.put(point)))
|> Enum.sort(:desc)
|> Enum.take(3)
|> Enum.reduce(&*/2)

This problem is about the right level of difficulty for me. Slightly challenging but I can pull it off without tearing out my hair. Also the kind of problem where formal education in algorithms becomes apparent given everyone else’s solutions above. At least you’ll know I didn’t crib it!

My solution: y2021/d9.ex

Not sure if I like it, but it’s fast. (10ms)

Late to solve this one. Took a break for a week.

Since I already had solved Day 15 with libgraph I figured, why not just reuse that and get to know that library a bit better? (for part 2). Just called strongly connected components on a graph created on data with 9's removed to get basins.

Link: Day 9 - Advent of Code 2021