summaryrefslogtreecommitdiff
path: root/2023/rust/day11
diff options
context:
space:
mode:
Diffstat (limited to '2023/rust/day11')
-rw-r--r--2023/rust/day11/Cargo.toml8
-rw-r--r--2023/rust/day11/example.txt10
-rw-r--r--2023/rust/day11/input.txt140
-rw-r--r--2023/rust/day11/src/lib.rs130
4 files changed, 288 insertions, 0 deletions
diff --git a/2023/rust/day11/Cargo.toml b/2023/rust/day11/Cargo.toml
new file mode 100644
index 0000000..8f5b9a5
--- /dev/null
+++ b/2023/rust/day11/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day11"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/2023/rust/day11/example.txt b/2023/rust/day11/example.txt
new file mode 100644
index 0000000..986aad4
--- /dev/null
+++ b/2023/rust/day11/example.txt
@@ -0,0 +1,10 @@
+...#......
+.......#..
+#.........
+..........
+......#...
+.#........
+.........#
+..........
+.......#..
+#...#.....
diff --git a/2023/rust/day11/input.txt b/2023/rust/day11/input.txt
new file mode 100644
index 0000000..6ba87be
--- /dev/null
+++ b/2023/rust/day11/input.txt
@@ -0,0 +1,140 @@
+.......................................#..........................................................#......................................#..
+.....................#................................#.....................................................................................
+....#.....#...................#...............#....................#.....................#.....................#....................#.......
+............................................................................................................................................
+.................#......................................................#......#..............#....................#........................
+......................................#.....................................................................................................
+.......................................................#...................................................#..............#.................
+.............................................................#..........................#...................................................
+............#..............................#.................................#.................................................#............
+#.................................#.............#................#....................................................................#.....
+....................................................................................#................#......................................
+....#..........#............#...........................................#..................#..................#...................#.........
+......................................#...................#.................................................................#.............#.
+........#....................................#.......#......................................................................................
+........................................................................................#..........#........................................
+..#................................................................#........................................................................
+..............................#...............................................#.....................................#............#..........
+...................#........................................................................................................................
+...........#......................#........#................................................................................................
+...............................................................#.................#.........................#................................
+......................................................#.....................................#...............................................
+........#............................................................................#................................#.........#...........
+................#...........#...............................................................................................................
+.....................#........................#........................#.....................................#............................#.
+....#........................................................#................#.............................................#...............
+............................................................................................................................................
+.....................................................................................................#.............#...................#....
+..........................#...........#.........................................................................................#...........
+#......................................................#.........................................#............#........#....................
+.........#.....................................#....................................#.......................................................
+.................................#..................................#......................................................#........#.......
+.........................................................................................................#..................................
+......#.............#....................................................#..................................................................
+..........................#........................................................................................#........................
+.#.......................................#...................#...............#........................#..................#..................
+..................................#..............#...........................................................#.................#............
+.........#.........................................................#........................#...............................................
+....................................................................................#.......................................................
+.....#........#............................#...............................#.........................................#......................
+......................................................................#..................................#..................................
+............................#..................#........#..............................................................................#....
+.......................#.............#......................................................................................................
+#..........#...................................................#.......................#........................#......#....................
+....................................................#.............................................#.........................................
+.................................................................................................................................#..........
+..................................#....................................................................#....................................
+........#.......................................#............#.....#........#...............................................................
+............................................................................................................................................
+............................................................................................................................................
+..........................#.............................................................#.........................#.........................
+..#............................#..........#..................................................................................#..............
+..................#...................................................#.............#.......................#.............................#.
+............#.................................#........#.....#..............................................................................
+............................................................................................................................................
+.......................................................................................#..............#.................#...........#.......
+....................#.....#....................................................#............#.................#.............................
+....#............................................................................................#..............................#..........#
+............................................................................................................................................
+...............................#......................#...............................................................#.....................
+.................................................#...............#..................#.........#.............................#...............
+........#......#.....................#................................................................................................#.....
+.............................................#.................................#............................................................
+.#......................#..............................................................#................#...................................
+............#.....#.....................................................................................................#...................
+..................................#.....................................................................................................#...
+............................................................................................................................................
+......#...............................................................#........................#..............................#.............
+.....................#...........................#....................................#..............................#......................
+............................................................................#...............................................................
+............#................#........#.......................#.....................................#.......................................
+............................................................................................#.................#...........#.................
+...................#................................................................................................................#.......
+...................................#...................#..........#............#............................................................
+#.........................................#.....#..................................................................#........................
+............................................................................................................#....................#..........
+..........#..........................................................#.................................#...................................#
+............................................................................................................................................
+......#.................#.......................................................#...............#.........................#.................
+.............................#................#...................#.............................................#...........................
+.............#.......................................#......................#.......#................................#......................
+........................................#................................................#...........................................#......
+...................................#........................................................................................................
+.................#...........................................#..............................................................#...............
+.........#................#.......................................................................................#.........................
+.....................#......................................................................................................................
+.#..............................................................#............#..........#.....#.........#...................................
+......#.................................#.............................#.....................................................................
+................................................................................................................................#...........
+......................................................#............................................#....................#..............#....
+.........................#...................#..............................................................................................
+...............................................................#............#..........#.................#..................................
+..................................#.........................................................................................................
+...............#..........................................................................................................#......#..........
+............................................................................................................................................
+......#........................................#..................................#................#..................................#.....
+.#..........................#.........#.............................................................................#.......................
+.......................................................#......................#.......#.....................................................
+.............................................................#.................................................................#............
+...............#......................................................................................#.......#...........................#.
+.....#....................................................................#...................#.............................................
+..........................#................#.....#................#.........................................................................
+..................................................................................#.................................#......#...........#....
+.................#..........................................................................................................................
+..................................#.........................................................................................................
+...........#.........................................#.................#...............#....................................................
+................................................................#..............................#..........#....................#............
+...............#.............#............................#..................#..............................................................
+..#............................................#...........................................................................#................
+......................#.....................................................................................................................
+.......................................#.................................#..........................................................#.......
+...................................................................#........................................................................
+....#.............#................................................................#..................................#......#..............
+.............................................................#..............................................................................
+.........#................#.....................#.....................#.....#.....................#.......#.................................
+...................................................................................................................................#........
+...........................................#...............................................#................................................
+.....................................................#..........#....................#...........................#............#.........#...
+.#.............#......#.....................................................................................................................
+.............................#............................................#..............................#..................................
+.......................................#............................................................................#.......................
+..................#......................................#............#.............................#.......................................
+.........#................#.....................................................#..............#.............#....................#.......#.
+..#..............................................................#.........................................................#................
+...................................#..........#.............................#.........................................................#.....
+......#..............................................................................................................#......................
+..............#.............................................................................................................................
+......................................................#........#.................#.......................................#..................
+......................#.......#.................#......................................#.......#...............#............................
+..#..............#.......................#..................................................................................................
+.......................................................................#...................#.............#..................................
+.........#..........................................................................#.................................#.....................
+......................................#..................#.......................................#....................................#.....
+.........................#............................................................................#.......#.............#...............
+....................#.........................................#.............................................................................
+...............#............................................................................................................................
+......................................................................#...........#........#...................................#............
+.................................#..........#...............................................................................................
+......#..........................................#............................#....................................#........................
+...............................................................#...........................................#.............................#..
+..#.........#..........#.................#..........................................................#.......................................
diff --git a/2023/rust/day11/src/lib.rs b/2023/rust/day11/src/lib.rs
new file mode 100644
index 0000000..66c95c4
--- /dev/null
+++ b/2023/rust/day11/src/lib.rs
@@ -0,0 +1,130 @@
+fn expand(m: &mut Vec<Vec<i16>>, ch: i16) {
+ let rows = m.len();
+ let mut cols = m[0].len();
+
+ let mut i = 0;
+ while i < rows {
+ if m[i].iter().filter(|&x| *x != 0).count() == 0 {
+ m.insert(i, vec![ch; cols]);
+ i += 1;
+ }
+ i += 1;
+ }
+ let rows = m.len();
+ i = 0;
+
+ while i < cols {
+ let mut c = 0;
+ for j in 0..rows {
+ if m[j][i] != 0 {
+ c += 1;
+ }
+ }
+
+ if c == 0 {
+ for j in 0..rows {
+ m[j].insert(i, ch);
+ }
+ cols += 1;
+ i += 1;
+ }
+ i += 1;
+ }
+}
+
+pub fn part1(input: &str) -> u32 {
+ let mut res: u32 = 0;
+
+ let mut m: Vec<Vec<i16>> = input
+ .trim_end()
+ .split('\n')
+ .map(|y| y.chars().map(|x| if x == '#' { 1 } else { 0 }).collect())
+ .collect();
+
+ expand(&mut m, 0);
+ let mut hs: Vec<(usize, usize)> = vec![];
+ let rows = m.len();
+ let cols = m[0].len();
+ for i in 0..rows {
+ for j in 0..cols {
+ if m[i][j] != 0 {
+ hs.push((i, j));
+ }
+ }
+ }
+
+ let n = hs.len();
+ for i in 0..n {
+ for j in i + 1..n {
+ res += ((hs[j].1 as i16 - hs[i].1 as i16).abs()
+ + (hs[j].0 as i16 - hs[i].0 as i16).abs()) as u32;
+ }
+ }
+
+ res
+}
+
+pub fn part2(input: &str) -> u32 {
+ let mut res: u32 = 0;
+
+ let mut m: Vec<Vec<i16>> = input
+ .trim_end()
+ .split('\n')
+ .map(|y| y.chars().map(|x| if x == '#' { 1 } else { 0 }).collect())
+ .collect();
+
+ expand(&mut m, 1);
+ let mut hs: Vec<(usize, usize)> = vec![];
+ let rows = m.len();
+ let cols = m[0].len();
+ for i in 0..rows {
+ for j in 0..cols {
+ if m[i][j] > 0 {
+ hs.push((i, j));
+ }
+ }
+ }
+
+ let n = hs.len();
+ for i in 0..n {
+ for j in i + 1..n {
+ res += ((hs[j].1 as i16 - hs[i].1 as i16).abs()
+ + (hs[j].0 as i16 - hs[i].0 as i16).abs()) as u32;
+ }
+ }
+
+ res
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn example_part1() {
+ let input = include_str!("../example.txt");
+ let result = part1(input);
+ assert_eq!(result, 374);
+ }
+
+ #[test]
+ fn input_part1() {
+ let input = include_str!("../input.txt");
+ let result = part1(input);
+ assert_eq!(result, 9623138);
+ }
+
+ #[test]
+ fn example_part2() {
+ let input = include_str!("../example.txt");
+ let result = part2(input);
+ assert_eq!(result, 1030);
+ }
+ //
+ // #[test]
+ // fn input_part2() {
+ // let input = include_str!("../input.txt");
+ // let result = part2(input);
+ // assert_eq!(result, 71585);
+ // }
+}