Advent of Code 2022 - Day 8

This one has been quite the ride. Struggled at first to find a good data format to suite the problem. I really like how that turned out by separating the map data from coordinates to look at when counting. Part 2 also was imo not well defined. It took me a while to figure out I don’t need to subtract smaller trees behind larger trees anymore.

Solution
defmodule Day8 do
  defstruct map: nil, size: nil

  def parse(text) do
    lines = text |> String.split("\n") |> Enum.reject(&(&1 == ""))

    {map, _} =
      lines
      |> Enum.with_index()
      |> Enum.flat_map_reduce(0, fn {line, y}, next ->
        line
        |> String.split("", trim: true)
        |> Enum.with_index()
        |> Enum.map_reduce(next, fn {height, x}, next ->
          item = {{x, y}, %{id: next, height: String.to_integer(height)}}
          {item, next + 1}
        end)
      end)

    map = Map.new(map)

    keys = Map.keys(map)
    size_x = keys |> Enum.map(fn {x, _} -> x end) |> Enum.max()
    size_y = keys |> Enum.map(fn {_, y} -> y end) |> Enum.max()

    %__MODULE__{map: map, size: %{x: size_x, y: size_y}}
  end

  def count_visible_from_outside(text) do
    data = parse(text)

    from_left_keys =
      for y <- 0..data.size.y//1 do
        for x <- 0..data.size.x//1, do: {x, y}
      end

    from_right_keys =
      for y <- 0..data.size.y//1 do
        for x <- data.size.x..0//-1, do: {x, y}
      end

    from_top_keys =
      for x <- 0..data.size.x//1 do
        for y <- 0..data.size.y//1, do: {x, y}
      end

    from_bottom_keys =
      for x <- 0..data.size.x//1 do
        for y <- data.size.y..0//-1, do: {x, y}
      end

    [
      from_left_keys,
      from_right_keys,
      from_top_keys,
      from_bottom_keys
    ]
    |> Enum.flat_map(& &1)
    |> Enum.flat_map(&count_visible_line(data.map, &1))
    |> Enum.uniq()
    |> Enum.count()
  end

  defp count_visible_line(map, line) do
    {_, trees} =
      line
      |> Enum.map(fn coordinate -> Map.fetch!(map, coordinate) end)
      |> Enum.reduce({-1, []}, fn
        %{height: tree_height} = tree, {line_of_sight, visible}
        when tree_height > line_of_sight ->
          {tree_height, [tree | visible]}

        _, acc ->
          acc
      end)

    trees
  end

  def count_visible_from_tree_house(text) do
    data = parse(text)

    for y <- 0..data.size.y//1, x <- 0..data.size.x//1 do
      tree = Map.fetch!(data.map, {x, y})
      to_left = for x <- (x - 1)..0//-1, do: {x, y}
      to_right = for x <- (x + 1)..data.size.x//1, do: {x, y}
      to_top = for y <- (y - 1)..0//-1, do: {x, y}
      to_bottom = for y <- (y + 1)..data.size.y//1, do: {x, y}

      [
        to_top,
        to_left,
        to_right,
        to_bottom
      ]
      |> Enum.map(fn line ->
        data.map |> count_visible_line_treehouse(line, tree.height)
      end)
      |> Enum.reduce(&Kernel.*/2)
    end
    |> Enum.max()
  end

  defp count_visible_line_treehouse(map, line, limit) do
    line
    |> Enum.map(fn coordinate -> Map.fetch!(map, coordinate) end)
    |> Enum.reduce_while(0, fn
      tree, num when tree.height >= limit -> {:halt, num + 1}
      _, num -> {:cont, num + 1}
    end)
  end
end
2 Likes

Yeah, part 2 was not very well defined. I made the same “mistake” as you with not counting smaller trees behind taller ones… quite annoying.

Something I keep having use for in these problems where you have to walk around in a matrix is to use a list of “vectors” instead of hardcoding the movements.
This is for part 2, made a more “clever”/convoluted solution for part 1… but I had no use for in part 2.

