Day 8: Playground

Rust

Part 1 took a decent while, partly life getting in the way, partly as I was struggling with some Rust things like floats not being sortable without mucking around, plus some weird bugs trying to get collect to do everything that I eventually just rewrote to avoid.

I found the noisy_float crate which let me wrap f64 as a "real" r64 which meant no NaN which meant Ord which meant sort_by_cached_key() and the rest worked.

I'd planned how to partition the closest neighbour search, but the whole thing runs in 24ms so I didn't bother.

type Id = usize;
type Connection = (Id, Id);
type Circuit = HashSet<Id>;

#[derive(PartialEq)]
struct Point {
    x: usize,
    y: usize,
    z: usize,
}

impl FromStr for Point {
    type Err = Report;

    fn from_str(s: &str) -> Result<Self> {
        let mut parts = s.split(',');
        Ok(Point {
            x: parts.next().ok_or_eyre("missing x")?.parse()?,
            y: parts.next().ok_or_eyre("missing y")?.parse()?,
            z: parts.next().ok_or_eyre("missing z")?.parse()?,
        })
    }
}

impl Point {
    fn distance(&self, other: &Point) -> R64 {
        let dist = ((
            self.x.abs_diff(other.x).pow(2) +
            self.y.abs_diff(other.y).pow(2) +
            self.z.abs_diff(other.z).pow(2)) as f64)
            .sqrt();
        r64(dist)
    }
}

struct Boxes(Vec<Point>);

impl Boxes {
    fn closest(&self) -> Vec<Connection> {
        let mut closest = (0..self.0.len())
            .flat_map(|a| ((a + 1)..self.0.len()).map(move |b| (a, b)))
            .collect::<Vec<_>>();

        closest.sort_by_cached_key(|&(a, b)| self.0[a].distance(&self.0[b]));
        closest
    }

    fn connect_all(&self, p1_threshold: usize) -> Result<(usize, usize)> {
        let mut circuits: Vec<Circuit> = (0..self.0.len())
            .map(|id| HashSet::from_iter(iter::once(id)))
            .collect();

        let mut closest = self.closest().into_iter();
        let mut p1 = 0;
        let mut n = 0;
        loop {
            n += 1;
            let (a, b) = closest.next().ok_or_eyre("All connected already")?;
            let a_circ = circuits.iter().position(|c| c.contains(&a));
            let b_circ = circuits.iter().position(|c| c.contains(&b));
            match (a_circ, b_circ) {
                (None, None) => {
                    circuits.push(vec![a, b].into_iter().collect());
                }
                (None, Some(idx)) => {
                    circuits[idx].insert(a);
                }
                (Some(idx), None) => {
                    circuits[idx].insert(b);
                }
                (Some(a_idx), Some(b_idx)) if a_idx != b_idx => {
                    let keep_idx = a_idx.min(b_idx);
                    let rem_idx = a_idx.max(b_idx);

                    let drained = circuits.swap_remove(rem_idx);
                    // this position is still valid since we removed the later set
                    circuits[keep_idx].extend(drained);
                }
                _ => { /* already connected to same circuit */ }
            };

            if n == p1_threshold {
                circuits.sort_by_key(|set| set.len());
                circuits.reverse();
                p1 = circuits.iter().take(3).map(|set| set.len()).product();
            }
            if circuits.len() == 1 {
                let p2 = self.0[a].x * self.0[b].x;
                return Ok((p1, p2));
            }
        }
    }
}