Advent of Code - 2021

This is a solution to Day 22 of Advent of Code 2021.

Day 22 - Reactor Reboot

Operating at these extreme ocean depths has overloaded the submarine's reactor; it needs to be rebooted.

The reactor core is made up of a large 3-dimensional grid made up entirely of cubes, one cube per integer 3-dimensional coordinate (x,y,z). Each cube can be either on or off; at the start of the reboot process, they are all off. (Could it be an old model of a reactor you've seen before?)

To reboot the reactor, you just need to set all of the cubes to either on or off by following a list of reboot steps (your puzzle input). Each step specifies a cuboid (the set of all cubes that have coordinates which fall within ranges for x, y, and z) and whether to turn all of the cubes in that cuboid on or off.

For example, given these reboot steps:

on x=10..12,y=10..12,z=10..12
on x=11..13,y=11..13,z=11..13
off x=9..11,y=9..11,z=9..11
on x=10..10,y=10..10,z=10..10

The first step (on x=10..12,y=10..12,z=10..12) turns on a 3x3x3 cuboid consisting of 27 cubes:

10,10,10
10,10,11
10,10,12
10,11,10
10,11,11
10,11,12
10,12,10
10,12,11
10,12,12
11,10,10
11,10,11
11,10,12
11,11,10
11,11,11
11,11,12
11,12,10
11,12,11
11,12,12
12,10,10
12,10,11
12,10,12
12,11,10
12,11,11
12,11,12
12,12,10
12,12,11
12,12,12

The second step (on x=11..13,y=11..13,z=11..13) turns on a 3x3x3 cuboid that overlaps with the first. As a result, only 19 additional cubes turn on; the rest are already on from the previous step:

11,11,13
11,12,13
11,13,11
11,13,12
11,13,13
12,11,13
12,12,13
12,13,11
12,13,12
12,13,13
13,11,11
13,11,12
13,11,13
13,12,11
13,12,12
13,12,13
13,13,11
13,13,12
13,13,13

The third step (off x=9..11,y=9..11,z=9..11) turns off a 3x3x3 cuboid that overlaps partially with some cubes that are on, ultimately turning off 8 cubes:

10,10,10
10,10,11
10,11,10
10,11,11
11,10,10
11,10,11
11,11,10
11,11,11

The final step (on x=10..10,y=10..10,z=10..10) turns on a single cube, 10,10,10. After this last step, 39 cubes are on.

The initialization procedure only uses cubes that have x, y, and z positions of at least -50 and at most 50. For now, ignore cubes outside this region.

Here is a larger example:

on x=-20..26,y=-36..17,z=-47..7
on x=-20..33,y=-21..23,z=-26..28
on x=-22..28,y=-29..23,z=-38..16
on x=-46..7,y=-6..46,z=-50..-1
on x=-49..1,y=-3..46,z=-24..28
on x=2..47,y=-22..22,z=-23..27
on x=-27..23,y=-28..26,z=-21..29
on x=-39..5,y=-6..47,z=-3..44
on x=-30..21,y=-8..43,z=-13..34
on x=-22..26,y=-27..20,z=-29..19
off x=-48..-32,y=26..41,z=-47..-37
on x=-12..35,y=6..50,z=-50..-2
off x=-48..-32,y=-32..-16,z=-15..-5
on x=-18..26,y=-33..15,z=-7..46
off x=-40..-22,y=-38..-28,z=23..41
on x=-16..35,y=-41..10,z=-47..6
off x=-32..-23,y=11..30,z=-14..3
on x=-49..-5,y=-3..45,z=-29..18
off x=18..30,y=-20..-8,z=-3..13
on x=-41..9,y=-7..43,z=-33..15
on x=-54112..-39298,y=-85059..-49293,z=-27449..7877
on x=967..23432,y=45373..81175,z=27513..53682

The last two steps are fully outside the initialization procedure area; all other steps are fully within it. After executing these steps in the initialization procedure region, 590784 cubes are on.

Execute the reboot steps. Afterward, considering only cubes in the region x=-50..50,y=-50..50,z=-50..50, how many cubes are on?

Read input

Today I'm using regular expression's named groups feature for the first time here. By prefixing a group with ?P<name>, after running re.match, you can refer to individual groups by their name.

It makes the regex often very much harder to read but I wanted to try it here.

Without named groups, I actually think this code would have looked better:

pattern = r'(on|off) x=(-?\d+..-?\d+),y=(-?\d+..-?\d+),z=(-?\d+..-?\d+)'
groups = re.match(pattern, line)
action = groups[0]
y_range = groups[1]
x_range = groups[2]
z_range = groups[3]

The thing with regex is that it can get complicated to read and understand real quick. I try to use it only for very simple patterns to make sure it can be understood by a glimpse. Anything more complicated than that, I prefer doing over multiple steps for clarity.

import re
from collections import namedtuple

from utils import read_input

Point = namedtuple('Point', ['x', 'y', 'z'])
Instruction = namedtuple('Instruction', ['action', 'start', 'end'])

def transformer(line):
    pattern = r'(?Pon|off) x=(?P-?\d+..-?\d+),y=(?P-?\d+..-?\d+),z=(?P-?\d+..-?\d+)'
    m = re.match(pattern, line)
    action = m.group('action')
    x_range = m.group('x')
    y_range = m.group('y')
    z_range = m.group('z')
    
    x1, x2 = x_range.split('..')
    y1, y2 = y_range.split('..')
    z1, z2 = z_range.split('..')
    
    start = Point(x=int(x1), y=int(y1), z=int(z1))
    end = Point(x=int(x2), y=int(y2), z=int(z2))
    
    return Instruction(action, start, end)
    
instructions = read_input(22, transformer)

Part 1

To start, we need to create all the cuboids in each of these ranges.

Since we're limiting our functionality to points between [-50, 50], we have a bit of bookkeeping in the start and then a triple for-loop for each of the axis.

def get_cuboids_in_range(start, end):
    cuboids = []
    if start.x < -50 and end.x < -50 or start.x > 50 and end.x > 50:
        return []
    if start.y < -50 and end.y < -50 or start.y > 50 and end.y > 50:
        return []
    if start.z < -50 and end.z < - 50 or start.z > 50 and end.z > 50:
        return []

    min_x = max(-50, min(50, start.x))
    max_x = min(50, max(-50, end.x))
    min_y = max(-50, min(50, start.y))
    max_y = min(50, max(-50, end.y))
    min_z = max(-50, min(50, start.z))
    max_z = min(50, max(-50, end.z))
        
    for x in range(min_x, max_x + 1):
        for y in range(min_y, max_y + 1):
            for z in range(min_z, max_z + 1):
                cuboids.append(Point(x,y,z))
    return cuboids

I keep track of lit cuboids and for each point in the given range, we either add it to the set (on) or take it off (off). Finally, we're left with a set of lit cuboids.

I learned today that set has two methods for removing items: discard and remove. I've been using remove with an if guard all these years but there's a nice difference:

discard(...) method of builtins.set instance
Remove an element from a set if it is a member.

If the element is not a member, do nothing.

remove(...) method of builtins.set instance
Remove an element from a set; it must be a member.

If the element is not a member, raise a KeyError.

So whenever you need to remove items that might not exist in a set, discard is a good option.

def activate_cuboids(instructions):
    lit = set()

    for instruction in instructions:
        for point in get_cuboids_in_range(instruction.start, instruction.end):
            match instruction.action:
                case 'on':
                    lit.add(point)
                case 'off':
                    lit.discard(point)
    return lit

Afterward, considering only cubes in the region x=-50..50,y=-50..50,z=-50..50, how many cubes are on?

Let's count our lit cuboids!

result = len(activate_cuboids(instructions))
print(f'Solution: {result}')
assert result == 648681

Solution: 648681

Part 2

Now that the initialization procedure is complete, you can reboot the reactor.

Starting with all cubes off, run all of the reboot steps for all cubes in the reactor.

Consider the following reboot steps:

on x=-5..47,y=-31..22,z=-19..33
on x=-44..5,y=-27..21,z=-14..35
on x=-49..-1,y=-11..42,z=-10..38
on x=-20..34,y=-40..6,z=-44..1
off x=26..39,y=40..50,z=-2..11
on x=-41..5,y=-41..6,z=-36..8
off x=-43..-33,y=-45..-28,z=7..25
on x=-33..15,y=-32..19,z=-34..11
off x=35..47,y=-46..-34,z=-11..5
on x=-14..36,y=-6..44,z=-16..29
on x=-57795..-6158,y=29564..72030,z=20435..90618
on x=36731..105352,y=-21140..28532,z=16094..90401
on x=30999..107136,y=-53464..15513,z=8553..71215
on x=13528..83982,y=-99403..-27377,z=-24141..23996
on x=-72682..-12347,y=18159..111354,z=7391..80950
on x=-1060..80757,y=-65301..-20884,z=-103788..-16709
on x=-83015..-9461,y=-72160..-8347,z=-81239..-26856
on x=-52752..22273,y=-49450..9096,z=54442..119054
on x=-29982..40483,y=-108474..-28371,z=-24328..38471
on x=-4958..62750,y=40422..118853,z=-7672..65583
on x=55694..108686,y=-43367..46958,z=-26781..48729
on x=-98497..-18186,y=-63569..3412,z=1232..88485
on x=-726..56291,y=-62629..13224,z=18033..85226
on x=-110886..-34664,y=-81338..-8658,z=8914..63723
on x=-55829..24974,y=-16897..54165,z=-121762..-28058
on x=-65152..-11147,y=22489..91432,z=-58782..1780
on x=-120100..-32970,y=-46592..27473,z=-11695..61039
on x=-18631..37533,y=-124565..-50804,z=-35667..28308
on x=-57817..18248,y=49321..117703,z=5745..55881
on x=14781..98692,y=-1341..70827,z=15753..70151
on x=-34419..55919,y=-19626..40991,z=39015..114138
on x=-60785..11593,y=-56135..2999,z=-95368..-26915
on x=-32178..58085,y=17647..101866,z=-91405..-8878
on x=-53655..12091,y=50097..105568,z=-75335..-4862
on x=-111166..-40997,y=-71714..2688,z=5609..50954
on x=-16602..70118,y=-98693..-44401,z=5197..76897
on x=16383..101554,y=4615..83635,z=-44907..18747
off x=-95822..-15171,y=-19987..48940,z=10804..104439
on x=-89813..-14614,y=16069..88491,z=-3297..45228
on x=41075..99376,y=-20427..49978,z=-52012..13762
on x=-21330..50085,y=-17944..62733,z=-112280..-30197
on x=-16478..35915,y=36008..118594,z=-7885..47086
off x=-98156..-27851,y=-49952..43171,z=-99005..-8456
off x=2032..69770,y=-71013..4824,z=7471..94418
on x=43670..120875,y=-42068..12382,z=-24787..38892
off x=37514..111226,y=-45862..25743,z=-16714..54663
off x=25699..97951,y=-30668..59918,z=-15349..69697
off x=-44271..17935,y=-9516..60759,z=49131..112598
on x=-61695..-5813,y=40978..94975,z=8655..80240
off x=-101086..-9439,y=-7088..67543,z=33935..83858
off x=18020..114017,y=-48931..32606,z=21474..89843
off x=-77139..10506,y=-89994..-18797,z=-80..59318
off x=8476..79288,y=-75520..11602,z=-96624..-24783
on x=-47488..-1262,y=24338..100707,z=16292..72967
off x=-84341..13987,y=2429..92914,z=-90671..-1318
off x=-37810..49457,y=-71013..-7894,z=-105357..-13188
off x=-27365..46395,y=31009..98017,z=15428..76570
off x=-70369..-16548,y=22648..78696,z=-1892..86821
on x=-53470..21291,y=-120233..-33476,z=-44150..38147
off x=-93533..-4276,y=-16170..68771,z=-104985..-24507

After running the above reboot steps, 2758514936282235 cubes are on. (Just for fun, 474140 of those are also in the initialization procedure region.)

Starting again with all cubes off, execute all reboot steps. Afterward, considering all cubes, how many cubes are on?

The size of the 3D grid grows so big (in my case, roughly 200k^3 points) that we can't rely on looping over every single point on every single range.

We need to do math! And to make that easier to manage, we'll make objects too!

Area class is like a cuboid but without all of its bits.

Like a cuboid from the previous part, it knows its start and end points but also keeps track of points that are off from it.

To calculate Area's volume, we take each of the x/y/z axis, subtract start value from end (and add 1 to make these ranges inclusive on both ends; a (1,1) -> (3,3) has 3 points each way, not 2) and multiply those together. We then remove the volume of any area that's bit off from it to get the actual volume.

To subtract one Area from another, we calculate its intersection (using math I found from the Interwebs), then subtract that intersection from all our off'd areas and finally add the intersection to our own off area.

class Area:
    
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.off = []
        
    def volume(self):
        full_volume = (self.end.x - self.start.x + 1) * (self.end.y - self.start.y + 1) * (self.end.z - self.start.z + 1)
        off_volume = sum(area.volume() for area in self.off)        
        return full_volume - off_volume

    def subtract(self, other):
        intersection = self.intersection(other)
        if intersection.is_empty():
            return
        for other in self.off:
            other.subtract(intersection)
        self.off.append(intersection)
        
    def intersection(self, another):
        new = {
            'start': [],
            'end': []
        }
        for axis in ['x', 'y', 'z']:
            one_start = getattr(self.start, axis)
            one_end = getattr(self.end, axis)
            another_start = getattr(another.start, axis)
            another_end = getattr(another.end, axis)

            max_start = max(one_start, another_start)
            min_end = min(one_end, another_end)

            if max_start < min_end + 1:
                new_start = max_start
                new_end = min_end
            else:
                new_start = 0
                new_end = 0
            new['start'].append(new_start)
            new['end'].append(new_end)

        start = Point(*new['start'])
        end = Point(*new['end'])
        return Area(start, end)
        
    def is_empty(self):
        xs = (self.start.x, self.end.x)
        ys = (self.start.y, self.end.y)
        zs = (self.start.z, self.end.z)
        return xs == (0, 0) or ys == (0, 0) or zs == (0, 0)

    
    def __repr__(self):
        return f': {self.start}, {self.end}'

areas = []

for instruction in instructions:
    area = Area(instruction.start, instruction.end)
    
    for other in areas:
        other.subtract(area)
        
    if instruction.action == 'on':
        areas.append(area)
        
result = sum(area.volume() for area in areas)
print(f'Solution: {result}')
assert result == 1302784472088899

Solution: 1302784472088899