Skip to content

Instantly share code, notes, and snippets.

@TrebledJ
Created December 2, 2022 19:41
Show Gist options
  • Save TrebledJ/7190c102579bfde273a7b74e90116b49 to your computer and use it in GitHub Desktop.
Save TrebledJ/7190c102579bfde273a7b74e90116b49 to your computer and use it in GitHub Desktop.
Advent of Code 2021 Day 22 Rust solution. Writeup: https://trebledj.github.io/posts/aoc-2021-day-22/
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,
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment