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