From 3cb621a318630db251d64b8f0ae532f68d23a87a Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Fri, 23 Dec 2022 14:19:40 -0500 Subject: day 23 --- benches/2022.rs | 5 ++ data/2022/23.txt | 75 +++++++++++++++++++++ src/bin/2022/day23.rs | 177 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2022/main.rs | 2 + 4 files changed, 259 insertions(+) create mode 100644 data/2022/23.txt create mode 100644 src/bin/2022/day23.rs diff --git a/benches/2022.rs b/benches/2022.rs index e4c40d5..6eb6c5e 100644 --- a/benches/2022.rs +++ b/benches/2022.rs @@ -43,6 +43,8 @@ mod day19; mod day20; #[path = "../src/bin/2022/day21.rs"] mod day21; +#[path = "../src/bin/2022/day23.rs"] +mod day23; // NEXT MOD day!(2022, 1, day1); @@ -66,6 +68,7 @@ day!(2022, 18, day18); day!(2022, 19, day19); day!(2022, 20, day20); day!(2022, 21, day21); +day!(2022, 23, day23); // NEXT DAY fn bench_2022(c: &mut criterion::Criterion) { @@ -92,6 +95,7 @@ fn bench_2022(c: &mut criterion::Criterion) { day_combined!(2022, 19, day19); day_combined!(2022, 20, day20); day_combined!(2022, 21, day21); + day_combined!(2022, 23, day23); // NEXT DAY COMBINED }) }); @@ -121,5 +125,6 @@ criterion::criterion_main!( bench_2022day19, bench_2022day20, bench_2022day21, + bench_2022day23, // NEXT GROUP ); diff --git a/data/2022/23.txt b/data/2022/23.txt new file mode 100644 index 0000000..44cae66 --- /dev/null +++ b/data/2022/23.txt @@ -0,0 +1,75 @@ +..###.#####....####.......###.####.#.....##..#.##.....#.##..#.#.........#.# +.##...#.##...#.##.######.######.#######.#####.#..##...#..#....#.#.#.#...#.. +#.#.#......#.#..#...#..###..###.#####..#####.#.....##.#.#...##.#.###..#..## +#..##...#####..##...#.##.#.##..##..#...#.###.###..##..####.####.#..#...##.. +#.#...#..#.#####..#####..##.##...#....#.###.....##.#..###....#.#.##..#####. +#.#..#.#.#..#....#...#..##.#.##...#####.#..###..#.#.#.##...#.##.#.##..#..#. +#.####..#...####..........##.#.#....#.#.#...###.#......#.######.#..##.###.. +######...#.#.######.........#.##..####.##..#.#.##....##.#.##.#.#..##.##...# +.##.#.#.###..#.#.##.#..###..##..##.#.###...#..###..#..###.####...###.##.#.. +#.#..#.....##.#.#..##...##..####.####...##..#....##.##.#....#.#..#.#.#..### +..#.###..#..######.##..#.#..#.#..#.#####.##.####...##.#....#.####....##.##. +.......#.###..#.##.#.##....#....#.#...##....####..#.#.#...###.##..#.#.#.### +.####.####..#..##...##...##.####.#.#.#.#.####..##..###.##...##.##....##..#. +###..##.###..###...###....###....####...#..#######....#.#.#.#....###..##..# +##.###..######....#.##..####..#...##..#.#...#..#..#.#.#.#..#.###.###.###### +#....#.#....#.#...####...#.#..##...##.#..#..#.#############....#.###....#.. +#..##.#######.#..###...##...#...####.#.####.....#.....#...##.#.####.##.#.## +#.#.#..###.######.#.###.#.#####.........##....###.#####..###.#.####.#..###. +####.#.#..#.####....#######...###.#.#####.#..#.....###.#.###..#.#..###..### +##..#.#..#.....###.####..###.#...##.#....#..#..#.##....#..#.#...#.#.###..#. +########..#.....##.##.####..#####....##.#.####.###.....#.......###.##....#. +#..#.#######..#...###..#.###..###...##..#.###.##..###..#......##.###..##..# +##..###.#..#.###...##..##.#.#...#.###.##.###.#..#..#...###..#.#####..##.... +##.#.#...#.#..#.#.###....#.#.#.#..#..#.###..#..#.#..##.#####.#..##.######.. +##..#####..........##.##...#.....#..##.#####..##.##.#..#..#####....##...### +#..###.#.##.##..##...######..#.###..#.#.#..###.###.####.##.##.#...##..####. +#.###..###..##.#####..####.....##.#.....#..#.#...#..####.#.######.##.#.#..# +.##....#.#.##...#.#.#...##..#.....#...##..##..####.#..####.##.#.#.#..#.###. +########..#.#.#...#...##...##....##..#.....#.......##..#.#######.##.#....## +.#..#...##.#.##..##.#..#..#.#####.#.#.#..#.....##.##.....##.#.##.##.#.#.### +#..####.##.###..#...#..#.##.#########.#######...#...#..##..#.....###..#..## +##....###..#.#....##...##.####.######..####....###....########..##...###..# +.##...##.#.#.##..###.##.###..#.#..#......#######..#..##....#....###.##..#.. +##..###...###..#.###.#.##.###.#...#.#.#.####.#.####..#.#..###..#####...#### +#####...######.#.#..##.#.###.#.#.#...###......#.#..##..#..##...##.######### +#..#.##.....#.#####.##.....#.#..#.###.#..##.##..##..##..##..#.#..#..##.#### +..###.#...#.##...##.#.....#.#####..#.#..#...#.####...#.#####.#######..#.### +..#.##..#.#..#.###.##..#...#.#....##.....#..#.#...#.##..###.###.##..###..#. +..#.#.#..#....#.#..##..#......#..#...#####.##.....#.##..##.#####.#.#...#... +.#..#.....########......##.####..#..#...##.#.###...#.#...##..#####.#..##... +#..#.#.##.#......##.#......#..####.###....#.#.##..##.....#.#.##.#####..##.# +...#...###...####..#.#.#......#.#..#..##.##..###.#...#.###..#..#...###.###. +##.##.#.........#..#..#....#..#......##.#.######.#..#.#...##.#.##..#..#..#. +.#.##..####.#..##.##....#....###...##..#.#..#.#.##.####...##..#..####....#. +.....##.#..##.#.###.....####..###.##.###.....##..##...#.#..#.##..#.##.#.#.# +##.##.#.#..........#..#.####.#..##.#..#.#.###....###.###.#.##.###.#.....#.. +#..#.#.##.##..##.###..###..#.#..#..##.....#......#####.#..###.#.#.....####. +.##....###..##...#..#.######.####..#.##....#..##.#..####..##....#.....#.##. +..#.#.##....#...#.#..#.....#...###.#.#.#####...####.###.##...###.###.#.##.. +#..###.#...##.#.#.#.#..#.#..#.##...#######....#.####.####.##.#######..##### +..#..#.####...#....#...#......#...#..##.#...#...#######..#..#.#####.###..## +.#.#.###...##.###....#.....####.##.####...#...........###..##...####.#..##. +.###.####.#..#....###.#.##.#.#####..#.#######.#..##.#.###...#.#..####.#.#.. +..###.#....###.#.....###.#####.#.##.#..###.####.....#..#..#..##.....##.#.## +##.##.##...#....##..###.##.#...#......#.....##.#....#.#...##..##...#..####. +.###.....#....##..#####.##..#.#.....#..###..#####.#.#...##..##....#.###.#.. +.##..####..#....##.#####.#.#..#.#.#.##.#..#.#....###.##.###..#....######.#. +#.###..#...##.##...####..##....#.##..###.....#.....#..##.#...###..###.....# +..#.#.##...##.##.##..#.#.##.##...##..#.###.#...######.....#.....#.....#.##. +#.#.#.##.#.#.##.###...####...####..#.....###.#..###.....#..##.#...#.###..## +#..###.##.#####..#.##...#..###.#.#.#.#....##...###.#..#####.#......##..#.#. +##.#.##...##.#####...#...#.#...#..##.##.#...#.###..##...##..##.#..##.#.###. +....####....##..#....##.#...##.#.....##.####.#..#......#.##.##....#.#..#.## +#.#.#####.##...#..#.#....#.####..#####....#.###..######..##....####..#.#### +.##.#...##..####.#....##..##....#....##.#.#....#....#.##......##....#...#.# +####..#..#.#.#.#.#..###.###.##..##..#..#.####...##.#..####.........#..#.#.. +.##...#..###.#.#.#.#.###.#.#.#########........###.#.#..#.....####..#..#.#.# +##..###..#.##......#.#.....#....#....#..#####.#.####..###.#.###....#.##.#.. +#.#.#.##...#.....#.#..###.#..######.#..##.#.###..#.####..###.#....##.####.. +.##...#..#..###.###.........##....##...#.###..#..#.#.#.#.#.###......##..##. +.##.##.##..#.######..#.##..##.#...#.##.#..###.#....#..#####.##..#..#.###... +..####.##.#..#..##..##...####.######.##.#.....##.#....#....###.##.##....### +.##......#.....#.#..#.#.##....#.#.#.####...#...##...##...#.##.#.#.#.##...## +.##.#######..#.#..#.#..##..#.#....##...#####...##..#.......##...##..##..#.# +#...#.#..#.###.#.##....##..#...#.#..##.###.......##.#.....######..######### diff --git a/src/bin/2022/day23.rs b/src/bin/2022/day23.rs new file mode 100644 index 0000000..d469095 --- /dev/null +++ b/src/bin/2022/day23.rs @@ -0,0 +1,177 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +fn print_elves(elves: &HashSet<(IRow, ICol)>) { + let min_row = elves.iter().map(|elf| elf.0).min().unwrap(); + let max_row = elves.iter().map(|elf| elf.0).max().unwrap(); + let min_col = elves.iter().map(|elf| elf.1).min().unwrap(); + let max_col = elves.iter().map(|elf| elf.1).max().unwrap(); + for row in (min_row.0..=max_row.0).map(IRow) { + for col in (min_col.0..=max_col.0).map(ICol) { + if elves.contains(&(row, col)) { + print!("#"); + } else { + print!(".") + } + } + println!() + } +} + +pub fn parse(fh: File) -> Result> { + let mut elves = HashSet::new(); + for (row, line) in parse::raw_lines(fh).enumerate() { + for (col, c) in line.chars().enumerate() { + match c { + '#' => { + elves.insert((IRow(row as isize), ICol(col as isize))); + } + '.' => {} + _ => panic!("unexpected char {}", c), + } + } + } + Ok(elves) +} + +fn neighbors(elf: (IRow, ICol)) -> Vec<(IRow, ICol)> { + vec![ + (elf.0 - 1, elf.1 - 1), + (elf.0 - 1, elf.1), + (elf.0 - 1, elf.1 + 1), + (elf.0, elf.1 - 1), + (elf.0, elf.1 + 1), + (elf.0 + 1, elf.1 - 1), + (elf.0 + 1, elf.1), + (elf.0 + 1, elf.1 + 1), + ] +} + +pub fn part1(mut elves: HashSet<(IRow, ICol)>) -> Result { + let mut possible: VecDeque<(IRow, ICol)> = VecDeque::new(); + possible.push_back((IRow(-1), ICol(0))); + possible.push_back((IRow(1), ICol(0))); + possible.push_back((IRow(0), ICol(-1))); + possible.push_back((IRow(0), ICol(1))); + for _ in 0..10 { + let mut moves: HashSet<((IRow, ICol), (IRow, ICol))> = HashSet::new(); + for elf in &elves { + if neighbors(*elf) + .iter() + .all(|neighbor| !elves.contains(neighbor)) + { + continue; + } + for diff in &possible { + let occupied = if diff.0 == IRow(0) { + elves.contains(&(elf.0 - 1, elf.1 + diff.1 .0)) + || elves.contains(&(elf.0, elf.1 + diff.1 .0)) + || elves.contains(&(elf.0 + 1, elf.1 + diff.1 .0)) + } else { + elves.contains(&(elf.0 + diff.0 .0, elf.1 - 1)) + || elves.contains(&(elf.0 + diff.0 .0, elf.1)) + || elves.contains(&(elf.0 + diff.0 .0, elf.1 + 1)) + }; + if !occupied { + moves.insert(( + *elf, + (elf.0 + diff.0 .0, elf.1 + diff.1 .0), + )); + break; + } + } + } + let mut targets: HashMap<(IRow, ICol), usize> = HashMap::new(); + for (from, to) in &moves { + *targets.entry(*to).or_default() += 1; + } + for (from, to) in &moves { + if targets.get(to).copied().unwrap_or(0) == 1 { + elves.remove(from); + elves.insert(*to); + } + } + + let first = possible.pop_front().unwrap(); + possible.push_back(first); + } + let min_row = elves.iter().map(|elf| elf.0).min().unwrap(); + let max_row = elves.iter().map(|elf| elf.0).max().unwrap(); + let min_col = elves.iter().map(|elf| elf.1).min().unwrap(); + let max_col = elves.iter().map(|elf| elf.1).max().unwrap(); + let area = (max_row.0 - min_row.0 + 1) * (max_col.0 - min_col.0 + 1); + Ok(area - elves.len() as isize) +} + +pub fn part2(mut elves: HashSet<(IRow, ICol)>) -> Result { + let mut possible: VecDeque<(IRow, ICol)> = VecDeque::new(); + possible.push_back((IRow(-1), ICol(0))); + possible.push_back((IRow(1), ICol(0))); + possible.push_back((IRow(0), ICol(-1))); + possible.push_back((IRow(0), ICol(1))); + let mut round = 0; + loop { + round += 1; + let mut moves: HashSet<((IRow, ICol), (IRow, ICol))> = HashSet::new(); + for elf in &elves { + if neighbors(*elf) + .iter() + .all(|neighbor| !elves.contains(neighbor)) + { + continue; + } + for diff in &possible { + let occupied = if diff.0 == IRow(0) { + elves.contains(&(elf.0 - 1, elf.1 + diff.1 .0)) + || elves.contains(&(elf.0, elf.1 + diff.1 .0)) + || elves.contains(&(elf.0 + 1, elf.1 + diff.1 .0)) + } else { + elves.contains(&(elf.0 + diff.0 .0, elf.1 - 1)) + || elves.contains(&(elf.0 + diff.0 .0, elf.1)) + || elves.contains(&(elf.0 + diff.0 .0, elf.1 + 1)) + }; + if !occupied { + moves.insert(( + *elf, + (elf.0 + diff.0 .0, elf.1 + diff.1 .0), + )); + break; + } + } + } + let mut targets: HashMap<(IRow, ICol), usize> = HashMap::new(); + for (from, to) in &moves { + *targets.entry(*to).or_default() += 1; + } + let mut moved = false; + for (from, to) in &moves { + if targets.get(to).copied().unwrap_or(0) == 1 { + elves.remove(from); + elves.insert(*to); + moved = true; + } + } + if !moved { + break; + } + + let first = possible.pop_front().unwrap(); + possible.push_back(first); + } + + Ok(round) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 23).unwrap()).unwrap()).unwrap(), + 0 + ); + assert_eq!( + part2(parse(parse::data(2022, 23).unwrap()).unwrap()).unwrap(), + 0 + ); +} diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs index 25e7c34..14aac9b 100644 --- a/src/bin/2022/main.rs +++ b/src/bin/2022/main.rs @@ -32,6 +32,7 @@ mod day18; mod day19; mod day20; mod day21; +mod day23; // NEXT MOD #[paw::main] @@ -59,6 +60,7 @@ fn main(opt: Opt) -> Result<()> { 19 => advent_of_code::day!(2022, opt.day, opt.puzzle, day19), 20 => advent_of_code::day!(2022, opt.day, opt.puzzle, day20), 21 => advent_of_code::day!(2022, opt.day, opt.puzzle, day21), + 23 => advent_of_code::day!(2022, opt.day, opt.puzzle, day23), // NEXT PART _ => panic!("unknown day {}", opt.day), } -- cgit v1.2.3-54-g00ecf