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
- turn the robot,
- move the robot, and
- 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!
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.