defmodule VisibilityChecker do
  def max_visibility(grid) do
    heights = for {rows, y} <- Enum.with_index(grid), 
      {h, x} <- Enum.with_index(rows), into: %{} do
      {{x, y}, h}
    end

    heights
    |> Stream.map(&elem(&1, 0))
    |> Stream.map(&score(&1, heights))
    |> Enum.max()
  end

  @directions [{-1, 0},{1, 0},{0, -1},{0, 1},]
  defp score(pos, heights) do
    for dir <- @directions, reduce: 1 do
      score -> score * visible(heights, pos, dir, heights[pos], 0)
    end
  end

  defp visible(heights, pos, direction, max_height, line_height) do
    new_pos = translate(pos, direction)
    case heights[new_pos] do
      nil -> 0
      tree_height when tree_height >= max_height -> 1
      tree_height when tree_height >= line_height -> 
        1 + visible(heights, new_pos, direction, max_height, tree_height)
      _ -> 
        1 + visible(heights, new_pos, direction, max_height, line_height)
    end
  end

  defp translate({x, y}, {dx, dy}), do: {x + dx, y + dy}
end

# input is a list of lists with the three heights [ [ 1, 2], [ 3, 4 ]]
#  
# 1 2
# 3 4
#
# would be 
# [
#.  [ 1, 2 ],
#   [ 3, 4 ]
# ]
VisibilityChecker.max_visibility(input)
1 Like

Loops in loops in loops :sweat_smile: My slowest answer to date this year. I avoided scanning out from every tree, but I did do 4 passes of the forest, and each of those passes does a lot of map lookups, so pretty slow I guess. By slow I mean 40ms.

Brute forcing it. Now off checking on the subreddit aoc to see how clever people do it :smiley:

defmodule Day8 do
  @width 99
  @height 99

  def boolean_to_integer(bool) do
    if bool, do: 1, else: 0
  end

  def at(trees, x, y) do
    index = y * @width + x
    trees[index]
  end

  # precondition: the tree is not on the edge
  def is_visible(trees, x, y) do
    height = at(trees, x, y)

    left = 0..(x - 1) |> Enum.all?(fn i -> at(trees, i, y) < height end)
    right = (x + 1)..(@width - 1) |> Enum.all?(fn i -> at(trees, i, y) < height end)
    up = 0..(y - 1) |> Enum.all?(fn i -> at(trees, x, i) < height end)
    down = (y + 1)..(@height - 1) |> Enum.all?(fn i -> at(trees, x, i) < height end)
    left or right or up or down
  end

  def count_visible(trees) do
    edge = @width * 2 + (@height - 2) * 2

    interior = Enum.sum(for i <- 1..(@width - 2), j <- 1..(@height - 2) do
      boolean_to_integer(is_visible(trees, i, j))
    end)

    edge + interior
  end

  # precondition: the tree is not on the edge
  def scenic_score(trees, x, y) do
    height = at(trees, x, y)

    left = (x - 1)..0
    |> Enum.reduce_while(0, fn i, acc ->
       h = at(trees, i, y)
       if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
       end)

    right = (x + 1)..(@width - 1)
    |>  Enum.reduce_while(0, fn i, acc ->
       h = at(trees, i, y)
       if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
       end)

    up = (y - 1)..0
    |> Enum.reduce_while(0, fn j, acc ->
        h = at(trees, x, j)
        if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
        end)

    down =  (y + 1)..(@height - 1)
    |>  Enum.reduce_while(0, fn j, acc ->
       h = at(trees, x, j)
       if h < height, do: {:cont, acc + 1}, else: {:halt, acc + 1}
       end)

    left * right * up * down
  end

  def find_best_scenic_score(trees) do
    Enum.max(for i <- 1..(@width - 2), j <- 1..(@height - 2) do
      scenic_score(trees, i, j)
    end)
  end

  def start() do
    trees = File.stream!("input08")
    |> Stream.map(&String.trim/1)
    |> Enum.join
    |> String.graphemes
    |> Enum.map(&String.to_integer/1)
    |> Arrays.new

    Day8.count_visible(trees) |> IO.puts
    Day8.find_best_scenic_score(trees) |> IO.puts
  end
