WIP aoc2018d23.rs

aoc2018d23.rs

use regex::Regex;
use std::{
    collections::{HashMap, HashSet},
    hash::Hash,
    str::FromStr,
};

// const INPUT: &str = REAL;
const INPUT: &str = TEST2;

type Coord = (i64, i64, i64);
type Bot = (Coord, i64);

fn main() {
    // d1
    let (largest_radius_bot, non_largest_bots) = parse_d1();
    let ((target_x, target_y, target_z), target_r) = largest_radius_bot;
    // we're always in range of ourself
    let d1 = 1 + non_largest_bots
        .into_iter()
        .map(|((x, y, z), _)| (x - target_x).abs() + (y - target_y).abs() + (z - target_z).abs())
        .filter(|d| *d <= target_r)
        .count();

    // d2
    let bots = parse_d2();

    let mut x_starts_with_ix = vec![];
    let mut x_ends_with_ix = vec![];
    let mut y_starts_with_ix = vec![];
    let mut y_ends_with_ix = vec![];
    let mut z_starts_with_ix = vec![];
    let mut z_ends_with_ix = vec![];

    for (ix, ((x, y, z), r)) in bots.into_iter().enumerate() {
        x_starts_with_ix.push((x - r, ix)); // off by 1?
        x_ends_with_ix.push((x + r, ix));
        y_starts_with_ix.push((y - r, ix)); // off by 1?
        y_ends_with_ix.push((y + r, ix));
        z_starts_with_ix.push((z - r, ix)); // off by 1?
        z_ends_with_ix.push((z + r, ix));
    }
    // sort in reverse so we can pop the smallest
    x_starts_with_ix.sort_by_key(|(x, _)| -*x);
    x_ends_with_ix.sort_by_key(|(x, _)| -*x);
    y_starts_with_ix.sort_by_key(|(y, _)| -*y);
    y_ends_with_ix.sort_by_key(|(y, _)| -*y);
    z_starts_with_ix.sort_by_key(|(z, _)| -*z);
    z_ends_with_ix.sort_by_key(|(z, _)| -*z);

    // for two ix_0 and ix_1, where (wlog) ix_0 < ix_1,
    // for each axis x,y,z, if there was a collision and how many ixs were there (or 0 if not)
    let mut collisions = HashMap::<(usize, usize), (u32, u32, u32)>::default();

    let mut active_x_ranges = HashSet::<usize>::default();
    loop {
        match (x_starts_with_ix.last(), x_ends_with_ix.last()) {
            (Some(next_start), Some(next_end)) => todo!(), // which is smaller
            (None, Some(next_end)) => todo!(),             // finish up
            (None, None) => break,                         // we're done
            _ => panic!("how can we have a start after the last end?"),
        }
    }
    // TODO: same for y and z
    // TODO: of the ranges that collided on all 3 axes, the "actual" overlaps is the min of x,y,z overlaps
    // TODO: which coord has the largest (how to find this??)

    println!("{}", d1);
}

fn parse_d1() -> (Bot, Vec<Bot>) {
    let mut largest_radius_bot: Option<Bot> = None;
    let mut non_largest_bots: Vec<Bot> = vec![];

    let re = Regex::new(r"^pos=<(-?\d+),(-?\d+),(-?\d+)>, r=(\d+)$").unwrap();
    for line in INPUT.lines() {
        let captures = re.captures(line).unwrap();
        let bot = (
            (
                i64::from_str(&captures[1]).unwrap(),
                i64::from_str(&captures[2]).unwrap(),
                i64::from_str(&captures[3]).unwrap(),
            ),
            i64::from_str(&captures[4]).unwrap(),
        );
        let largest_radius = largest_radius_bot.map(|(_, r)| r).unwrap_or_default();
        if bot.1 > largest_radius {
            if let Some(old_largest) = largest_radius_bot.take() {
                // the old largest bot was never stored in the vec
                non_largest_bots.push(old_largest);
            }
            largest_radius_bot = Some(bot);
        } else {
            non_largest_bots.push(bot);
        }
    }
    (largest_radius_bot.unwrap(), non_largest_bots)
}

fn parse_d2() -> Vec<Bot> {
    let mut bots: Vec<Bot> = vec![];

    let re = Regex::new(r"^pos=<(-?\d+),(-?\d+),(-?\d+)>, r=(\d+)$").unwrap();
    for line in INPUT.lines() {
        let captures = re.captures(line).unwrap();
        let x = i64::from_str(&captures[1]).unwrap();
        let y = i64::from_str(&captures[2]).unwrap();
        let z = i64::from_str(&captures[3]).unwrap();

        let bot = (
            to_diag_space((x, y, z)),
            i64::from_str(&captures[4]).unwrap(),
        );

        bots.push(bot);
    }
    bots
}

// okay we're going to shift the coord space by 45deg in two axes. This means that our
// "spheres" are actually squares
// x' = x+y+z
// y' = -x+y+z
// z' = x-y+z
fn to_diag_space(c: Coord) -> Coord {
    let (x, y, z) = c;
    (z + y + x, z + y - x, z + x - y)
}

// x' - y' = 2x
// x' - z' = 2y
fn from_diag_space(c: Coord) -> Coord {
    let (x_prime, y_prime, z_prime) = c;
    let x = (x_prime - y_prime) / 2;
    let y = (x_prime - z_prime) / 2;
    let z = x_prime - x - y;

    // let's just check we haven't accidentally picked a coord that is unrepresentable
    // in ints in the new basis
    // if this is a problem, can start multiplying things by 2
    debug_assert_eq!(x * 2, x_prime - y_prime);
    debug_assert_eq!(y * 2, x_prime - z_prime);
    (x, y, z)
}

const REAL: &str = include_str!("input.txt");
const TEST: &str = "\
pos=<0,0,0>, r=4
pos=<1,0,0>, r=1
pos=<4,0,0>, r=3
pos=<0,2,0>, r=1
pos=<0,5,0>, r=3
pos=<0,0,3>, r=1
pos=<1,1,1>, r=1
pos=<1,1,2>, r=1
pos=<1,3,1>, r=1
";

const TEST2: &str = "\
pos=<10,12,12>, r=2
pos=<12,14,12>, r=2
pos=<16,12,12>, r=4
pos=<14,14,14>, r=6
pos=<50,50,50>, r=200
pos=<10,10,10>, r=5
";

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn coord_shift() {
        for x in 0..50 {
            for y in 0..50 {
                for z in 0..50 {
                    println!("(X,Y,Z): {:?}", (x, y, z));
                    assert_eq!((x, y, z), from_diag_space(dbg!(to_diag_space((x, y, z)))));
                }
            }
        }
    }
}