Advent of Code 2021 - Day 9

bjorng · December 9, 2021, 6:16am

This topic is about Day 9 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

bjorng · December 9, 2021, 6:22am

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.

github.com

bjorng/advent-of-code-2021/blob/49f0d8eff0110e6e5d823bf314236c6bf7dcc991/day09/lib/day09.ex

defmodule Day09 do
  def part1(input) do
    map = parse(input)
    Enum.reduce(map, 0, fn {coord, h}, acc ->
      nh = neighbors(map, coord)
      |> Enum.map(&(Map.fetch!(map, &1)))
      |> Enum.min
      if h < nh do
        acc + 1 + h
      else
        acc
      end
    end)
  end

  # Find the largest basin using a simple union-find algorithm.
  # The run time on my computer is less than 2 seconds.
  def part2(input) do
    map = parse(input)
    |> Enum.reject(fn {_key, value} -> value === 9 end)

This file has been truncated. show original

deadbeef · December 9, 2021, 6:48am

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.

github.com

ed-flanagan/advent-of-code-solutions-elixir/blob/main/lib/advent/y2021/d09.ex

defmodule Advent.Y2021.D09 do
  @moduledoc """
  https://adventofcode.com/2021/day/9
  """

  @typep point :: {non_neg_integer(), non_neg_integer()}
  @typep grid :: %{point() => non_neg_integer()}

  @doc """
  Find all of the low points on your heightmap. What is the sum of the risk
  levels of all low points on your heightmap?
  """
  @spec part_one(Enumerable.t()) :: non_neg_integer()
  def part_one(input) do
    grid = parse_input(input)

    grid
    |> find_low_points()
    |> Enum.map(&risk_level(grid, &1))
    |> Enum.sum()

This file has been truncated. show original

wasi0013 · December 9, 2021, 7:51am

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

ramuuns · December 9, 2021, 8:58am

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

APB9785 · December 9, 2021, 4:14pm

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

fabionebbia · December 9, 2021, 4:33pm

Here is mine:

github.com

fabionebbia/aoc/blob/main/2021/day9/lib/day9.ex

defmodule Day9 do
  @doc """
      iex>Day9.part1(\"""
      ...>2199943210
      ...>3987894921
      ...>9856789892
      ...>8767896789
      ...>9899965678
      ...>\""")
      15
  """
  def part1(input) do
    input
    |> Grid.new()
    |> get_low_points()
    |> Enum.map(&(elem(&1, 1) + 1))
    |> Enum.sum()
  end

  @doc """

This file has been truncated. show original

epilgrim · December 9, 2021, 5:17pm

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

stefanluptak · December 9, 2021, 7:25pm

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

hauleth · December 9, 2021, 8:33pm

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

Day 9

input =
  File.read!("day9.txt")
  # ~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)
  |> 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)

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

Task 2

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)

stevensonmt · December 10, 2021, 4:58am

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!

github.com

stevensonmt/advent_of_code/blob/0ac15008a585b0b384507e1abaf937f95685e1f5/2021/day9/lib/day9.ex

defmodule Day9 do
  @moduledoc false

  @input "input.txt"
         |> File.read!()
         |> String.trim()
         |> String.split()

  @processed Stream.with_index(@input)
             |> Stream.flat_map(fn {l, r} ->
               String.trim(l)
               |> String.graphemes()
               |> Enum.with_index()
               |> Enum.map(fn {n, c} -> {c, String.to_integer(n)} end)
               |> Enum.map(fn {c, n} -> {{r, c}, n} end)
             end)
             |> Enum.into(%{})

  @neighbors [{0, 1}, {0, -1}, {1, 0}, {-1, 0}]

This file has been truncated. show original

princemaple · December 10, 2021, 5:27am

github.com

princemaple/aoc/blob/main/2021/day9.exs

# Title: Day9

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> String.split(["\n", "\r\n"], trim: true)
  |> Enum.map(&(&1 |> String.split("", trim: true) |> Enum.map(fn n -> String.to_integer(n) end)))

data =
  for {line, row} <- Enum.with_index(data), {point, col} <- Enum.with_index(line), into: %{} do
    {{row, col}, point}
  end

defmodule P1 do
  @offsets [{-1, 0}, {1, 0}, {0, -1}, {0, 1}]

  def calc(data) do

This file has been truncated. show original

egze · December 10, 2021, 4:13pm

My solution: y2021/d9.ex

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

code-shoily · December 19, 2021, 6:57am

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