Intcode Day 5

Today we add input and output to the intcode computer. We now have Opcode 3 which reads input and puts it into memory, and Opcode 4 which pushes an integer to output.
Both take addresses that get input or output.

Secondly, we now need to differentiate between position mode and immediate mode.

Thirdly, we need to start to account for the difference in opcode length, as the input and output operations have varying length.

This means that it's probably time to adjust the opcodes to be a structure, an enum and have an implementation.

Currently, we just match on the digit, so 1 mean we execute all the things from add. But we can move the logic into a set of functions.

The simplest thing is to have an enum of OpCodes, so OpAdd, OpMul etc, and then within each Op, we define a length. However the immediate and position modes adds a complication. Do we repeat the logic in every op for getting param1 in immediate mode, in position mode etc?

I wonder if we can define a GetParam, which can use the opcode to switch for how to get the value? I'm thinking something like

fn get_param(opcode: usize, position: usize) -> usize {
    match opcode {
        x if (opcode / 100) % 10 == 1=> self.memory[self.memory[self.pc + position]
        x if (opcode / 1000) % 10  == 1=> self.memory[self.pc + position]
    }
}

But that's a bit over complex, why should get parameter care about the opcode? Far more sensible to pass the mode into the get_param function, and make the opcode understand which mode to use. This makes get_param similar, but more explicit:

fn get_param(position: usize, mode: usize) -> usize {
    match mode {
        0 => self.memory[self.memory[self.pc + position]
        1 => self.memory[self.pc + position]
    }
}

Let's give this a try, lets sort out the position and immediate mode first, lets start with a simple intcode example that should add two immediate parameters together and loads answer into position 0.

    let mut cpu = IntCodeCPU::new(vec![1101,1,2,0,99]);
    assert_eq!(cpu.memory[0], 1101);   
    cpu.execute();
    assert_eq!(cpu.pc, 4);
    assert_eq!(cpu.memory[3], 3);   

This should fail, as opcode 1101 won't be understood, so we implement our get_param and refit the ad opcode to handle it. (We need to mod the opcode by 100 to make sure we only get the last 2 digits of course)

    let opcode = self.memory[self.pc];
    match opcode % 100 {
        1 => {
            let src1 = self.get_parameter(1, (opcode / 100) % 10);
            let src2 = self.get_parameter(2, (opcode / 1000) % 10);
            let dest = self.memory[self.pc+3] as usize;
            self.memory[dest] = src1 + src2;
            self.pc += 4;
        }
        ...
    }

That works, lets update the other opcode, test it and then we're good to go

Dealing with opcodes

Ok, so halfway through shaving the yak, lets fix up our opcodes into something a bit nicer.

We want each opcode to be a struct that consists of the length, the number of parameters, and the opcode type itself.

I'm not a fan of Rust's structures here, probably because I spent far too long in C++ and Java worlds so for me, I want structure, enum and methods to all be in the same place.

We've got some refactoring to do, we'll start by changing our modes to be a real enum rather than just 0 or 1

pub enum Modes {
    Position,
    Immediate,
}

impl Modes {
    pub fn from_u32(value: u32) -> Self {
        match value {
            0 => Modes::Position,
            1 => Modes::Immediate,
            _ => panic!("Unknown mode: {}", value),
        }
    }
}

We can use from_u32 to generate the right enum based on a 0 or 1 u32 value. That means we can switch our mode selecting code to be much more sensible:

    Modes::from_u32((opcode / 100) % 10),

Secondly, we want to specify new operations. Each operation takes a set of parameters that vary, specifically a set of modes for each parameter, and a size to advance the programme counter by.

pub struct IntCodeOpParams {
    modes: Vec<Modes>,
    size: usize,
}
pub enum IntCodeOp {
    Add(IntCodeOpParams),
    Mul(IntCodeOpParams),
    Halt(IntCodeOpParams),
}

We can now move our code that processes opcodes from the CPU into an implementation detail of the IntCodeOp function.

impl IntCodeOp {
    pub fn from_opcode(opcode: u32) -> Self {
        match opcode % 100 {
            1 => IntCodeOp::Add(IntCodeOpParams{
                modes: vec![
                    Modes::from_u32((opcode / 100) % 10),
                    Modes::from_u32((opcode / 1000) % 10),
                ],
                size: 4,
            }),
            2 => IntCodeOp::Mul(IntCodeOpParams{
                modes: vec![
                    Modes::from_u32((opcode / 100) % 10),
                    Modes::from_u32((opcode / 1000) % 10),
                ],
                size: 4,
            }),
            99 => IntCodeOp::Halt(IntCodeOpParams { size: 1, modes: vec![] }),
            _ => panic!("Unknown opcode: {}", opcode),
        }
    }
}

But we still need to execute these ops, and that should be a simple match statement for each. We can move the get_parameters into the operation itself while we're at it, and make it call out to the memory in the passed CPU.

    pub fn get_parameter(&self, cpu: &mut IntCodeCPU, offset: usize, mode: Modes) -> u32 {
        let param_value = cpu.memory[cpu.pc + offset];
        match mode {
            Modes::Position => {
                cpu.memory[param_value as usize] // Position mode
            }
            Modes::Immediate => param_value, // Immediate mode
        }
    }

    pub fn execute(&self, cpu: &mut IntCodeCPU) {
        match self {
            IntCodeOp::Add(params) => {
                let target = cpu.memory[cpu.pc + 3] as usize;
                cpu.memory[target] = self.get_parameter(cpu, 1, params.modes[0])
                    + self.get_parameter(cpu, 2, params.modes[1]);
                cpu.pc += params.size;
            }
            IntCodeOp::Mul(params) => {
                let target = cpu.memory[cpu.pc + 3] as usize;
                cpu.memory[target] = self.get_parameter(cpu, 1, params.modes[0])
                    * self.get_parameter(cpu, 2, params.modes[1]);
                cpu.pc += params.size;
            }
            IntCodeOp::Halt(params) => {
                cpu.running = false;
                cpu.pc += params.size;
            }
        }
    }

That results in working code, and a much simpler CPU implementation:

    pub fn execute(&mut self) {
        let opcode = IntCodeOp::from_opcode(self.memory[self.pc]);
        opcode.execute(self);
    }

Finally, we add a test to validate the little note in the description that negative integers are allowed, so 1101,100,-1,4,0 is a valid program that adds 100 and -1 and stores it into position 4.

    #[test]
    fn test_intcode_add_negative() {
        let mut cpu = IntCodeCPU::new(vec![1101,100,-1,4,0]);
        assert_eq!(cpu.memory[4], 0);
        cpu.execute();
        assert_eq!(cpu.pc, 4);
        assert_eq!(cpu.memory[4], 99);
    }

This fails to compile for me because I've used the u32, which is unsigned through, whereas what I really need is i32, the signed integer. That should be mostly just a find/replace fix.

So actual Day 5?

All of that was in preparation for creating two new opcodes that handle IO. They are only 2 ints wide, but they need to interact with some external peripherals to the CPU.

It's going to read in a program, and it will consume a single input integer, it will then output a stream of output integers, and they should be a series of 0's followed by a diagnostic code.

This is tricky to debug as there aren't any tests provided, so you just have to run the actual intcode provided and then somehow debug the actual intcode machine.

But first, internally, we're going to model the input and output as vectors. In this case, there's only one input, but for the sake of mirroring, I like the idea of a vector of inputs. We'll append to the mutable output vector everytime the Output operation is called. We'll store the input and output vectors in the CPU.

We'll start with simple operation tests, check that input copies the value from IO into memory and output does the opposite. Because we moved the opcodes out, this is a simple update to the match statement to add some new commands and we're off.

    IntCodeOp::Input(params) => {
        let target = cpu.memory[cpu.pc + 1] as usize;
        if cpu.input.is_empty() {
            panic!("No input available for IntCode Input operation");
        }
        let input_value = cpu.input.remove(0);
        cpu.memory[target] = input_value;
        cpu.pc += params.size;
    }
    IntCodeOp::Output(params) => {
        let target = cpu.memory[cpu.pc + 1];
        cpu.output.push(cpu.memory[target as usize]);
        cpu.pc += params.size;
    }

We're also going to write our own tests to make sure it works, so we'll set our input to a known value, say 3, run an intcode program that inputs and loads into a specific memory location, then does an add, and then outputs the result and then halts. We can start to use the run function for these as well. My intcode program is therefore 3,9,101,9,5,10,4,10,99,0,0, that's INPUT 9, ADD [9] 5 -> 10, OUTPUT 10, HALT. We expect this to take the input, add 5 to it, and output the result.

        let mut cpu = IntCodeCPU::new_with_IO(vec![3,9,101,9,5,10,4,10,99,0,0], vec![52]);
        assert_eq!(cpu.output, vec![]);
        cpu.run();
        assert_eq!(cpu.memory, vec![3,9,101,9,5,10,4,10,99, 52,57]);
        assert_eq!(cpu.output, vec![57]);

I get an odd result with that, instead of getting 57 out, I get 19. I suspect this means instead of adding position 9 to immediate value 5, we've added position 5 to immediete value 9. Is that my intcode that's wrong, or my implementation?

I'm going to add some tests to handle combinations of add, mul, immediete and position arguments and verify they all work.

    for (expected, program) in &[
        (30,  vec![   1,5,6,4,0,10,20]),
        (25,  vec![ 101,5,6,4,0,10,20]),
        (16,  vec![1001,5,6,4,0,10,20]),
        (11,  vec![1101,5,6,4,0,10,20]),
        (200, vec![   2,5,6,4,0,10,20]),
        (100, vec![ 102,5,6,4,0,10,20]),
        (60,  vec![1002,5,6,4,0,10,20]),
        (30,  vec![1102,5,6,4,0,10,20]),
    ] {
        let mut cpu = IntCodeCPU::new(program.clone());
        cpu.execute();
        assert_eq!(cpu.memory[4], *expected);
    }

That all works, so it looks like it's my intcode that's wrong. Which on further inspection it is, 101 says the value of param1 and the location of param2, not the other way around. I want 1001. Doing that, fixes the problem, and we're good to try the real data.

That partially worked, I got the right result, but got an error 3 instead of a 0 in one of the numbers. Adding some breakpoints and manually debugging, I realised that the error is where we try to do the output, and the output instruction instead of being 3, is 103, indicating that the value should be immediete mode, not position mode! I forgot to implement the immedite and position mode for the input and output instructions. We'll add a test and then fix it.

And we're done with part 1.