From df9672fd8865cde6fa75968991d52da9ecf715e7 Mon Sep 17 00:00:00 2001 From: Gard Spreemann Date: Tue, 12 Dec 2023 10:24:30 +0100 Subject: Day 11 --- 11/Cargo.toml | 14 ++++++ 11/input.txt | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 11/src/part-1.rs | 44 +++++++++++++++++ 11/src/part-2.rs | 44 +++++++++++++++++ 11/src/stuff.rs | 48 +++++++++++++++++++ 11/test.txt | 10 ++++ 6 files changed, 300 insertions(+) create mode 100644 11/Cargo.toml create mode 100644 11/input.txt create mode 100644 11/src/part-1.rs create mode 100644 11/src/part-2.rs create mode 100644 11/src/stuff.rs create mode 100644 11/test.txt 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 = Vec::new(); + + let mut galaxies: Vec = 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 = Vec::from_iter(std::iter::repeat(true).take(buf.len())); + let mut row_empty_mask: Vec = 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 = cumulative_sum_expansion(& row_empty_mask, 2); + let cumulative_col_sum: Vec = 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 = Vec::new(); + + let mut galaxies: Vec = 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 = Vec::from_iter(std::iter::repeat(true).take(buf.len())); + let mut row_empty_mask: Vec = 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 = cumulative_sum_expansion(& row_empty_mask, 1_000_000); + let cumulative_col_sum: Vec = 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, token: u8) -> std::io::Result { + 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 { + let mut ret: Vec = 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 @@ +...#...... +.......#.. +#......... +.......... +......#... +.#........ +.........# +.......... +.......#.. +#...#..... -- cgit v1.2.3