day08.livemd

Treetop Tree House

Mix.install([
  {:kino, "~> 0.8.0"},
  {:kino_vega_lite, "~> 0.1.7"},
  {:vega_lite, "~> 0.1.6"}
])

alias VegaLite, as: Vl
:ok

Puzzle Input

input = Kino.Input.textarea("Puzzle Input:")

Convert into a map: {x, y} => height

input =
  Kino.Input.read(input)
  |> String.split("\n", trim: true)
  |> Enum.with_index(fn line, y ->
    String.to_charlist(line)
    |> Enum.with_index(fn ch, x ->
      {{x, y}, ch - ?0}
    end)
  end)
  |> List.flatten()
  |> Enum.into(%{})

Calculate the size of the grid.

{{{min_x, _}, _}, {{max_x, _}, _}} = input |> Enum.min_max_by(fn {{x, _y}, _} -> x end)
{{{_, min_y}, _}, {{_, max_y}, _}} = input |> Enum.min_max_by(fn {{_x, y}, _} -> y end)
bounds = [{min_x, min_y}, {max_x, max_y}]

Preview Visualization

render_heatmap = fn values, visible ->
  heatmap =
    Enum.map(values, fn {{x, y}, height} ->
      heat = if Enum.member?(visible, {x, y}), do: height, else: -height
      %{x: x, y: y, heat: heat}
    end)

  heat_layer =
    Vl.new()
    |> Vl.mark(:rect)
    |> Vl.data(values: heatmap)
    |> Vl.encode_field(:x, "x")
    |> Vl.encode_field(:y, "y")
    |> Vl.encode_field(:color, "heat",
      type: :ordinal,
      legend: nil,
      scale: [scheme: "bluegreen", domain: Enum.to_list(-9..9)]
    )

  Vl.new(width: 600, height: 600)
  |> Vl.layers([heat_layer])
end

• for each row and column (in each direction):
  • for each tree
    • if it's taller than the previous tallest found in the row, it's visible, else invisible.

inspect_row = fn values, visible, xs, y ->
  acc =
    Enum.reduce(xs, {visible, -1}, fn x, {acc, mx} ->
      height = Map.fetch!(values, {x, y})

      if height > mx do
        {[{x, y} | acc], height}
      else
        {acc, mx}
      end
    end)

  {visible, _} = acc
  visible
end

inspect_col = fn values, visible, x, ys ->
  acc =
    Enum.reduce(ys, {visible, -1}, fn y, {acc, mx} ->
      height = Map.fetch!(values, {x, y})

      if height > mx do
        {[{x, y} | acc], height}
      else
        {acc, mx}
      end
    end)

  {visible, _} = acc
  visible
end

get_visible = fn values, bounds ->
  [{x0, y0}, {x1, y1}] = bounds
  visible = []

  visible =
    Enum.reduce(y0..y1, visible, fn y, acc ->
      inspect_row.(values, acc, x0..x1, y)
    end)

  visible =
    Enum.reduce(y0..y1, visible, fn y, acc ->
      inspect_row.(values, acc, x1..x0//-1, y)
    end)

  visible =
    Enum.reduce(x0..x1, visible, fn x, acc ->
      inspect_col.(values, acc, x, y0..y1)
    end)

  visible =
    Enum.reduce(x0..x1, visible, fn x, acc ->
      inspect_col.(values, acc, x, y1..y0//-1)
    end)

  visible |> Enum.uniq()
end

visible = get_visible.(input, bounds)

render_heatmap.(input, visible)

Part 1

length(visible)

Part 2

defmodule Part2 do
  def get_scores(values, bounds) do
    Enum.map(values, fn tree = {{x, y}, _h} ->
      {{x, y}, get_score(tree, values, bounds)}
    end)
  end

  def get_score(tree = {{x, y}, height}, values, _bounds = [{x0, y0}, {x1, y1}])
      when x == x0 or x == x1 or y == y0 or y == y1 do
    # IO.puts("edge #{inspect(tree)}")
    0
  end

  def get_score(tree = {{x, y}, height}, values, _bounds = [{x0, y0}, {x1, y1}]) do
    # IO.inspect(tree)

    get_col_score(x, (y - 1)..y0//-1, values, height) *
      get_col_score(x, (y + 1)..y1, values, height) *
      get_row_score((x - 1)..x0//-1, y, values, height) *
      get_row_score((x + 1)..x1, y, values, height)
  end

  defp get_col_score(x, ys, values, height) do
    # Count trees until we hit one at least as high as us.
    Enum.reduce_while(ys, 0, fn y, acc ->
      other = Map.fetch!(values, {x, y})
      # IO.inspect({x, y, other})

      if other >= height do
        {:halt, acc + 1}
      else
        {:cont, acc + 1}
      end
    end)
  end

  defp get_row_score(xs, y, values, height) do
    # Count trees until we hit one at least as high as us.
    Enum.reduce_while(xs, 0, fn x, acc ->
      other = Map.fetch!(values, {x, y})
      # IO.inspect({x, y, other})

      if other >= height do
        {:halt, acc + 1}
      else
        {:cont, acc + 1}
      end
    end)
  end
end

scores = Part2.get_scores(input, bounds)
best = scores |> Enum.max_by(fn {{_x, _y}, h} -> h end)
best

render_scores = fn scores, _best = {{best_x, best_y}, _s} ->
  heatmap =
    Enum.map(scores, fn {{x, y}, score} ->
      %{x: x, y: y, heat: score}
    end)

  heat_layer =
    Vl.new()
    |> Vl.mark(:rect)
    |> Vl.data(values: heatmap)
    |> Vl.encode_field(:x, "x")
    |> Vl.encode_field(:y, "y")
    |> Vl.encode_field(:color, "heat",
      type: :ordinal,
      legend: nil,
      scale: [scheme: "bluegreen"]
    )

  best_layer =
    Vl.new()
    |> Vl.mark(:point, size: 500, shape: :circle, color: "#ff0000")
    |> Vl.data(values: %{x: best_x, y: best_y})
    |> Vl.encode_field(:x, "x")
    |> Vl.encode_field(:y, "y")

  Vl.new(width: 600, height: 600)
  |> Vl.layers([heat_layer, best_layer])
end

render_scores.(input, best)

render_scores.(scores, best)