Skip to content

Instantly share code, notes, and snippets.

@djmcgill
Created February 4, 2023 18:54
Show Gist options
  • Save djmcgill/1f3b45ecbe6cb835d9da859463757fed to your computer and use it in GitHub Desktop.
Save djmcgill/1f3b45ecbe6cb835d9da859463757fed to your computer and use it in GitHub Desktop.
WIP 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)))));
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment