Day 11

6 files changed, 300 insertions, 0 deletions

diff --git a/11/Cargo.toml b/11/Cargo.toml
new file mode 100644
index 0000000..b828620
--- /dev/null
+++ b/11/Cargo.toml
@@ -0,0 +1,14 @@
+[package]
+name = "day-11"
+version = "0.1.0"
+edition = "2021"
+
+[[bin]]
+name = "part-1"
+path = "src/part-1.rs"
+
+[[bin]]
+name = "part-2"
+path = "src/part-2.rs"
+
+[dependencies]
diff --git a/11/input.txt b/11/input.txt
new file mode 100644
index 0000000..bf6403e
--- /dev/null
+++ b/11/input.txt
@@ -0,0 +1,140 @@
+........#..........................#...............#.....#..................................#..........................#....................
+..............................................................................#.........................................................#...
+............#..............................#....................#.........................................#.................................
+................................#...........................................................................................................
+....................................................................................................#........................#..............
+..................#.....#.............................#..............................................................#......................
+.....................................#..............................#......#....................#.......#...................................
+...................................................................................#................................................#.......
+.......#.....................#..................................#.............................................#.............................
+..........................................................#............................#....................................................
+#............................................#.....#.......................................................................#................
+..................................#...........................................#.................................................#.........#.
+........................#........................................................................#..........................................
+....#.........#..........................................................................#..........................#.......................
+..............................#...........#......................#..........................................................................
+..................#.................#.......................................................................................................
+...........#................................................................................................................................
+......................................................#...................#...................#...................................#........#
+............................#...............#...............................................................................................
+....#................................................................................................#...............#........#.............
+.....................................#...........#...........#...............#..........#..............................................#....
+..............#......................................................#......................................#............#..................
+.........#.....................................................................................#............................................
+........................................................................................................#...................................
+............................................................................................................................................
+...#...........................................#..........................#.................................................................
+.................................................................................................#..........................................
+.............................#........................................................#....................#........#...........#...........
+............#......#.....................#.........#................#.......................................................................
+......................................................................................................#..................................#..
+..............................................................#.............................................................................
+.#........................#..............................................................#..................................................
+.........#.........................................................................#...............#...............#...............#........
+..................................#......................................#..................................................................
+............................................#............#.......#.............................#............................................
+............................#.......................#..........................................................#.......#.......#..........#.
+.....#..................................................................................#...................................................
+.................#.....................................................#..............................#.....................................
+.........................................#.....#............#......................................................................#........
+..........................................................................................................#.................................
+.................................................................#.............#............................................................
+.......................#.....#......................#......................................................................#................
+.#...........#.........................#.....................................................#.........#.........................#..........
+..................................................................................#..............................#..........................
+.......#...................................................................#................................................................
+................#..............#......................................................#...........#.....................#.............#.....
+.........................#...................#.............................................................#...............................#
+............................................................................................................................................
+........................................#.....................................................................................#.............
+....................#...............................................#........#........................#.....................................
+......#....................#................................#...............................#.....................#.........................
+.#..........................................................................................................................................
+............................................................................................................................................
+................#.............#...........#..........#............#....................................................#........#.....#.....
+.....................................#...................................................#........#...........#.............................
+....................#.........................................#............#................................................................
+#.................................................#..................................#.....................................#................
+............................................#................................................#.....................#........................
+..................................#.................................................................................................#.......
+.........#...............#..............#........................#............#..............................#..............................
+..............................#.........................#.......................................#.....#.....................................
+...............................................#.......................#....................................................................
+.....................#......................................................................................................................
+...............#...........................................................................................#................................
+..#...................................#....................................#........................#............#.............#............
+............................................#............................................#.............................................#....
+...............................................................#............................................................................
+........#.......................................................................................#..........................#................
+..........................#.......#......................#....................#.............................................................
+....#...........#.....................................................................................................#.....................
+...................................................................#..............#...................#..........................#..........
+..............................#..................................................................................#..........................
+.............#......#........................................#.........#..........................#.........................................
+.................................................#...................................#......................#............................#..
+........#..............................................#....................................................................................
+......................................#...................................#...................................................#.............
+............................................................................................................................................
+........................#.......................................................#.......................#...................................
+........................................................................................................................#.........#.........
+.......#....................................................................................................................................
+.............................................................#.....#........................#......................#.......................#
+#...........#.........................................................................#.....................................................
+...................................................#............................................#..........................#.........#......
+...................#................#....................................................................#.....#............................
+............................................................................................................................................
+..........................#............................#.......#.............................#..............................................
+....#...................................#........#......................#.....#.............................................................
+.....................................................................................................#.................#....................
+............................................#................................................................#.....................#........
+.........#.......................................................#...................#......................................................
+............................................................................................................................................
+................................#........................#.................#................................................................
+..........................#.........................................#.......................................................#..............#
+.#.................................................#.........#..............................................................................
+..................#.................#.............................................#.........#...........#............#......................
+.......................................................................................................................................#....
+.........#..................#...............................................................................................................
+............................................#........................................#.............................................#........
+........................................................................#...................................................................
+.#.................................................#..............#...........#............................#................................
+....................#.................#.........................................................#.........................................#.
+.............#.............................................................................#......................#........#................
+...............................#......................................................................#..........................#..........
+............................................................................................................................................
+........................#................................................#..............#...................................................
+........#.........................#......#.........#.........#..............................................................................
+..................................................................#................#............................#...........................
+..............................................................................................#.....#.......................................
+.....#......................................................................#...............................................................
+...................#.........................#........................................#..............................#..................#...
+.#.........................#.............................#.......................................#................................#.........
+............................................................................................................................................
+................................................#........................#...................................................#..............
+...........#............#.............................................................................#.....................................
+..................................#................................#...........#....................................#.......................
+#.........................................#....................................................#...............#............................
+.............................#...........................................................................................................#..
+.....#.......#.................................#.......................................#...........................................#........
+........................................................................................................#...................#...............
+...................................#.........................#..............................................................................
+.........#...........................................................#.............#..............................#.........................
+..................#........#.......................#....................................................................#......#........#...
+........................................................................................#...........#.......................................
+.................................#.......#..................................................................#...............................
+.............#......................................................................................................................#.......
+#.............................................................................#..................#..........................................
+....................#................#.......................#.............................#............#...................................
+....................................................................#...........................................#..........#.....#..........
+...............................#.......................#...............................................................................#....
+........#.......#...........................................................................................#...............................
+........................#..................................................................................................................#
+............................................................................................................................................
+..............................................................................................#......................................#......
+..........................................#..............................#...........#............................#.........................
+............#.............#..................................#..........................................#.................#.................
+........................................................................................................................................#...
+...................#.......................................................................#................................................
+#.................................#..................#.......................#..............................................................
+.............................#......................................................................#.....#.....#...................#.......
+......#........#.................................#............#......#......................................................................
diff --git a/11/src/part-1.rs b/11/src/part-1.rs
new file mode 100644
index 0000000..075da3e
--- /dev/null
+++ b/11/src/part-1.rs
@@ -0,0 +1,44 @@
+mod stuff;
+
+use crate::stuff::{is_galaxy, read_helper, cumulative_sum_expansion, distance, Position};
+
+
+fn main() {
+    let mut stdin = std::io::stdin().lock();
+
+    let mut buf: Vec<u8> = Vec::new();
+
+    let mut galaxies: Vec<Position> = Vec::new();
+    
+    let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+    if num_bytes == 0 { panic!("Malformed input"); }
+    let mut col_empty_mask: Vec<bool> = Vec::from_iter(std::iter::repeat(true).take(buf.len()));
+    let mut row_empty_mask: Vec<bool> = Vec::new();
+    loop {
+        let mut row_empty: bool = true;
+        let i = row_empty_mask.len();
+        for (j, & c) in (& buf).into_iter().enumerate() {
+            if is_galaxy(c) {
+                col_empty_mask[j] = false;
+                row_empty = false;
+                galaxies.push([i, j]);
+            }
+        }
+        row_empty_mask.push(row_empty);
+
+        let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+        if num_bytes == 0 { break; }
+    }
+
+    let cumulative_row_sum: Vec<usize> = cumulative_sum_expansion(& row_empty_mask, 2);
+    let cumulative_col_sum: Vec<usize> = cumulative_sum_expansion(& col_empty_mask, 2);
+
+    let mut res: usize = 0;
+    for (i, pos_1) in (& galaxies).into_iter().enumerate() {
+        for (_, pos_2) in (& galaxies).into_iter().enumerate().skip(i) {
+            res += distance(& cumulative_row_sum, & cumulative_col_sum, pos_1, pos_2);
+        }
+    }
+
+    println!("{}", res);
+}
diff --git a/11/src/part-2.rs b/11/src/part-2.rs
new file mode 100644
index 0000000..e79e3bf
--- /dev/null
+++ b/11/src/part-2.rs
@@ -0,0 +1,44 @@
+mod stuff;
+
+use crate::stuff::{is_galaxy, read_helper, cumulative_sum_expansion, distance, Position};
+
+
+fn main() {
+    let mut stdin = std::io::stdin().lock();
+
+    let mut buf: Vec<u8> = Vec::new();
+
+    let mut galaxies: Vec<Position> = Vec::new();
+    
+    let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+    if num_bytes == 0 { panic!("Malformed input"); }
+    let mut col_empty_mask: Vec<bool> = Vec::from_iter(std::iter::repeat(true).take(buf.len()));
+    let mut row_empty_mask: Vec<bool> = Vec::new();
+    loop {
+        let mut row_empty: bool = true;
+        let i = row_empty_mask.len();
+        for (j, & c) in (& buf).into_iter().enumerate() {
+            if is_galaxy(c) {
+                col_empty_mask[j] = false;
+                row_empty = false;
+                galaxies.push([i, j]);
+            }
+        }
+        row_empty_mask.push(row_empty);
+
+        let num_bytes = read_helper(&mut stdin, &mut buf, b'\n').expect("IO error");
+        if num_bytes == 0 { break; }
+    }
+
+    let cumulative_row_sum: Vec<usize> = cumulative_sum_expansion(& row_empty_mask, 1_000_000);
+    let cumulative_col_sum: Vec<usize> = cumulative_sum_expansion(& col_empty_mask, 1_000_000);
+
+    let mut res: usize = 0;
+    for (i, pos_1) in (& galaxies).into_iter().enumerate() {
+        for (_, pos_2) in (& galaxies).into_iter().enumerate().skip(i) {
+            res += distance(& cumulative_row_sum, & cumulative_col_sum, pos_1, pos_2);
+        }
+    }
+
+    println!("{}", res);
+}
diff --git a/11/src/stuff.rs b/11/src/stuff.rs
new file mode 100644
index 0000000..82540ef
--- /dev/null
+++ b/11/src/stuff.rs
@@ -0,0 +1,48 @@
+use core::cmp::{max, min};
+use std::io::{BufRead};
+
+pub fn read_helper<'a, 'b, R: BufRead>(r: &'a mut R, buf: &'b mut Vec<u8>, token: u8) -> std::io::Result<usize> {
+    buf.clear();
+    let num_bytes = r.read_until(token, buf)?;
+    if buf.last() == Some(& token) { buf.pop(); }
+    Ok(num_bytes)
+}
+
+pub fn is_galaxy(c: u8) -> bool {
+    c == b'#'
+}
+
+pub type Position = [usize; 2];
+
+pub fn cumulative_sum_expansion(doubling: & [bool], factor: usize) -> Vec<usize> {
+    let mut ret: Vec<usize> = Vec::with_capacity(doubling.len());
+
+    let mut sum: usize = 0;
+    for &x in doubling.into_iter() {
+        if x {
+            sum += factor;
+        }
+        else {
+            sum += 1;
+        }
+        ret.push(sum);
+    }
+    
+    ret
+}
+
+pub fn distance(cumul_rows: & [usize], cumul_cols: & [usize], p: & Position, q: & Position) -> usize {
+    (cumul_rows[max(p[0], q[0])] - cumul_rows[min(p[0], q[0])])
+        + (cumul_cols[max(p[1], q[1])] - cumul_cols[min(p[1], q[1])])
+}
+
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+    }
+
+}
diff --git a/11/test.txt b/11/test.txt
new file mode 100644
index 0000000..986aad4
--- /dev/null
+++ b/11/test.txt
@@ -0,0 +1,10 @@
+...#......
+.......#..
+#.........
+..........
+......#...
+.#........
+.........#
+..........
+.......#..
+#...#.....