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
|
use std::io;
use std::io::BufRead;
use std::cmp::max;
use std::collections::HashSet;
fn parse_pt(l: &str) -> ((i32, i32), (i32, i32)) {
let i1 = l.find('<').unwrap();
let i2 = l[i1..].find(',').unwrap() + i1;
let i3 = l[i2..].find('>').unwrap() + i2;
let i4 = l[i3..].find('<').unwrap() + i3;
let i5 = l[i4..].find(',').unwrap() + i4;
let i6 = l[i5..].find('>').unwrap() + i5;
let s1 = &l[i1+1..i2];
let s2 = &l[i2+1..i3];
let s3 = &l[i4+1..i5];
let s4 = &l[i5+1..i6];
((s1.trim().parse().unwrap(), s2.trim().parse().unwrap()),
(s3.trim().parse().unwrap(), s4.trim().parse().unwrap()))
}
fn dist((x, y): (i32, i32), (u, v): (i32, i32)) -> i32 {
return ((u - x) as f32 * (u - x) as f32 + (v - y) as f32 * (v - y) as f32).sqrt() as i32;
}
pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
let dots: Vec<((i32, i32), (i32, i32))> =
reader.lines().map(|l| l.unwrap())
.map(|l| parse_pt(&l))
.collect();
let mut pts: Vec<_> = dots.iter().map(|&(xy, _)| xy).collect();
let vels: Vec<_> = dots.iter().map(|&(_, v)| v).collect();
let maxvel = vels.iter().map(|&xy| dist(xy, (0, 0)) + 1).max().unwrap();
let mut maxscore = -1;
let mut maxat;
let mut iter = 0;
loop {
let mut has_dot: HashSet<(i32, i32)> = HashSet::new();
let mut avg = (0, 0);
let mut score = 0;
for &xy in &pts {
if has_dot.contains(&xy) { score += 1; }
else { has_dot.insert(xy); }
avg.0 += xy.0;
avg.1 += xy.1;
}
avg.0 /= dots.len() as i32;
avg.1 /= dots.len() as i32;
let maxdist = pts.iter().map(|&xy| dist(xy, avg)).max().unwrap();
if score > maxscore {
maxscore = score;
maxat = (iter, pts.clone(), has_dot.clone());
if maxscore > dots.len() as i32 / 2 {
break;
}
}
let multiplier =
if maxdist > maxvel && maxdist > 100 { max(1, (maxdist - 100) / maxvel) }
else { 1 };
// println!("iter={} multiplier={} maxdist={} maxvel={}", iter, multiplier, maxdist, maxvel);
for i in 0..dots.len() {
pts[i].0 += multiplier * vels[i].0;
pts[i].1 += multiplier * vels[i].1;
}
iter += multiplier;
}
let mut part1 = String::new();
let part2 = maxat.0.to_string();
let pts = maxat.1;
let has_dot = maxat.2;
let minx = pts.iter().map(|&(x, _)| x).min().unwrap();
let miny = pts.iter().map(|&(_, y)| y).min().unwrap();
let maxx = pts.iter().map(|&(x, _)| x).max().unwrap();
let maxy = pts.iter().map(|&(_, y)| y).max().unwrap();
for y in miny..maxy+1 {
if y != miny { part1 += "\n"; }
for x in minx..maxx + 1 {
if has_dot.contains(&(x, y)) { part1 += "#"; }
else { part1 += "."; }
}
}
Ok((part1, part2))
}
|
