Day 11

2 files changed, 240 insertions, 8 deletions

diff --git a/2023/inputs/day_11.txt b/2023/inputs/day_11.txt
new file mode 100644
index 0000000..b95a785
--- /dev/null
+++ b/2023/inputs/day_11.txt
@@ -0,0 +1,140 @@
+...#...................#.......................#.......................................................#....................................
+........................................................#...................................................................................
+...............................#..........#..........................#.....#......................#.........................................
+......#.................................................................................#.............................#..............#......
+...........................................................................................................................................#
+.................#........#.........................#...........#................#....................#......#..............................
+........................................#................#....................................#..............................#..............
+......................#.....................................................................................................................
+..#.........#.......................#..............................#...............................................................#........
+.............................................................#..................................................#...........................
+...................#...........#...................#....................#...............................................#...................
+...........................................#...................................#.....................#......#...............................
+....#.........................................................................................................................#.............
+........................................................................................#..........................#........................
+...........#........................#..........................#............#...............................................................
+.#...........................#..............................................................................................................
+...............#..........................#................#.......................#.......................#................................
+.....................#...........................................................................................#..........................
+.........#.......................................#..................#..........#............#..........#..................#.................
+.......................................................................................................................................#....
+....................................#........................#..........................#...................................................
+.....#.....................................#................................................................................................
+...............#......................................#......................................................#....................#.........
+....................#................................................................#.......#...............................#..............
+...........#................................................................................................................................
+.........................#......................#...........................................................................................
+...#..............................#....................................#...........................#........................................
+..................................................................#..................................................................#......
+..........................................#..........#......................#............................................#..................
+...............#......................................................................#..........................#........................#.
+.....................#......................................................................................................................
+..................................................#.............#.................................#.........................................
+#..........................#.........................................................................................#......................
+.....................................#......#................................#..............#...............#..................#............
+........#............................................................................................#................................#.....
+................................................................................................................#...........................
+...............................#.......................#..................#................................................#................
+..................................................................................................#...................#....................#
+............................................................................................................................................
+................#..........#....................#..................#..........................................#.............................
+........#.................................#........................................#.....#.....................................#............
+.......................#............................................................................................#.......................
+.........................................................................................................................#.........#........
+........................................................................................................#...................................
+....#.......#...............#........................................#......................................................................
+...........................................#.....#.............................................................#..............#.........#...
+............................................................................................................................................
+.....................#................#..................#....................#..............#..............................................
+......#.....................................................................................................................................
+...............#......................................................................................#.........................#...........
+........................#...........................#..........#......................................................#.....................
+.........................................#...........................#.................#......................#.............................
+............................................................................................................................................
+............................#.............................#.................................#..............................#...........#....
+.#...........#......................#.........#...........................#.................................................................
+............................................................................................................................................
+.................#..................................................................#...........#.........#......................#..........
+............................................................................................................................................
+............................................................................................................................................
+.........#...................#.................................#.............#..............................................................
+...............#....................................................#...............................................#.....#.................
+..........................................#..............................................#...........#.......#..............................
+..#..................................................................................................................................#......
+..........................................................................#.........#.......................................................
+....................................#.........................#.........................................................#...................
+...............................#................................................................#...........................................
+...........#.............................................#............................................#............#........................
+...........................................................................................................................#............#...
+................#...........................#......................#..........#.......#.....................................................
+#......................................................................................................................#............#.......
+........................................................................#..................................#................................
+..............................................................#...........................#.....#.........................................#.
+......#.......#.....#.............#.........................................................................................................
+.............................#.........#..................#.................................................................................
+..........#.........................................................................................................#.......................
+......................................................#................................................#...................#................
+....#....................#.........................................#.........................................#..............................
+....................................#.........#...............#...............#..............#...................................#..........
+............................................................................................................................................
+.............................#..................................................................................#.......#...................
+........................................#................#...............#..................................................................
+............................................................................................................................................
+.............................................................#.........................#................#...................................
+..........#......#............................#..................................#...............#..............................#.........#.
+..................................#.................................................................................#.......................
+....................................................#.......................#...............#.................#.......................#.....
+.#...........#........................#..............................................#......................................................
+................................................................#.......#..............................#....................................
+..................................................................................................#...........................#.............
+............................................................#............................................................#..............#...
+......#.....................#......................................#...........#............................................................
+.....................................................#.............................................................#.............#..........
+.......................#.............#.....................................................................................................#
+...........#.................................#............................#...........................#.....................................
+.#...............................#....................................................................................#.....................
+...................#...................................#..........................................#..............#..........................
+.........................#.......................................#.............#............................................................
+..........................................#.......#.....................#................#..................................#...............
+...#.......................................................................................................#............................#...
+............#.............................................#..................................#...................................#..........
+............................#..........#.............................................................#.............#........................
+......................#.....................................................................................................................
+.............................................................................................................#..............................
+....#........................................#.....................................#.......................................#................
+.....................................................#..............#...................................................................#...
+#....................................#....................#.......................................................................#.........
+................................................................................................#...........................................
+...........#.........#....................#...............................#.............#................................#..................
+............................................................................................................................................
+......#..........................#...........................#...........................................#...........#......................
+.#.............#.........#.........................................#...........#.....#..................................................#...
+.....................................#...................#.....................................................................#............
+...........................................................................................#................................................
+...................#................................................................................#..............#........................
+...........................................#......#........................................................................................#
+..#........................#..................................#.........................#...................................................
+........#.............................#...............................................................................#.....................
+...............................#........................#...............#..............................#....................................
+.................................................................#..........................................#...............................
+....................................................#........................#........#....................................#.........#......
+....#.........#....................................................................................#.......................................#
+......................#.....#.............................................................#.................................................
+#......................................#......#....................................#...............................#.............#..........
+.......................................................#..................................................#.................................
+.........................................................................#......................#...........................................
+...............................................................................#............................................#...............
+....#........#................#...............................#.......................................................................#.....
+.......................#.................................................................#..................#...............................
+.....................................#.............#........................................................................................
+...................................................................................................#......................................#.
+..#.........................................................................................................................................
+........#.................................#.............#...........#................#......................................................
+...............................................................................................#............................#...............
+.................#....................#.........................#..................................................................#........
+....#.............................................#........................................................#........#.......................
+.........................#.............................................#............................#.......................................
+......................................................#.................................#................................................#..
+.............................#...............#.................................#............................................................
+.........#....................................................................................#........................#........#...........
+..................#...........................................#.................................................#...........................
diff --git a/2023/src/bin/day_11.rs b/2023/src/bin/day_11.rs
index b3a610b..f78417e 100644
--- a/2023/src/bin/day_11.rs
+++ b/2023/src/bin/day_11.rs
@@ -1,19 +1,111 @@
-use nom::IResult;
+use nom::{
+    branch::alt,
+    character::complete::{char, line_ending},
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    IResult,
+};
 use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let input = fs::read_to_string("inputs/day_11.txt")?;
+    let galaxy_map = GalaxyMap::parser(&input).unwrap().1;
+
+    let part_1_expanded_galaxy_map = galaxy_map.expand(2);
+    dbg!(&part_1_expanded_galaxy_map.distance_sum_between_galaxies());
+
+    let part_2_expanded_galaxy_map = galaxy_map.expand(1_000_000);
+    dbg!(&part_2_expanded_galaxy_map.distance_sum_between_galaxies());
 
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct GalaxyMap(Vec<Point>);
+
+#[derive(Debug, Clone)]
+struct Point {
+    x: usize,
+    y: usize,
+}
+
+#[derive(Debug, Clone)]
+enum Token {
+    Space,
+    Galaxy,
+}
+
+impl GalaxyMap {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(
+                line_ending,
+                many1(alt((
+                    value(Token::Space, char('.')),
+                    value(Token::Galaxy, char('#')),
+                ))),
+            ),
+            |rows| {
+                GalaxyMap(
+                    rows.into_iter()
+                        .enumerate()
+                        .flat_map(move |(y, row)| {
+                            row.into_iter()
+                                .enumerate()
+                                .filter_map(move |(x, token)| match token {
+                                    Token::Space => None,
+                                    Token::Galaxy => Some(Point { x, y }),
+                                })
+                        })
+                        .collect(),
+                )
+            },
+        )(input)
+    }
+
+    fn expand(&self, expansion_factor: usize) -> GalaxyMap {
+        let max_y = self.0.iter().map(|p| p.y).max().unwrap();
+        let empty_rows: Vec<usize> = (0..max_y)
+            .filter(|y| !self.0.iter().any(|p| p.y == *y))
+            .collect();
+
+        let max_x = self.0.iter().map(|p| p.x).max().unwrap();
+        let empty_cols: Vec<usize> = (0..max_x)
+            .filter(|x| !self.0.iter().any(|p| p.x == *x))
+            .collect();
+
+        let extra_spaces = expansion_factor - 1;
+
+        GalaxyMap(
+            self.0
+                .iter()
+                .map(|p| Point {
+                    x: p.x
+                        + empty_cols.iter().filter(|empty_x| **empty_x < p.x).count()
+                            * extra_spaces,
+                    y: p.y
+                        + empty_rows.iter().filter(|empty_y| **empty_y < p.y).count()
+                            * extra_spaces,
+                })
+                .collect(),
+        )
+    }
+
+    fn distance_sum_between_galaxies(&self) -> usize {
+        let mut sum = 0;
+
+        for i in 0..self.0.len() {
+            for j in i + 1..self.0.len() {
+                sum += self.0[i].distance_to(&self.0[j]);
+            }
+        }
+
+        sum
+    }
+}
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+impl Point {
+    fn distance_to(&self, other: &Point) -> usize {
+        other.x.abs_diff(self.x) + other.y.abs_diff(self.y)
     }
 }