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.

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