Day 08

Mix.install([
  {:kino, "~> 0.7.0"}
])

IEx.Helpers.c("/Users/johnb/dev/2022adventOfCode/advent_of_code.ex")
alias AdventOfCode, as: AOC
alias Kino.Input

# Note: when making the next template, something like this works well:
#   `cat day04.livemd | sed 's/03/04/' > day04.livemd`
#

Installation and Data

input_p1example = Kino.Input.textarea("Example Data")

input_p1puzzleInput = Kino.Input.textarea("Puzzle Input")

input_source_select =
  Kino.Input.select("Source", [{:example, "example"}, {:puzzle_input, "puzzle input"}])

p1data = fn ->
  (Kino.Input.read(input_source_select) == :example &&
     Kino.Input.read(input_p1example)) ||
    Kino.Input.read(input_p1puzzleInput)
end

Part 1

Day 8: Treetop Tree House

The expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they’re curious if this would be a good location for a tree house.

First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.

The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:

30373
25512
65332
33549
35390

Each tree is represented as a single digit whose value is its height, where 0 is the shortest and 9 is the tallest.

A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.

All of the trees around the edge of the grid are visible - since they are already on the edge, there are no trees to block the view. In this example, that only leaves the interior nine trees to consider:

• The top-left 5 is visible from the left and top. (It isn’t visible from the right or bottom since other trees of height 5 are in the way.)
• The top-middle 5 is visible from the top and right.
• The top-right 1 is not visible from any direction; for it to be visible, there would need to only be trees of height 0 between it and an edge.
• The left-middle 5 is visible, but only from the right.
• The center 3 is not visible from any direction; for it to be visible, there would need to be only trees of at most height 2 between it and an edge.
• The right-middle 3 is visible from the right.
• In the bottom row, the middle 5 is visible, but the 3 and 4 are not.
• With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees are visible in this arrangement.

Consider your map; how many trees are visible from outside the grid?

###

defmodule Day08 do
  def grid_rows(grid) do
    Enum.map(0..(grid.grid_height - 1), fn y ->
      Enum.map(0..(grid.grid_width - 1), fn x ->
        grid[x + y * grid.grid_width]
      end)
    end)
  end

  def grid_columns(grid) do
    Enum.map(0..(grid.grid_width - 1), fn x ->
      Enum.map(0..(grid.grid_height - 1), fn y ->
        grid[x + y * grid.grid_width]
      end)
    end)
  end

  def count_visible(slice) do
    slice
    |> Enum.chunk_every(2, 1, :discard)
    |> Enum.reduce_while(0, fn [t1, t2], acc ->
      cond do
        t1 < t2 -> {:cont, acc + 1}
        true -> {:halt, acc}
      end
    end)

    # |> IO.inspect(label: Enum.join(slice))
  end

  def count_edge_trees(grid) do
    grid.grid_width * 2 + grid.grid_height * 2 - 4
    # |> IO.inspect(label: "edge trees")
  end

  def shadow_grid(grid) do
    %{
      grid_width: grid.grid_width,
      grid_height: grid.grid_height,
      last_cell: grid.last_cell
    }
  end

  def grid_index_at(grid, {x, y}) do
    x + y * grid.grid_width
  end

  def until_first_nil(list) do
    list
    |> Enum.reduce_while([], fn cell_value, acc ->
      cond do
        is_nil(cell_value) -> {:halt, Enum.reverse(acc)}
        true -> {:cont, [cell_value | acc]}
      end
    end)
  end

  def _cells(_grid, _center, _delta, _limit = 0) do
    []
  end

  def _cells(grid, center, delta, limit) do
    Enum.map(1..limit, fn offset -> grid[center + offset * delta] end)
  end

  def _cells(grid, center, +1 = delta) do
    center_right = grid.grid_width - rem(center, grid.grid_width) - 1
    _cells(grid, center, delta, center_right)
  end

  def _cells(grid, center, -1 = delta) do
    left_center = rem(center, grid.grid_width)
    _cells(grid, center, delta, left_center)
  end

  def _cells(grid, center, delta) do
    Enum.map(1..grid.grid_width, fn offset -> grid[center + offset * delta] end)
    |> until_first_nil()
  end

  def grid_cells_in_a_direction(grid, center, :up), do: _cells(grid, center, -grid.grid_width)
  def grid_cells_in_a_direction(grid, center, :down), do: _cells(grid, center, +grid.grid_width)
  def grid_cells_in_a_direction(grid, center, :left), do: _cells(grid, center, -1)
  def grid_cells_in_a_direction(grid, center, :right), do: _cells(grid, center, +1)

  def can_see_to_edge?(grid, coordinate) do
    current_index = grid_index_at(grid, coordinate)
    current_height = grid[current_index]

    [:up, :down, :left, :right]
    |> Enum.map(fn direction -> grid_cells_in_a_direction(grid, current_index, direction) end)
    |> Enum.any?(fn grid_cells ->
      Enum.all?(grid_cells, fn cell -> current_height > cell end)
    end)
  end

  def grid_set(grid, current_index, value) do
    put_in(grid, [current_index], value)
  end

  def gridcount(grid) do
    # 3 to remove grid_width, grid_height, and last_cell
    Enum.count(grid) - 3
  end

  def central_coordinates(grid) do
    for x <- 1..(grid.grid_width - 2), y <- 1..(grid.grid_height - 2), do: {x, y}
  end

  def count_visible_from_edges(grid) do
    grid
    |> central_coordinates()
    |> Enum.reduce(shadow_grid(grid), fn coordinate, shadow ->
      current_index = grid_index_at(grid, coordinate)

      cond do
        shadow[current_index] == "visible" ->
          shadow

        can_see_to_edge?(grid, coordinate) ->
          grid_set(shadow, current_index, "visible")

        true ->
          shadow
      end
    end)
    # |> IO.inspect(label: "shadow")
    |> gridcount()
  end

  def solve(text) do
    grid = AOC.as_grid_of_digits(text)

    count_edge_trees(grid) + count_visible_from_edges(grid)
  end

  def solve2(text) do
    grid = AOC.as_grid_of_digits(text)

    grid
    |> central_coordinates()
    |> Enum.reduce(shadow_grid(grid), fn coordinate, shadow ->
      current_index = grid_index_at(grid, coordinate)
      current_height = grid[current_index]

      score =
        [:up, :down, :left, :right]
        |> Enum.map(fn direction -> grid_cells_in_a_direction(grid, current_index, direction) end)
        |> Enum.reduce(1, fn grid_cells, acc ->
          distance =
            grid_cells
            |> Enum.reduce_while(0, fn cell_value, counter ->
              cond do
                current_height <= cell_value -> {:halt, counter + 1}
                true -> {:cont, counter + 1}
              end
            end)

          acc * distance
        end)

      get_and_update_in(shadow, [current_index], fn current ->
        cond do
          is_nil(current) -> {nil, score}
          true -> {current, current * score}
        end
      end)
      |> elem(1)
    end)
    |> Map.reject(fn {k, _v} -> k in [:grid_height, :grid_width, :last_cell] end)
    |> Map.values()
    |> Enum.max()
  end
end

p1data.()
|> Day08.solve()
|> IO.inspect(label: "\n*** Part 1 solution (example: 21)")

# 1669

p1data.()
|> Day08.solve2()
|> IO.inspect(label: "\n*** Part 2 solution (example: 8)")

# 331344

Part Two

Of the non-edge trees, which one can see the most trees - meaning the same height or shorter in each of the cardinal directions? Multiply these numbers to get the tree’s “score”. What is the highest score?