end

I used Maps of Maps for faster access

Part 1

visible? =
  fn x, y, height, forest ->
    #IO.inspect({x, y, height})
    Enum.map(0..x-1, &(forest[&1][y])) |> Enum.all?(&(&1 < height)) or
    Enum.map(x+1..98, &(forest[&1][y])) |> Enum.all?(&(&1 < height)) or
    Enum.map(0..y-1, &(forest[x][&1])) |> Enum.all?(&(&1 < height)) or
    Enum.map(y+1..98, &(forest[x][&1])) |> Enum.all?(&(&1 < height)) 
  end

forest =
  input
  |> Kino.Input.read()
  |> String.split("\n")
  |> Enum.with_index()
  |> Enum.reduce(%{}, fn {row, row_index}, acc -> 
    row =
      String.codepoints(row)
      |> Enum.with_index()
      |> Enum.reduce(%{}, fn {tree_height, col_index}, acc -> 
        Map.put(acc, col_index, String.to_integer(tree_height))
      end)

    Map.put(acc, row_index, row)
  end)

forest
|> Enum.reduce(0, fn {row, trees}, count_visible -> 
  count_visible + 
  Enum.reduce(trees, 0, fn {col, tree_height}, count_visible ->
    cond do
      row == 0 -> count_visible + 1
      col == 0 -> count_visible + 1
      row == 98 -> count_visible + 1
      col == 98 -> count_visible + 1
      true -> 
        if visible?.(row, col, forest[row][col], forest) do
          count_visible + 1
        else
          count_visible
        end
    end
  end)
end)

Part 2

visibility_count = 
  fn heights, height ->
    heights
    |> Enum.reduce_while(0, fn h, acc -> 
      if h >= height do
        {:halt, acc + 1}
      else
        {:cont, acc + 1}
      end
    end)
  end

score =
  fn x, y, height, forest ->
    l = Enum.map(0..x-1, &(forest[&1][y])) |> Enum.reverse() |> visibility_count.(height)
    r = Enum.map(x+1..98, &(forest[&1][y])) |> visibility_count.(height)
    t = Enum.map(0..y-1, &(forest[x][&1])) |> Enum.reverse() |> visibility_count.(height)
    d = Enum.map(y+1..98, &(forest[x][&1])) |> visibility_count.(height) 

    l * r * t * d
  end

forest
|> Enum.reduce(0, fn {row, trees}, max_score -> 
  new_score = 
    Enum.reduce(trees, 0, fn {col, tree_height}, max_score ->
      cond do
        row == 0 -> max_score
        col == 0 -> max_score
        row == 98 -> max_score
        col == 98 -> max_score
        true -> 
          new_score = score.(row, col, forest[row][col], forest)
          if max_score < new_score do
            new_score
          else
            max_score
          end
      end
    end)

  if max_score < new_score do
    new_score
  else
    max_score
  end
end)

Done with Livebook

1 Like

Fun with index math. I started the first part with the assumption that visibility is increasing unlikely toward the center so I should go from the edges in. But I made a serious logic error thinking I could get away with just tracking the visibility of the previous row/column as a short hand, forgetting that if a height was equal then I would need to consider the one before that, and the one before that if it was equal…so it took much longer than it should have :dizzy_face:

After fixing that things went smoothly although I had to do way more debugging in the second part than any previous day. All in all I really enjoyed this one, surveying a matrix from the outside in and then inside out

There is an optimization you can do in part 1, as you know that once the tree height is 9 you can’t see anything behind that, so there so use checking.

Late to the party. Brute forced like others

2 Likes

Didn’t have a chance to do this before now. Just threw together the quickest brute force solution I could. I’m sure there’s a clever dynamic programming approach that I’m missing. I hate that I couldn’t come up with a more concise way of searching the four directions.

