From 9b84f5b0d90676aa8e578d367e7870c86a4ebf3b Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Mon, 11 Dec 2023 00:33:35 -0500 Subject: day 11 --- benches/2023.rs | 5 ++ data/2023/11.txt | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2023/day11.rs | 94 +++++++++++++++++++++++++++++++++ src/bin/2023/main.rs | 2 + src/grid.rs | 13 +++++ 5 files changed, 254 insertions(+) create mode 100644 data/2023/11.txt create mode 100644 src/bin/2023/day11.rs 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> { + Ok(parse::grid(parse::raw_lines(fh), |c, _, _| c == b'#')) +} + +pub fn part1(mut map: Grid) -> Result { + 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) -> Result { + 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 Grid { .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 -- cgit v1.2.3-54-g00ecf