day09.livemd

Rope Bridge

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

alias VegaLite, as: Vl

Instructions

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

instructions =
  Kino.Input.read(input)
  |> String.trim()
  |> String.split("\n")
  |> Enum.map(fn i ->
    [direction, distance] = String.split(i, " ")
    {direction, String.to_integer(distance)}
  end)

Expand Instructions

If we want to run an animation, we need to see the individual steps. The easiest way to do that is to convert the instructions into single steps, so that "D 3" becomes "D 1, D 1, D 1" and so on.

steps =
  Enum.flat_map(instructions, fn
    {direction, distance} -> for _ <- 1..distance, do: direction
  end)

Rope

defmodule Rope do
  defmodule Knot do
    defstruct x: 0, y: 0, visited: MapSet.new(), text: "?"
  end

  def new(_num_tails = 1) do
    {%Knot{text: "H"}, [%Knot{text: "T"}]}
  end

  def new(num_tails) do
    head = %Knot{text: "H"}
    tails = for t <- 1..num_tails, do: %Knot{text: Integer.to_string(t)}
    {head, tails}
  end

  def bounds(steps) do
    # TODO: Calculate this as we go along; saves the second pass.
    {visited, _final} =
      Enum.map_reduce(steps, {0, 0}, fn
        "D", {x, y} -> {{x, y - 1}, {x, y - 1}}
        "U", {x, y} -> {{x, y + 1}, {x, y + 1}}
        "L", {x, y} -> {{x - 1, y}, {x - 1, y}}
        "R", {x, y} -> {{x + 1, y}, {x + 1, y}}
      end)

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

  def run(state, steps) do
    Enum.reduce(steps, state, &step/2)
  end

  def step(step, _state = {head, tails}) do
    head = move(head, step) |> mark_visited()

    {tails, _} =
      Enum.map_reduce(tails, head, fn tail, head ->
        tail = chase(tail, head) |> mark_visited()
        {tail, tail}
      end)

    {head, tails}
  end

  def mark_visited(knot = %Knot{x: x, y: y, visited: visited}) do
    %Knot{knot | visited: MapSet.put(visited, {x, y})}
  end

  def move(knot = %Knot{x: x}, "R"), do: %Knot{knot | x: x + 1}
  def move(knot = %Knot{y: y}, "U"), do: %Knot{knot | y: y + 1}
  def move(knot = %Knot{x: x}, "L"), do: %Knot{knot | x: x - 1}
  def move(knot = %Knot{y: y}, "D"), do: %Knot{knot | y: y - 1}

  # The head and tail must always be touching.
  def chase(tail = %Knot{x: tx, y: ty}, _head = %Knot{x: hx, y: hy})
      when hx - 1 <= tx and tx <= hx + 1 and hy - 1 <= ty and ty <= hy + 1,
      do: tail

  def chase(tail = %Knot{x: tx, y: ty}, _head = %Knot{x: hx, y: hy}),
    do: %Knot{tail | x: tx + sign(hx - tx), y: ty + sign(hy - ty)}

  def sign(value) when value < 0, do: -1
  def sign(value) when value == 0, do: 0
  def sign(value) when value > 0, do: 1
end

Part 1

rope = Rope.new(1)
final = Rope.run(rope, steps)
{_h, [_t = %Rope.Knot{visited: visited}]} = rope |> Rope.run(steps)
Enum.count(visited)

Part 2

rope = Rope.new(9)
final = Rope.run(rope, steps)
{_h, tails} = rope |> Rope.run(steps)
%Rope.Knot{visited: visited} = List.last(tails)
Enum.count(visited)

Heatmap

defmodule Render do
  def heatmap(_bounds = {x_scale, y_scale}, _state = {head, tails}) do
    visited_layers =
      for %Rope.Knot{visited: visited} <- [head | tails] do
        visited_points =
          Enum.map(visited, fn {x, y} ->
            %{x: x, y: y}
          end)

        Vl.new()
        |> Vl.mark(:rect)
        |> Vl.data(values: visited_points)
        |> Vl.encode_field(:x, "x", axis: false, scale: [domain: Enum.to_list(x_scale)])
        |> Vl.encode_field(:y, "y",
          axis: false,
          scale: [domain: Enum.to_list(y_scale) |> Enum.reverse()]
        )
      end

    text_layer =
      Vl.new()
      |> Vl.mark(:text)
      |> Vl.data(values: [head | tails] |> Enum.map(&Map.take(&1, [:x, :y, :text])))
      |> Vl.encode_field(:x, "x", axis: false)
      |> Vl.encode_field(:y, "y", axis: false)
      |> Vl.encode_field(:text, "text")

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

bounds = Rope.bounds(steps)
Render.heatmap(bounds, final)