From 4f858d88055712f451a893be1b0a78f56879c2ce Mon Sep 17 00:00:00 2001 From: Ummon Date: Wed, 11 Dec 2019 23:44:09 +0100 Subject: [PATCH] Day 10 part1 + WIP of part 2 --- data/day10.input | 24 +++++ src/day10.rs | 224 +++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 4 +- 3 files changed, 251 insertions(+), 1 deletion(-) create mode 100644 data/day10.input create mode 100644 src/day10.rs diff --git a/data/day10.input b/data/day10.input new file mode 100644 index 0000000..7939634 --- /dev/null +++ b/data/day10.input @@ -0,0 +1,24 @@ +.###.#...#.#.##.#.####.. +.#....#####...#.######.. +#.#.###.###.#.....#.#### +##.###..##..####.#.####. +###########.#######.##.# +##########.#########.##. +.#.##.########.##...###. +###.#.##.#####.#.###.### +##.#####.##..###.#.##.#. +.#.#.#####.####.#..##### +.###.#####.#..#..##.#.## +########.##.#...######## +.####..##..#.###.###.#.# +....######.##.#.######.# +###.####.######.#....### +############.#.#.##.#### +##...##..####.####.#..## +.###.#########.###..#.## +#.##.#.#...##...#####..# +##.#..###############.## +##.###.#####.##.######.. +##.#####.#.#.##..####### +...#######.######...#### +#....#.#.#.####.#.#.#.## \ No newline at end of file diff --git a/src/day10.rs b/src/day10.rs new file mode 100644 index 0000000..9b8aebb --- /dev/null +++ b/src/day10.rs @@ -0,0 +1,224 @@ +use std::collections::{HashMap, HashSet}; + +pub fn read_map(raw: &str) -> Vec<(i32, i32)> { + let lines: Vec<&str> = raw.lines().map(|l| l.trim()).collect(); + let mut map = Vec::<(i32, i32)>::new(); + for x in 0 .. lines[0].len() { + for y in 0 .. lines.len() { + if lines[y].chars().nth(x) == Some('#') { + map.push((x as i32, y as i32)); + } + } + } + map +} + +fn angle(x1: i32, y1: i32, x2: i32, y2: i32) -> i64 { + // Axis are reverted to match the clockwise laser rotation beginning up. + let angle_f64 = (2.0 * std::f64::consts::PI - ((x1 - x2) as f64).atan2((y1 - y2) as f64)) % (2.0 * std::f64::consts::PI); + (angle_f64 * 1_000_000.0) as i64 +} + +fn squared_distance(x1: i32, y1: i32, x2: i32, y2: i32) -> i64 { + ((x1 - x2) as i64).pow(2) + ((y1 - y2) as i64).pow(2) +} + +pub fn find_best_location(map: &[(i32, i32)]) -> (usize, (i32, i32)) { + let mut best_nb_observable_asteroid = 0; + let (mut best_x, mut best_y) = (0, 0); + for (x1, y1) in map { + let mut angles = HashSet::::new(); + for (x2, y2) in map { + angles.insert(angle(*x1, *y1, *x2, *y2)); + } + let n = angles.len(); + if n > best_nb_observable_asteroid { + best_nb_observable_asteroid = n; + best_x = *x1; + best_y = *y1; + } + } + (best_nb_observable_asteroid, (best_x, best_y)) +} + +pub fn location_nth_vaporized_asteroid(pos: (i32, i32), map: &[(i32, i32)], n: usize) -> (i32, i32) { + // Angle -> [] + let mut asteroids = HashMap::>::new(); + + let (x1, y1) = pos; + for (x2, y2) in map { + let angle = angle(x1, y1, *x2 , *y2); + let dist = squared_distance(x1, y1, *x2 , *y2); + match asteroids.get_mut(&angle) { + Some (lineup_asteroids) => lineup_asteroids.push(((*x2, *y2), dist)), + None => { asteroids.insert(angle, vec![((*x2, *y2), dist)]); } + } + } + + let mut sorted_angles: Vec = asteroids.keys().copied().collect(); + sorted_angles.sort(); + + asteroids.values_mut().for_each(|lineup_asteroids| lineup_asteroids.sort_by(|(_, l1), (_, l2)| l1.cmp(l2))); + + dbg!(&sorted_angles); + dbg!(&asteroids); + //return (0, 0); + + let mut i = 1; + loop { + for angle in &sorted_angles { + if let Some (lineup_asteroids) = asteroids.get_mut(angle) { + let ((x, y), _) = lineup_asteroids.remove(0); + if i == n { + return (x, y) + } else if lineup_asteroids.is_empty() { + asteroids.remove(angle); + } + i += 1; + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn part1_sample_1() { + let raw_map = + ".#..# + ..... + ##### + ....# + ...##"; + let map = read_map(raw_map); + assert_eq!(find_best_location(&map).0, 8); + } + + #[test] + fn part1_sample_2() { + let raw_map = + "......#.#. + #..#.#.... + ..#######. + .#.#.###.. + .#..#..... + ..#....#.# + #..#....#. + .##.#..### + ##...#..#. + .#....####"; + let map = read_map(raw_map); + assert_eq!(find_best_location(&map).0, 33); + } + + #[test] + fn part1_sampl3() { + let raw_map = + "#.#...#.#. + .###....#. + .#....#... + ##.#.#.#.# + ....#.#.#. + .##..###.# + ..#...##.. + ..##....## + ......#... + .####.###."; + let map = read_map(raw_map); + assert_eq!(find_best_location(&map).0, 35); + } + + #[test] + fn part1_sample_4() { + let raw_map = + ".#..#..### + ####.###.# + ....###.#. + ..###.##.# + ##.##.#.#. + ....###..# + ..#.#..#.# + #..#.#.### + .##...##.# + .....#.#.."; + let map = read_map(raw_map); + assert_eq!(find_best_location(&map).0, 41); + } + + #[test] + fn part1_sample_5() { + let raw_map = + ".#..##.###...####### + ##.############..##. + .#.######.########.# + .###.#######.####.#. + #####.##.#.##.###.## + ..#####..#.######### + #################### + #.####....###.#.#.## + ##.################# + #####.##.###..####.. + ..######..##.####### + ####.##.####...##..# + .#####..#.######.### + ##...#.##########... + #.##########.####### + .####.#.###.###.#.## + ....##.##.###..##### + .#.#.###########.### + #.#.#.#####.####.### + ###.##.####.##.#..##"; + let map = read_map(raw_map); + assert_eq!(find_best_location(&map).0, 210); + } + + + #[test] + fn part2_sample_1() { + let raw_map = + ".#....#####...#.. + ##...##.#####..## + ##...#...#.#####. + ..#.....X...###.. + ..#.#.....#....##"; + let map = read_map(raw_map); + let pos = (8, 3); + let pos_200th = location_nth_vaporized_asteroid(pos, &map, 200); + dbg!(pos_200th); + assert_eq!(2, 210); + } + /* + + #[test] + fn part2_sample_2() { + let raw_map = + ".#..##.###...####### + ##.############..##. + .#.######.########.# + .###.#######.####.#. + #####.##.#.##.###.## + ..#####..#.######### + #################### + #.####....###.#.#.## + ##.################# + #####.##.###..####.. + ..######..##.####### + ####.##.####...##..# + .#####..#.######.### + ##...#.##########... + #.##########.####### + .####.#.###.###.#.## + ....##.##.###..##### + .#.#.###########.### + #.#.#.#####.####.### + ###.##.####.##.#..##"; + let map = read_map(raw_map); + let pos = find_best_location(&map).1; + let pos_200th = location_nth_vaporized_asteroid(pos, &map, 200); + dbg!(pos_200th); + assert_eq!(2, 210); + } + */ +} \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 99ea6e0..c025b79 100644 --- a/src/main.rs +++ b/src/main.rs @@ -10,6 +10,7 @@ mod day03; mod day06; mod day07; mod day08; +mod day10; mod day11; fn day01() -> String { @@ -71,7 +72,8 @@ fn day09() -> String { } fn day10() -> String { - format!("") + let map = day10::read_map(&fs::read_to_string("data/day10.input").unwrap()); + format!("part1: {}, part2: {}", day10::find_best_location(&map).0, "") } fn day11() -> String { -- 2.45.2