# 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:
`370884-a6a71927`

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.

4 Likes

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()

grid
|> 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)
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 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 =
matrix
|> get_sorrownding(point)
|> Enum.reject(fn {_, v} -> v == 9 end)
|> Enum.reject(fn {p, _} -> p in already_visited end)
|> Enum.map(fn {p, _} -> p end)

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

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
end)
|> Enum.map(fn point -> {point, get_value(matrix, point)} end)
end
``````

OK, this day went smoothly. Probably not the most brilliant solution, but I like it. It took me way to much time to come with it, but it works. Overkill over overkill:

## Day 9

``````input =
# ~S[110
#   101
#   110]
|> String.split("\n", trim: true)
|> Enum.map(&String.to_charlist(String.trim(&1)))
|> Nx.tensor(names: [:y, :x])
|> Nx.subtract(?0)

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

``````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)

input
|> Nx.multiply(minimas)
|> Nx.sum()
|> Nx.to_number()
``````
``````452
``````

``````input
|> Nx.equal(10)
|> Nx.logical_not()
|> Nx.select(Nx.iota(shape), 9999)
|> Nx.to_flat_list()
|> Enum.reject(&(&1 == 9999))
|> Enum.map(fn 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} ->
[MapSet.new([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)))
end
end)
|> Enum.map(&MapSet.size/1)
|> Enum.sort(:desc)
|> Enum.take(3)
|> Enum.reduce(&*/2)
``````
``````1263735
``````

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.