day15.rs

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)]
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 main() {
    let program_file = "prog".to_string();
    let program: Vec<i64> = load_program(&program_file);
    let mut machine = Machine {
        prog_ptr: 0,
        relative_base: 0,
        program: program.clone(),
        input: vec!(),
        output: vec!(),
        state: MachineState::ReadyToRun
    };

    // direction indicates back track to start position)
    let mut exploration: HashMap<(i64, i64), (Tile, Direction)> = HashMap::new();
    let mut current_position = (0, 0);
    let mut current_direction = Direction::North;
    let mut backtracking = false;

    exploration.insert(current_position, (Tile::Empty, Direction::South));
    loop {
        match machine.state {
            MachineState::Terminated => break,
            MachineState::OutputAvailable => {
                current_position = update_exploration(machine.output.remove(0), current_position, current_direction, backtracking, &mut exploration)
            },
            MachineState::WaitingForInput => {
                if let Some((c, b)) = select_direction(current_position, &exploration) {
                    current_direction = c;
                    backtracking = b;
                    machine.input.push(current_direction as i64)
                } else {
                    if current_position != (0, 0) {
                        panic!("Exploration terminated unexpectedly.")
                    }
                    break
                }
            },
            MachineState::ReadyToRun => {},
        }
        machine.resume()
    }
    paint_exploration(current_position, &exploration);
    let mut n_rounds = 0;
    loop {
         if !flood_area(&mut exploration) {
             break;
         }
        n_rounds += 1;
    }
    paint_exploration(current_position, &exploration);
    println!("Number of rounds to flood entire area: {}", n_rounds);
}

fn flood_area(exploration: &mut HashMap<(i64, i64), (Tile, Direction)>) -> bool {
    let keys: Vec<(i64, i64)> = exploration.iter().filter(|(_, v)| v.0 == Tile::Oxygen).map(|(k, _)| k.clone()).collect();
    let mut flooded = false;
    for k in keys {
        if let Some(v) = exploration.get(&k) {
            if v.0 == Tile::Oxygen {
                flooded =  flood_neighbours(k, exploration)|| flooded
            }
        }
    }
    flooded
}

fn flood_neighbours(pos: (i64, i64), exploration: &mut HashMap<(i64, i64), (Tile, Direction)>) -> bool {
    let (x, y) = pos;
    let f1 = flood_position((x, y - 1), exploration);
    let f2 = flood_position((x, y + 1), exploration); 
    let f3 = flood_position((x + 1, y), exploration); 
    let f4 =flood_position((x - 1, y), exploration);
    f1 || f2 || f3 || f4
}

fn flood_position(pos: (i64, i64), exploration: &mut HashMap<(i64, i64), (Tile, Direction)>) -> bool {
    if let Some(value_at_pos) = exploration.get(&pos) {
        if value_at_pos.0 == Tile::Empty {
            exploration.insert(pos, (Tile::Oxygen, value_at_pos.1));
            true
        } else {
            false
        }    
    } else {
        false
    }
}

fn update_exploration(c: i64, current_position: (i64, i64), current_direction: Direction, backtracking: bool, exploration: &mut HashMap<(i64, i64), (Tile, Direction)>) -> (i64, i64) {
    let (cx, cy) = current_position;
    let backtrack_direction = reverse(current_direction);
    let attempted_position = {
        match current_direction {
            Direction::North => (cx, cy - 1),
            Direction::South => (cx, cy + 1),
            Direction::East => (cx + 1, cy),
            Direction::West => (cx - 1, cy)
        }
    };
    if backtracking {
        attempted_position
    } else {
        match c {
            // Wall hit
            0 => {
                exploration.insert(attempted_position, (Tile::Wall, backtrack_direction));
                current_position
            },
            // Moved
            1 => {
                exploration.insert(attempted_position, (Tile::Empty, backtrack_direction));
                attempted_position
            },
            // Moved and oxygen system found
            2 => {
                println!("System found at: {:#?}", attempted_position);
                exploration.insert(attempted_position, (Tile::Oxygen, backtrack_direction));
                attempted_position
            }
            _ => panic!("Unexpected reply from Droid: {}", c)
        }    
    }
}

fn select_direction(current_position: (i64, i64), exploration: &HashMap<(i64, i64), (Tile, Direction)>) -> Option<(Direction, bool)> {
    let (cx, cy) = current_position;
    if exploration.get(&(cx, cy - 1)) == None {
        Some((Direction::North, false))
    } else if exploration.get(&(cx, cy + 1)) == None {
        Some((Direction::South, false))
    } else if exploration.get(&(cx + 1, cy)) == None {
        Some((Direction::East, false))
    } else if exploration.get(&(cx -1, cy)) == None {
        Some((Direction::West, false))
    } else if current_position == (0, 0) {
        // Back to beginning and no more paths to explore
        None
    } else {
        // Dead end, back track
        Some((exploration.get(&current_position).unwrap().1, true))
    }
}

fn paint_exploration(current_position: (i64, i64), area: &HashMap<(i64, i64), (Tile, Direction)>) {
    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));
    for y in min_y..=max_y {
        for x in min_x..=max_x {
            let color_char = if (x, y) == current_position {
                '+'
            } else {
                match area.get(&(x, y)) {
                    Some(tile) => char_for_tile(&tile.0),
                    None => char_for_tile(&Tile::Empty)
                }                    
            };            
            print!("{}", color_char)
        }
        println!();
    }
}

fn char_for_tile(tile: &Tile) -> char {
    match tile {
        Tile::Empty => ' ',
        Tile::Wall => '#',
        Tile::Oxygen => '*'
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
enum Direction {
    North = 1,
    South = 2,
    West = 3,
    East = 4
}

fn reverse(direction: Direction) -> Direction {
    match direction {
        Direction::North => Direction::South,
        Direction::South => Direction::North,
        Direction::East => Direction::West,
        Direction::West => Direction::East
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
enum Tile {
    Empty = 0,
    Wall = 1,
    Oxygen = 2
}