From 6d72191e2ce5d423ca03c894d2dad1d3061bd4f3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:27:29 +0200 Subject: Refile for merging repos --- 2021/src/bin/day_22.rs | 379 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 379 insertions(+) create mode 100644 2021/src/bin/day_22.rs (limited to '2021/src/bin/day_22.rs') diff --git a/2021/src/bin/day_22.rs b/2021/src/bin/day_22.rs new file mode 100644 index 0000000..85d9ec9 --- /dev/null +++ b/2021/src/bin/day_22.rs @@ -0,0 +1,379 @@ +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::{cmp, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_22.txt")?; + let instructions = parse_instructions(&input).unwrap().1; + { + let bounds_50 = Block { + min_x: -50, + max_x: 51, + min_y: -50, + max_y: 51, + min_z: -50, + max_z: 51, + }; + let mut octtree_50 = OctTree::default(); + for instruction in &instructions { + octtree_50.set_block(&bounds_50, &instruction.bounds, instruction.new_state); + } + dbg!(octtree_50.count_on_blocks(&bounds_50)); + } + + { + let problem_boundary = 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), + } + .expand_to_power_cube(); + + // This chunking and adding partial solutions is necessary + // because I can't fit the whole thing in memory at once :( + // It runs really slowly. + let mut count = 0; + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + let mut octtree = OctTree::default(); + for instruction in &instructions { + octtree.set_block( + &problem_boundary, + &instruction.bounds, + instruction.new_state, + ); + } + count += dbg!(octtree.count_on_blocks(&problem_boundary)); + } + } + } + dbg!(count); + } + + Ok(()) +} + +#[derive(Default, Clone)] +struct OctTree { + data: OctTreeData, +} + +impl OctTree { + fn set_block(&mut self, self_bounds: &Block, bounds: &Block, new_val: bool) { + if bounds.completely_covers(self_bounds) { + self.data = new_val.into(); + } else if bounds.intersects(self_bounds) { + match &mut self.data { + OctTreeData::AllOff => { + if new_val { + self.split(self_bounds); + self.set_block(self_bounds, bounds, new_val); + } + } + OctTreeData::AllOn => { + if !new_val { + self.split(self_bounds); + self.set_block(self_bounds, bounds, new_val); + } + } + OctTreeData::BitSet(ref mut bits) => { + let min_x = cmp::max(self_bounds.min_x, bounds.min_x); + let max_x = cmp::min(self_bounds.max_x, bounds.max_x); + let min_x_index = (min_x - self_bounds.min_x) as usize; + let max_x_index = min_x_index + (max_x - min_x) as usize; + + let min_y = cmp::max(self_bounds.min_y, bounds.min_y); + let max_y = cmp::min(self_bounds.max_y, bounds.max_y); + let min_y_index = (min_y - self_bounds.min_y) as usize; + let max_y_index = min_y_index + (max_y - min_y) as usize; + + let min_z = cmp::max(self_bounds.min_z, bounds.min_z); + let max_z = cmp::min(self_bounds.max_z, bounds.max_z); + let min_z_index = (min_z - self_bounds.min_z) as usize; + let max_z_index = min_z_index + (max_z - min_z) as usize; + + for z_index in min_z_index..max_z_index { + let z_bit_index = z_index << 4; + for y_index in min_y_index..max_y_index { + let y_bit_index = y_index << 2; + for x_index in min_x_index..max_x_index { + let x_bit_index = x_index; + let bit_mask = 1u64 << (z_bit_index + y_bit_index + x_bit_index); + if new_val { + *bits |= bit_mask; + } else { + *bits &= !bit_mask; + } + } + } + } + + if *bits == 0 { + self.data = OctTreeData::AllOff; + } else if *bits == !0u64 { + self.data = OctTreeData::AllOn; + } + } + OctTreeData::Diverse(ref mut subtrees) => { + for (sub_index, sub) in subtrees.iter_mut().enumerate() { + sub.set_block(&self_bounds.oct_chunk(sub_index as u8), bounds, new_val); + } + if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::AllOn)) + { + self.data = OctTreeData::AllOn; + } else if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::AllOff)) + { + self.data = OctTreeData::AllOff; + } + } + }; + } + } + + fn split(&mut self, self_bounds: &Block) { + assert!(!matches!(self.data, OctTreeData::Diverse(_))); + if self_bounds.volume() == 64 { + let new_bitset = match self.data { + OctTreeData::AllOn => !0u64, + OctTreeData::AllOff => 0, + _ => panic!("weird split"), + }; + self.data = OctTreeData::BitSet(new_bitset); + } else { + let template = OctTree { + data: self.data.clone(), + }; + self.data = OctTreeData::Diverse(Box::new([ + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + ])); + } + } + + fn count_on_blocks(&self, self_bounds: &Block) -> usize { + match &self.data { + OctTreeData::AllOff => 0, + OctTreeData::AllOn => self_bounds.volume(), + OctTreeData::BitSet(bitset) => bitset.count_ones() as usize, + OctTreeData::Diverse(subtrees) => subtrees + .iter() + .enumerate() + .map(|(index, sub)| sub.count_on_blocks(&self_bounds.oct_chunk(index as u8))) + .sum(), + } + } +} + +#[derive(Clone)] +enum OctTreeData { + AllOff, + AllOn, + BitSet(u64), + Diverse(Box<[OctTree; 8]>), +} + +impl Default for OctTreeData { + fn default() -> OctTreeData { + Self::AllOff + } +} + +impl From for OctTreeData { + fn from(b: bool) -> Self { + if b { + Self::AllOn + } else { + Self::AllOff + } + } +} + +#[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 expand_to_power_cube(&self) -> Block { + let mag_x = self.max_x - self.min_x; + let mag_y = self.max_y - self.min_y; + let mag_z = self.max_z - self.min_z; + let mag_max = cmp::max(mag_x, cmp::max(mag_y, mag_z)); + let first_power_of_2 = (0..) + .map(|pow| 2_i32.pow(pow)) + .filter(|pow_size| *pow_size >= mag_max) + .next() + .unwrap(); + + Block { + min_x: self.min_x, + max_x: self.max_x + first_power_of_2 - mag_x, + min_y: self.min_y, + max_y: self.max_y + first_power_of_2 - mag_y, + min_z: self.min_z, + max_z: self.max_z + first_power_of_2 - mag_z, + } + } +} + +fn parse_instructions(input: &str) -> IResult<&str, Vec> { + 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) +} -- cgit v1.2.3