Day 2 was pretty interesting! Design a small interpreter to run the int-code program, and find the result.
Puzzle 1
A couple interesting twists in Puzzle 1 that I liked here are that the program is allowed to modify itself, and that I have to modify the program ahead of time. First, the (small) computer:
defmodule AdventOfCode.Y2019.Intcode do
defstruct program: [], position: 0
def new(program), do: %__MODULE__{program: program}
def run_all(computer) when not is_tuple(computer), do: run_all({:ok, computer})
def run_all({:halt, %__MODULE__{program: prog}}), do: prog
def run_all({:error, computer}), do: {:error, computer}
def run_all({:ok, computer}), do: run_all(run(computer))
def run(%{program: prog, position: pos} = computer) do
code = Enum.at(prog, pos)
op(computer, code)
end
def op(%__MODULE__{program: prog, position: pos}, 1) do
prog = compute(prog, pos, &Kernel.+/2)
{:ok, %__MODULE__{program: prog, position: pos + 4}}
end
def op(%__MODULE__{program: prog, position: pos}, 2) do
prog = compute(prog, pos, &Kernel.*/2)
{:ok, %__MODULE__{program: prog, position: pos + 4}}
end
def op(computer, 99), do: {:halt, computer}
def op(computer, _), do: {:error, computer}
defp compute(prog, pos, f) do
List.update_at(prog, Enum.at(prog, pos + 3), fn _ ->
f.(Enum.at(prog, Enum.at(prog, pos + 1)), Enum.at(prog, Enum.at(prog, pos + 2)))
end)
end
end
I decided to make a struct here, because I like to be able to quickly declare
defaults. new creates a new Intcode struct that contains the program and
the starting position. run_all is a recursive function, that runs the current
operation, and checks to make sure everything is :ok before continuing. op
uses pattern matching to decide whether this is an addition instruction, the
1, or a multiplication instruction, the 2. compute modifies the program by
performing the instruction and updating the program’s memory. If op receives
the code 99, the run :halts, which signifies a successful run. Anything else
returns an :error, which means something somewhere went terribly wrong.
Instead of really being able to test my solution ahead of time, I was able to test the computer.
defmodule AdventOfCode.Y2019.IntcodeTest do
use ExUnit.Case
alias AdventOfCode.Y2019.Intcode
test "it adds properly" do
[2, 0, 0, 0, 99] =
[1, 0, 0, 0, 99]
|> Intcode.new()
|> Intcode.run_all()
end
test "it multiplies properly" do
[2, 3, 0, 6, 99] =
[2, 3, 0, 3, 99]
|> Intcode.new()
|> Intcode.run_all()
end
test "it halts properly" do
[2, 4, 4, 5, 99, 9801] =
[2, 4, 4, 5, 99, 0]
|> Intcode.new()
|> Intcode.run_all()
end
test "it overwrites itself nicely" do
[30, 1, 1, 4, 2, 5, 6, 0, 99] =
[1, 1, 1, 4, 99, 5, 6, 0, 99]
|> Intcode.new()
|> Intcode.run_all()
end
end
The solution, then, is quite small.
import AdventOfCode
alias AdventOfCode.Y2019.Intcode
aoc 2019, 2 do
def p1 do
input_stream()
|> Enum.at(0)
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> List.replace_at(1, 12)
|> List.replace_at(2, 2)
|> Intcode.new()
|> Intcode.run_all()
|> Enum.at(0)
end
end
A simple matter of parsing the input, modifying the program’s “inputs”, running, and returning the result!
Puzzle 2
Oh no… Puzzle 2 wants me to find the “inputs” that generate a specific output? That’s the opposite of the whole point of this computer! Fortunately, the inputs can each be between 0 and 99. I’m sure there is a better or faster way of pulling this off, but it was getting late so I decided to brute force it until it cracked! This… really increases the size of the solution.
def p2 do
input_stream()
|> Enum.at(0)
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> find()
end
def compute(prog, n, v) do
prog
|> List.replace_at(1, n)
|> List.replace_at(2, v)
|> Intcode.new()
|> Intcode.run_all()
|> Enum.at(0)
end
def find(prog) do
{n, v} =
Enum.reduce_while(0..99, 0, fn n, _ ->
v =
Enum.find(0..99, fn v ->
result = compute(prog, n, v)
case result do
19_690_720 -> true
_ -> false
end
end)
case v do
nil -> {:cont, 0}
v -> {:halt, {n, v}}
end
end)
100 * n + v
end
The output I am looking for is 19,690,720, and by gradually incrementing the
“inputs” (labelled as the “noun” and “verb”), I can find it!
find takes the program (the same program as part 1), and starts with a noun
of 0. I then check all the verbs from 0 to 99, stopping if my result is
achieved. If the result isn’t found, Enum.find will return nil. I match to
see if I have a real result or nil. If nil, I continue with the next noun.
If not, I halt the search and return the noun and verb that generated the result
(modified for the solution’s input box).
Luckily, it took about a second or two to find the right answer!
Final Version and Conclusion
import AdventOfCode
alias AdventOfCode.Y2019.Intcode
aoc 2019, 2 do
def p1, do: p(&compute(&1, 12, 2))
def p2, do: p(&find/1)
def p(f) do
input_stream()
|> Enum.at(0)
|> String.split(",")
|> Enum.map(&String.to_integer/1)
|> f.()
end
def compute(prog, n, v) do
prog
|> List.replace_at(1, n)
|> List.replace_at(2, v)
|> Intcode.new()
|> Intcode.run_all()
|> Enum.at(0)
end
def find(prog) do
{n, v} =
Enum.reduce_while(0..99, 0, fn n, _ ->
v =
Enum.find(0..99, fn v ->
result = compute(prog, n, v)
case result do
19_690_720 ->
true
_ ->
false
end
end)
case v do
nil -> {:cont, 0}
v -> {:halt, {n, v}}
end
end)
100 * n + v
end
end
Is there a better way to do this? I HOPE so! Some ideas that stand out:
- Because everything is immutable in elixir, this would be fairly easy to do in a parallel manner. Each instance of new inputs doesn’t affect the others, and so can be run in isolation.
- Maybe there’s some sort of obvious relationship between the inputs and outputs? If so, maybe some linear algebra here could help.
- Maybe a binary search would’ve been faster? Unsure, as it’s not guaranteed that ordered inputs consistently return ordered outputs.
- Constraint programming would be interesting here, but I don’t know of any constraint programming libraries in elixir. My only experience with constraint programming is some cool Prolog.
Did you solve this? What tactic did you take?