diff options
Diffstat (limited to 'src/bin/day_22.rs')
| -rw-r--r-- | src/bin/day_22.rs | 277 |
1 files changed, 277 insertions, 0 deletions
diff --git a/src/bin/day_22.rs b/src/bin/day_22.rs new file mode 100644 index 0000000..5dee0da --- /dev/null +++ b/src/bin/day_22.rs @@ -0,0 +1,277 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{i32 as nom_i32, line_ending}, + combinator::{map, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_22.txt")?; + let instructions = parse_instructions(&input).unwrap().1; + { + let mut octtree_50 = OctTree::with_bounds(Block { + min_x: -50, + max_x: 51, + min_y: -50, + max_y: 51, + min_z: -50, + max_z: 51, + }); + for instruction in &instructions { + octtree_50.set_block(&instruction.bounds, instruction.new_state); + } + dbg!(octtree_50.count_on_blocks()); + } + + { + let mut octtree = OctTree::with_bounds(Block { + min_x: instructions + .iter() + .map(|i| i.bounds.min_x) + .min() + .unwrap_or(0), + max_x: instructions + .iter() + .map(|i| i.bounds.max_x) + .max() + .unwrap_or(0), + min_y: instructions + .iter() + .map(|i| i.bounds.min_y) + .min() + .unwrap_or(0), + max_y: instructions + .iter() + .map(|i| i.bounds.max_y) + .max() + .unwrap_or(0), + min_z: instructions + .iter() + .map(|i| i.bounds.min_z) + .min() + .unwrap_or(0), + max_z: instructions + .iter() + .map(|i| i.bounds.max_z) + .max() + .unwrap_or(0), + }); + for instruction in &instructions { + octtree.set_block(&instruction.bounds, instruction.new_state); + } + dbg!(octtree.count_on_blocks()); + } + + Ok(()) +} + +#[derive(Clone)] +struct OctTree { + bounds: Block, + data: OctTreeData, +} + +impl OctTree { + fn with_bounds(bounds: Block) -> OctTree { + OctTree { + bounds, + data: OctTreeData::default(), + } + } + + fn set_block(&mut self, bounds: &Block, new_val: bool) { + if bounds.completely_covers(&self.bounds) { + self.data = OctTreeData::Same(new_val); + } else if bounds.intersects(&self.bounds) { + match &mut self.data { + OctTreeData::Same(current_val) => { + if *current_val != new_val { + self.split(); + self.set_block(bounds, new_val); + } + } + OctTreeData::Diverse(ref mut subtrees) => { + for sub in subtrees.iter_mut() { + sub.set_block(bounds, new_val); + } + self.try_join(); + } + }; + } + } + + fn split(&mut self) { + if let OctTreeData::Same(current_value) = &self.data { + let subdata = OctTreeData::Same(*current_value); + let chunk_labels = [0, 1, 2, 3, 4, 5, 6, 7]; + + self.data = OctTreeData::Diverse(Box::new(chunk_labels.map(|label| OctTree { + bounds: self.bounds.oct_chunk(label), + data: subdata.clone(), + }))) + } + } + + fn try_join(&mut self) { + if let OctTreeData::Diverse(subtrees) = &self.data { + if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::Same(true))) + { + self.data = OctTreeData::Same(true); + } else if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::Same(false))) + { + self.data = OctTreeData::Same(false); + } + } + } + + fn count_on_blocks(&self) -> usize { + match &self.data { + OctTreeData::Same(false) => 0, + OctTreeData::Same(true) => self.bounds.volume(), + OctTreeData::Diverse(subtrees) => { + subtrees.iter().map(|sub| sub.count_on_blocks()).sum() + } + } + } +} + +#[derive(Clone)] +enum OctTreeData { + Same(bool), + Diverse(Box<[OctTree; 8]>), +} + +impl Default for OctTreeData { + fn default() -> OctTreeData { + Self::Same(false) + } +} + +#[derive(Debug)] +struct Instruction { + new_state: bool, + bounds: Block, +} + +#[derive(Debug, Clone)] +struct Block { + min_x: i32, + max_x: i32, + min_y: i32, + max_y: i32, + min_z: i32, + max_z: i32, +} + +impl Block { + fn volume(&self) -> usize { + let x = (self.max_x - self.min_x) as usize; + let y = (self.max_y - self.min_y) as usize; + let z = (self.max_z - self.min_z) as usize; + x * y * z + } + + fn completely_covers(&self, other: &Self) -> bool { + self.min_x <= other.min_x + && self.max_x >= other.max_x + && self.min_y <= other.min_y + && self.max_y >= other.max_y + && self.min_z <= other.min_z + && self.max_z >= other.max_z + } + + fn intersects(&self, other: &Self) -> bool { + if self.max_x <= other.min_x + || self.min_x >= other.max_x + || self.max_y <= other.min_y + || self.min_y >= other.max_y + || self.max_z <= other.min_z + || self.min_z >= other.max_z + { + false + } else { + true + } + } + + fn oct_chunk(&self, chunk: u8) -> Block { + let lower_x = (chunk & 1) == 0; + let lower_y = (chunk & 2) == 0; + let lower_z = (chunk & 4) == 0; + + let mid_x = (self.min_x + self.max_x) / 2; + let mid_y = (self.min_y + self.max_y) / 2; + let mid_z = (self.min_z + self.max_z) / 2; + + Block { + min_x: if lower_x { self.min_x } else { mid_x }, + max_x: if lower_x { mid_x } else { self.max_x }, + min_y: if lower_y { self.min_y } else { mid_y }, + max_y: if lower_y { mid_y } else { self.max_y }, + min_z: if lower_z { self.min_z } else { mid_z }, + max_z: if lower_z { mid_z } else { self.max_z }, + } + } +} + +fn parse_instructions(input: &str) -> IResult<&str, Vec<Instruction>> { + separated_list1(line_ending, parse_instruction)(input) +} + +fn parse_instruction(input: &str) -> IResult<&str, Instruction> { + map( + tuple(( + alt((value(true, tag("on ")), value(false, tag("off ")))), + parse_block, + )), + |(new_state, bounds)| Instruction { new_state, bounds }, + )(input) +} + +fn parse_block(input: &str) -> IResult<&str, Block> { + map( + tuple(( + tag("x="), + nom_i32, + tag(".."), + nom_i32, + tag(",y="), + nom_i32, + tag(".."), + nom_i32, + tag(",z="), + nom_i32, + tag(".."), + nom_i32, + )), + |( + _, + min_x, + _, + max_x_inclusive, + _, + min_y, + _, + max_y_inclusive, + _, + min_z, + _, + max_z_inclusive, + )| Block { + min_x, + max_x: max_x_inclusive + 1, + min_y, + max_y: max_y_inclusive + 1, + min_z, + max_z: max_z_inclusive + 1, + }, + )(input) +} |