day-10.rs (4599B)
1 use std::collections::HashMap;
2 use std::collections::HashSet;
3 use std::fs::File;
4 use std::io::prelude::*;
5 use std::io::BufReader;
6
7 fn main() {
8 let input = BufReader::new(File::open("input.txt").unwrap())
9 .lines()
10 .map(|line| {
11 line.unwrap()
12 .trim()
13 .chars()
14 .map(|x| x == '#')
15 .collect::<Vec<bool>>()
16 })
17 .collect::<Vec<Vec<bool>>>();
18
19 println!("Rust:");
20 println!("Part 1:");
21 let (coord, num_obs) = part_1(&input);
22 println!("{} asteroids observed at {:?}", num_obs, coord);
23 println!("Part 2: {}", part_2(&input, coord));
24 }
25
26 fn gcd(mut x: i32, mut y: i32) -> i32 {
27 // Assumes both are positive.
28 x = x.abs();
29 y = y.abs();
30 while x > 0 && y > 0 {
31 x %= y;
32 if x != 0 {
33 y %= x;
34 }
35 }
36 x + y
37 }
38
39 fn line_of_sight(x_diff: i32, y_diff: i32) -> (i32, i32) {
40 // A hash to encode both x_diff and y_diff.
41 // Built such that stars along the same line of sight have the same hash.
42 // Guard against zeros.
43 if x_diff == 0 || y_diff == 0 {
44 return (x_diff.signum(), y_diff.signum());
45 }
46 let gcd = gcd(x_diff, y_diff);
47 (x_diff / gcd, y_diff / gcd)
48 }
49
50 fn coord_to_angle(coord: &(i32, i32)) -> f64 {
51 // Convert to angle ranging from 0 to 2 * pi.
52 // Designed such that angles are measured wrt to (0, -1) clockwise.
53 let x = coord.0 as f64;
54 let y = coord.1 as f64;
55 // |
56 // ---+---> x
57 // |
58 // V y
59 // Count angle from north.
60 let mut angle = y.atan2(x) + 0.5 * std::f64::consts::PI;
61 if angle < 0.0 {
62 angle += 2.0 * std::f64::consts::PI;
63 }
64 angle
65 }
66
67 fn part_1(input: &Vec<Vec<bool>>) -> ((i32, i32), usize) {
68 // Record coordinates.
69 let mut detected = HashMap::<(i32, i32), HashSet<(i32, i32)>>::new();
70 for x in 0..input.len() {
71 for y in 0..input[0].len() {
72 if input[y][x] {
73 // If there's an asteroid, compute line of sight with all others.
74 let mut view_curr = HashSet::<(i32, i32)>::new();
75 for (coord, view) in detected.iter_mut() {
76 view.insert(line_of_sight(x as i32 - coord.0, y as i32 - coord.1));
77 view_curr.insert(line_of_sight(coord.0 - x as i32, coord.1 - y as i32));
78 }
79 detected.insert((x as i32, y as i32), view_curr);
80 }
81 }
82 }
83
84 detected
85 .iter()
86 .map(|(&key, val)| (key, val.len()))
87 .max_by_key(|(_, len)| *len)
88 .unwrap()
89 }
90
91 fn part_2(input: &Vec<Vec<bool>>, station: (i32, i32)) -> i32 {
92 // Record detected asteroids sorted by line of sight angle.
93 let mut detected = HashMap::<(i32, i32), Vec<(i32, i32)>>::new();
94 for x in 0..input.len() {
95 for y in 0..input[0].len() {
96 if input[y][x] && (x as i32, y as i32) != station {
97 let x_diff = x as i32 - station.0;
98 let y_diff = y as i32 - station.1;
99 detected
100 .entry(line_of_sight(x_diff, y_diff))
101 .or_default()
102 .push((x_diff, y_diff));
103 }
104 }
105 }
106 // Sort line of sight by angle, which starts CW from north.
107 let mut los_sorted = detected.keys().cloned().collect::<Vec<(i32, i32)>>();
108 los_sorted.sort_unstable_by(|a, b| {
109 coord_to_angle(a)
110 .partial_cmp(&coord_to_angle(b))
111 .unwrap_or(std::cmp::Ordering::Less)
112 });
113 // Count number of asteroids in each los.
114 let mut los_count = detected
115 .iter()
116 .map(|(&key, val)| (key, val.len()))
117 .collect::<HashMap<_, _>>();
118 // Vaporize by going around sorted los until we hit 200th.
119 let mut num_vaporized = 0;
120 let mut last_los;
121 'vaporize: loop {
122 for key in &los_sorted {
123 if los_count[&key] > 0 {
124 *los_count.get_mut(&key).unwrap() -= 1;
125 num_vaporized += 1;
126 last_los = *key;
127 if num_vaporized == 200 {
128 break 'vaporize;
129 }
130 }
131 }
132 }
133 // Sort asteroids in that los and count back.
134 let mut asteroids_in_los = detected[&last_los].clone();
135 asteroids_in_los.sort_unstable_by_key(|&(x, y)| x ^ 2 + y ^ 2);
136 asteroids_in_los.reverse();
137 let jackpot = asteroids_in_los[los_count[&last_los]];
138 // Convert relative coordinates to absolute one.
139 let jackpot = ((jackpot.0 + station.0), (jackpot.1 + station.1));
140 jackpot.0 * 100 + jackpot.1
141 }