Reactor Reboot

Advent of Code 2021 Day 22

Why no visualization?

• Because I was unable to solve it with code or other proof of work that I authored
• But here's a great visualization by another talented solver

Solve for X where X equals...

• An integer greater than or equal to 0
• that represents the number of cubes still on

That's our output. What's our input?

• A multi-line string
• Where each line consists of an on/off command
• And x y z integer ranges denoted by = and ..

What does our input represent?

• A series of on/off instructions
• Each one targeting varying-sized cuboids that compose part of a larger cuboid
• Where each smaller cuboid's length is expressed as a range of x values, height as a range of y values, and depth as a range of z values

Inspecting our input for similarities, differences and algorithmic shortcuts or hurdles

• Each instruction follows this pattern:

[on/off] ([x/y/z][=][(-?)n][..][(-?)n][,])*3

• The first 20 instructions feature a few patterns: 1) the first 10 instructions are all on; 2) the second 10 instructions alternate on and off; 3) integer boundaries lie completely within the -50 to 50 range; 4) If a represents the lower boundary and b the upper, all instructions are a..b
• All subsequent instructions feature integer boundaries that appear to lie within a larger range of -100000 to 100000
• Instructions 21-220 are all on
• All instructions feature an a..b pattern, thankfully

Regular Expressions (RegEx) are terrifying(ly powerful)

• I need to extract important information from each line of the input string: power status, lower and upper x, y and z
• I'm not too familiar with - and have rarely, if ever used - regular expressions
• Thankfully, tools like RegExr exist to make RegEx a little less painful to beginners
• I used it to craft a RegEx that suited my needs, complete with named groups

/(?<power>on|off)\sx=(?<x1>-*\d+)..(?<x2>-*\d+),y=(?<y1>-*\d+)..(?<y2>-*\d+),z=(?<z1>-*\d+)..(?<z2>-*\d+)/g

That's gross-looking. Here's how it breaks down:

• (?<power>on|off) saves a group called power for on or off
• Each of the (?<n1>-*\d+) saves a group called n1 for the lower and upper x, y and z integer boundaries
• Everything not inside () is searched but ultimately not saved as part of a group
• I assume it could be much shorter using other RegEx tools, but this gets the job done for me, a RegEx noob

Saving the conversion as a list

[...input.matchAll(regex)]
    .map(m => [
      m.groups.power == 'on' ? true : false,
      [+m.groups.x1,+m.groups.x2],
      [+m.groups.y1,+m.groups.y2],
      [+m.groups.z1,+m.groups.z2],
    ])

• matchAll() returns an Iterator
• ... spreads that Iterator out into a full array
• Each item in that array contains a group object storing the named groups
• map() helps to quickly replace each item with a new consolidated array filled with something that resembles this pattern:

[boolean, [lowerX, upperX], [lowerY, upperY], [lowerZ, upperZ]]

My poor attempt at solving Part 1

Here's the brute-force algorithm that I incorrectly assumed would work, let alone finish running:

Create an array to store all cuboids set to 'on'
Loop over each instruction
  Loop through each value in the x range
    Loop through each value in the y range
      Loop through each value in the z range
        If the instruction is on and the coordinates are not in the array, add them
        Else if the instruction is off and the coordinates are in the array, replace the coordinates with 'null'
Filter the array to exclude 'null' values
Return the length of the array

Running this program made my repl.it and Terminal programs hang, as expected.

Searching Github and Reddit for eloquent solutions from which to learn and queue up further readings

• Several mentions of the Principle of Inclusion-Exclusion (PIE)
• One mention of a Sweep Line algorithm
• References to AABB, or Axis-Aligned Bounding Boxes - a collision detection formula, it seems
• JavaScript solver Totto16's code for Part 1 was well-labeled and included some great utility methods like 'fillElements' - to turn an array of shape [a, '..', d] into [a, b, c, d] and combine - to merge and flatten arrays
• Great observations about how at the intersection of any two cuboids is another cuboid, and how perhaps the order of instructions can be sorted so that all on steps occur before all off steps

Ultimately, I don't feel mentally prepared to reverse engineer any of these algorithms yet

• This puzzle, with my input, will remain unsolved
• I'm excited to return to this puzzle some day and try solving it again with more algorithmic gusto

I'm glad this puzzle challenged me to write my first RegEx from scratch, gaining more comfort with the cryptic syntax.