Advent of Code 2019 - Day 7

Advent of CodeRust

The problem today was an application of our Intcode interpreter that we wrote on day 5.

Part 1 was very easy to do with my existing design of the Intcode machine but for part 2 I needed to change a few things. First of all I added different ExitCodes. This way I can see if the machine exited because of no avaiable input or because it was halted by opcode 99. The other thing was a small fix in my handling of the output. Previously I returned a copy of the output queue and then took the element from it. This way the original queue was never modified. Now I changed it that a value from the queue is removed and then returned.

Code

use utils::get_permutations;

struct VM {
    memory: Vec<i32>,
    ip: usize,
    input: Vec<i32>,
    output: Vec<i32>,
    exit_code: ExitCode,
}

#[derive(Clone, PartialEq, Debug)]
enum ExitCode {
    Running,
    NeedInput,
    Stop,
}

impl From<&str> for VM {
    fn from(input: &str) -> Self {
        let memory = input
            .trim()
            .split(',')
            .map(|x| x.trim().parse().unwrap())
            .collect();

        VM {
            memory,
            ip: 0,
            input: Vec::new(),
            output: Vec::new(),
            exit_code: ExitCode::Running,
        }
    }
}

impl VM {
    pub fn run(&mut self) -> ExitCode {
        self.set_exit_code(ExitCode::Running);
        loop {
            if !self.run_cycle() {
                return self.get_exit_code();
            }
        }
    }

    fn get_exit_code(&self) -> ExitCode {
        self.exit_code.clone()
    }

    fn set_exit_code(&mut self, exit_code: ExitCode) {
        self.exit_code = exit_code;
    }

    pub fn add_input(&mut self, input: i32) {
        self.input.push(input);
    }

    pub fn get_output(&mut self) -> i32 {
        self.output.remove(0)
    }

    fn get_param(&self, param: usize) -> i32 {
        let opcode = self.memory[self.ip];
        let power = 10i32.pow((param + 1) as u32);
        let parameter_mode = (opcode / power) % 10;

        match parameter_mode {
            0 => self.memory[self.memory[self.ip + param] as usize],
            1 => self.memory[self.ip + param],
            _ => panic!("Unknown parameter mode: {}", parameter_mode),
        }
    }

    fn get_address(&self, position: usize) -> usize {
        self.memory[self.ip + position] as usize
    }

    fn op_add(&mut self) {
        let addr = self.get_address(3);
        self.memory[addr] = self.get_param(1) + self.get_param(2);
        self.ip += 4
    }

    fn op_mul(&mut self) {
        let addr = self.get_address(3);
        self.memory[addr] = self.get_param(1) * self.get_param(2);
        self.ip += 4
    }

    fn op_in(&mut self) {
        if self.input.is_empty() {
            self.exit_code = ExitCode::NeedInput;
            return;
        }

        let addr = self.get_address(1);
        self.memory[addr] = self.input.remove(0);
        self.ip += 2;
    }

    fn op_out(&mut self) {
        self.output.push(self.get_param(1));
        self.ip += 2
    }

    fn op_jnz(&mut self) {
        if self.get_param(1) != 0 {
            self.ip = self.get_param(2) as usize;
        } else {
            self.ip += 3
        }
    }

    fn op_jz(&mut self) {
        if self.get_param(1) == 0 {
            self.ip = self.get_param(2) as usize;
        } else {
            self.ip += 3
        }
    }

    fn op_lt(&mut self) {
        let addr = self.get_address(3);
        if self.get_param(1) < self.get_param(2) {
            self.memory[addr] = 1;
        } else {
            self.memory[addr] = 0;
        }
        self.ip += 4
    }

    fn op_eq(&mut self) {
        let addr = self.get_address(3);
        if self.get_param(1) == self.get_param(2) {
            self.memory[addr] = 1;
        } else {
            self.memory[addr] = 0;
        }
        self.ip += 4
    }

    fn run_cycle(&mut self) -> bool {
        let opcode = self.memory[self.ip] % 100;
        match opcode {
            1 => self.op_add(),
            2 => self.op_mul(),
            3 => self.op_in(),
            4 => self.op_out(),
            5 => self.op_jnz(),
            6 => self.op_jz(),
            7 => self.op_lt(),
            8 => self.op_eq(),
            99 => self.set_exit_code(ExitCode::Stop),
            _ => panic!("Unknown opcode: {}", self.memory[self.ip]),
        }

        if self.exit_code != ExitCode::Running {
            return false;
        }

        true
    }
}

pub fn part_one(input: &str) -> i32 {
    let settings = vec![0, 1, 2, 3, 4];
    let permutations = get_permutations(settings);
    let mut max_signal = 0;
    for permutation in permutations {
        let mut vm_input = 0;
        for setting in permutation.iter() {
            let mut vm = VM::from(input);
            vm.add_input(*setting);
            vm.add_input(vm_input);
            vm.run();
            vm_input = vm.get_output();
        }

        if vm_input > max_signal {
            max_signal = vm_input;
        }
    }

    max_signal
}

pub fn part_two(input: &str) -> i32 {
    let settings = vec![5, 6, 7, 8, 9];
    let permutations = get_permutations(settings);
    let mut max_signal = 0;

    for permutation in permutations {
        let mut vms = Vec::new();
        for setting in permutation.iter() {
            let mut vm = VM::from(input);
            vm.add_input(*setting);
            vms.push(vm);
        }

        let mut index = 0;
        let mut vm_input = 0;
        loop {
            vms[index].add_input(vm_input);
            let exit_code = vms[index].run();

            vm_input = vms[index].get_output();

            if exit_code == ExitCode::Stop && index == 4 {
                max_signal = i32::max(max_signal, vm_input);
                break;
            }

            index = (index + 1) % 5;
        }
    }

    max_signal
}

Benchmarks

2019 - Day 07 - Part 1 time: 7.161998ms
2019 - Day 07 - Part 2 time: 7.797594ms

Feedback or Questions?

I don't have a direct way to leave comments on posts. But if you want to give some feedback or have some questions you can contact in other ways.

©2019–2020 Severin Kaderli