Advent of Code 2021 Day 22 Rust solution. Writeup: https://trebledj.github.io/posts/aoc-2021-day-22/

d22.rs

use regex::Regex;
use std::collections::{HashSet, LinkedList};
use std::fs;

type Set = HashSet<(cube_t, cube_t, cube_t)>;

#[allow(non_camel_case_types)]
type cube_t = i64;
type Cuboid = ((cube_t, cube_t), (cube_t, cube_t), (cube_t, cube_t));
struct Command(bool, Cuboid);

fn main() {
    let filename = "../input/d22.txt";

    let contents = fs::read_to_string(filename).unwrap();
    let cmds = parse(contents);

    println!("part1: {}", part1(&cmds));
    println!("part2: {}", part2(&cmds));
}

fn parse(contents: String) -> Vec<Command> {
    let re =
        Regex::new(r"(on|off) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)").unwrap();
    contents
        .lines()
        .map(|s| {
            for cap in re.captures_iter(s) {
                return Command(
                    cap[1].eq("on"),
                    (
                        (
                            cap[2].parse::<cube_t>().unwrap(),
                            cap[3].parse::<cube_t>().unwrap(),
                        ),
                        (
                            cap[4].parse::<cube_t>().unwrap(),
                            cap[5].parse::<cube_t>().unwrap(),
                        ),
                        (
                            cap[6].parse::<cube_t>().unwrap(),
                            cap[7].parse::<cube_t>().unwrap(),
                        ),
                    ),
                );
            }
            unreachable!("aaaaaah")
        })
        .collect()
}

fn part1(cmds: &Vec<Command>) -> u32 {
    // Naive approach.
    let mut set: Set = HashSet::new();
    let r = 50;
    for &Command(onoff, ((x1_, x2_), (y1_, y2_), (z1_, z2_))) in cmds {
        let x1 = x1_.max(-r);
        let x2 = x2_.min(r);
        let y1 = y1_.max(-r);
        let y2 = y2_.min(r);
        let z1 = z1_.max(-r);
        let z2 = z2_.min(r);
        for i in x1..=x2 {
            for j in y1..=y2 {
                for k in z1..=z2 {
                    if onoff {
                        set.insert((i, j, k));
                    } else {
                        set.remove(&(i, j, k));
                    }
                }
            }
        }
    }

    set.len() as u32
}

fn part2(cmds: &Vec<Command>) -> u64 {
    // Set Union approach.
    let mut alternating_unions: LinkedList<Vec<usize>> = LinkedList::new();
    let lookup = cmds.iter().map(|&Command(_, c)| c).collect::<Vec<_>>();
    for (i, &Command(on, _)) in cmds.iter().enumerate() {
        for v in alternating_unions.iter_mut() {
            v.push(i);
        }
        if (alternating_unions.len() % 2 == 0) == on {
            // A new union term is added if "on" and even, or "off" and odd.
            let mut v = vec![i];
            v.reserve(cmds.len() - i);
            alternating_unions.push_back(v);
        }
    }

    /**
     * eval_union computes the number of points in the union of sets `u`.
     *
     * lookup: A lookup table of cuboids. Our sets will be represented as an array of indices (storing one i32 instead of six i32's).
     * add: Whether the current iteration adds or subtracts the union.
     * int: The current intersected cuboid.
     * u: The set of cuboids in the current union.
     */
    fn eval_union(lookup: &Vec<Cuboid>, add: bool, int: Cuboid, u: &[usize]) -> i64 {
        u.iter()
            .enumerate()
            .map(|(i, &tag)| match intersect(&int, &lookup[tag]) {
                Some(next_int) => {
                    let v = eval_cuboid(&next_int) as i64;
                    let rest = eval_union(lookup, !add, next_int, &u[i + 1..]);
                    if add {
                        rest + v
                    } else {
                        rest - v
                    }
                }
                // No intersection. No need to evaluate deeper, since any intersection with the empty set will just be the empty set.
                None => 0,
            })
            .sum::<i64>()
    }

    let scope = ((-200000, 200000), (-200000, 200000), (-200000, 200000));
    alternating_unions
        .iter()
        .enumerate()
        .map(|(i, u)| eval_union(&lookup, i % 2 == 0, scope, &u[..]))
        .sum::<i64>() as u64
}

fn eval_cuboid(((x1, x2), (y1, y2), (z1, z2)): &Cuboid) -> u64 {
    ((x2 - x1 + 1) * (y2 - y1 + 1) * (z2 - z1 + 1)) as u64
}

fn intersect((x1, y1, z1): &Cuboid, (x2, y2, z2): &Cuboid) -> Option<Cuboid> {
    fn range_intersect(
        &(a1, a2): &(cube_t, cube_t),
        &(b1, b2): &(cube_t, cube_t),
    ) -> Option<(cube_t, cube_t)> {
        if a2 < b1 || b2 < a1 {
            None
        } else if a1 <= b1 && b2 <= a2 {
            Some((b1, b2))
        } else if b1 <= a1 && a2 <= b2 {
            Some((a1, a2))
        } else if a1 <= b1 && a2 <= b2 {
            Some((b1, a2))
        } else if b1 <= a1 && b2 <= a2 {
            Some((a1, b2))
        } else {
            None
        }
    }
    match (
        range_intersect(x1, x2),
        range_intersect(y1, y2),
        range_intersect(z1, z2),
    ) {
        (Some(x), Some(y), Some(z)) => Some((x, y, z)),
        _ => None,
    }
}