Day 9: Smoke Basin

2021/09.livemd

Roy Veshovda

@royveshovda

aoc

Share to X

Share to Bluesky

More notebooks

Day 9: Smoke Basin

Intro

https://adventofcode.com/2021/day/9

Input

input_test =
  """
  2199943210
  3987894921
  9856789892
  8767896789
  9899965678
  """
  |> String.split(["\n"], trim: true)
  |> Enum.map(fn x -> String.graphemes(x) |> Enum.map(fn y -> String.to_integer(y) end) end)

[
  [2, 1, 9, 9, 9, 4, 3, 2, 1, 0],
  [3, 9, 8, 7, 8, 9, 4, 9, 2, 1],
  [9, 8, 5, 6, 7, 8, 9, 8, 9, 2],
  [8, 7, 6, 7, 8, 9, 6, 7, 8, 9],
  [9, 8, 9, 9, 9, 6, 5, 6, 7, 8]
]

input =
  File.read!("input09.txt")
  |> String.split(["\n"], trim: true)
  |> Enum.map(fn x -> String.graphemes(x) |> Enum.map(fn y -> String.to_integer(y) end) end)

[
  [7, 6, 5, 4, 5, 9, 8, 9, 5, 4, 3, 2, 1, 0, 9, 5, 4, 1, 0, 1, 2, 5, 7, 9, 8, 7, 5, 4, 5, 7, 8, 9,
   9, 9, 8, 9, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4, 9, ...],
  [6, 5, 4, 3, 4, 8, 7, 8, 9, 5, 9, 9, 2, 9, 8, 7, 3, 2, 4, 2, 3, 4, 5, 9, 9, 5, 4, 3, 4, 6, 7, 9,
   9, 8, 7, 8, 9, 9, 3, 4, 5, 6, 7, 8, 9, 3, 2, 9, ...],
  [7, 6, 3, 2, 3, 5, 6, 7, 8, 9, 8, 8, 9, 8, 7, 6, 5, 3, 5, 3, 4, 5, 9, 8, 7, 6, 5, 4, 7, 8, 8, 9,
   8, 7, 6, 7, 8, 8, 9, 7, 6, 7, 8, 9, 5, 4, 9, ...],
  [7, 5, 4, 3, 4, 8, 7, 8, 9, 6, 6, 7, 3, 9, 8, 7, 6, 7, 6, 7, 6, 7, 8, 9, 8, 9, 9, 5, 6, 8, 9, 8,
   7, 6, 5, 5, 6, 7, 8, 9, 7, 8, 9, 7, 6, 9, ...],
  [9, 8, 5, 4, 5, 6, 7, 9, 6, 5, 4, 3, 2, 3, 9, 8, 9, 8, 9, 8, 9, 8, 9, 5, 9, 9, 8, 7, 7, 8, 9, 9,
   8, 7, 3, 4, 7, 8, 9, 9, 8, 9, 9, 8, 7, ...],
  [8, 7, 6, 7, 7, 7, 8, 9, 5, 4, 3, 2, 1, 2, 3, 9, 7, 9, 9, 9, 7, 9, 5, 4, 5, 2, 9, 9, 8, 9, 7, 8,
   9, 8, 2, 5, 8, 9, 7, 6, 9, 8, 9, 9, ...],
  [9, 8, 7, 8, 9, 8, 9, 7, 6, 5, 9, 3, 2, 3, 4, 5, 6, 8, 9, 9, 6, 5, 4, 3, 2, 1, 3, 4, 9, 5, 6, 7,
   8, 9, 3, 4, 9, 9, 6, 5, 6, 7, 8, ...],
  [9, 9, 8, 9, 9, 9, 9, 9, 7, 9, 8, 9, 6, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 1, 0, 1, 2, 3, 4, 7, 8,
   9, 8, 7, 6, 7, 8, 9, 4, 5, 6, ...],
  [9, 9, 9, 9, 9, 8, 7, 8, 9, 8, 7, 8, 9, 7, 6, 7, 8, 9, 9, 9, 8, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 7,
   8, 9, 8, 9, 8, 9, 9, 3, 6, ...],
  [8, 9, 9, 9, 8, 7, 6, 7, 6, 5, 6, 7, 8, 9, 9, 8, 9, 8, 9, 9, 9, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8,
   9, 9, 9, 6, 9, 7, 8, 9, ...],
  [7, 8, 9, 8, 7, 6, 5, 4, 5, 4, 5, 7, 8, 9, 4, 9, 6, 7, 8, 9, 8, 7, 8, 5, 4, 3, 4, 5, 6, 8, 8, 9,
   8, 9, 9, 5, 4, 6, 5, ...],
  [6, 9, 8, 7, 6, 5, 4, 3, 2, 3, 4, 6, 9, 4, 3, 4, 5, 8, 9, 7, 9, 8, 9, 7, 5, 4, 5, 8, 7, 9, 9, 5,
   6, 9, 8, 9, 3, 2, ...],
  [5, 6, 9, 8, 7, 6, 5, 5, 4, 5, 6, 7, 8, 9, 9, 5, 6, 9, 5, 6, 9, 9, 8, 7, 6, 5, 6, 9, 8, 9, 3, 4,
   5, 6, 7, 8, 9, ...],
  [4, 5, 6, 9, 8, 7, 7, 6, 5, 8, 7, 9, 9, 9, 8, 9, 9, 5, 4, 9, 8, 7, 9, 8, 7, 6, 7, 8, 9, 7, 4, 5,
   6, 7, 8, 9, ...],
  [3, 5, 6, 7, 9, 9, 8, 9, 6, 9, 9, 8, 9, 8, 7, 7, 8, 9, 6, 9, 9, 6, 5, 9, 8, 7, 8, 9, 7, 6, 5, 6,
   7, 8, 9, ...],
  [2, 3, 5, 7, 6, 7, 9, 8, 7, 9, 8, 7, 8, 7, 6, 6, 7, 8, 9, 8, 9, 5, 4, 5, 9, 8, 9, 9, 8, 9, 9, 8,
   8, 9, ...],
  [1, 2, 3, 4, 5, 8, 9, 9, 9, 8, 7, 6, 9, 6, 5, 5, 4, 5, 6, 7, 9, 9, 3, 4, 9, 9, 7, 8, 9, 1, 2, 9,
   9, ...],
  [0, 3, 9, 5, 6, 7, 9, 3, 1, 9, 9, 4, 3, 2, 4, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 7, 8, 9, 9, 8,
   ...],
  [1, 9, 8, 9, 9, 8, 9, 4, 2, 9, 8, 3, 2, 1, 0, 1, 2, 3, 6, 7, 8, 9, 9, 8, 7, 6, 5, 6, 9, 9, 8, ...],
  [9, 8, 7, 8, 9, 9, 8, 9, 9, 8, 7, 6, 3, 2, 1, 2, 3, 6, 7, 8, 9, 5, 4, 9, 8, 5, 4, 7, 8, 9, ...],
  [8, 8, 6, 7, 8, 9, 7, 9, 8, 7, 6, 5, 4, 7, 2, 3, 4, 5, 6, 7, 8, 9, 5, 9, 7, 6, 3, 4, 9, ...],
  [7, 6, 5, 8, 9, 5, 6, 7, 9, 8, 7, 6, 5, 6, 7, 4, 5, 6, 7, 9, 9, 9, 9, 9, 9, 7, 4, 5, ...],
  [6, 5, 4, 5, 6, 9, 7, 8, 9, 9, 9, 8, 6, 8, 9, 7, 6, 7, 8, 9, 8, 9, 8, 9, 9, 8, 6, ...],
  [7, 6, 5, 6, 7, 8, 9, 9, 9, 8, 9, 9, 7, 9, 9, 8, 9, 8, 9, 9, 7, 6, 7, 8, 9, 8, ...],
  [8, 7, 8, 9, 8, 9, 1, 2, 9, 7, 6, 9, 8, 9, 7, 9, 3, 9, 8, 7, 6, 5, 3, 9, 8, ...],
  [9, 8, 9, 8, 9, 8, 9, 9, 7, 5, 4, 5, 9, 7, 6, 3, 2, 0, 9, 8, 7, 9, 9, 8, ...],
  [4, 9, 8, 7, 6, 7, 8, 9, 8, 4, 3, 4, 8, 9, 5, 4, 3, 4, 5, 9, 9, 8, 9, ...],
  [3, 9, 8, 6, 5, 6, 7, 8, 9, 5, 4, 6, 7, 8, 9, 5, 9, 5, 6, 9, 8, 7, ...],
  [9, 8, 9, 5, 4, 5, 6, 7, 8, 9, 5, 7, 8, 9, 9, 9, 8, 9, 9, 8, 7, ...],
  [6, 7, 5, 4, 3, 4, 5, 6, 7, 8, 9, 8, 9, 9, 9, 8, 7, 9, 8, 7, ...],
  [5, 4, 2, 1, 2, 3, 4, 7, 8, 9, 9, 9, 9, 9, 8, 7, 6, 7, 9, ...],
  [4, 3, 1, 0, 1, 2, 3, 6, 7, 8, 9, 9, 9, 9, 7, 6, 5, 9, ...],
  [5, 5, 2, 3, 2, 3, 4, 5, 9, 9, 9, 9, 8, 7, 6, 5, 4, ...],
  [7, 6, 5, 4, 3, 4, 5, 6, 7, 8, 9, 8, 9, 8, 7, 6, ...],
  [8, 7, 9, 5, 9, 5, 9, 7, 8, 9, 8, 7, 8, 9, 8, ...],
  [9, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 6, 9, 8, ...],
  [9, 8, 7, 6, 7, 8, 7, 8, 9, 8, 9, 5, 4, ...],
  [9, 9, 8, 5, 6, 7, 6, 5, 6, 7, 9, 6, ...],
  [9, 6, 5, 4, 3, 2, 4, 4, 5, 6, 9, ...],
  [8, 7, 4, 3, 2, 1, 2, 3, 4, 5, ...],
  [9, 8, 5, 4, 5, 9, 9, 4, 5, ...],
  [7, 9, 6, 5, 6, 7, 8, 5, ...],
  [6, 7, 9, 8, 7, 8, 9, ...],
  [5, 6, 7, 9, 8, 9, ...],
  [4, 2, 9, 8, 9, ...],
  [5, 9, 8, 7, ...],
  [6, 7, 9, ...],
  [7, 9, ...],
  [9, ...],
  [...],
  ...
]

Part 1

defmodule Floor do
  def at(m, {x, y}) do
    row = Enum.at(m, y)
    Enum.at(row, x)
  end

  def get_adjacent(floor, {x, y}) do
    x_max = length(hd(floor)) - 1
    y_max = length(floor) - 1

    [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]
    |> Enum.filter(fn {x, y} -> x >= 0 and x <= x_max and y >= 0 and y <= y_max end)
  end
end

{:module, Floor, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:get_adjacent, 2}}

i = input_test
x_max = length(hd(i)) - 1
y_max = length(i) - 1

adj =
  for y <- 0..y_max do
    for x <- 0..x_max do
      {{x, y}, [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]}
    end
  end
  |> List.flatten()
  |> Enum.map(fn {loc, a} ->
    {loc, Enum.filter(a, fn {x, y} -> x >= 0 and x <= x_max and y >= 0 and y <= y_max end)}
  end)
  |> Enum.map(fn {loc, a} ->
    {Floor.at(i, loc), Enum.map(a, fn loc2 -> Floor.at(i, loc2) end) |> Enum.min()}
  end)
  |> Enum.filter(fn {loc, m} -> loc < m end)
  |> Enum.map(fn {loc, _m} -> loc + 1 end)
  |> Enum.sum()

i = input
x_max = length(hd(i)) - 1
y_max = length(i) - 1

for y <- 0..y_max do
  for x <- 0..x_max do
    {{x, y}, [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]}
  end
end
|> List.flatten()
|> Enum.map(fn {loc, a} ->
  {loc, Enum.filter(a, fn {x, y} -> x >= 0 and x <= x_max and y >= 0 and y <= y_max end)}
end)
|> Enum.map(fn {loc, a} ->
  {Floor.at(i, loc), Enum.map(a, fn loc2 -> Floor.at(i, loc2) end) |> Enum.min()}
end)
|> Enum.filter(fn {loc, m} -> loc < m end)
|> Enum.map(fn {loc, _m} -> loc + 1 end)
|> Enum.sum()

Correct: 512

Part 2

i = input_test
x_max = length(hd(i)) - 1
y_max = length(i) - 1

low_points =
  for y <- 0..y_max do
    for x <- 0..x_max do
      {{x, y}, [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]}
    end
  end
  |> List.flatten()
  |> Enum.map(fn {loc, a} ->
    {loc, Enum.filter(a, fn {x, y} -> x >= 0 and x <= x_max and y >= 0 and y <= y_max end)}
  end)
  |> Enum.map(fn {loc, a} ->
    {loc, Floor.at(i, loc), Enum.map(a, fn loc2 -> Floor.at(i, loc2) end) |> Enum.min()}
  end)
  |> Enum.filter(fn {_loc, loc_v, m} -> loc_v < m end)
  |> Enum.map(fn {loc, _loc_v, _m} -> loc end)

