Advertisement
krzysz00

Advent of code, day 20

Dec 20th, 2017
175
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env run-cargo-script
  2. // cargo-deps: lazy_static, regex, euclid
  3. extern crate euclid;
  4. use euclid::{Vector3D,vec3};
  5.  
  6. #[macro_use] extern crate lazy_static;
  7. extern crate regex;
  8. use regex::Regex;
  9.  
  10. use std::str::FromStr;
  11. use std::error::Error;
  12. use std::io::{stdin,BufRead};
  13.  
  14. type Vec3 = Vector3D<i64>;
  15.  
  16. use std::collections::HashSet;
  17.  
  18. #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
  19. struct Particle {
  20.     p: Vec3,
  21.     v: Vec3,
  22.     a: Vec3,
  23. }
  24.  
  25. impl FromStr for Particle {
  26.     type Err = Box<Error>;
  27.  
  28.     fn from_str(input: &str) -> Result<Self, Self::Err> {
  29.         lazy_static! {
  30.             static ref PARSER: Regex =
  31.                 Regex::new(r"^p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>$").unwrap();
  32.         };
  33.  
  34.         let mut captures_iter = PARSER.captures_iter(input);
  35.         let captures = captures_iter.next().ok_or("Input does not match format")?;
  36.         let position = vec3(captures[1].parse()?, captures[2].parse()?, captures[3].parse()?);
  37.         let velocity = vec3(captures[4].parse()?, captures[5].parse()?, captures[6].parse()?);
  38.         let accel = vec3(captures[7].parse()?, captures[8].parse()?, captures[9].parse()?);
  39.         Ok(Particle {p: position, v: velocity, a: accel })
  40.     }
  41. }
  42.  
  43. impl Particle {
  44.     pub fn update(self) -> Self {
  45.         let new_v = self.v + self.a;
  46.         let new_p = self.p + new_v;
  47.         Particle {p: new_p, v: new_v, a: self.a}
  48.     }
  49.  
  50.     pub fn l1_pos(&self) -> i64 {
  51.         self.p.x.abs() + self.p.y.abs() + self.p.z.abs()
  52.     }
  53.  
  54. }
  55.  
  56. fn update_system(system: &mut Vec<Particle>) {
  57.     for p in system {
  58.         *p = p.update()
  59.     }
  60. }
  61.  
  62. const STABILITY_TIMEOUT: usize = 1000;
  63. fn solve_a(system_a: &mut Vec<Particle>) -> usize {
  64.     let mut min_coord = system_a.len() + 1;
  65.     let mut stable_iters = 0;
  66.     loop {
  67.         if let Some((idx, _)) = system_a.iter().enumerate().min_by_key(|&(_, p)| p.l1_pos()) {
  68.             if idx != min_coord {
  69.                 stable_iters = 0;
  70.                 min_coord = idx
  71.             }
  72.             if stable_iters > STABILITY_TIMEOUT {
  73.                 break;
  74.             }
  75.             stable_iters += 1;
  76.         }
  77.         else {
  78.             panic!("No minima");
  79.         }
  80.         update_system(system_a);
  81.     }
  82.     min_coord
  83. }
  84.  
  85. fn solve_b(system_b: &mut Vec<Particle>) {
  86.     let mut collisions = HashSet::<Particle>::new();
  87.     let mut no_collision_count = 0;
  88.     loop {
  89.         for (idx_i, i) in system_b.iter().enumerate() {
  90.             if idx_i == 0 { continue; }
  91.             for j in &system_b[..idx_i] {
  92.                 if i.p == j.p {
  93.                     collisions.insert(i.clone());
  94.                     collisions.insert(j.clone());
  95.                 }
  96.             }
  97.         }
  98.  
  99.         if collisions.len() != 0 {
  100.             no_collision_count = 0;
  101.         }
  102.  
  103.         if no_collision_count > STABILITY_TIMEOUT {
  104.             break;
  105.         }
  106.  
  107.         system_b.retain(|p| !collisions.contains(p));
  108.         collisions.clear();
  109.         no_collision_count += 1;
  110.  
  111.         update_system(system_b);
  112.     }
  113. }
  114.  
  115. fn main() {
  116.     let stdin = stdin();
  117.     let handle = stdin.lock();
  118.  
  119.     let mut system_a: Vec<Particle> = handle.lines().map(|l| l.expect("I/O error")
  120.                                                          .parse().expect("Parse error")).collect();
  121.     let mut system_b = system_a.clone();
  122.  
  123.     println!("Long term minimum is {}", solve_a(&mut system_a));
  124.  
  125.     solve_b(&mut system_b);
  126.     println!("Uncollided particles count: {}", system_b.len());
  127. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement