`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 {` ` [` ` 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 {` ` 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>,` ` robot: Position,` ` start: Position,` ` oxygen: Option,` `}` `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(&self, start: Position, is_target: F, unknown_ok: bool) -> Result, usize>` ` where` ` F: Fn(Position) -> bool,` ` {` ` // sad simulation of a "min-priority queue" - but our problem is small enough.` ` let mut border: HashMap = HashMap::new();` ` // for traversing found path in the end` ` let mut known: HashMap> = 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[¤t] {` ` 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::().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` ` }` `}`