Created
December 2, 2022 19:41
-
-
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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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