Day 9 - Smoke Basin

Puzzle 1

These caves seem to be lava tubes. Parts are even still volcanically active; small hydrothermal vents release smoke into the caves that slowly settles like rain.

If you can model how the smoke flows through the caves, you might be able to avoid it and be that much safer. The submarine generates a heightmap of the floor of the nearby caves for you (your puzzle input).

Smoke flows to the lowest point of the area it’s in. For example, consider the following heightmap:

2199943210
3987894921
9856789892
8767896789
9899965678

Each number corresponds to the height of a particular location, where 9 is the highest and 0 is the lowest a location can be.

Your first goal is to find the low points - the locations that are lower than any of its adjacent locations. Most locations have four adjacent locations (up, down, left, and right); locations on the edge or corner of the map have three or two adjacent locations, respectively. (Diagonal locations do not count as adjacent.)

In the above example, there are four low points, all highlighted: two are in the first row (a 1 and a 0), one is in the third row (a 5), and one is in the bottom row (also a 5). All other locations on the heightmap have some lower adjacent location, and so are not low points.

The risk level of a low point is 1 plus its height. In the above example, the risk levels of the low points are 2, 1, 6, and 6. The sum of the risk levels of all low points in the heightmap is therefore 15.

Find all of the low points on your heightmap. What is the sum of the risk levels of all low points on your heightmap?

sample = """
2199943210
3987894921
9856789892
8767896789
9899965678
"""

input = File.read!("./input-09.txt")

defmodule HeightMap do
  defstruct values: "", height: 0, width: 0

  def parse(input) do
    lines = String.split(input, "\n", trim: true)
    width = lines |> List.first() |> String.length()
    height = Enum.count(lines)
    values = Enum.join(lines, "")
    %__MODULE__{values: values, height: height, width: width}
  end

  def puzzle1(%__MODULE__{} = map) do
    0..(map.height * map.width - 1)
    |> Enum.map(fn position -> {position, height_of(map, position)} end)
    |> Enum.filter(fn {position, height} -> is_low_point(map, position, height) end)
    |> Enum.map(fn {_position, height} -> height + 1 end)
    |> Enum.sum()
  end

  def puzzle2(%__MODULE__{} = map) do
    0..(map.height * map.width - 1)
    |> Enum.map(fn position -> {position, height_of(map, position)} end)
    |> Enum.filter(fn {position, height} -> is_low_point(map, position, height) end)
    |> Enum.map(fn point -> get_basin(map, point) end)
    |> Enum.map(fn basin -> basin.size end)
    |> Enum.sort(:desc)
    |> Enum.take(3)
    |> Enum.reduce(fn number, product -> number * product end)
  end

  def is_low_point(map, position, height) do
    Enum.all?(
      [:top, :bottom, :left, :right],
      fn dir -> is_higher_or_nil(map, neighbor(map, position, dir), height) end
    )
  end

  def is_higher_or_nil(map, position, height) do
    case height_of(map, position) do
      nil -> true
      number -> number > height
    end
  end

  def get_basin(map, low_point) do
    explore_basin(Basin.new(low_point), map, low_point)
  end

  def explore_basin(basin, _map, {position, 9}), do: Basin.record_explored(basin, position)

  def explore_basin(basin, _map, {position, nil}), do: Basin.record_explored(basin, position)

  def explore_basin(basin, map, {position, _height} = point) do
    if Basin.explored?(basin, position) do
      basin
    else
      [:top, :bottom, :left, :right]
      |> Enum.map(fn dir -> neighbor(map, position, dir) end)
      |> Enum.map(fn pos -> {pos, height_of(map, pos)} end)
      |> Enum.filter(fn {pos, height} -> !is_nil(height) && !Basin.explored?(basin, pos) end)
      |> Enum.reduce(
        Basin.record_member_point(basin, point),
        fn point, basin -> explore_basin(basin, map, point) end
      )
    end
  end

  def height_of(_map, nil), do: nil

  def height_of(_map, position) when position < 0, do: nil

  def height_of(%__MODULE__{height: h, width: w}, position) when position >= h * w, do: nil

  def height_of(%__MODULE__{values: values}, position) do
    <<_head::binary-size(position), height, _rest::binary>> = values
    height - 48
  end

  def neighbor(%__MODULE__{width: width}, position, :top), do: position - width

  def neighbor(%__MODULE__{width: width}, position, :bottom), do: position + width

  def neighbor(%__MODULE__{width: width}, position, :left) do
    if rem(position, width) == 0 do
      nil
    else
      position - 1
    end
  end

  def neighbor(%__MODULE__{width: width}, position, :right) do
    if rem(position, width) == width - 1 do
      nil
    else
      position + 1
    end
  end
end

defmodule Basin do
  defstruct low_point: nil, points: [], explored: MapSet.new(), size: 0

  def new({_position, _height} = point), do: %__MODULE__{low_point: point}

  def explored?(basin, position), do: MapSet.member?(basin.explored, position)

  def size(basin), do: basin.size

  def record_member_point(basin, {position, _} = point) do
    basin
    |> record_explored(position)
    |> Map.put(:points, [point | basin.points])
    |> Map.put(:size, basin.size + 1)
  end

  def record_explored(basin, position) do
    %{basin | explored: MapSet.put(basin.explored, position)}
  end
end

sample |> HeightMap.parse() |> HeightMap.puzzle1()

input |> HeightMap.parse() |> HeightMap.puzzle1()

sample |> HeightMap.parse() |> HeightMap.puzzle2()

input |> HeightMap.parse() |> HeightMap.puzzle2()