diff options
Diffstat (limited to '2018/src/day17.rs')
| -rw-r--r-- | 2018/src/day17.rs | 288 |
1 files changed, 288 insertions, 0 deletions
diff --git a/2018/src/day17.rs b/2018/src/day17.rs new file mode 100644 index 0000000..3730e60 --- /dev/null +++ b/2018/src/day17.rs @@ -0,0 +1,288 @@ +use std::io; +use std::io::BufRead; +use std::collections::{VecDeque, BinaryHeap, HashSet}; +use std::cmp; +use std::iter::{self, Iterator}; +use std::{thread, time}; + +enum Clay { + Horizontal(i32, i32, i32), // y, x1, x2 + Vertical(i32, i32, i32), // x, y1, y2 +} + +impl Clay { + fn gety<F: Fn(i32, i32) -> i32>(&self, func: &F) -> i32 { + match self { + &Clay::Horizontal(y, _, _) => y, + &Clay::Vertical(_, y1, y2) => func(y1, y2), + } + } + + fn getx<F: Fn(i32, i32) -> i32>(&self, func: &F) -> i32 { + match self { + &Clay::Horizontal(_, x1, x2) => func(x1, x2), + &Clay::Vertical(x, _, _) => x, + } + } +} + +#[derive(Copy, Clone, PartialEq, Eq)] +enum Cell { + Sand, + Clay, + Still, + Flow, + Source, +} + +impl Cell { + fn produces(&self) -> bool { + match self { + Cell::Flow => true, + Cell::Source => true, + _ => false, + } + } + + fn is_wall(&self) -> bool { + match self { + Cell::Clay => true, + Cell::Still => true, + _ => false, + } + } + + fn is_water(&self) -> bool { + match self { + Cell::Still => true, + Cell::Flow => true, + Cell::Source => true, + _ => false, + } + } + + fn print(&self) { + print!("{}", match self { + Cell::Sand => '.', + Cell::Clay => '#', + Cell::Still => '~', + Cell::Flow => '|', + Cell::Source => '+', + }); + } +} + +struct Grid { + miny: i32, minx: i32, + data: Vec<Vec<Cell>>, +} + +impl Grid { + fn new(minx: i32, maxx: i32, miny: i32, maxy: i32) -> Self { + assert!(minx <= 500 && 500 <= maxx); + assert!(miny <= 0 && 0 <= maxy); + let data = iter::repeat(vec![Cell::Sand; (maxx - minx + 1) as usize]).take((maxy - miny + 1) as usize).collect::<Vec<_>>(); + Self { miny, minx, data } + } + + fn inrange(&self, x: i32, y: i32) -> bool { + self.minx <= x && x < self.minx + self.data[0].len() as i32 + && self.miny <= y && y < self.miny + self.data.len() as i32 + } + + fn get(&self, x: i32, y: i32) -> Cell { + if self.inrange(x, y) { + self.data[(y - self.miny) as usize][(x - self.minx) as usize] + } else { + Cell::Sand + } + } + + fn set(&mut self, x: i32, y: i32, value: Cell) { + if self.inrange(x, y) { + self.data[(y - self.miny) as usize][(x - self.minx) as usize] = value; + } + } + + fn print(&self) { + for y in 0..self.data.len() { + for x in 0..self.data[0].len() { + self.data[y][x].print(); + } + println!(""); + } + } + + fn print_range(&self, y1: i32, y2: i32, hlx: i32, hly: i32) { + for y in 0..self.data.len() { + if self.miny + (y as i32) < y1 { + continue; + } + if self.miny + y as i32 >= y2 { + break; + } + for x in 0..self.data[0].len() { + if self.minx + x as i32 == hlx && self.miny + y as i32 == hly { + print!("\x1B[45m"); + } + self.data[y][x].print(); + if self.minx + x as i32 == hlx && self.miny + y as i32 == hly { + print!("\x1B[0m"); + } + } + println!(""); + } + } +} + +fn parse(line: &str) -> Clay { + let comma = line.find(',').unwrap(); + let dot = line[comma+4..].find('.').unwrap() + comma + 4; + let num1 = line[2..comma].parse().unwrap(); + let num2 = line[comma+4..dot].parse().unwrap(); + let num3 = line[dot+2..].parse().unwrap(); + if &line[..1] == "x" { + Clay::Vertical(num1, num2, num3) + } else { + Clay::Horizontal(num1, num2, num3) + } +} + +fn apply_patterns(grid: &mut Grid, (x, y): (i32, i32)) -> Vec<(i32, i32)> { + let mut res = Vec::new(); + + // P -> P + // . | + if grid.get(x, y).produces() && grid.get(x, y+1) == Cell::Sand { + grid.set(x, y+1, Cell::Flow); + res.push((x, y+1)); + } + + if grid.get(x, y).produces() && grid.get(x, y+1).is_wall() { + // P. -> P| + // W W + if grid.get(x+1, y) == Cell::Sand { + grid.set(x+1, y, Cell::Flow); + res.push((x+1, y)); + } + // .P -> |P + // W W + if grid.get(x-1, y) == Cell::Sand { + grid.set(x-1, y, Cell::Flow); + res.push((x-1, y)); + } + } + + for dx in &[-1, 1] { + // WP···PW -> W~···~W + // W···W W···W + if grid.get(x, y).produces() && grid.get(x, y+1).is_wall() && grid.get(x-dx, y).is_wall() { + let mut x2 = x + dx; + let make_still; + + loop { + if grid.get(x2, y).is_wall() { + make_still = true; + break; + } + + if !(grid.get(x2, y).produces() && grid.get(x2, y+1).is_wall()) { + make_still = false; + break; + } + + x2 += dx; + } + + if make_still { + x2 = x; + while !grid.get(x2, y).is_wall() { + grid.set(x2, y, Cell::Still); + res.push((x2, y-1)); + x2 += dx; + } + } + } + } + + res +} + +pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { + let input = reader.lines().map(|l| parse(&l.unwrap())).collect::<Vec<_>>(); + + let miny = input.iter().map(|c| c.gety(&cmp::min)).min().unwrap(); + let maxy = input.iter().map(|c| c.gety(&cmp::max)).max().unwrap(); + let minx = input.iter().map(|c| c.getx(&cmp::min)).min().unwrap(); + let maxx = input.iter().map(|c| c.getx(&cmp::max)).max().unwrap(); + + let mut grid = Grid::new(minx - 1, maxx + 1, cmp::min(miny, 0), maxy); + + grid.set(500, 0, Cell::Source); + + for clay in input { + match clay { + Clay::Horizontal(y, x1, x2) => { + for x in x1..x2+1 { + grid.set(x, y, Cell::Clay); + } + } + Clay::Vertical(x, y1, y2) => { + for y in y1..y2+1 { + grid.set(x, y, Cell::Clay); + } + } + } + } + + let mut queue = BinaryHeap::new(); + queue.push((0, 500)); + // let mut queue = VecDeque::new(); + // queue.push_back((500, 0)); + + let mut inqueue = HashSet::new(); + inqueue.insert((500, 0)); + + // grid.print(); + + while queue.len() > 0 { + let (my, x) = queue.pop().unwrap(); + inqueue.remove(&(my, x)); + let pos = (x, -my); + // let (x, y) = queue.pop_back().unwrap(); + // inqueue.remove(&(x, y)); + // let pos = (x, y); + + for &(x, y) in apply_patterns(&mut grid, pos).iter().filter(|&&(x, y)| grid.inrange(x, y)) { + let p = (-y, x); + // let p = (x, y); + if !inqueue.contains(&p) { + queue.push(p); + // queue.push_back(p); + inqueue.insert(p); + } + } + + // println!("\x1B[H\x1B[2J"); + // grid.print_range(pos.1 - 10, pos.1 + 10, pos.0, pos.1); + // thread::sleep(time::Duration::from_millis(50)); + // let mut line = String::new(); + // io::stdin().read_line(&mut line)?; + } + + let part1 = + (miny..maxy+1).map(|y| + (minx-1..maxx+2).map(|x| + grid.get(x, y).is_water() as i32 + ).sum::<i32>() + ).sum::<i32>(); + + let part2 = + (miny..maxy+1).map(|y| + (minx-1..maxx+2).map(|x| + (grid.get(x, y) == Cell::Still) as i32 + ).sum::<i32>() + ).sum::<i32>(); + + Ok((part1.to_string(), part2.to_string())) +} |