From 9ab2a7320f7d1eeee9a42198c2cb1667612a62d1 Mon Sep 17 00:00:00 2001 From: cos Date: Wed, 11 Dec 2019 19:40:45 +0100 Subject: Add day11, 2019 --- 2019/rust/Cargo.toml | 1 + 2019/rust/day11/both_parts.sh | 3 + 2019/rust/day11/src/main.rs | 410 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 414 insertions(+) create mode 100755 2019/rust/day11/both_parts.sh create mode 100644 2019/rust/day11/src/main.rs diff --git a/2019/rust/Cargo.toml b/2019/rust/Cargo.toml index 0f57bd0..20977c7 100644 --- a/2019/rust/Cargo.toml +++ b/2019/rust/Cargo.toml @@ -10,4 +10,5 @@ members = [ "day08", "day09", "day10", + "day11", ] diff --git a/2019/rust/day11/both_parts.sh b/2019/rust/day11/both_parts.sh new file mode 100755 index 0000000..c9ed7ef --- /dev/null +++ b/2019/rust/day11/both_parts.sh @@ -0,0 +1,3 @@ +../target/release/day11 --program input +../target/release/day11 --program input --use-emergency-panel + diff --git a/2019/rust/day11/src/main.rs b/2019/rust/day11/src/main.rs new file mode 100644 index 0000000..6add91a --- /dev/null +++ b/2019/rust/day11/src/main.rs @@ -0,0 +1,410 @@ +use std::env; +use std::io::{BufRead, BufReader}; +use std::fs::File; +use std::sync::mpsc::{channel, Receiver, Sender}; +use std::thread; +use std::collections::{HashMap}; + +type BusWidth = i128; +type IOType = i128; + +fn read_program(filename: &str) -> Vec { + let f = File::open(filename).expect(filename); + let f = BufReader::new(f); + + f.lines() + .filter(|line| match line { + Ok(s) => { + let b = s.as_bytes(); + if b.len() == 0 || b.len() > 0 && b[0] == b'#' { false } else { true } + }, + _ => true, + }) + .map(|line| match line { + Ok(line) => { + let data:Vec = line.split(',').map(|e| { e.trim_start().trim_end() }) + .filter(|v| match v.parse::() { Ok(_) => true, _ => { + eprintln!("Could not parse: {:?}", v); + false + }, + }) + .map(|r| r.parse().unwrap()) + .collect(); + + data + }, + Err(_) => panic!("Could not parse {}.", filename), + }).flatten().collect() +} + +#[derive(Clone, Debug)] +struct Memory { + mem: Vec, +} + +impl Memory { + fn new() -> Memory { + Memory { mem: Vec::new(), } + } + + fn init(&mut self, mem:Vec) { + self.mem = mem; + } + + fn read(&self, address: usize) -> BusWidth { + match self.mem.get(address) { + Some(value) => *value, + None => 0, + } + } + + fn write(&mut self, address: usize, value: BusWidth) { + if self.len() < address { + self.mem.resize(address*2, 0); + } + self.mem[address] = value; + } + + fn len(&self) -> usize { + self.mem.len() + } +} + +#[derive(Debug)] +struct Registers { + ip: usize, + base: usize, +} + +#[derive(Debug)] +enum Arithm { + Add, + Mul, + LessThan, + Equals, +} + +#[derive(Debug)] +enum IO { + In, + Out, +} + +#[derive(Debug)] +enum Jmp { + JmpTrue, + JmpFalse, +} + +#[derive(Debug)] +enum RegOp { + BaseMod, +} + +#[derive(Debug, PartialEq)] +enum ParameterMode { + Position, + Immediate, + Relative, +} + +#[derive(Debug, PartialEq)] +enum DataDirection { + Read, + Write, +} + +struct Intcode { + r: Registers, + sender: Sender, + receiver: Receiver, +} + +struct Robot { + canvas: HashMap<(isize, isize), u8>, + sender: Sender, + receiver: Receiver, +} + +enum Direction { + Up, + Down, + Left, + Right, +} + +impl Robot { + fn new(sender: Sender, receiver: Receiver) -> Robot { + Robot { + canvas: HashMap::new(), + sender, + receiver, + } + } + + fn run(&mut self) -> usize { + let mut x = 0; + let mut y = 0; + let mut direction = Direction::Up; + let mut painted = 0; + + loop { + match self.sender.send(match self.canvas.get(&(x, y)) { Some(1) => 1, _ => 0, }) { + Ok(_) => {}, _ => break, + } + let (brush, turn) = match self.receiver.iter().zip(self. receiver.iter()).next() { + Some((b, t)) => (b as u8, t), _ => break, + }; + + match self.canvas.insert((x, y), brush as u8) { + None => painted += 1, + _ => {}, + } + + self.propulse(turn, &mut x, &mut y, &mut direction); + } + + painted + } + + fn place_emergency_panel(&mut self) { + self.canvas.insert((0, 0), 1); + } + + fn propulse(&self, turn: IOType, x: &mut isize, y: &mut isize, direction: &mut Direction) { + *direction = if turn == 0 { + match direction { + Direction::Up => Direction::Left, + Direction::Left => Direction::Down, + Direction::Down => Direction::Right, + Direction::Right => Direction::Up, + } + } else if turn == 1 { + match direction { + Direction::Up => Direction::Right, + Direction::Right => Direction::Down, + Direction::Down => Direction::Left, + Direction::Left => Direction::Up, + } + } else { + panic!("Invalid turn instruction: {}", turn); + }; + + match direction { + Direction::Up => *y -= 1, + Direction::Right => *x += 1, + Direction::Down => *y += 1, + Direction::Left => *x -= 1, + } + } + + fn show_painted_panels(&self) { + let boundary_msg = &"Could not determine plot boundary"; + + let min_x = *self.canvas.keys().map(|(x, _)| x).min().expect(boundary_msg); + let max_x = *self.canvas.keys().map(|(x, _)| x).max().expect(boundary_msg); + let min_y = *self.canvas.keys().map(|(_, y)| y).min().expect(boundary_msg); + let max_y = *self.canvas.keys().map(|(_, y)| y).max().expect(boundary_msg); + for y in min_y..=max_y { + for x in min_x..=max_x { + print!("{}", match self.canvas.get(&(x, y)) { + Some(1) => "██", + _ => " ", + }); + } + println!(""); + } + println!(""); + } +} + +impl Intcode { + fn new(sender: Sender, receiver: Receiver) -> Intcode { + Intcode { + r: Registers { ip: 0, base: 0, }, + sender, + receiver, + } + } + + fn param_to_argument(&self, mode: &ParameterMode, mem: &Memory, offset: usize, + dir: &DataDirection) -> usize + { + match mode { + ParameterMode::Position => { + if mem.read(offset) < 0 { + panic!("Attempt to address negative memory at IP: {}"); + } + mem.read(offset) as usize + }, + ParameterMode::Immediate => { + if *dir == DataDirection::Write { + panic!("Immediate parameter mode at IP: {}", self.r.ip); + } + offset + }, + ParameterMode::Relative => { + if (mem.read(offset) + self.r.base as BusWidth) < 0 { + panic!("Attempt to address negative memory at IP: {}"); + } + (mem.read(offset) + self.r.base as BusWidth) as usize + }, + } + } + + fn arithm(&self, op: Arithm, modes: Vec, memory: &mut Memory) { + let parameter_directions = + [DataDirection::Read, DataDirection::Read, DataDirection::Write]; + let params:Vec = (0..parameter_directions.len()) + .zip(parameter_directions.iter()) + .map(|(p, d)| { + self.param_to_argument(&modes[p], memory, self.r.ip + 1 + p, d) + }).collect(); + let left = params[0]; + let right = params[1]; + let result = params[2]; + + match op { + Arithm::Add => memory.write(result, memory.read(left) + memory.read(right)), + Arithm::Mul => memory.write(result, memory.read(left) * memory.read(right)), + Arithm::LessThan => memory.write(result, if memory.read(left) < memory.read(right) { + 1 } else { 0 }), + Arithm::Equals => memory.write(result, if memory.read(left) == memory.read(right) { + 1 } else { 0 }), + } + } + + fn jmp(&mut self, op: Jmp, modes: Vec, memory: &mut Memory) + { + let parameter_directions = [DataDirection::Read, DataDirection::Read]; + let params:Vec = (0..parameter_directions.len()) + .zip(parameter_directions.iter()) + .map(|(p, d)| { + self.param_to_argument(&modes[p], memory, self.r.ip + 1 + p, d) + }).collect(); + let value = params[0]; + let address = params[1]; + + self.r.ip = match op { + Jmp::JmpTrue => (if memory.read(value) != 0 { + memory.read(address) as usize } else { self.r.ip + 3 }), + Jmp::JmpFalse => (if memory.read(value) == 0 { + memory.read(address) as usize } else { self.r.ip + 3 }), + }; + + } + + fn regop(&mut self, op: RegOp, modes: Vec, memory: &mut Memory) + { + let parameter_directions = [DataDirection::Read]; + let params:Vec = (0..parameter_directions.len()) + .zip(parameter_directions.iter()) + .map(|(p, d)| { + self.param_to_argument(&modes[p], memory, self.r.ip + 1 + p, d) + }).collect(); + let value = memory.read(params[0]); + + match op { + RegOp::BaseMod => { + if value < 0 { + self.r.base -= (-1 * value) as usize; + } else { + self.r.base += value as usize; + } + }, + }; + } + + fn io_in(&mut self, _op: IO, modes: Vec, memory:&mut Memory) + { + let parameter_directions = [DataDirection::Write]; + let params:Vec = (0..parameter_directions.len()) + .zip(parameter_directions.iter()) + .map(|(p, d)| { + self.param_to_argument(&modes[p], memory, self.r.ip + 1 + p, d) + }).collect(); + let address = params[0]; + + let value = self.receiver.recv(); + match value { + Ok(v) => memory.write(address, v), + _ => panic!("Could not receive input. Remote disappeared."), + } + } + + fn io_out(&mut self, _op: IO, modes: Vec, memory:&mut Memory ) + { + let parameter_directions = [DataDirection::Read]; + let params:Vec = (0..parameter_directions.len()) + .zip(parameter_directions.iter()) + .map(|(p, d)| { + self.param_to_argument(&modes[p], memory, self.r.ip + 1 + p, d) + }).collect(); + let address = params[0]; + + let o = memory.read(address); +// println!("{}", o); + self.sender.send(o as IOType).expect("Communication error. Nothing connected to CPU?"); + } + + fn intcode(&mut self, mut memory: Memory) + { + while self.r.ip < memory.len() { + let op = memory.read(self.r.ip) % 100; + let modes:Vec = (2..=4) + .map(|e| memory.read(self.r.ip) / 10i32.pow(e) as BusWidth % 10) + .map(|n| match n { + 0 => ParameterMode::Position, + 1 => ParameterMode::Immediate, + 2 => ParameterMode::Relative, + p => panic!("Invalid parameter mode {} at IP: {}", p, self.r.ip), + }).collect(); + + match op { + 1 => { self.arithm(Arithm::Add, modes, &mut memory); self.r.ip += 4 }, + 2 => { self.arithm(Arithm::Mul, modes, &mut memory); self.r.ip += 4 }, + 7 => { self.arithm(Arithm::LessThan, modes, &mut memory); self.r.ip += 4 }, + 8 => { self.arithm(Arithm::Equals, modes, &mut memory); self.r.ip += 4 }, + 3 => { self.io_in( IO::In, modes, &mut memory); self.r.ip += 2 }, + 4 => { self.io_out(IO::Out, modes, &mut memory); self.r.ip += 2 }, + 5 => { self.jmp( Jmp::JmpTrue, modes, &mut memory); }, + 6 => { self.jmp( Jmp::JmpFalse, modes, &mut memory); }, + 9 => { self.regop(RegOp::BaseMod, modes, &mut memory); self.r.ip += 2}, + 99 => break, + op => panic!("Invalid operation {} at IP: {}", op, self.r.ip), + } + } + } +} + +fn main() { + let args: Vec = env::args().collect(); + + let mut opts = getopts::Options::new(); + opts.optflag("e", "use-emergency-panel", "Place white panel at (0,0)"); + opts.reqopt("p", "program", "File to load program from", "FILE"); + let matches = match opts.parse(&args[1..]) { + Ok(m) => { m } + Err(f) => { panic!(f.to_string()) } + }; + let program: String = matches.opt_str("program").unwrap(); + let mut memory = Memory::new(); + memory.init(read_program(&program)); + let ( to_cpu, from_robot ): (Sender, Receiver) = channel(); + let ( to_robot, from_cpu ): (Sender, Receiver) = channel(); + let mut cpu = Intcode::new(to_cpu, from_cpu); + let mut robot = Robot::new(to_robot, from_robot); + if matches.opt_present("use-emergency-panel") { + robot.place_emergency_panel(); + } + + let cpu_handler = thread::spawn(move || cpu.intcode(memory.clone())); + let robot_handler = thread::spawn(move || { + let n = robot.run(); + robot.show_painted_panels(); + n + }); + + cpu_handler.join().expect("Problem with cpu thread."); + println!("Panes painted: {:?}", robot_handler.join().unwrap()); +} -- cgit v1.2.3