commit bba64a36e16913403868854c5467498dc816ae49
parent 5ffcef53935f6e2a70deb9079ba98475de33c812
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Tue, 10 Dec 2019 11:03:49 -0500
Add Rust solution for day 10
Diffstat:
3 files changed, 186 insertions(+), 0 deletions(-)
diff --git a/day-10/Makefile b/day-10/Makefile
@@ -0,0 +1,9 @@
+CC := g++
+CCFLAGS := --std=c++17 -Wall
+
+all: day-10-rust day-10.jl
+ julia day-10.jl
+ ./day-10-rust
+
+day-10-rust: day-10.rs
+ rustc $^ -o $@
diff --git a/day-10/day-10.rs b/day-10/day-10.rs
@@ -0,0 +1,141 @@
+use std::collections::HashMap;
+use std::collections::HashSet;
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+
+fn main() {
+ let input = BufReader::new(File::open("input.txt").unwrap())
+ .lines()
+ .map(|line| {
+ line.unwrap()
+ .trim()
+ .chars()
+ .map(|x| x == '#')
+ .collect::<Vec<bool>>()
+ })
+ .collect::<Vec<Vec<bool>>>();
+
+ println!("Rust:");
+ println!("Part 1:");
+ let (coord, num_obs) = part_1(&input);
+ println!("{} asteroids observed at {:?}", num_obs, coord);
+ println!("Part 2: {}", part_2(&input, coord));
+}
+
+fn gcd(mut x: i32, mut y: i32) -> i32 {
+ // Assumes both are positive.
+ x = x.abs();
+ y = y.abs();
+ while x > 0 && y > 0 {
+ x %= y;
+ if x != 0 {
+ y %= x;
+ }
+ }
+ x + y
+}
+
+fn line_of_sight(x_diff: i32, y_diff: i32) -> (i32, i32) {
+ // A hash to encode both x_diff and y_diff.
+ // Built such that stars along the same line of sight have the same hash.
+ // Guard against zeros.
+ if x_diff == 0 || y_diff == 0 {
+ return (x_diff.signum(), y_diff.signum());
+ }
+ let gcd = gcd(x_diff, y_diff);
+ (x_diff / gcd, y_diff / gcd)
+}
+
+fn coord_to_angle(coord: &(i32, i32)) -> f64 {
+ // Convert to angle ranging from 0 to 2 * pi.
+ // Designed such that angles are measured wrt to (0, -1) clockwise.
+ let x = coord.0 as f64;
+ let y = coord.1 as f64;
+ // |
+ // ---+---> x
+ // |
+ // V y
+ // Count angle from north.
+ let mut angle = y.atan2(x) + 0.5 * std::f64::consts::PI;
+ if angle < 0.0 {
+ angle += 2.0 * std::f64::consts::PI;
+ }
+ angle
+}
+
+fn part_1(input: &Vec<Vec<bool>>) -> ((i32, i32), usize) {
+ // Record coordinates.
+ let mut detected = HashMap::<(i32, i32), HashSet<(i32, i32)>>::new();
+ for x in 0..input.len() {
+ for y in 0..input[0].len() {
+ if input[y][x] {
+ // If there's an asteroid, compute line of sight with all others.
+ let mut view_curr = HashSet::<(i32, i32)>::new();
+ for (coord, view) in detected.iter_mut() {
+ view.insert(line_of_sight(x as i32 - coord.0, y as i32 - coord.1));
+ view_curr.insert(line_of_sight(coord.0 - x as i32, coord.1 - y as i32));
+ }
+ detected.insert((x as i32, y as i32), view_curr);
+ }
+ }
+ }
+
+ detected
+ .iter()
+ .map(|(&key, val)| (key, val.len()))
+ .max_by_key(|(_, len)| *len)
+ .unwrap()
+}
+
+fn part_2(input: &Vec<Vec<bool>>, station: (i32, i32)) -> i32 {
+ // Record detected asteroids sorted by line of sight angle.
+ let mut detected = HashMap::<(i32, i32), Vec<(i32, i32)>>::new();
+ for x in 0..input.len() {
+ for y in 0..input[0].len() {
+ if input[y][x] && (x as i32, y as i32) != station {
+ let x_diff = x as i32 - station.0;
+ let y_diff = y as i32 - station.1;
+ detected
+ .entry(line_of_sight(x_diff, y_diff))
+ .or_default()
+ .push((x_diff, y_diff));
+ }
+ }
+ }
+ // Sort line of sight by angle, which starts CW from north.
+ let mut los_sorted = detected.keys().cloned().collect::<Vec<(i32, i32)>>();
+ los_sorted.sort_unstable_by(|a, b| {
+ coord_to_angle(a)
+ .partial_cmp(&coord_to_angle(b))
+ .unwrap_or(std::cmp::Ordering::Less)
+ });
+ // Count number of asteroids in each los.
+ let mut los_count = detected
+ .iter()
+ .map(|(&key, val)| (key, val.len()))
+ .collect::<HashMap<_, _>>();
+ // Vaporize by going around sorted los until we hit 200th.
+ let mut num_vaporized = 0;
+ let mut last_los;
+ 'vaporize: loop {
+ for key in &los_sorted {
+ if los_count[&key] > 0 {
+ *los_count.get_mut(&key).unwrap() -= 1;
+ num_vaporized += 1;
+ last_los = *key;
+ if num_vaporized == 200 {
+ break 'vaporize;
+ }
+ }
+ }
+ }
+ // Sort asteroids in that los and count back.
+ let mut asteroids_in_los = detected[&last_los].clone();
+ asteroids_in_los.sort_unstable_by_key(|&(x, y)| x ^ 2 + y ^ 2);
+ asteroids_in_los.reverse();
+ let jackpot = asteroids_in_los[los_count[&last_los]];
+ // Convert relative coordinates to absolute one.
+ let jackpot = ((jackpot.0 + station.0), (jackpot.1 + station.1));
+ jackpot.0 * 100 + jackpot.1
+}
diff --git a/day-10/input.txt b/day-10/input.txt
@@ -0,0 +1,36 @@
+.#..#..#..#...#..#...###....##.#....
+.#.........#.#....#...........####.#
+#..##.##.#....#...#.#....#..........
+......###..#.#...............#.....#
+......#......#....#..##....##.......
+....................#..............#
+..#....##...#.....#..#..........#..#
+..#.#.....#..#..#..#.#....#.###.##.#
+.........##.#..#.......#.........#..
+.##..#..##....#.#...#.#.####.....#..
+.##....#.#....#.......#......##....#
+..#...#.#...##......#####..#......#.
+##..#...#.....#...###..#..........#.
+......##..#.##..#.....#.......##..#.
+#..##..#..#.....#.#.####........#.#.
+#......#..........###...#..#....##..
+.......#...#....#.##.#..##......#...
+.............##.......#.#.#..#...##.
+..#..##...#...............#..#......
+##....#...#.#....#..#.....##..##....
+.#...##...........#..#..............
+.............#....###...#.##....#.#.
+#..#.#..#...#....#.....#............
+....#.###....##....##...............
+....#..........#..#..#.......#.#....
+#..#....##.....#............#..#....
+...##.............#...#.....#..###..
+...#.......#........###.##..#..##.##
+.#.##.#...##..#.#........#.....#....
+#......#....#......#....###.#.....#.
+......#.##......#...#.#.##.##...#...
+..#...#.#........#....#...........#.
+......#.##..#..#.....#......##..#...
+..##.........#......#..##.#.#.......
+.#....#..#....###..#....##..........
+..............#....##...#.####...##.