summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2018-12-17 13:38:27 +0100
committertomsmeding <tom.smeding@gmail.com>2018-12-17 13:56:47 +0100
commit0d3f096f6e9c01203031f5a2a0ce066bdb61b3be (patch)
treefeb4cc5d32218b0d3dfe69bd7a01910e961712e5 /2018/src
parent0195c76570a61331c72480c0053dadc2f68b08d9 (diff)
Day 17
This was a really fun one! Enjoyed making the simulation that is really a complicated kind of automaton, and enjoyed looking at the automaton doing its thing in the terminal.
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day17.rs288
-rw-r--r--2018/src/main.rs4
2 files changed, 291 insertions, 1 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()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 4bc8d50..21a77df 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -21,8 +21,9 @@ mod day13;
mod day14;
mod day15;
mod day16;
+mod day17;
-static NUM_DAYS: i32 = 16;
+static NUM_DAYS: i32 = 17;
fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
match day {
@@ -42,6 +43,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
14 => day14::main(reader),
15 => day15::main(reader),
16 => day16::main(reader),
+ 17 => day17::main(reader),
_ => Err(Error::new(ErrorKind::Other, "Invalid day"))
}
}