Day 2 of Advent of Code starts off with a computer failure. Not my computer thankfully, but that of our…character? Are we Santa? I have no clue, but the good news is it doesn’t matter.
Our task is to replace the broken flight computer which uses a strange self-modifying program. There are three possible instruction types called “intcodes”: 1 (addition), 2 (multiplication), or 99 (halt). The addition and multiplication instructions are 4 integers long where the second and third values are the address (within the list of instructions) of inputs and the fourth value is the address of the output.
Judging from the problem statement alone, I think this challenge should be rather easy, but will take a little longer due to my lack of Lisp knowledge.
We will start off once again by parsing the input file. This time it is a little more complicated because each value is comma-separated rather than on an individual line. We’ll still use
ioup to read the file and then we’ll use the
string-sequence package to perform the split:
Now we know we will need to modify this list in place while executing the instructions. Some quick searches along the lines of “common lisp modify element of list” return a variety of solutions and none of them pretty. What that digging does get us is a suggestion to use an array instead. Common Lisp has lists AND arrays? Who would’ve known. Not me.
If our instructions are in an array instead of a list, we can easily get and set values by index using the
get-instructions function updated to return an array looks something like this:
vector is a one-dimensional array. It’s unclear to me whether that is a different data type in Common Lisp or not, but that won’t stop us from using it.
Next we’re going to create a couple helpers since the
aref syntax I laid out above is awkward:
We’re not getting much (besides a better name) with
get-at, but I think
set-at is an improvement.
Now we’re ready to start on the core logic. The basic loop is going to be rather simple: read the next instruction, execute it, and increment the program counter. It’s all the details in between that get messy.
Let’s think about what is involved in reading an instruction first. Each instruction has at least a single value to represent the intcode. We’ll definitely need that, but in the case of addition and multiplication we’ll also want easy access to the input and output addresses specified by the remaining values.
First we can define a
value-to-intcode function that converts to a human-readable instruction name:
We will also create some predicates to test whether an instruction is a certain type:
Then we will implement the
get-instruction function. The intent is for it to return a list containing the type of instruction and addresses (e.g.
(add 0 0 3)):
let we immediately construct a list with the intcode value. If it isn’t a halt instruction, we go ahead and append the three addresses, otherwise return it as-is. We need to handle the halt case in order to avoid potential index out of bounds errors.
With that we now have something we can execute. The actual operations are rather simple, we just need to read the two input values using the addresses in our instruction, add or multiply based on the instruction type, and then write back to the output address. It ends up looking something like this:
Finally, the overall program loop we outlined earlier:
This ended up far more complicated than I intended, likely due to a mixture of Lisp inexperience and lack of sleep. It’s probably not worth spending more time on now, but it may be an interesting problem to revisit when my Lisp skills are a little stronger. Speaking of sleep and my lack of it…I am going to bed so the second half of the exercise will have to wait.
My full solution can be found on Github.
EDIT: I took a look at this the next morning. It wasn’t as bad as I thought it was last night. The only change I made was to get rid of the use of symbols (
halt) for the opcodes. All it did was complicate things. Here’s the diff of those changes:
(defun addp (instruction) - (equal 'add (first instruction))) + (equal 1 (first instruction))) (defun multp (instruction) - (equal 'mult (first instruction))) + (equal 2 (first instruction))) (defun haltp (instruction) - (equal 'halt (first instruction))) - -(defun value-to-intcode (intcode) - (cond ((equal 1 intcode) 'add) - ((equal 2 intcode) 'mult) - ((equal 99 intcode) 'halt))) + (equal 99 (first instruction))) (defun get-instruction (program pc) - (let ((instruction (list (value-to-intcode (get-at program pc))))) + (let ((instruction (list (get-at program pc)))) (if (haltp instruction) instruction (append