def parse(input) do
    input
    |> String.split()
    |> Enum.with_index()
    |> Enum.map(&parse_line/1)
    |> List.flatten()
    |> Enum.reduce(Map.new(), fn {value, key}, map -> Map.put(map, key, value) end)
  end

Maybe purely stylistic but in a previous year’s AOC thread someone pointed out to me that Map.new/2 makes Enum.reduce(Map.new(), ... unnecessary. Just pipe the enumerable into Map.new(fn {v, k} -> {k, v} end). Also I think Enum.flat_map(&parse_line/1) does the same thing in one line as your current Enum.map(&parse_line/1) |> List.flatten()

I’m still one day behind but here goes my day 8. I struggled at puzzle 2 getting my ranges right. Yup, and I had the same issue with counting the taller tree.

defmodule ExAOC2022.Day8 do
  @input "./lib/day8_input.txt"

  def puzzle1() do
    lines = file_by_line(@input)
    grid = Enum.map(lines, &(String.split(&1, "", trim: true)))

    rows_num = length(lines)
    cols_num = hd(grid) |> length

    for i <- 0..rows_num-1, j <- 0..cols_num-1, reduce: 0 do
      acc ->
        if visible?(grid, i, j, rows_num, cols_num), do: acc + 1, else: acc
    end
  end

  def puzzle2() do
    lines = file_by_line(@input)
    grid = Enum.map(lines, &(String.split(&1, "", trim: true)))

    rows_num = length(lines)
    cols_num = hd(grid) |> length

    for i <- 1..rows_num-2, j <- 1..cols_num-2, reduce: 0 do
      acc ->
        score = scenic_score(grid, i, j, rows_num-1, cols_num-1)
        if score > acc, do: score, else: acc
    end
  end

  defp visible?(grid, x, y, max_x, max_y) do
    v = val(grid, x, y)

    cond do
      # edge
      x == 0 or y == 0 or x == (max_x - 1) or y == (max_y - 1) ->
        true
      # up
      max_num_y(grid, x, 0, y-1) < v ->
        true
      # down
      max_num_y(grid, x, y+1, max_y-1) < v ->
        true
      # left
      max_num_x(grid, y, 0, x-1) < v ->
        true
      # right
      max_num_x(grid, y, x+1, max_x-1) < v ->
        true
      true ->
        false
    end
  end

  defp scenic_score(grid, x, y, max_x, max_y) do
    v = val(grid, x, y)
    up_trees = Enum.map(y-1..0//-1, &val(grid, x, &1)) |> dist(v)
    left_trees = Enum.map(x-1..0//-1, &val(grid, &1, y)) |> dist(v)
    down_trees = Enum.map(y+1..max_y, &val(grid, x, &1)) |> dist(v)
    right_trees = Enum.map(x+1..max_x, &val(grid, &1, y)) |> dist(v)

    up_trees * down_trees * left_trees * right_trees
  end

  defp dist(trees, our_tree) do
    Enum.reduce_while(trees, 0, fn tree, score ->
      if tree >= our_tree, do: {:halt, score + 1}, else: {:cont, score + 1}
    end)
  end

  defp max_num_y(grid, x, from, to), do:
    Enum.map(from..to, &val(grid, x, &1)) |> Enum.max()

  defp max_num_x(grid, y, from, to), do:
    Enum.map(from..to, &val(grid, &1, y)) |> Enum.max()

  defp int(s), do: String.to_integer(s)

  defp val(grid, x, y) do
    get_in(grid, [Access.at(y), Access.at(x)]) |> int
  end

  defp file_by_line(file) do
    file
    |> File.read!()
    |> String.split(~r/\R/, trim: true)
  end
end

Way late with this, but I took the last Advent of Code as a means to learn Elixir a bit and this is what I came up with for the day 8 challenge.

defmodule Aoc2022.Day8 do
  @moduledoc """
  Documentation for `Day 8`.
  
  --- Day 8: Treetop Tree House ---
  https://adventofcode.com/2022/day/8
  
  """

  defmodule Tree do
    defstruct height: nil, visible: false, score: 1
  end

  def process_input do
    rows =
      File.read!("./input/day8.txt")
      |> String.split("\r\n")

    row_count = Enum.count(rows) - 1
    cols = rows |> Enum.at(0) |> String.graphemes()
    col_count = Enum.count(cols) - 1

    trees =
      rows
      |> Enum.with_index()
      |> Enum.map(fn {x, i} ->
        t =
          x
          |> String.graphemes()
          |> Enum.with_index()
          |> Enum.reduce(%{}, fn {y, j}, acc ->
            Map.put(acc, {i, j}, %Tree{height: String.to_integer(y), visible: false})
          end)

        t
      end)
      |> Enum.reduce(%{}, fn x, acc ->
        Map.merge(acc, x)
      end)

    trees_with_visibility =
      0..row_count
      |> Enum.map(fn i ->
        0..col_count
        |> Enum.map(fn j ->
          case {i, j} do
            {0, _} ->
              tree = Map.get(trees, {i, j})
              %{{i, j} => %Tree{tree | visible: true}}

            {_, 0} ->
              tree = Map.get(trees, {i, j})
              %{{i, j} => %Tree{tree | visible: true}}

            {r, _} when r == row_count ->
              tree = Map.get(trees, {i, j})
              %{{i, j} => %Tree{tree | visible: true}}

            {_, c} when c === col_count ->
              tree = Map.get(trees, {i, j})
              %{{i, j} => %Tree{tree | visible: true}}

            {r, c} when r == row_count and c == col_count ->
              tree = Map.get(trees, {i, j})
              %{{i, j} => %Tree{tree | visible: true}}

            {row, column} ->
              %{height: current, visible: _v} = Map.get(trees, {i, j})

              trees_left = traverse_x(trees, column - 1, 0, row)

              visibility_score_left =
                trees_left
                |> visibility_score(current)

              visible_left? =
                trees_left
                |> Enum.filter(fn x -> current <= x end)
                |> Enum.empty?()

              trees_right = traverse_x(trees, column + 1, col_count, row)

              visibility_score_right =
                trees_right
                |> visibility_score(current)

              visible_right? =
                trees_right
                |> Enum.filter(fn x -> current <= x end)
                |> Enum.empty?()

              trees_up = traverse_y(trees, row - 1, 0, column)

              visibility_score_up =
                trees_up
                |> visibility_score(current)

              visible_up? =
                trees_up
                |> Enum.filter(fn x -> current <= x end)
                |> Enum.empty?()

              trees_down = traverse_y(trees, row + 1, row_count, column)

              visibility_score_down =
                trees_down
                |> visibility_score(current)

              visible_down? =
                trees_down
                |> Enum.filter(fn x -> current <= x end)
                |> Enum.empty?()

              %{
                {i, j} => %Tree{
                  height: current,
                  visible: visible_up? || visible_down? || visible_left? || visible_right?,
                  score:
                    visibility_score_down * visibility_score_left * visibility_score_right *
                      visibility_score_up
                }
              }
          end
        end)
      end)
      |> List.flatten()
      |> Enum.reduce(%{}, fn w, acc ->
        Map.merge(w, acc)
      end)

    visible_count =
      trees_with_visibility
      |> Enum.filter(fn {_, %{height: _, visible: v}} -> v end)
      |> Enum.count()

    highest_score =
      trees_with_visibility
      |> Enum.map(fn {_, %{score: s}} -> s end)
      |> Enum.max()

    {visible_count, highest_score}
  end

  defp traverse_x(trees, from, to, axis) do
    from..to
    |> Enum.map(fn x ->
      %{height: u, visible: _v} = Map.get(trees, {axis, x})
      u
    end)
  end

  defp traverse_y(trees, from, to, axis) do
    from..to
    |> Enum.map(fn x ->
      %{height: u, visible: _v} = Map.get(trees, {x, axis})
      u
    end)
  end

  defp visibility_score(trees, current) do
    score =
      trees
      |> Enum.reduce_while(0, fn x, acc ->
        if x >= current, do: {:halt, acc + 1}, else: {:cont, acc + 1}
      end)

    score
  end
end

A tiny bit of code review on the above - nothing major, mostly “here’s a shorter way to write the same ideas” tips.

  • many Enum functions have a variant that lets you transform the input before doing their thing. For instance, Enum.count/2 or Enum.max_by/4. There’s a minor performance benefit of using them since the intermediate list doesn’t need to be constructed, but IMO the readability gain is better.

  • Enum.map + List.flatten == Enum.flat_map, only again the intermediate list doesn’t need to be constructed.

  • Most code that uses Enum.reduce with an initial value of %{} will be clearer with Map.new. I say “most” because sometimes there’s code in the block passed to reduce that returns acc unchanged, which you can’t do with Map.new

  • most of the time when you want one-line-at-a-time, File.stream! will save you some typing. By default, it already splits lines. There is also a theoretical memory-usage advantage since using Stream means you don’t need every line in memory at once, but it’s unlikely to be important.

  • functions are basically free: make more of them. In my experience, if you’d use a phrase to name a piece of code when discussing it with a colleague, it should probably be a separate function. For instance, here’s the “read the file in” part from my day 8 solution:

  def read(filename) do
    File.stream!(filename)
    |> Stream.map(&String.trim/1)
    |> Stream.with_index()
    |> Stream.flat_map(&parse_line/1)
    |> Map.new()
  end

  defp parse_line({line, row_index}) do
    line
    |> String.codepoints()
    |> Enum.map(&String.to_integer/1)
    |> Enum.with_index()
    |> Enum.map(fn {h, col_index} -> {{row_index, col_index}, h} end)
  end

If you wanted %Tree{} structs like in your version, you’d change that very last statement of parse_line to build one out of row_index / col_index / h values.

Another guideline I find useful: repeat yourself, find the common parts, and then make THAT a function. For instance, you might notice this pattern (placeholders in SHOUTING_CASE):

trees_DIR = GET_TREES

visibility_score_DIR =
  trees_DIR
  |> visibility_score(current)

visible_DIR? =
  trees_DIR
  |> Enum.filter(fn x -> current <= x end)
  |> Enum.empty?()

This becomes a function:

defp visibility_of(trees, current) do
  score = visibility_score(trees, current)

  flag =
    trees
    |> Enum.filter(fn x -> current <= x end)
    |> Enum.empty? # NOTE: consider using any? instead of filter + empty?

  {score, flag}
end

then the big branch of the case shortens to:

            {row, column} ->
              %{height: current, visible: _v} = Map.get(trees, {i, j})

              {visibility_score_left, visible_left?} =
                trees
                |> traverse_x(column - 1, 0, row)
                |> visibility_of(current)

              {visibility_score_right, visible_right?} =
                trees
                |> traverse_x(column + 1, col_count, row)
                |> visibility_of(current)

              {visibility_score_up, visible_up?} =
                trees
                |> traverse_y(row - 1, 0, column)
                |> visibility_of(current)

              {visibility_score_down, visible_down?} =
                trees
                |> traverse_y(row + 1, row_count, column)
                |> visibility_of(current)

              %{
                {i, j} => %Tree{
                  height: current,
                  visible: visible_up? || visible_down? || visible_left? || visible_right?,
                  score:
                    visibility_score_down * visibility_score_left * visibility_score_right *
                      visibility_score_up
                }
              }

Writing things this way makes it clearer that only the trees change between the four copies of the code.

2 Likes

Hi Matt!

Thanks for taking the time to analyze the code, these are very valuable suggestions which I’ll try to use in the future.

Elixir is indeed a special language, there is (almost) always a better and more elegant solution to a particular problem. :slight_smile: