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 alternateon
andoff
; 3) integer boundaries lie completely within the-50
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 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 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 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 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)