Andrew Fontaine

Mostly code

Advent of Code 2019: Day 11

12 Dec 2019
Code Snippet for Advent of Code 2019: Day 11

More intcode problems! First, I’ll tune up the intcode computer a little bit. I noticed day 9 ran a little slow, and I think it’s because the program is a list. In elixir, lists are implemented as linked lists, which don’t have the best access time, as the list needs to be iterated through to find the element at the given index, so read-heavy operations, like the intcode computer, can suffer, especially as the intcode computer appends a memory space at the end of the list to use as variables. Iterating through 1000 items every time I need to read an element there can take its toll! I can do better.

I also wasn’t pleased with how the list had to expand when writing to an address outside of the bounds of the current memory space. I wanted something that didn’t need to grow as much while also providing an easy way of returning a default for address that I don’t know about yet. A Map is perfect for this!

First, I need to modify the struct and Intcode.new/3 to handle a program being a map.

  defstruct program: %{},
            position: 0,
            input: [],
            output: [],
            offset: 0

  def new(program, input \\ [], output \\ []),
    do: %__MODULE__{
      program:
        program |> Enum.with_index() |> Enum.map(fn {p, i} -> {i, p} end) |> Enum.into(%{}),
      input: input,
      output: output
    }

The keys of the map are the addresses of my program, and their values are the values of the program, turning a program like [1, 0, 0, 0, 99] into %{0 => 1, 1 => 0, 2 => 0, 3 => 0, 4 => 99}.

After updating all the Enum.at(program, position, 0) calls to Map.get(program, position, 0), and cleaning up that store function to remove the memory extending code, and there are significant speed ups, going from just over 2 minutes for Day 9 Part 2 to just over 2 seconds!

This clean-up wasn’t possible without my existing test cases, which did need to be updated slightly, going from assert ^expected = c.output to assert ^expected = Map.values(c.output), but all the tests passed and the computer was much faster 💻🏁

As for the actually problem, I created one task to handle the intcode computer, the robots “brain”, and one to handle its movements. The robot was taught to talk to the brain, and all that was left was to await the result.

  def p1(),
    do:
      input_stream()
      |> p(0)
      |> Map.keys()
      |> length()

  defp p(stream, input) do
    robot =
      Task.async(fn ->
        loop(%{direction: :up, panel: {0, 0}, panels: %{}, action: :paint, computer: nil})
      end)

    computer =
      Task.async(fn ->
        stream
        |> Enum.at(0)
        |> String.split(",")
        |> Enum.map(&String.to_integer/1)
        |> Intcode.new(:server, robot.pid)
        |> Intcode.run_all()
      end)

    send(robot.pid, {:computer, computer.pid})
    send(computer.pid, {:message, input})

    robot
    |> Task.await()
    |> Map.get(:panels)
  end

  defp loop(state) do
    receive do
      :halt -> state
      {:message, i} -> state |> handle_message(i) |> loop()
      {:computer, i} when is_pid(i) -> loop(%{state | computer: i})
    end
  end

loop/1 takes the starting state of the robot, and then I send the computer and the robot their starting messages. When the robot receives :halt, it means the computer has finished its work, and I can return the final state. Receiving {:computer, i} stores the PID of the computer so the robot can send it further data. When the robot receives {:message, i}, I need to update the state and loop again.

  defp handle_message(%{action: :paint, panel: panel, panels: panels} = state, i) do
    %{state | action: :turn, panels: Map.put(panels, panel, paint(i))}
  end

  defp handle_message(%{action: :turn, direction: d, panel: p, computer: c} = state, i) do
    d = turn(d, i)
    state = %{state | action: :paint, direction: d, panel: move(d, p)}

    state.panels
    |> Map.get(state.panel, :black)
    |> colour()
    |> (&send_colour(c, &1)).()

    state
  end

  defp send_colour(computer, colour), do: send(computer, {:message, colour})

By pattern matching on the :action the robot is on, I can decided which is the appropriate action to take. :paint adds the current panel to the map of panels that I have been painted with the colour that it has been painted.

  defp paint(0), do: :black
  defp paint(1), do: :white

I also update the action to :turn so the next message received runs the next function.

The :turn action is a little bigger. It has to

  1. turn the robot,
  2. move the robot, and
  3. send the brain the colour of the panel it just moved to.

The first two are handled by 2 simple functions that match on the direction and return the updated :direction and :panel.

  defp turn(:up, 0), do: :left
  defp turn(:up, 1), do: :right
  defp turn(:right, 0), do: :up
  defp turn(:right, 1), do: :down
  defp turn(:down, 0), do: :right
  defp turn(:down, 1), do: :left
  defp turn(:left, 0), do: :down
  defp turn(:left, 1), do: :up

  defp move(:up, {x, y}), do: {x, y + 1}
  defp move(:right, {x, y}), do: {x + 1, y}
  defp move(:left, {x, y}), do: {x - 1, y}
  defp move(:down, {x, y}), do: {x, y - 1}

The colour the panel is on is gotten by checking the map of painted panels for a colour, and returning the default of :black if there isn’t one.

  defp colour(:black), do: 0
  defp colour(:white), do: 1

This continues on until the computer is done. For puzzle one, returning the number of panels I’ve painted is as simple as returning the number of keys in the :panels map. ⭐ one done!

Puzzle 2

Part 2’s only extra work is to print the painted panels. By reusing the code from day 8, it’s a simple extension to draw the panels.

  def p2(), do: input_stream() |> p(1) |> draw()

  defp draw(panels) do
    [{x1, y1}, {x2, y2}] =
      panels
      |> Map.keys()
      |> Enum.reduce([{0, 0}, {0, 0}], fn {x, y}, [{x1, y1}, {x2, y2}] ->
        [{min(x, x1), min(y, y1)}, {max(x, x2), max(y, y2)}]
      end)

    Enum.map(Range.new(x1, x2), fn x ->
      Enum.map(Range.new(y1, y2), fn y ->
        panels
        |> Map.get({x, y}, :black)
        |> write()
      end)
    end)
    |> Enum.each(&IO.puts/1)
  end

  defp write(colour), do: IO.ANSI.format_fragment([colour, "█", :reset])

I do need to check and make sure I draw all the panels, so I need to quickly find the bounds of the painted panels, then iterate over the panels to draw out the ship’s new registration code!

Day 11 Solution

That’s another 🌟!

Conclusion

Elixir’s easy ability to have tasks talk to each other made today a lot easier than it potentially could’ve been. I think the next time a problem like this comes around, I’ll be thinking on how to generalize this runner into something reusable. Also Lists in Elixir can be sneakily expensive, so if you aren’t using a majority of the list, reach for a Map instead.

I ❤ feedback. Let me know what you think of this article on Twitter @afontaine_ca