defmodule Basin do
  def find_basin_size(_floor, [], _opened, basin) do
    basin
  end

  def find_basin_size(floor, head, opened, basin) do
    {c, head} = List.pop_at(head, 0)
    val_c = Floor.at(floor, c)
    close = Floor.get_adjacent(floor, c)
    close_and_not_opened = Enum.filter(close, fn pos -> pos not in opened end)
    rising = Enum.filter(close_and_not_opened, fn pos -> Floor.at(floor, pos) != 9 end)

    basin = basin ++ [{c, val_c}]
    opened = opened ++ [c]

    rising_and_not_in_head =
      Enum.filter(rising, fn pos -> pos not in head and Floor.at(floor, pos) < 9 end)

    head = head ++ rising_and_not_in_head

    find_basin_size(floor, head, opened, basin)
  end

  def get_max_from_list(_list, 0, so_far) do
    so_far
  end

  def get_max_from_list(list, numbers_to_get, so_far) do
    m = Enum.max(list)
    new_list = List.delete(list, m)
    get_max_from_list(new_list, numbers_to_get - 1, so_far ++ [m])
  end
end

basin_sizes =
  low_points
  |> Enum.map(fn pos -> Basin.find_basin_size(i, [pos], [], []) end)
  |> Enum.map(fn b -> length(b) end)

Basin.get_max_from_list(basin_sizes, 3, []) |> Enum.reduce(1, fn x, acc -> x * acc end)

i = input
x_max = length(hd(i)) - 1
y_max = length(i) - 1

low_points =
  for y <- 0..y_max do
    for x <- 0..x_max do
      {{x, y}, [{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}]}
    end
  end
  |> List.flatten()
  |> Enum.map(fn {loc, a} ->
    {loc, Enum.filter(a, fn {x, y} -> x >= 0 and x <= x_max and y >= 0 and y <= y_max end)}
  end)
  |> Enum.map(fn {loc, a} ->
    {loc, Floor.at(i, loc), Enum.map(a, fn loc2 -> Floor.at(i, loc2) end) |> Enum.min()}
  end)
  |> Enum.filter(fn {_loc, loc_v, m} -> loc_v <= m and loc_v < 9 end)
  |> Enum.map(fn {loc, _loc_v, _m} -> loc end)

low_points
|> Enum.map(fn pos -> Floor.at(i, pos) end)
|> Enum.count()

basin_sizes =
  low_points
  |> Enum.map(fn pos -> Basin.find_basin_size(i, [pos], [], []) end)
  |> Enum.map(fn b -> length(b) end)

Basin.get_max_from_list(basin_sizes, 3, []) |> Enum.reduce(1, fn x, acc -> x * acc end)

Wrong: 1600104

Other notebooks:

@alde103

Build_Large_Language_Mode...

Chapter 4: Implementing a GPT model from scratch t...

ch4.livemd

nx exla axon tiktoken table_rex kino_vega_lite

2024-11-26
@DockYard-Academy

curriculum

Guards

guards.livemd

jason kino youtube hidden_cell

2023-3-21
Poeticoding Ltd.
@poeticoding

yolo_elixir

YoloV8 on a single image

yolov8_single_image.livemd

yolo nx exla kino image evision

2024-12-23
@DockYard-Academy

curriculum

Strings

strings.livemd

jason kino youtube hidden_cell

2023-1-21
@solidsnakecase

livebook

Live Math

livemath.livemd

nx exla kino stb_image vega_lite kino_vega_lite

2024-8-26
Ryo Wakabayashi
@RyoWakabayashi

elixir-learning

Titanic optimized

titanic_optimized.livemd

exla axon kino kino_vega_lite explorer table_rex

2023-4-3
Luis Ezcurdia
@3zcurdia

chroma

Chroma Example

chroma-example.livemd

chroma req floki bumblebee exla

2023-8-28

Back