day 11

5 files changed, 254 insertions, 0 deletions

diff --git a/benches/2023.rs b/benches/2023.rs
index d633f55..fd48120 100644
--- a/benches/2023.rs
+++ b/benches/2023.rs
@@ -21,6 +21,8 @@ mod day8;
 mod day9;
 #[path = "../src/bin/2023/day10.rs"]
 mod day10;
+#[path = "../src/bin/2023/day11.rs"]
+mod day11;
 // NEXT MOD
 
 day!(2023, 1, day1);
@@ -33,6 +35,7 @@ day!(2023, 7, day7);
 day!(2023, 8, day8);
 day!(2023, 9, day9);
 day!(2023, 10, day10);
+day!(2023, 11, day11);
 // NEXT DAY
 
 fn bench_2023(c: &mut criterion::Criterion) {
@@ -48,6 +51,7 @@ fn bench_2023(c: &mut criterion::Criterion) {
             day_combined!(2023, 8, day8);
             day_combined!(2023, 9, day9);
             day_combined!(2023, 10, day10);
+            day_combined!(2023, 11, day11);
             // NEXT DAY COMBINED
         })
     });
@@ -66,5 +70,6 @@ criterion::criterion_main!(
     bench_2023day8,
     bench_2023day9,
     bench_2023day10,
+    bench_2023day11,
     // NEXT GROUP
 );
diff --git a/data/2023/11.txt b/data/2023/11.txt
new file mode 100644
index 0000000..e93afdc
--- /dev/null
+++ b/data/2023/11.txt
@@ -0,0 +1,140 @@
+......................#..................#................................#............#..........................#.........................
+..........#....................................#.................#..........................................................................
+................................#......................#..........................#.....................#................#..................
+...........................#....................................................................#........................................#..
+.....#..........#...................................................................................................................#.......
+........................................................................................#...................................................
+........................................#............#......................................................................................
+.....................#....................................................#...................#.......................#.....................
+..............................................................................................................................#...........#.
+............................#.......#......................#................................................................................
+...........#......................................#..............#............#.............................................................
+.........................................................................................#..................................................
+....#...............................................................................#.....................................#...........#.....
+..................#...........#...............#..............................................#.......#........#.............................
+........................................#...........................#.......................................................................
+............................................................................................................................................
+.........................#..........................#.........................#.........................#...................................
+................#...................#..................................................................................#...................#
+...#...........................................................#........#.............#..............................................#......
+..................................................................................................#.........................................
+.............#..............................#...............................................................................................
+.....................#.........................................................................................#............................
+............................#........................#............#.........................#..................................#............
+.......#..............................................................................................................#.....................
+........................................................................#........#..................#.......................................
+...#......................................#.......#......................................................#........#...............#.........
+...........................................................#.............................................................................#..
+................................#..................................#........................................................................
+.............#.................................#............................................................................................
+#.......................#...............#.................................#...........#.........#...................................#.......
+...........................................................................................#..................#.............................
+........#....................#........................................................................................#......#..............
+............................................................#......................................#......................................#.
+..#.......................................#.................................................................................................
+....................#................................................................#....................................#........#........
+.............#......................#................#......................................#...............................................
+.......#............................................................#................................................#......................
+..............................#.................#.................................................#.........................................
+.......................#...................................................................................#................................
+..................#..........................................#..................................................#..............#.....#......
+...................................................#...............................#.....#.............#....................................
+...#..........#.............#........#......................................................................................................
+............................................................................#..................#.............#...........................#..
+......................................................#..............#......................................................................
+#......#....................................................................................................................#...............
+..............................................#.............................................................................................
+...................#................#...................................#.......................................................#..........#
+...........#............#.................................#.................................................#...........#...................
+.....................................................................................#.....#........#............#.....................#....
+....................................................#..........#............................................................................
+............................................................................................................................................
+.#.......#..................#..........#.............................#............#............#..........#................#..............#.
+...............#.....#...................................................................#..................................................
+.................................................#..........................#.........................................#........#.....#......
+......#..........................................................#...............................................#..........................
+............................................................................................................................................
+.............................#................#.......................................#.....................#...............................
+..................#..................#.......................#..........#.....................#.............................#...............
+............................................................................................................................................
+..................................................................................#.................#...................#..........#........
+..................................#.....#..............#..........#.....................#...................................................
+.....#.................#....................................................................................................................
+#......................................................................................................................................#....
+..................#..................#........#...........#..................#.................#............................................
+.....................................................................#................................#.........#.............#.............
+..........#..........................................................................#.....#................................................
+............................#.......................#...........#...........................................................................
+.#.................................#.............................................................#.................#........................
+............................................................................#................................#..........................#...
+......#..................................................................................................................#..................
+...................#..............................#.................................................#.........................#.............
+..............#................#.........................................................#..........................................#.......
+............................................#....................#...............#..........................................................
+.......................#................................................#.................................#.................................
+..................................#.....#...........#...................................................................#...................
+.#.....................................................................................#........#...........................................
+.......#......................#................................#.......................................#....................................
+...............................................#............................................................................................
+..........................................................#................#.....................................#..........................
+......................#.....................................................................................................................
+............................................#.........#.......................................#..................................#..........
+.#.........#........................................................#...................................#.....#.............................
+.......................................#.............................................#..................................................#...
+...............................#............................................................................................................
+.............................................................................#..................#................#........#.................
+......................#.....................................................................................................................
+...#..............................................#.........#.....................#......................#...........................#......
+..................................#.........................................................................................................
+...........................................................................#...............#...................................#............
+..........#..............#....................#.............................................................................................
+...............................................................................................................#........................#...
+....#.........#...............................................................#.....#.......................................................
+.......................................................#..........#.......................................................#.................
+..................................#...............#..............................................................................#..........
+..............................................................#..........................#................#.........#.......................
+........#............................................................#......................................................................
+#...............................................................................................#...........................................
+......................#....................................................................................................................#
+.....#......................#..............................................#...........#..........................#.....#...................
+................#.................................................#..............#..........................................................
+...........#.........................................#......................................................................................
+..#..................................#.............................................................................................#.....#..
+..........................................#................................................#.....#........#.................................
+..............#...............................................#.................................................#...........................
+....................#.............#....................#..............................................#.....................................
+.............................#..........................................#...................................................................
+...........................................................#................................................................................
+.......................#.........................#.....................................#...........#........................................
+.................................................................#............................................#.......#.....................
+........#.....#............................................................#........................................................#.......
+.................................#...........................................................#..............................................
+.#.................#......................#.................#.........#..................................#.......#........#................#
+...........#................................................................................................................................
+........................#..............................#.............................#......................................................
+...................................#.....................................#.........................#.................................#......
+............................................................................................................................................
+....#..................................#.................................................#...............................#..................
+.............................#....................#......................................................................................#..
+.............................................................................#.........................#....................................
+.............#.....#......................#.......................#.................#........................................#..............
+......................................................................................................................................#.....
+...#.................................................#...........................................#..........................................
+......................#.....................................#...............................................................................
+................#..........#..................................................................................#..........#..................
+..........#.........................#............#.................#..........#............................................................#
+............................................................................................................................................
+.......................................................#............................................................#.......................
+...#.........................................#.....................................#...............#..............................#.........
+............#.........................#.....................................................................................................
+.......................#...........................#.....................................................#..................................
+..............................................................#............................#...............................#..........#.....
+.........#......................#..........#.........................................#......................................................
+...............#................................................................................#.....#.....................................
+....#.......................#..................#....................#......................................#...................#............
+..........................................................#.................................................................................
+.....................................#.........................#.........................#..................................................
+#..........................................................................#................................................................
+...........................................#..................................................................#........#...........#........
+......................#...........................................................#...................#.....................................
+....#...........#................................................................................#..........................................
diff --git a/src/bin/2023/day11.rs b/src/bin/2023/day11.rs
new file mode 100644
index 0000000..885a99b
--- /dev/null
+++ b/src/bin/2023/day11.rs
@@ -0,0 +1,94 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Grid<bool>> {
+    Ok(parse::grid(parse::raw_lines(fh), |c, _, _| c == b'#'))
+}
+
+pub fn part1(mut map: Grid<bool>) -> Result<i64> {
+    let mut expand_rows = vec![];
+    for row in map.each_row() {
+        if map[row].iter().all(|b| !b) {
+            expand_rows.push(row);
+        }
+    }
+    let mut expand_cols = vec![];
+    for col in map.each_col() {
+        if map.each_row().map(|row| map[row][col]).all(|b| !b) {
+            expand_cols.push(col);
+        }
+    }
+    for row in expand_rows.into_iter().rev() {
+        map.insert_row(row);
+    }
+    for col in expand_cols.into_iter().rev() {
+        map.insert_col(col);
+    }
+
+    let galaxies: HashSet<(Row, Col)> = map
+        .indexed_cells()
+        .filter_map(|(pos, galaxy)| if *galaxy { Some(pos) } else { None })
+        .collect();
+
+    let mut total = 0;
+    for a in &galaxies {
+        for b in &galaxies {
+            total += a.0.abs_diff(b.0).0 + a.1.abs_diff(b.1).0
+        }
+    }
+
+    Ok((total / 2).try_into().unwrap())
+}
+
+pub fn part2(map: Grid<bool>) -> Result<i64> {
+    let mut expand_rows = vec![];
+    for row in map.each_row() {
+        if map[row].iter().all(|b| !b) {
+            expand_rows.push(row);
+        }
+    }
+    let mut expand_cols = vec![];
+    for col in map.each_col() {
+        if map.each_row().map(|row| map[row][col]).all(|b| !b) {
+            expand_cols.push(col);
+        }
+    }
+
+    let galaxies: HashSet<(Row, Col)> = map
+        .indexed_cells()
+        .filter_map(|(pos, galaxy)| if *galaxy { Some(pos) } else { None })
+        .collect();
+
+    let mut total = 0;
+    for a in &galaxies {
+        for b in &galaxies {
+            let expanded_rows = expand_rows
+                .iter()
+                .filter(|row| (a.0.min(b.0)..a.0.max(b.0)).contains(row))
+                .count();
+            let expanded_cols = expand_cols
+                .iter()
+                .filter(|col| (a.1.min(b.1)..a.1.max(b.1)).contains(col))
+                .count();
+            total += a.0.abs_diff(b.0).0
+                + a.1.abs_diff(b.1).0
+                + 999999 * (expanded_rows + expanded_cols);
+        }
+    }
+
+    Ok((total / 2).try_into().unwrap())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2023, 11).unwrap()).unwrap()).unwrap(),
+        10033566
+    );
+    assert_eq!(
+        part2(parse(parse::data(2023, 11).unwrap()).unwrap()).unwrap(),
+        560822911938
+    );
+}
diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs
index c6f9207..44c0ff0 100644
--- a/src/bin/2023/main.rs
+++ b/src/bin/2023/main.rs
@@ -21,6 +21,7 @@ mod day7;
 mod day8;
 mod day9;
 mod day10;
+mod day11;
 // NEXT MOD
 
 #[paw::main]
@@ -37,6 +38,7 @@ fn main(opt: Opt) -> Result<()> {
         8 => advent_of_code::day!(2023, opt.day, opt.puzzle, day8),
         9 => advent_of_code::day!(2023, opt.day, opt.puzzle, day9),
         10 => advent_of_code::day!(2023, opt.day, opt.puzzle, day10),
+        11 => advent_of_code::day!(2023, opt.day, opt.puzzle, day11),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }
diff --git a/src/grid.rs b/src/grid.rs
index 040b92b..f299bee 100644
--- a/src/grid.rs
+++ b/src/grid.rs
@@ -333,6 +333,19 @@ impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> Grid<T> {
                 .resize_with(cols.0.max(row.cells.len()), T::default);
         }
     }
+
+    pub fn insert_row(&mut self, row: Row) {
+        let mut cells = vec![];
+        cells.resize_with(self.cols().0, Default::default);
+        self.rows.insert(row.0, GridRow { cells });
+    }
+
+    pub fn insert_col(&mut self, col: Col) {
+        for row in self.each_row() {
+            let row = &mut self[row];
+            row.cells.insert(col.0, Default::default());
+        }
+    }
 }
 
 impl<T: Clone + Eq + PartialEq + std::hash::Hash + std::fmt::Display>