1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
use std::io::{self, BufRead};
use std::collections::BTreeMap;
#[derive(Clone, Copy, Debug, PartialEq)]
struct Asteroid {
x: f64,
y: f64,
}
impl Asteroid {
fn new(x: f64, y: f64) -> Asteroid {
Asteroid {
x,
y,
}
}
}
#[derive(Clone, Copy, Debug)]
struct Pair<'a> {
first: &'a Asteroid,
second: &'a Asteroid,
}
type Asteroids = Vec<Asteroid>;
fn read_map() -> Asteroids {
let mut asteroids: Asteroids = Vec::new();
let stdin = io::stdin();
for (y, line) in stdin.lock().lines().enumerate() {
match line {
Ok(s) => {
for (x, byte) in s.as_bytes().iter().enumerate() {
if *byte == b'#' {
// println!("Asteroid found at {}, {}.", x, y);
asteroids.push(Asteroid::new(x as f64, y as f64));
}
}
},
_ => eprintln!("Failed to parse input at row {}.", y),
}
}
asteroids
}
fn calc_distance_angle(observer: &Asteroid, observee: &Asteroid) -> (f64, f64)
{
let xdiff = observee.x - observer.x;
let ydiff = observer.y - observee.y;
let distance = f64::sqrt(xdiff.powf(2.0) + ydiff.powf(2.0));
let mut angle = f64::atan2(xdiff,ydiff);
if angle.is_sign_negative() {
angle += std::f64::consts::PI*2.0;
}
(distance, angle)
}
fn float_encode(f: f64) -> i128 {
(f * f64::powf(10.0, 37.0)) as i128
}
fn float_decode(i: i128) -> f64 {
(i as f64 / i128::pow(10, 37) as f64)
}
fn main() {
println!("Reading map");
let asteroids = read_map();
let mut angles = BTreeMap::new();
println!("Calculating distances between all asteroids");
for observer in &asteroids {
for observee in &asteroids {
if observer == observee { continue; }
let ( distance, angle ) = calc_distance_angle(observer, observee);
let dist_int = float_encode(distance);
let ang_int = float_encode(angle);
let pair = Pair {first: observer, second: observee};
let distances:&mut BTreeMap<i128, Vec<Pair>> =
angles.entry(ang_int).or_insert(BTreeMap::new());
distances.entry(dist_int).or_insert(Vec::new()).push(pair);
}
}
println!("Building huge angle and distance sorted datastructure of all asteroids.");
let mut huge:Vec<Vec<(Asteroid, f64, f64, Asteroid)>> = asteroids.iter()
.map(|asteroid| { let a:Vec<(Asteroid, f64, f64, Asteroid)> = angles.iter()
.map(|(angle, distances)| {
let a:Vec<(Asteroid, f64, f64, Asteroid)> = distances.iter()
.map(|(distance, pairs)| pairs.iter()
.filter(|pair| if asteroid == pair.first {
true
} else {
false
})
.map(move |pair| { (
*asteroid,
float_decode(*angle),
float_decode(distance.clone()),
*pair.second
)})
).flatten().collect(); a
}).flatten().collect() ; a
}).collect();
println!("Creating vector merely containing visible asteroids");
let visible_asteroids:Vec<usize> = huge.iter()
.map(|i| { let (_, n) = i.iter()
.fold((std::f64::consts::PI*3.0, 0),
|( ang, res ), (_asteroid, angle, _distance, _other)|
{
if f64::abs(ang - *angle) < 0.00000001 {
( *angle, res )
} else {
( *angle, res + 1)
} }); n
}
).collect();
let highest_no_visible_asteroids = visible_asteroids.iter().max().unwrap();
let mut best_asteroid = 0;
for ( which, val ) in visible_asteroids.iter().enumerate() {
if val == highest_no_visible_asteroids {
best_asteroid = which;
}
}
println!("Found out that {} other asteroids can be seen from the best asteroid.",
visible_asteroids[best_asteroid]);
let mut no_zapped = 0;
let mut index = 0;
let mut last_angle = -1.0;
println!("Powering up lazer...");
loop {
if index >= huge[best_asteroid].len() {
if index == 1 {
eprintln!("Not enough asteroids to zap!");
break;
}
index = 0;
}
let short = huge[best_asteroid][index];
if short.1 != last_angle {
let (_, angle, _, zapped_asteroid) = huge[best_asteroid].remove(index);
last_angle = angle;
no_zapped += 1;
if no_zapped == 200 {
println!("\rLast asteroid zapped was at {:?} {:?}",
zapped_asteroid.x, zapped_asteroid.y);
break;
}
} else {
index += 1;
}
}
}
|
