advent_of_code_2021

My attempts to work through the 2021 Advent of Code problems.
git clone https://git.eamoncaddigan.net/advent_of_code_2021.git
Log | Files | Refs | README | LICENSE

day22_part2.py (8222B)


      1 #!/usr/bin/env python
      2 """Advent of Code 2021, day 22 (part 2): Reactor Reboot
      3 Apply on/off instructions to a much larger 3D grid of cuboids"""
      4 
      5 # Okay so part 2 updated part 1 in the obvious way that I totally expected. No
      6 # way we can store the on/off status of every coordinate. Insted we'll take a
      7 # different approach:
      8 #
      9 # Since everything starts in an "off" state, and the goal of the problem is to
     10 # determine how many cubes are "on", we don't need to pay attention to every
     11 # single coordinate. Instead, we can find the _total on-volume_. The _total
     12 # on-volume_ is the sum of the volume of every rectangular cuboid (which I will
     13 # just call "cubes" from now on). We'll process the on/off cuboids one at a
     14 # time. Each time we add a cube, we'll check its intersection with previous
     15 # cubes. When there's an intersection between old cube A and new cube B, we'll
     16 # find the set of cubes corresponding to the volume A not B, and these will
     17 # replace A in the list of on-cubes. When B is on, it will be added to the
     18 # list, and when B is off, it won't. This alogirhm is O(n^2) and could probably
     19 # be beaten by other approaches (I'm wondering about a sweep-plane, for
     20 # instance), but it's fairly straightforward to code; the hardest function is
     21 # the A not B cube splitter.
     22 
     23 from typing import Tuple, List, Union, NewType
     24 from functools import reduce
     25 from operator import mul
     26 
     27 from day22_part1 import Instruction, parse_input
     28 from utils import get_puzzle_input
     29 
     30 EXAMPLE_INPUT = \
     31 """on x=-5..47,y=-31..22,z=-19..33
     32 on x=-44..5,y=-27..21,z=-14..35
     33 on x=-49..-1,y=-11..42,z=-10..38
     34 on x=-20..34,y=-40..6,z=-44..1
     35 off x=26..39,y=40..50,z=-2..11
     36 on x=-41..5,y=-41..6,z=-36..8
     37 off x=-43..-33,y=-45..-28,z=7..25
     38 on x=-33..15,y=-32..19,z=-34..11
     39 off x=35..47,y=-46..-34,z=-11..5
     40 on x=-14..36,y=-6..44,z=-16..29
     41 on x=-57795..-6158,y=29564..72030,z=20435..90618
     42 on x=36731..105352,y=-21140..28532,z=16094..90401
     43 on x=30999..107136,y=-53464..15513,z=8553..71215
     44 on x=13528..83982,y=-99403..-27377,z=-24141..23996
     45 on x=-72682..-12347,y=18159..111354,z=7391..80950
     46 on x=-1060..80757,y=-65301..-20884,z=-103788..-16709
     47 on x=-83015..-9461,y=-72160..-8347,z=-81239..-26856
     48 on x=-52752..22273,y=-49450..9096,z=54442..119054
     49 on x=-29982..40483,y=-108474..-28371,z=-24328..38471
     50 on x=-4958..62750,y=40422..118853,z=-7672..65583
     51 on x=55694..108686,y=-43367..46958,z=-26781..48729
     52 on x=-98497..-18186,y=-63569..3412,z=1232..88485
     53 on x=-726..56291,y=-62629..13224,z=18033..85226
     54 on x=-110886..-34664,y=-81338..-8658,z=8914..63723
     55 on x=-55829..24974,y=-16897..54165,z=-121762..-28058
     56 on x=-65152..-11147,y=22489..91432,z=-58782..1780
     57 on x=-120100..-32970,y=-46592..27473,z=-11695..61039
     58 on x=-18631..37533,y=-124565..-50804,z=-35667..28308
     59 on x=-57817..18248,y=49321..117703,z=5745..55881
     60 on x=14781..98692,y=-1341..70827,z=15753..70151
     61 on x=-34419..55919,y=-19626..40991,z=39015..114138
     62 on x=-60785..11593,y=-56135..2999,z=-95368..-26915
     63 on x=-32178..58085,y=17647..101866,z=-91405..-8878
     64 on x=-53655..12091,y=50097..105568,z=-75335..-4862
     65 on x=-111166..-40997,y=-71714..2688,z=5609..50954
     66 on x=-16602..70118,y=-98693..-44401,z=5197..76897
     67 on x=16383..101554,y=4615..83635,z=-44907..18747
     68 off x=-95822..-15171,y=-19987..48940,z=10804..104439
     69 on x=-89813..-14614,y=16069..88491,z=-3297..45228
     70 on x=41075..99376,y=-20427..49978,z=-52012..13762
     71 on x=-21330..50085,y=-17944..62733,z=-112280..-30197
     72 on x=-16478..35915,y=36008..118594,z=-7885..47086
     73 off x=-98156..-27851,y=-49952..43171,z=-99005..-8456
     74 off x=2032..69770,y=-71013..4824,z=7471..94418
     75 on x=43670..120875,y=-42068..12382,z=-24787..38892
     76 off x=37514..111226,y=-45862..25743,z=-16714..54663
     77 off x=25699..97951,y=-30668..59918,z=-15349..69697
     78 off x=-44271..17935,y=-9516..60759,z=49131..112598
     79 on x=-61695..-5813,y=40978..94975,z=8655..80240
     80 off x=-101086..-9439,y=-7088..67543,z=33935..83858
     81 off x=18020..114017,y=-48931..32606,z=21474..89843
     82 off x=-77139..10506,y=-89994..-18797,z=-80..59318
     83 off x=8476..79288,y=-75520..11602,z=-96624..-24783
     84 on x=-47488..-1262,y=24338..100707,z=16292..72967
     85 off x=-84341..13987,y=2429..92914,z=-90671..-1318
     86 off x=-37810..49457,y=-71013..-7894,z=-105357..-13188
     87 off x=-27365..46395,y=31009..98017,z=15428..76570
     88 off x=-70369..-16548,y=22648..78696,z=-1892..86821
     89 on x=-53470..21291,y=-120233..-33476,z=-44150..38147
     90 off x=-93533..-4276,y=-16170..68771,z=-104985..-24507
     91 """
     92 
     93 # We'll represent cubes using a 3-tuple of 2-tuples giving the X, Y, and Z
     94 # extents
     95 Cube = NewType(
     96     'Cube',
     97     Tuple[Tuple[int, int], Tuple[int, int], Tuple[int, int]]
     98 )
     99 
    100 def cleave_cube(on_cube: Cube, value: int,
    101                 axis: int) -> Tuple[Union[None, Cube], Union[None, Cube]]:
    102     """Split a cube along the given axis, returning two cubes (or one cube and
    103     `None`), corresponding to the cube strictly greater than `value` along
    104     `axis`, and the cube less than or equal to `value` along `axis`"""
    105     if on_cube[axis][0] > value:
    106         return (None, on_cube)
    107     if on_cube[axis][1] <= value:
    108         return (on_cube, None)
    109     # We actually have to cleave the cube. First we create a list of lists of
    110     # lists representing two copies of the cube.
    111     new_cubes_list = [[list(e) for e in on_cube] for _ in range(2)]
    112     new_cubes_list[0][axis][1] = value
    113     new_cubes_list[1][axis][0] = value + 1
    114     # I don't know why but this is giving me Lisp flashbacks
    115     return tuple(Cube(tuple(tuple(e) for e in c)) for c in new_cubes_list)
    116 
    117 def split_cube(old_cube: Cube, new_cube: Cube) -> List[Cube]:
    118     """Return a list containing one or more cubes representing the volume of
    119     `old_cube` that doesn't intersect with `new_cube`"""
    120     # This is the hard part. If this doesn't work I'm sunk!
    121     new_cubes = []
    122     intersection_cube = old_cube
    123     for axis in range(3):
    124         # First check if the cubes intersect along this axis. If they don't,
    125         # we're done: no splitting necessary!
    126         if old_cube[axis][0] > new_cube[axis][1] \
    127                 or old_cube[axis][1] < new_cube[axis][0]:
    128             return [old_cube]
    129         # So they may intersect somehow. We'll cleave the cube into as many as
    130         # three new cubes: the part "above" `new_cube`, the part "below" it,
    131         # and the intersection; above and below could either or both be `None`,
    132         # but intersection better not be. Note that this can create way more
    133         # cubes than necessary; I'm hoping that the number of cubes doesn't
    134         # explode.
    135         intersection_cube, above_cube = cleave_cube(intersection_cube,
    136                                                     new_cube[axis][1],
    137                                                     axis)
    138         below_cube, intersection_cube = cleave_cube(intersection_cube,
    139                                                     new_cube[axis][0]-1,
    140                                                     axis)
    141         if above_cube is not None:
    142             new_cubes.append(above_cube)
    143         if below_cube is not None:
    144             new_cubes.append(below_cube)
    145     return new_cubes
    146 
    147 def add_cube(on_cubes: List[Cube], instruction: Instruction) -> List[Cube]:
    148     """Apply a single step of the instructions to the list of on-cubes and
    149     return a new list of cubes"""
    150     new_cube = Cube(instruction[1:])
    151     new_on_cubes = []
    152     for old_cube in on_cubes:
    153         new_on_cubes.extend(split_cube(old_cube, new_cube))
    154     if instruction[0]:
    155         new_on_cubes.append(new_cube)
    156     return new_on_cubes
    157 
    158 def create_on_cube_list(instructions: List[Instruction]) -> List[Cube]:
    159     """Build a list of on-cubes by following the instructions"""
    160     return reduce(add_cube, instructions[1:], [Cube(instructions[0][1:])])
    161 
    162 def cube_volume(on_cube: Cube) -> int:
    163     """Return the volume of a single cube"""
    164     return reduce(mul, [e[1] - e[0] + 1 for e in on_cube])
    165 
    166 def solve_puzzle(input_string: str) -> int:
    167     """Return the numeric solution to the puzzle"""
    168     return sum(map(cube_volume,
    169                    create_on_cube_list(parse_input(input_string))))
    170 
    171 def main() -> None:
    172     """Run when the file is called as a script"""
    173     assert solve_puzzle(EXAMPLE_INPUT) == 2758514936282235
    174     print("Number of cubes turned on:",
    175           solve_puzzle(get_puzzle_input(22)))
    176 
    177 if __name__ == "__main__":
    178     main()