day19.rs

/*
  Brute force solution in Rust. No attempt is made to predict the shape of the
  tractor beam. Instead the beam is scanned for a sufficient distance (1200 steps).
  and then the 100x100 box (supposedly Santa's ship) is fitted into the scan at
  the optimal posistion

  It take about 30 minutes to run this when compiled in release mode.
*/

use std::io::{BufReader, BufRead};
use std::fs::File;
use std::collections::HashMap;


struct Machine {
    prog_ptr: i64,
    relative_base: i64,
    program: Vec<i64>,
    input: Vec<i64>,
    output: Vec<i64>,
    state: MachineState
}

#[derive(PartialEq, Debug)]
enum MachineState {
    ReadyToRun,
    WaitingForInput,
    OutputAvailable,
    Terminated
}

enum InstructionResult {
    Continue,
    WaitForInput,
    OutputDelivered,
    Invalid,
    Exit
}

enum ParameterMode {
    Position = 0,
    Direct = 1,
    Relative= 2
}

impl Machine {
    fn resume(&mut self) {
        loop {
            let a = self.run_one_instruction();
            match a {
                InstructionResult::Continue => { self.state = MachineState::ReadyToRun },
                InstructionResult::WaitForInput => { self.state = MachineState::WaitingForInput; break; },
                InstructionResult::OutputDelivered => { self.state = MachineState::OutputAvailable; break; },
                InstructionResult::Exit => { self.state = MachineState::Terminated; break; },
                _ => panic!("Unexpected action."),
            }
        }    
    }

    fn grow_storage_if_required(&mut self, location: i64) {
        if location >= self.program.len() as i64 {
            self.program.resize((location + 1) as usize, 0)
        }
    }

    fn get(&mut self, location: i64) -> i64 {
        self.grow_storage_if_required(location);
        self.program[location as usize]
    }

    fn put(&mut self, location: i64, value: i64) {
        self.grow_storage_if_required(location);
        self.program[location as usize] = value;
    }

    fn next_cell(&mut self) -> i64 {
        let ind = self.prog_ptr;
        self.prog_ptr += 1;
        self.get(ind)
    }

    fn get_parameter_value(&mut self, mode: i64) -> i64 {
        let value = self.next_cell();
        if mode == ParameterMode::Position as i64 {
            return self.get(value)
        } else if mode == ParameterMode::Direct as i64 {
            return value
        } else if mode == ParameterMode::Relative as i64 {
            return self.get(value + self.relative_base)
        } else {
            panic!("Unknown parameter mode: {}", mode)
        }
    }

    fn get_storage_location(&mut self, mode: i64) -> i64 {
        if mode == ParameterMode::Relative as i64 {
            self.next_cell() + self.relative_base
        } else {
            self.next_cell()
        }
    }

    const ADD: i64 =  1;
    const MULT: i64 =  2;
    const INPUT: i64 = 3;
    const OUTPUT: i64 = 4;
    const JUMP_TRUE: i64 = 5;
    const JUMP_FALSE: i64 = 6;
    const LESS_THAN: i64 = 7;
    const EQUALS: i64 = 8;
    const RELATIVE_BASE_OFFSET: i64 = 9;
    const EXIT: i64 =  99;

    fn run_one_instruction(&mut self) -> InstructionResult {
        let saved_prog_ptr = self.prog_ptr;
        let next_instruction_code = self.next_cell();
        let next_op_code = next_instruction_code % 100;
        let mode_par_1 =  (next_instruction_code / 100) % 10;
        let mode_par_2 = (next_instruction_code / 1000) % 10;
        let mode_par_3 = (next_instruction_code / 10000) % 10;
        match next_op_code {
            Machine::ADD => {
                let t1 = self.get_parameter_value(mode_par_1);
                let t2 = self.get_parameter_value(mode_par_2);
                let store_at = self.get_storage_location(mode_par_3);
                self.put(store_at, t1 + t2);
                InstructionResult::Continue
            },
            Machine::MULT => {
                let f1 = self.get_parameter_value(mode_par_1);
                let f2 = self.get_parameter_value(mode_par_2);
                let store_at = self.get_storage_location(mode_par_3);
                self.put(store_at, f1 * f2);
                InstructionResult::Continue
            },
            Machine::INPUT => {
                if !self.input.is_empty() {
                    let store_at = self.get_storage_location(mode_par_1);
                    let c = self.input.remove(0);
                    self.put(store_at, c);
                    InstructionResult::Continue
                } else {
                    self.prog_ptr = saved_prog_ptr;
                    InstructionResult::WaitForInput
                }
            },
            Machine::JUMP_TRUE => {
                let value = self.get_parameter_value(mode_par_1);
                let jump_target = self.get_parameter_value(mode_par_2);
                if value != 0 {
                    self.prog_ptr = jump_target
                }
                InstructionResult::Continue
            },
            Machine::JUMP_FALSE => {
                let value = self.get_parameter_value(mode_par_1);
                let jump_target = self.get_parameter_value(mode_par_2);
                if value == 0 {
                    self.prog_ptr = jump_target
                }
                InstructionResult::Continue
            },
            Machine::LESS_THAN => {
                let p1 = self.get_parameter_value(mode_par_1);
                let p2 = self.get_parameter_value(mode_par_2);
                let store_at = self.get_storage_location(mode_par_3);
                let result = if p1 < p2 { 1 } else { 0 };
                self.put(store_at, result);
                InstructionResult::Continue
            },
            Machine::EQUALS => {
                let p1 = self.get_parameter_value(mode_par_1);
                let p2 = self.get_parameter_value(mode_par_2);
                let store_at = self.get_storage_location(mode_par_3);
                let result = if p1 == p2 { 1 } else { 0 };
                self.put(store_at, result);
                InstructionResult::Continue
            },
            Machine::OUTPUT => {
                let v = self.get_parameter_value(mode_par_1);
                self.output.push(v);
                InstructionResult::OutputDelivered
            },
            Machine::RELATIVE_BASE_OFFSET => {
                let v = self.get_parameter_value(mode_par_1);
                self.relative_base += v;
                InstructionResult::Continue
            },
            Machine::EXIT => InstructionResult::Exit,
            _ => InstructionResult::Invalid
        }
    }    
}

