Advent of Code 2022 - Day 8

LostKobrakai

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

15 comments

#advent-of-code #2022

2 2595 15

2023-05-20 10:19:11 UTC

Showing Posts 1 to 10

Show Best Posts
Show All (oldest first)
Show All (newest first)

kwando

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.

Post #1

kwando

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)

Post #2

adamu

Loops in loops in loops 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.

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2022/day8.exs

Post #3

Arzar

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

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

Post #4

cnschroter

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)

Post #5

adolfont

Done with Livebook
https://github.com/adolfont/pensandoemelixir/blob/main/adventofcode/2022/day08_2022/day08.livemd

Post #6

tfwright

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

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

Post #7

adamu

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.

Post #8

deadbeef

Late to the party. Brute forced like others

https://github.com/ed-flanagan/advent-of-code-solutions-elixir/blob/main/lib/advent/y2022/d08.ex

Post #9

stevensonmt

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.
https://github.com/stevensonmt/advent_of_code/blob/2022/2022/day8/lib/day8.ex

Post #10

Load more posts (5 remaining)