diff options
| -rw-r--r-- | 2018/src/day10.rs | 34 |
1 files changed, 29 insertions, 5 deletions
diff --git a/2018/src/day10.rs b/2018/src/day10.rs index 28da8de..99be244 100644 --- a/2018/src/day10.rs +++ b/2018/src/day10.rs @@ -1,5 +1,6 @@ use std::io; use std::io::BufRead; +use std::cmp::max; use std::collections::HashSet; fn parse_pt(l: &str) -> ((i32, i32), (i32, i32)) { @@ -19,6 +20,10 @@ fn parse_pt(l: &str) -> ((i32, i32), (i32, i32)) { (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()) @@ -28,15 +33,26 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { 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 = (-1, vec![], HashSet::new()); - for iter in 0..20000 { + 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; } - has_dot.insert(xy); + 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; @@ -46,10 +62,18 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { } } + 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 += vels[i].0; - pts[i].1 += vels[i].1; + pts[i].0 += multiplier * vels[i].0; + pts[i].1 += multiplier * vels[i].1; } + + iter += multiplier; } let mut part1 = String::new(); |