6 votes

Day 22: Reactor Reboot

Today's problem description: https://adventofcode.com/2021/day/22

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

4 comments

  1. Liru
    Link
    After reading and expecting part 2, I think I'll skip it for now and come back to it later. I have vague recollections of how to do this from studying graphics. Part 1, Rust The hashbrown crate...

    After reading and expecting part 2, I think I'll skip it for now and come back to it later. I have vague recollections of how to do this from studying graphics.

    Part 1, Rust

    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());
    }
    
    1 vote
  2. [2]
    jzimbel
    (edited )
    Link
    Elixir Part 1 was easy-peasy, but those huge numbers in the puzzle input definitely struck fear into my heart. I did some thinking on paper for part 2, and I think I know what I need to do for an...

    Elixir
    Part 1 was easy-peasy, but those huge numbers in the puzzle input definitely struck fear into my heart.

    I did some thinking on paper for part 2, and I think I know what I need to do for an optimized solution, but... yikes, it seems like actually doing it will be really challenging. Here's what I've got for part 1, at least. Also a small hint at how I'm planning to implement part 2 from the function stubs/argument names.

    My naive solution for part 1 runs in about 1.4s.

    Part 1
    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
    
    Part 2 thoughts

    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.

    1 vote
    1. jzimbel
      (edited )
      Link Parent
      I got part 2! It runs in about 2.6s. Switching to the optimized function for part 1 also cuts down the runtime from 1.4s to 78ms. I absolutely melted my brain trying to get the logic...

      I got part 2! It runs in about 2.6s. Switching to the optimized function for part 1 also cuts down the runtime from 1.4s to 78ms. I absolutely melted my brain trying to get the logic right—visualizing this stuff is a challenge. The code you see is the result of starting with some longer pseudo-code that considers all the possible ways two cuboids can intersect and boiling it down to one function that works on every possible intersection.

      Part 2 (and part 1 using the optimized cuboid-intersecting function)
      defmodule AdventOfCode.Solution.Year2021.Day22 do
        def part1(input) do
          input
          |> parse_input()
          |> Enum.map(fn {action, cuboid} -> {action, clamp(cuboid)} end)
          |> Enum.reduce([], &switch_region/2)
          |> Enum.map(&volume/1)
          |> Enum.sum()
        end
      
        def part2(input) do
          input
          |> parse_input()
          |> Enum.reduce([], &switch_region/2)
          |> Enum.map(&volume/1)
          |> Enum.sum()
        end
      
        defp switch_region({:on, on_cuboid}, cuboids) do
          subtract_from_all([on_cuboid], cuboids) ++ cuboids
        end
      
        defp switch_region({:off, off_cuboid}, cuboids) do
          subtract_from_all(cuboids, [off_cuboid])
        end
      
        # Computes the difference of `lhs_cuboids` - `rhs_cuboids`,
        # splitting `lhs_cuboids` into smaller parts as necessary to preserve
        # it as a list of non-overlapping cuboids.
        defp subtract_from_all(lhs_cuboids, rhs_cuboids) do
          Enum.reduce(rhs_cuboids, lhs_cuboids, fn rhs_cuboid, lhs_acc ->
            Enum.flat_map(lhs_acc, &subtract(&1, rhs_cuboid))
          end)
        end
      
        # Subtracts `rhs_cuboid` from `lhs_cuboid`, splitting `lhs_cuboid` into
        # smaller parts as necessary. Returns result as a list of non-overlapping
        # cuboids.
        defp subtract(lhs_cuboid, rhs_cuboid) do
          if disjoint?(lhs_cuboid, rhs_cuboid) do
            [lhs_cuboid]
          else
            {xmin1..xmax1, ymin1..ymax1 = y, zmin1..zmax1 = z} = lhs_cuboid
            {xmin2..xmax2, ymin2..ymax2, zmin2..zmax2} = rhs_cuboid
      
            clamped_x = max(xmin1, xmin2)..min(xmax1, xmax2)//1
            clamped_y = max(ymin1, ymin2)..min(ymax1, ymax2)//1
      
            [
              {xmin1..(xmin2 - 1)//1, y, z},
              {(xmax2 + 1)..xmax1//1, y, z},
              {clamped_x, ymin1..(ymin2 - 1)//1, z},
              {clamped_x, (ymax2 + 1)..ymax1//1, z},
              {clamped_x, clamped_y, zmin1..(zmin2 - 1)//1},
              {clamped_x, clamped_y, (zmax2 + 1)..zmax1//1}
            ]
            |> Enum.reject(&(volume(&1) == 0))
          end
        end
      
        defp clamp({x_range, y_range, z_range}) do
          {clamp_range(x_range), clamp_range(y_range), clamp_range(z_range)}
        end
      
        defp clamp_range(lower..upper//1) do
          max(lower, -50)..min(upper, 50)//1
        end
      
        defp volume({x_range, y_range, z_range}) do
          Range.size(x_range) * Range.size(y_range) * Range.size(z_range)
        end
      
        defp disjoint?({x_range1, y_range1, z_range1}, {x_range2, y_range2, z_range2}) do
          Range.disjoint?(x_range1, x_range2) or
            Range.disjoint?(y_range1, y_range2) or
            Range.disjoint?(z_range1, z_range2)
        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
      
      2 votes
  3. wycy
    (edited )
    Link
    Rust This'll be my last day-of attempt this year as I'll be busy over the next few days. It's been fun working on these simultaneously with the rest of you. EDIT: Finished! Updated code posted....

    Rust

    Like many, I've only done part 1 so far because it was trivial. Part 2 seems relatively straightforward but non-trivial to implement (some spoiler thoughts & link below).

    This'll be my last day-of attempt this year as I'll be busy over the next few days. It's been fun working on these simultaneously with the rest of you.

    EDIT: Finished! Updated code posted.

    Rust
    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);
    }
    
    1 vote