diff options
Diffstat (limited to '22/src')
| -rw-r--r-- | 22/src/main.rs | 293 |
1 files changed, 293 insertions, 0 deletions
diff --git a/22/src/main.rs b/22/src/main.rs new file mode 100644 index 0000000..bc61faf --- /dev/null +++ b/22/src/main.rs @@ -0,0 +1,293 @@ +use advent_lib::prelude::*; + + +#[derive(Debug, Clone)] +struct Step { + set_to: bool, + min: Point, + max: Point, +} + +#[derive(Debug, Clone)] +struct Region { + min: Point, + max: Point, +} + +#[derive(Debug, Clone)] +struct Point { + x: i64, + y: i64, + z: i64, +} + +#[derive(Debug, Clone, Eq, PartialEq)] +struct Span { + min: i64, + max: i64, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut directions = Vec::new(); + for line in &input { + let mut step = Step { + set_to: false, + min: Point { x: 0, y: 0, z: 0 }, + max: Point { x: 0, y: 0, z: 0 }, + }; + + let words: Vec<&str> = line.split_whitespace().collect(); + + step.set_to = match words[0] { + "on" => true, + "off" => false, + _ => panic!("hm"), + }; + + let components: Vec<&str> = words[1].split(",").collect(); + + let parts: Vec<&str> = components[0].split("=").collect(); + let ends: Vec<&str> = parts[1].split("..").collect(); + step.min.x = ends[0].parse::<i64>().unwrap(); + step.max.x = ends[1].parse::<i64>().unwrap(); + + let parts: Vec<&str> = components[1].split("=").collect(); + let ends: Vec<&str> = parts[1].split("..").collect(); + step.min.y = ends[0].parse::<i64>().unwrap(); + step.max.y = ends[1].parse::<i64>().unwrap(); + + let parts: Vec<&str> = components[2].split("=").collect(); + let ends: Vec<&str> = parts[1].split("..").collect(); + step.min.z = ends[0].parse::<i64>().unwrap(); + step.max.z = ends[1].parse::<i64>().unwrap(); + + directions.push(step); + } + + let mut total_on = 0; + for x in -50 .. 51 { + for y in -50 .. 51 { + for z in -50 .. 51 { + let point = Point { x, y, z }; + if test_cube(&point, &directions) { + total_on += 1; + } + } + } + } + + println!("{}", total_on); + + let total_on_everywhere = count_everywhere(&directions); + println!("{}", total_on_everywhere); + + Ok(()) +} + + +fn test_cube(point: &Point, directions: &Vec<Step>) -> bool { + for step in directions.iter().rev() { + if (point.x >= step.min.x) && (point.y >= step.min.y) + && (point.z >= step.min.z) && (point.x <= step.max.x) + && (point.y <= step.max.y) && (point.z <= step.max.z) + { + return step.set_to; + } + } + + false +} + + +fn count_everywhere(directions: &Vec<Step>) -> i64 { + let mut lit_regions: Vec<Region> = Vec::new(); + + for step in directions { + if lit_regions.len() == 0 { + if step.set_to { + lit_regions.push(Region { + min: step.min.clone(), + max: step.max.clone(), + }); + } + continue; + } + + let mut new_lit_regions = Vec::new(); + for lit_region in lit_regions.into_iter() { + /* Depending on whether set_to is true or false, we may be doing union + * or difference. However, we implement union as difference followed by + * also including the entire subtracted volume. So difference is the + * only operation that needs the per-axis breakdown of cases. + * + * Start by determining whether it's overlapping or not. The + * non-overlapping cases are: + * + * A==========B (lit region) + * C=========D (step) + * + * A=========B (lit region) + * C==========D (step) + * + * Now eliminate cases where the step entirely covers the lit region: + * + * A======B (lit region) + * C==================D (step) + * + * The following cases remain: + * + * A==================B (lit region) + * C======D (step) + * + * A==========B (lit region) + * C=====.......? (step) + * + * A==========B (lit region) + * ?......=====D (step) + */ + let mut lit_spans = Vec::new(); + let mut step_spans = Vec::new(); + let mut differenced_spans = Vec::new(); + for axis in 0 .. 3 { + let mut relevant_spans = Vec::new(); + + let (lit_min, lit_max, step_min, step_max) = match axis { + 0 => { (lit_region.min.x, lit_region.max.x, step.min.x, step.max.x) }, + 1 => { (lit_region.min.y, lit_region.max.y, step.min.y, step.max.y) }, + 2 => { (lit_region.min.z, lit_region.max.z, step.min.z, step.max.z) }, + _ => { panic!("run in circles scream and shout"); }, + }; + + lit_spans.push(Span { min: lit_min, max: lit_max }); + step_spans.push(Span { min: step_min, max: step_max }); + + if (lit_max < step_min) || (lit_min > step_max) { + // Non-overlapping + relevant_spans.push(Span { min: lit_min, max: lit_max }); + } else if (step_min <= lit_min) && (step_max >= lit_max) { + // Step entirely covers lit + // It is intentional that nothing is done here. + } else if (lit_min < step_min) && (lit_max > step_max) { + // Step is a segment in the middle of lit + relevant_spans.push(Span { min: lit_min, max: step_min - 1 }); + relevant_spans.push(Span { min: step_max + 1, max: lit_max }); + } else if lit_min < step_min { + relevant_spans.push(Span { min: lit_min, max: step_min - 1 }); + } else { + relevant_spans.push(Span { min: step_max + 1, max: lit_max }); + } + + differenced_spans.push(relevant_spans); + } + + if ((differenced_spans[0].len() == 1) + && (differenced_spans[0][0] == lit_spans[0])) + || ((differenced_spans[1].len() == 1) + && (differenced_spans[1][0] == lit_spans[1])) + || ((differenced_spans[2].len() == 1) + && (differenced_spans[2][0] == lit_spans[2])) + { + new_lit_regions.push(Region { + min: Point { + x: lit_spans[0].min, + y: lit_spans[1].min, + z: lit_spans[2].min, + }, + max: Point { + x: lit_spans[0].max, + y: lit_spans[1].max, + z: lit_spans[2].max, + }, + }); + } else { + for z_span in &differenced_spans[2] { + let region = Region { + min: Point { + x: lit_spans[0].min, + y: lit_spans[1].min, + z: z_span.min, + }, + max: Point { + x: lit_spans[0].max, + y: lit_spans[1].max, + z: z_span.max, + }, + }; + new_lit_regions.push(region); + } + + let z_min = std::cmp::max(lit_spans[2].min, step_spans[2].min); + let z_max = std::cmp::min(lit_spans[2].max, step_spans[2].max); + + for y_span in &differenced_spans[1] { + let region = Region { + min: Point { + x: lit_spans[0].min, + y: y_span.min, + z: z_min, + }, + max: Point { + x: lit_spans[0].max, + y: y_span.max, + z: z_max, + }, + }; + new_lit_regions.push(region); + } + + let y_min = std::cmp::max(lit_spans[1].min, step_spans[1].min); + let y_max = std::cmp::min(lit_spans[1].max, step_spans[1].max); + + for x_span in &differenced_spans[0] { + let region = Region { + min: Point { + x: x_span.min, + y: y_min, + z: z_min, + }, + max: Point { + x: x_span.max, + y: y_max, + z: z_max, + }, + }; + new_lit_regions.push(region); + } + } + + } + + if step.set_to { + let region = Region { + min: step.min.clone(), + max: step.max.clone(), + }; + new_lit_regions.push(region); + } + + + lit_regions = new_lit_regions; + } + + let mut total_lit = 0; + for region in &lit_regions { + let x_extent = region.max.x - region.min.x + 1; + let y_extent = region.max.y - region.min.y + 1; + let z_extent = region.max.z - region.min.z + 1; + let volume = x_extent * y_extent * z_extent; + total_lit += volume; + } + + total_lit +} + |