Day 22: Reactor Reboot

The hashbrown crate seems to be doing a lot of heavy lifting here. Running this using the standard hashset and the difference call gives a runtime of ~15 seconds. hashbrown's hashset takes 6 seconds, and the current solution with the drain filter takes slightly more than 1 second.

use hashbrown::HashSet;
use itertools::iproduct;
use std::{ops::RangeInclusive, str::FromStr};

#[derive(Debug)]
pub struct Instruction {
    on: bool,
    x: RangeInclusive<i64>,
    y: RangeInclusive<i64>,
    z: RangeInclusive<i64>,
}

impl FromStr for Instruction {
    type Err = ();

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let mut i = s.split(' ');
        let instr = i.next().unwrap();
        let on = instr == "on";

        let ranges: Vec<_> = i
            .next()
            .unwrap()
            .split(',')
            .map(|s| {
                let coords: Vec<i64> = s[2..].split("..").flat_map(str::parse).collect();
                coords[0]..=coords[1]
            })
            .collect();

        Ok(Self {
            on,
            x: ranges[0].clone(),
            y: ranges[1].clone(),
            z: ranges[2].clone(),
        })
    }
}

fn clamp_range(r: RangeInclusive<i64>) -> RangeInclusive<i64> {
    *r.start().max(&-50)..=*r.end().min(&50)
}

impl Instruction {
    fn clamped(self) -> Self {
        Self {
            x: clamp_range(self.x),
            y: clamp_range(self.y),
            z: clamp_range(self.z),
            on: self.on,
        }
    }

    pub fn points(&self) -> HashSet<(i64, i64, i64)> {
        iproduct!(self.x.clone(), self.y.clone(), self.z.clone()).collect()
    }
}

pub fn main() {
    let a = std::fs::read_to_string("input/22.txt").unwrap();
    let instr: Vec<Instruction> = a
        .lines()
        .flat_map(str::parse)
        .map(Instruction::clamped) // would remove this for part 2 if it wasn't so slooooow
        .collect();

    let mut points: HashSet<(i64, i64, i64)> = HashSet::new();
    for p in instr {
        if p.on {
            points.extend(p.points());
        } else {
            let sub_points: HashSet<_> = p.points();
            let _: Vec<_> = points.drain_filter(|x| sub_points.contains(x)).collect();
            // points = points.difference(&sub_points).copied().collect();
        }
    }
    println!("P1: {}", points.len());
}