fn load_program(program_file: &String) -> Vec<i64> {
    let mut prog: Vec<i64> = vec![];
    let file = File::open(program_file).expect("Could not open program file!");
    let reader = BufReader::new(file);

    let line = reader.lines().next().expect("Could not read from file");
    let line = line.expect("No string there.");
    for s in line.split(",") {
        let c = i64::from_str_radix(&s, 10).expect("Could not parse int");
        prog.push(c);
    }
    prog
}

fn part_1(program: &Vec<i64>) -> Vec<Vec<char>> {
    let mut machine = Machine {
        prog_ptr: 0,
        relative_base: 0,
        program: program.clone(),
        input: vec!(),
        output: vec!(),
        state: MachineState::ReadyToRun
    };

    let mut positions_to_check: Vec<(usize, usize)> = vec!();
    let scan_size = 1200;
    for x in 0..scan_size {
        for y in 0..scan_size {
            positions_to_check.push((x, y))
        }
    }
    for pos in positions_to_check.clone() {
        machine.input.push(pos.0 as i64);
        machine.input.push(pos.1 as i64)
    }

    positions_to_check.reverse();

    let mut scan: Vec<Vec<char>> = vec!();
    for _ in 0..scan_size {
        let mut v = Vec::new();
        v.resize(scan_size, ' ');
        scan.push(v)
    }


    loop {
        match machine.state {
            MachineState::Terminated => break,
            MachineState::OutputAvailable => {
                while !machine.output.is_empty() {
                    let code = machine.output.remove(0);
                    let c = if code == 1 {'#'} else {'.'};
                    let (x, y) = positions_to_check.pop().unwrap();
                    scan[y][x] = c;
                }
            },
            MachineState::WaitingForInput => {
                panic!("Unexpected input requested")
            },
            MachineState::ReadyToRun => {},
        }
        if !machine.input.is_empty() {
            machine.state = MachineState::ReadyToRun;
            machine.prog_ptr = 0;
            machine.relative_base = 0;
            machine.program = program.clone();
        }
        machine.resume()
    }
    scan
}

fn main() {
    let program_file = "prog".to_string();
    let program: Vec<i64> = load_program(&program_file);
    let scan = part_1(&program);
    part_2(&scan)
}

fn first_hash(line: &Vec<char>) -> usize {
    for ind in 0..line.len() {
        if line[ind] == '#' {
            return ind
        }
    }
    panic!("No hash found")
}

fn last_hash(line: &Vec<char>) -> usize {
    for ind in (0..line.len()).rev() {
        if line[ind] == '#' {
            return ind
        }
    }
    panic!("No hash found")
}

fn part_2(scan: &Vec<Vec<char>>) {
    for y in 900..scan.len() {
        let line = &scan[y];
        let high_last_hash = last_hash(line);
        let low_line = &scan[y + 99];
        let low_first_hash = first_hash(low_line);
        if low_first_hash == high_last_hash - 99 {
            println!("Solution found at x={} y={} answer={}", low_first_hash, y, low_first_hash*10000 + y);
            break;
        }
    }
}

fn find_dimensions(area: &HashMap<(i64, i64), char>) -> ((i64, i64), (i64, i64)) {
    let min_x = area.keys().fold(0, |acc, k| std::cmp::min(acc, k.0));
    let max_x = area.keys().fold(0, |acc, k| std::cmp::max(acc, k.0));
    let min_y = area.keys().fold(0, |acc, k| std::cmp::min(acc, k.1));
    let max_y = area.keys().fold(0, |acc, k| std::cmp::max(acc, k.1));
    ((min_x, min_y), (max_x, max_y))
}

fn paint_area(area: &HashMap<(i64, i64), char>) {
    let ((min_x, min_y), (max_x, max_y)) = find_dimensions(&area);
    for y in min_y..=max_y {
        for x in min_x..=max_x {
            print!("{}", area.get(&(x, y)).unwrap())
        }
        println!();
    }
}