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 multiline 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 varyingsized 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 alternateon
andoff
; 3) integer boundaries lie completely within the50
to50
range; 4) Ifa
represents the lower boundary andb
the upper, all instructions area..b
 All subsequent instructions feature integer boundaries that appear to lie within a larger range of 100000 to 100000
 Instructions 21220 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>onoff)\sx=(?<x1>*\d+)..(?<x2>*\d+),y=(?<y1>*\d+)..(?<y2>*\d+),z=(?<z1>*\d+)..(?<z2>*\d+)/g
That's grosslooking. Here's how it breaks down:

(?<power>onoff)
saves a group calledpower
foron
oroff
 Each of the
(?<n1>*\d+)
saves a group calledn1
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 bruteforce 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 InclusionExclusion (PIE)
 One mention of a Sweep Line algorithm
 References to AABB, or AxisAligned Bounding Boxes  a collision detection formula, it seems

JavaScript solver Totto16's code for Part 1 was welllabeled 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 alloff
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.
Top comments (0)