defmodule AdventOfCode.Solution.Year2021.Day22 do
  def part1(input) do
    input
    |> parse_input()
    |> Enum.map(fn {action, {x_range, y_range, z_range}} ->
      {action, {clamp_range(x_range), clamp_range(y_range), clamp_range(z_range)}}
    end)
    |> Enum.reduce(MapSet.new(), &switch_region_naive/2)
    |> MapSet.size()
  end

  def part2(input) do
    input
    |> parse_input()
    |> Enum.reduce([], &switch_region_optimized/2)
    |> Enum.map(fn {xmin..xmax, ymin..ymax, zmin..zmax} ->
      (xmax - xmin) * (ymax - ymin) * (zmax - zmin)
    end)
    |> Enum.sum()
  end

  for {action, set_fn} <- [on: &MapSet.union/2, off: &MapSet.difference/2] do
    defp switch_region_naive({unquote(action), {x_range, y_range, z_range}}, on_now) do
      unquote(set_fn).(
        on_now,
        for(
          x <- x_range,
          y <- y_range,
          z <- z_range,
          into: MapSet.new(),
          do: {x, y, z}
        )
      )
    end
  end

  defp switch_region_optimized({_action, _ranges}, _non_overlapping_ranges) do
    :do_the_thing!
  end

  defp clamp_range(lower..upper//1) do
    max(lower, -50)..min(upper, 50)//1
  end

  defp parse_input(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_line/1)
  end

  defp parse_line(line) do
    line
    |> String.split()
    |> then(fn [on_off, ranges] ->
      {String.to_existing_atom(on_off), parse_ranges(ranges)}
    end)
  end

  defp parse_ranges(ranges) do
    ~r/(-?\d+)..(-?\d+)/
    |> Regex.scan(ranges, capture: :all_but_first)
    |> Enum.map(fn [lower, upper] ->
      String.to_integer(lower)..String.to_integer(upper)
    end)
    |> List.to_tuple()
  end
end

Whenever these optimization problems come up, the solution is usually to find a way to model the problem with numbers alone. I think this one is no different.

It looks like instead of using a set or similar structure to track every single 3d point that is currently "on", we need to keep the representation closer to how it's represented in the puzzle input—a list of groups of 3 ranges, each representing a cuboid.

I'm trying to figure out how to decompose the result of each action into a list of non-overlapping cuboids. Keeping them from overlapping is the important part—it makes calculating the total volume at the end as simple as summing the volumes of each cuboid. I found this SO question on the topic, and it looks pretty involved in two dimensions, let alone 3...

Edit: This problem is slightly more manageable than the SO post I linked because if you set it up right, you're only ever checking the overlap of two cuboids at a time and every operation starts and ends with non-overlapping cuboids. There are still a lot of different cases to consider in checking each pair of cuboids, though.

use std::env;
use std::io::{prelude::*, BufReader};
use std::fs::File;
use std::ops::RangeInclusive;
use std::collections::HashMap;
use std::cmp::{min,max};

extern crate regex;
use regex::Regex;

#[derive(Clone,Debug)]
struct Cuboid {
    status: bool,
    x: RangeInclusive<i64>,
    y: RangeInclusive<i64>,
    z: RangeInclusive<i64>,
}
impl From<&String> for Cuboid {
    fn from(s: &String) -> Self {
        let re = Regex::new(r"(on|off) x=(\-*\d+)\.\.(\-*\d+),y=(\-*\d+)\.\.(\-*\d+),z=(\-*\d+)\.\.(\-*\d+)").unwrap();
        let matches = re.captures(s).unwrap();
        let status = match &matches[1] {
            "on" => true,
            "off" => false,
            _ => unreachable!()
        };
        Self {
            status: status,
            x: (matches[2].parse().unwrap()..=matches[3].parse().unwrap()),
            y: (matches[4].parse().unwrap()..=matches[5].parse().unwrap()),
            z: (matches[6].parse().unwrap()..=matches[7].parse().unwrap()),
        }
    }
}
impl Cuboid {
    pub fn new(x: RangeInclusive<i64>, y: RangeInclusive<i64>, z: RangeInclusive<i64>, status: bool) -> Self {
        Self { status: status, x: x, y: y, z: z }
    }

    pub fn raw_volume(&self) -> i64 {
        range_size(&self.x) * range_size(&self.y) * range_size(&self.z)
    }

    pub fn signed_volume(&self) -> i64 {
        self.raw_volume() * if self.status { 1 } else { -1 }
    }

    pub fn intersection(&self, other: &Cuboid, status: bool) -> Cuboid {
        let xsect = RangeInclusive::new(*max(self.x.start(), other.x.start()), *min(self.x.end(), other.x.end()));
        let ysect = RangeInclusive::new(*max(self.y.start(), other.y.start()), *min(self.y.end(), other.y.end()));
        let zsect = RangeInclusive::new(*max(self.z.start(), other.z.start()), *min(self.z.end(), other.z.end()));
        Cuboid::new(xsect, ysect, zsect, status)
    }

    pub fn intersects(&self, other: &Cuboid) -> bool {
        // intersection: (max(a.begin, b.begin), min(a.end, b.end))
        let xsect = RangeInclusive::new(*max(self.x.start(), other.x.start()), *min(self.x.end(), other.x.end()));
        let ysect = RangeInclusive::new(*max(self.y.start(), other.y.start()), *min(self.y.end(), other.y.end()));
        let zsect = RangeInclusive::new(*max(self.z.start(), other.z.start()), *min(self.z.end(), other.z.end()));
        !xsect.is_empty() && !ysect.is_empty() && !zsect.is_empty()
    }
}

fn range_size(range: &RangeInclusive<i64>) -> i64 {
    if !range.is_empty() { range.end() - range.start() + 1 } else { 0 }
}

fn solve2(input: &str) {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };
    let cuboids: Vec<_> = input.iter().map(Cuboid::from).collect();

    // Process instructions
    let mut final_cuboids: Vec<Cuboid> = Vec::new();
    for cuboid in &cuboids {
        let mut new_cuboids: Vec<Cuboid> = Vec::new();
        for final_cuboid in &final_cuboids {
            if cuboid.intersects(final_cuboid) {
                // Helpful hints provided by u/leftylink
                // ON + ON -> OFF: Need to subtract the intersected volume
                // OFF + OFF -> ON: Intersecting with a previously placed OFF cube means we've
                // already intersected a different volume with OFF, so turn ON
                // Otherwise: New cuboid's status
                let new_status = if cuboid.status && final_cuboid.status { false } 
                           else if !cuboid.status && !final_cuboid.status { true }
                           else { cuboid.status };
                new_cuboids.push(cuboid.intersection(&final_cuboid,new_status));
            }
        }
        if cuboid.status { final_cuboids.push(cuboid.clone()); }
        final_cuboids.append(&mut new_cuboids);
    }

    // Count volumes
    let part2: i64 = final_cuboids
        .iter()
        .map(|s| s.signed_volume())
        .sum();
    println!("Part 2: {}", part2); // 1334238660555542
}


fn solve1(input: &str) {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    let steps: Vec<_> = input.iter().map(Cuboid::from).collect();

    // Reboot
    let mut reactor: HashMap<(i64,i64,i64),bool> = HashMap::new();
    steps.iter().for_each(|s| {
        let xmin = std::cmp::max(s.x.start(),&-50i64);
        let xmax = std::cmp::min(s.x.end(),&50i64);
        let ymin = std::cmp::max(s.y.start(),&-50i64);
        let ymax = std::cmp::min(s.y.end(),&50i64);
        let zmin = std::cmp::max(s.z.start(),&-50i64);
        let zmax = std::cmp::min(s.z.end(),&50i64);
        for z in *zmin..=*zmax {
            for y in *ymin..=*ymax {
                for x in *xmin..=*xmax {
                    if s.status {
                        reactor.insert((x,y,z),true);
                    } else {
                        reactor.remove(&(x,y,z));
                    }
                }
            }
        }
    });

    let part1 = reactor.iter().filter(|&(_,v)| *v).count();
    println!("Part 1: {}", part1); // 580012

}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve1(&filename);
    solve2(&filename);
}