The Day 5 puzzle heralds our (hopefully triumphant) return to intcode. We will be modifying our original intcode computer to handle a few new instructions as well as “parameter modes”. Up until now our computer implicitly supported a single parameter mode: position mode. This means that the value of a parameter tells you to look at that address (i.e. index) for its value. We will need to be able to support an additional parameter mode called immediate where the parameter itself is the value.

These modes are encoded directly in the instruction. For example, an instruction of CBAXX represents an instruction XX (such as 02 or 99) with three parameters where A is the mode (0 for position, 1 for immediate) of the first parameter, B the mode of the second, and C the mode of the third. Any leading zeroes can also be omitted with the assumption that they are mode 0, so the instruction 2, would have the same meaning as 00002. We can also assume that any parameters that involve writing/setting a value are in position mode.

In addition to parameter modes we will be supporting two new instructions. They are essentially a read and write that work based on an “input” value which is defined in the puzzle. The write instruction (opcode 03) takes a single parameter and writes the input value to that position and the read instruction (opcode 04) will output the value at the position of its parameter.

If we’re going to support these changes we’ll need to overhaul how we read instructions. Let’s start by attempting to decode the new instruction format and separate the instruction from the parameter modes.

(defun parse-opcode (opcode)
    (let ((opcode-list (pad-list-to-n (int-to-list opcode) (+ max-mode-length opcode-length))))
    (list (reverse (subseq opcode-list 0 max-mode-length)) (subseq opcode-list max-mode-length))))

This function is a little complicated but is easier to understand if we break it down into steps. Imagine we are parsing the 1002 instruction. We first use the int-to-list helper to turn it into (1 0 0 2). Since the instructions can omit leading zeroes for position mode parameters, we’ll want to add those back in so that we have a consistent format. The pad-list-to-n helper assists with that and turns the list into (0 1 0 0 2). Then we just divide the list up into modes and opcode and smash it back together resulting in ((0 1 0) (0 2)). The first list is the parameter modes and the second is the opcode. Also note that we’ve reversed the first list so that the modes are in the order of the parameters themselves.

To execute one of these instructions we’ll need to combine it with the parameters first. The goal here is to get to a point where we have an opcode along with pairs of parameters and their nodes. For example an instruction with parameters like 1002, 4, 3, 4 could give us something like ((0 2) (0 4) (1 3) (0 4)). Before we can combine the parameters with modes however, we will need to parse them out of the program.

(defun get-parameters (program ip opcode)
    (let ((num-parameters (- (instruction-size (list opcode)) 1)))
    (loop for index from (+ ip 1) to (+ ip num-parameters) collect (get-at program index))))

The function calculates the number of parameters to extract based on the instruction size. The 2 instruction has a size of 4 (one opcode plus three parameters). Using that value we can use the loop to collect the next N values starting at the current instruction pointer.

Now that we’ve parsed both the opcode and the parameters, we can attempt to put them together.

(defun get-instruction (program ip)
    (let* 
        ((opcode-and-modes (parse-opcode (get-at program ip)))
         (opcode (second opcode-and-modes))
         (modes (first opcode-and-modes)))
    (cons
        opcode
        (mapcar #'list modes (get-parameters program ip opcode)))))

The mapcar in the function is a neat little trick. Mapping list over multiple lists performs a zip of those lists. So if we hade modes (0 1 0) and parameters (4 3 4), it will neatly zip them together to get ((0 4) (1 3) (0 4)). We then combine that with the opcode to get the structure we laid out above.

We now have a way to retrieve the instruction at the current instruction pointer. All we have to do is update our instruction execution pipeline to handle the new format.

(defun execute-instruction (program instruction)
    (cond ((addp instruction) (execute-add program instruction))
          ((multp instruction) (execute-mult program instruction))
          ((writep instruction) (execute-write program instruction))
          ((readp instruction) (execute-read program instruction))))

(defun execute (program)
    (let ((ip 0))
        (loop
            (setf instruction (get-instruction program ip))
            (if (haltp instruction) (return 'HALT))
            (execute-instruction program instruction)
            (setf ip (+ ip (instruction-size instruction))))))

The big difference here is the last line of execute. Since not all instructions have the same number of parameters anymore we need to be able to advance the instruction pointer based on the size of the instruction executed.

In the execute-<instruction> functions we need to fetch the parameter values differently based on mode through the use of some helper methods. This is what the add instruction looks like now (along with the helpers):

(defun get-parameter-value-by-mode (program parameter)
    (let ((mode (first parameter)) (value (second parameter)))
    (if (positionp mode)
        (get-at program value)
        value)))

;; Sets are always performed by position so ignore mode
(defun set-parameter-value-by-mode (program parameter value)
    (set-at program (second parameter) value))

(defun execute-add (program instruction)
    (let
        ((input1 (get-parameter-value-by-mode program (second instruction)))
         (input2 (get-parameter-value-by-mode program (third instruction))))
    (set-parameter-value-by-mode program (fourth instruction) (+ input1 input2))))

The other instructions are implemented similarly. For the input value that the read/write instructions rely on I ended up just storing it as global state. I didn’t want to have to pass it through all of these other functions and I wasn’t sure of a better way to handle it. One idea I had was to have a top level computer function that encapsulated all of the other functions by defining them within itself. Any necessary state could then be set within that function and still used by the encapsulated function. In the end I abandoned this since the state makes it nearly impossible to run/test those functions independently.

My full solution can be found on Github.