Private Leaderboard: join 265794-f7a74408 https://adventofcode.com/2019/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

267 lines
6.4 KiB

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
}
}