From b960e5da5c31b026f4700e23ed8df8d85a63f63c Mon Sep 17 00:00:00 2001 From: Jack Kinsey Date: Sun, 8 Dec 2024 15:39:42 -0500 Subject: [PATCH] Complete day 8 --- src/day08.rs | 223 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 6 +- 2 files changed, 226 insertions(+), 3 deletions(-) create mode 100644 src/day08.rs diff --git a/src/day08.rs b/src/day08.rs new file mode 100644 index 0000000..4baa335 --- /dev/null +++ b/src/day08.rs @@ -0,0 +1,223 @@ +use std::collections::{HashMap, HashSet}; +use std::ops::{Add, Sub}; + +fn input() -> &'static str { + include_str!("../input/day08.txt") +} + +#[derive(Debug, Hash, Ord, PartialOrd, Eq, PartialEq, Copy, Clone)] +struct Point(i32, i32); + +impl Add for Point { + type Output = Point; + + fn add(self, rhs: Self) -> Self::Output { + Point(self.0 + rhs.0, self.1 + rhs.1) + } +} + +impl Sub for Point { + type Output = Point; + + fn sub(self, rhs: Self) -> Self::Output { + Point(self.0 - rhs.0, self.1 - rhs.1) + } +} + +fn parse(input: &str) -> HashMap> { + let chars = input.lines().zip(0..).flat_map(|(l, i)| { + l.chars().zip(0..).filter_map(move |(c, j)| { + if c == '.' { + None + } else { + Some((c, Point(i, j))) + } + }) + }); + let mut posmap = HashMap::new(); + for (char, pos) in chars { + let poslist: &mut Vec = posmap.entry(char).or_default(); + poslist.push(pos); + } + posmap +} + +fn get_nearby_colinear_points(bound: i32, a: Point, b: Point) -> Vec { + [a - b + a, b - a + b] + .iter() + .filter(move |Point(i, j)| *i >= 0 && *i < bound && *j >= 0 && *j < bound) + .copied() + .collect() +} + +fn get_colinear_points(bound: i32, a: Point, b: Point) -> Vec { + let d = a.min(b) - a.max(b); + let mut p0 = a.min(b); + while p0.0 >= 0 && p0.1 >= 0 && p0.0 < bound && p0.1 < bound { + p0 = p0 + d; + } + p0 = p0 - d; + [p0].iter() + .cycle() + .zip(0..) + .map(|(p, n)| *p - Point(n * d.0, n * d.1)) + .take_while(|&Point(i, j)| i >= 0 && j >= 0 && i < bound && j < bound) + .collect() +} + +fn find_nearby_antinodes(size: i32, pos: &[Point]) -> impl Iterator + use<'_> { + pos.iter() + .flat_map(|p| pos.iter().map(move |q| (p, q))) + .filter(|(a, b)| a != b) + .flat_map(move |(a, b)| get_nearby_colinear_points(size, *a, *b)) +} + +fn find_antinodes(size: i32, pos: &[Point]) -> impl Iterator + use<'_> { + pos.iter() + .flat_map(|p| pos.iter().map(move |q| (p, q))) + .filter(|(a, b)| a != b) + .flat_map(move |(a, b)| get_colinear_points(size, *a, *b)) +} + +pub fn part1() { + let size: i32 = input().lines().count().try_into().unwrap(); + let n = parse(input()) + .iter() + .flat_map(|(_, pos)| find_nearby_antinodes(size, pos)) + .collect::>() + .len(); + println!("Day 8 Part 1: {}", n); +} + +pub fn part2() { + let size: i32 = input().lines().count().try_into().unwrap(); + let n = parse(input()) + .iter() + .flat_map(|(_, pos)| find_antinodes(size, pos)) + .collect::>() + .len(); + println!("Day 8 Part 2: {}", n); +} + +#[cfg(test)] +mod test { + use super::*; + + const INPUT_STR: &str = concat!( + "............\n", + "........0...\n", + ".....0......\n", + ".......0....\n", + "....0.......\n", + "......A.....\n", + "............\n", + "............\n", + "........A...\n", + ".........A..\n", + "............\n", + "............\n", + ); + + #[test] + fn test_parse() { + assert_eq!( + parse(INPUT_STR), + HashMap::from([ + ('A', vec![Point(5, 6), Point(8, 8), Point(9, 9)]), + ( + '0', + vec![Point(1, 8), Point(2, 5), Point(3, 7), Point(4, 4)] + ) + ]) + ) + } + + #[test] + fn test_nearby_colinear_points() { + assert_eq!( + get_nearby_colinear_points(12, Point(5, 6), Point(8, 8)), + [Point(2, 4), Point(11, 10)] + ); + assert_eq!( + get_nearby_colinear_points(12, Point(5, 6), Point(9, 9)), + [Point(1, 3)] + ); + assert_eq!( + get_nearby_colinear_points(12, Point(8, 8), Point(9, 9)), + [Point(7, 7), Point(10, 10)] + ); + } + + #[test] + fn test_colinear_points() { + assert_eq!( + get_colinear_points(12, Point(5, 6), Point(8, 8)), + [Point(2, 4), Point(5, 6), Point(8, 8), Point(11, 10)] + ); + assert_eq!( + get_colinear_points(12, Point(5, 6), Point(9, 9)), + [Point(1, 3), Point(5, 6), Point(9, 9)] + ); + assert_eq!( + get_colinear_points(12, Point(8, 8), Point(9, 9)), + [ + Point(0, 0), + Point(1, 1), + Point(2, 2), + Point(3, 3), + Point(4, 4), + Point(5, 5), + Point(6, 6), + Point(7, 7), + Point(8, 8), + Point(9, 9), + Point(10, 10), + Point(11, 11), + ] + ); + } + + #[test] + fn test_find_nearby_antinodes() { + let map = parse(INPUT_STR); + assert_eq!( + find_nearby_antinodes(12, &map[&'0']) + .collect::>() + .len(), + 10 + ); + assert_eq!( + find_nearby_antinodes(12, &map[&'A']) + .collect::>() + .len(), + 5 + ); + assert_eq!( + map.iter() + .flat_map(|(_, pos)| find_nearby_antinodes(12, pos)) + .collect::>() + .len(), + 14 + ); + } + + #[test] + fn test_find_antinodes() { + let map = parse(INPUT_STR); + assert_eq!( + find_antinodes(12, &map[&'0']).collect::>().len(), + 21 + ); + assert_eq!( + find_antinodes(12, &map[&'A']).collect::>().len(), + 16 + ); + assert_eq!( + map.iter() + .flat_map(|(_, pos)| find_antinodes(12, pos)) + .collect::>() + .len(), + 34 + ); + } +} diff --git a/src/main.rs b/src/main.rs index 2b2032d..879fa54 100644 --- a/src/main.rs +++ b/src/main.rs @@ -5,7 +5,7 @@ pub mod day04; pub mod day05; pub mod day06; pub mod day07; -// pub mod day08; +pub mod day08; // pub mod day09; // pub mod day10; // pub mod day11; @@ -26,7 +26,7 @@ pub mod day07; type Part = fn(); -const DAYS: [(Part, Part); 7] = [ +const DAYS: [(Part, Part); 8] = [ (day01::part1 as fn(), day01::part2 as fn()), (day02::part1 as fn(), day02::part2 as fn()), (day03::part1 as fn(), day03::part2 as fn()), @@ -34,7 +34,7 @@ const DAYS: [(Part, Part); 7] = [ (day05::part1 as fn(), day05::part2 as fn()), (day06::part1 as fn(), day06::part2 as fn()), (day07::part1 as fn(), day07::part2 as fn()), - // (day08::part1 as fn(), day08::part2 as fn()), + (day08::part1 as fn(), day08::part2 as fn()), // (day09::part1 as fn(), day09::part2 as fn()), // (day10::part1 as fn(), day10::part2 as fn()), // (day11::part1 as fn(), day11::part2 as fn()), -- 2.38.5