aoc2019/day15/src/main.rs

use shared::intcode::{IntCode, CELL};
use std::collections::HashMap;

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub enum Cell {
	Unknown,
	Wall,
	Empty,
}

impl Default for Cell {
	fn default() -> Self {
		Self::Unknown
	}
}

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

impl Direction {
	fn all() -> impl Iterator<Item=Self> {
		[
			Self::North,
			Self::South,
			Self::West,
			Self::East,
		].iter().cloned()
	}
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct Position {
	x: usize,
	y: usize,
}

impl Position {
	fn go(self, field: &Field, d: Direction) -> Option<Self> {
		match d {
			Direction::North => {
				if self.y > 0 { return Some(Position { x: self.x, y: self.y - 1}); }
			},
			Direction::South => {
				if self.y + 1 < field.cells.len() { return Some(Position { x: self.x, y: self.y + 1 }); }
			},
			Direction::West => {
				if self.x > 0 { return Some(Position { x: self.x - 1, y: self.y }); }
			},
			Direction::East => {
				if self.x + 1 < field.columns { return Some(Position { x: self.x + 1, y: self.y }); }
			},
		}
		None
	}
}

pub struct Field {
	ic: IntCode,
	columns: usize,
	cells: Vec<Vec<Cell>>,
	robot: Position,
	start: Position,
	oxygen: Option<Position>,
}

impl Field {
	pub fn new(ic: IntCode) -> Self {
		Self {
			ic,
			columns: 3,
			cells: vec![
				vec![Cell::Unknown, Cell::Unknown, Cell::Unknown],
				vec![Cell::Unknown, Cell::Empty, Cell::Unknown],
				vec![Cell::Unknown, Cell::Unknown, Cell::Unknown],
			],
			robot: Position { x: 1, y: 1 },
			start: Position { x: 1, y: 1 },
			oxygen: None,
		}
	}

	fn prepend_row(&mut self) {
		let mut row = Vec::new();
		row.resize(self.columns, Cell::Unknown);
		self.cells.insert(0, row);
		self.robot.y += 1;
		self.start.y += 1;
		if let Some(oxygen) = &mut self.oxygen { oxygen.y += 1; }
	}

	fn append_row(&mut self) {
		let mut row = Vec::new();
		row.resize(self.columns, Cell::Unknown);
		self.cells.push(row);
	}

	fn prepend_col(&mut self) {
		self.columns += 1;
		for row in &mut self.cells {
			row.insert(0, Cell::Unknown);
		}
		self.robot.x += 1;
		self.start.x += 1;
		if let Some(oxygen) = &mut self.oxygen { oxygen.x += 1; }
	}

	fn append_col(&mut self) {
		self.columns += 1;
		for row in &mut self.cells {
			row.push(Cell::Unknown);
		}
	}

	fn set_cell(&mut self, pos: Position, cell: Cell) {
		self.cells[pos.y][pos.x] = cell;
		if pos.y == 0 { self.prepend_row(); }
		if pos.y + 1 == self.cells.len() { self.append_row(); }
		if pos.x == 0 { self.prepend_col(); }
		if pos.x + 1 == self.columns { self.append_col(); }
	}

	fn cell(&self, pos: Position) -> Cell {
		self.cells[pos.y][pos.x]
	}

	// returns whether robot moved (false: hit wall)
	fn robot_walk(&mut self, direction: Direction) -> bool {
		assert!(self.ic.next_input.is_none());
		self.ic.next_input = Some((direction as u8) as CELL);
		let next_pos = self.robot.go(self, direction).expect("invalid direction in current field");
		match self.ic.simulate_step().expect_output() {
			0 => {
				self.set_cell(next_pos, Cell::Wall);
				false
			},
			1 => {
				self.robot = next_pos; // set_cell might update this
				self.set_cell(next_pos, Cell::Empty);
				true
			},
			2 => {
				self.robot = next_pos; // set_cell might update this
				self.set_cell(next_pos, Cell::Empty);
				self.oxygen = Some(self.robot);
				true
			},
			_ => panic!("Invalid IC output"),
		}
	}

	// if it can't find a path, return maximum pathlen for shortest path to a reachable cell
	fn find_path<F>(&self, start: Position, is_target: F, unknown_ok: bool) -> Result<Vec<Direction>, usize>
	where
		F: Fn(Position) -> bool,
	{
		// sad simulation of a "min-priority queue" - but our problem is small enough.
		let mut border: HashMap<Position, usize> = HashMap::new();
		// for traversing found path in the end
		let mut known: HashMap<Position, Option<(Position, Direction)>> = HashMap::new();
		let mut max_path_len = 0;
		if is_target(start) { return Ok(vec![]); }
		known.insert(start, None);
		border.insert(start, 0);
		let target;
		'outer: loop {
			if border.is_empty() { return Err(max_path_len); }
			let source = *border.iter().min_by_key(|(_k, v)| *v).unwrap().0;
			let next_pathlen = border.remove(&source).unwrap() + 1;
			for d in Direction::all() {
				if let Some(next) = source.go(self, d) {
					if known.contains_key(&next) { continue; }
					match self.cell(next) {
						Cell::Wall => continue,
						Cell::Unknown => if !unknown_ok { continue; },
						Cell::Empty => (),
					}
					known.insert(next, Some((source, d)));
					if is_target(next) { target = next; break 'outer; }
					border.insert(next, next_pathlen);
					max_path_len = max_path_len.max(next_pathlen);
				}
			}
		}

		let mut path = Vec::new();
		let mut current = target;
		loop {
			let (previous, d) = match &known[&current] {
				Some((p, d)) => (*p, *d),
				None => break,
			};
			path.push(d);
			current = previous;
		}
		path.reverse();
		Ok(path)
	}

	fn draw(&self) {
		for (y, row) in self.cells.iter().enumerate() {
			for (x, cell) in row.iter().enumerate() {
				let pos = Position { x, y };
				if Some(pos) == self.oxygen {
					print!("O");
				} else if pos == self.robot {
					print!("D");
				} else if pos == self.start {
					print!("X");
				} else {
					match cell {
						Cell::Unknown => print!("⋅"),
						Cell::Wall => print!("#"),
						Cell::Empty => print!(" "),
					}
				}
			}
			println!("");
		}
		println!("-");
	}

	pub fn find_oxygen(&mut self) -> usize {
		let mut path = Vec::new();
		loop {
			// if self.oxygen.is_some() { break; }
			if path.is_empty() {
				path = match self.find_path(self.robot, |pos| {
					self.cell(pos) == Cell::Unknown
				}, true) {
					Ok(path) => path,
					Err(_) => break,
				};
			}
			let d = path.remove(0);
			if !self.robot_walk(d) { path.clear(); } // need new path when hitting a wall
			self.draw();
		}
		self.find_path(self.start, |pos| Some(pos) == self.oxygen, false).expect("no path to oxygen system").len()
	}
}

fn main() {
	let ic = include_str!("input.txt").parse::<IntCode>().unwrap();
	let mut field = Field::new(ic);
	field.draw();
	println!("Oxygen sytsem is {} moves away", field.find_oxygen());
	println!("Oxygen distributed after {} minutes", field.find_path(field.oxygen.unwrap(), |_| false, false).unwrap_err());
}

#[cfg(test)]
mod day15test {
	#[test]
	fn examples1() {
		// no runnable tests
	}

	#[test]
	fn examples2() {
		// no runnable tests
	}
}