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:

(defun get-instructions ()
    (mapcar 
        #'parse-integer 
        (split-sequence:split-sequence #\,
            (first (uiop:read-file-lines "input.txt")))))

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 aref and setf functions:

(setf a (make-array 3 :element-type 'integer))
;; #(0 0 0)
(setf (aref a 1) 10)
;; #(0 10 0)

Our get-instructions function updated to return an array looks something like this:

(defun get-instructions ()
    (coerce
        (mapcar 
            #'parse-integer 
            (split-sequence:split-sequence #\,
                (first (uiop:read-file-lines "input.txt"))))
        'vector))

A 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:

(defun get-at (arr index)
    (aref arr index))
(defun set-at (arr index value)
    (setf (aref arr index) value))

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:

(defun value-to-intcode (intcode)
    (cond ((equal 1 intcode)  'add)
          ((equal 2 intcode)  'mult)
          ((equal 99 intcode) 'halt)))

We will also create some predicates to test whether an instruction is a certain type:

(defun addp (instruction)
    (equal 'add (first instruction)))
(defun multp (instruction)
    (equal 'mult (first instruction)))
(defun haltp (instruction)
    (equal 'halt (first instruction)))

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)):

(defun get-instruction (program pc)
    (let ((instruction (list (value-to-intcode (get-at program pc)))))
    (if (haltp instruction) 
        instruction
        (append 
            instruction
            (list
                (get-at program (+ pc 1))
                (get-at program (+ pc 2))
                (get-at program (+ pc 3)))))))

In the 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:

(defun execute-instruction (program instruction)
    (let
        ((input1 (get-at program (second instruction)))
         (input2 (get-at program (third instruction))))
            (cond ((addp  instruction)
                    (set-at program (fourth instruction) (+ input1 input2)))
                  ((multp instruction)
                    (set-at program (fourth instruction) (* input1 input2))))))

Finally, the overall program loop we outlined earlier:

(defun execute (program)
    (let ((pc 0))
        (loop
            (setf instruction (get-instruction program pc))
            (if (haltp instruction) (return program))
            (execute-instruction program instruction)
            (setf pc (+ pc 4)))))

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 (add/mult/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