Part 1

This is it: the bottom of the ocean trench, the last place the sleigh keys could be. Your submarine's experimental antenna still isn't boosted enough to detect the keys, but they must be here. All you need to do is reach the seafloor and find them.

At least, you'd touch down on the seafloor if you could; unfortunately, it's completely covered by two large herds of sea cucumbers, and there isn't an open space large enough for your submarine.

You suspect that the Elves must have done this before, because just then you discover the phone number of a deep-sea marine biologist on a handwritten note taped to the wall of the submarine's cockpit.

"Sea cucumbers? Yeah, they're probably hunting for food. But don't worry, they're predictable critters: they move in perfectly straight lines, only moving forward when there's space to do so. They're actually quite polite!"

You explain that you'd like to predict when you could land your submarine.

"Oh that's easy, they'll eventually pile up and leave enough space for-- wait, did you say submarine? And the only place with that many sea cucumbers would be at the very bottom of the Mariana--" You hang up the phone.

There are two herds of sea cucumbers sharing the same region; one always moves east (>), while the other always moves south (v). Each location can contain at most one sea cucumber; the remaining locations are empty (.). The submarine helpfully generates a map of the situation (your puzzle input). For example:

v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>

Every step, the sea cucumbers in the east-facing herd attempt to move forward one location, then the sea cucumbers in the south-facing herd attempt to move forward one location. When a herd moves forward, every sea cucumber in the herd first simultaneously considers whether there is a sea cucumber in the adjacent location it's facing (even another sea cucumber facing the same direction), and then every sea cucumber facing an empty location simultaneously moves into that location.

So, in a situation like this:

...>>>>>...

After one step, only the rightmost sea cucumber would have moved:

...>>>>.>..

After the next step, two sea cucumbers move:

...>>>.>.>.

During a single step, the east-facing herd moves first, then the south-facing herd moves. So, given this situation:

..........
.>v....v..
.......>..
..........

After a single step, of the sea cucumbers on the left, only the south-facing sea cucumber has moved (as it wasn't out of the way in time for the east-facing cucumber on the left to move), but both sea cucumbers on the right have moved (as the east-facing sea cucumber moved out of the way of the south-facing sea cucumber):

..........
.>........
..v....v>.
..........

Due to strong water currents in the area, sea cucumbers that move off the right edge of the map appear on the left edge, and sea cucumbers that move off the bottom edge of the map appear on the top edge. Sea cucumbers always check whether their destination location is empty before moving, even if that destination is on the opposite side of the map:

Initial state:
...>...
.......
......>
v.....>
......>
.......
..vvv..

After 1 step:
..vv>..
.......
>......
v.....>
>......
.......
....v..

After 2 steps:
....v>.
..vv...
.>.....
......>
v>.....
.......
.......

After 3 steps:
......>
..v.v..
..>v...
>......
..>....
v......
.......

After 4 steps:
>......
..v....
..>.v..
.>.v...
...>...
.......
v......

To find a safe place to land your submarine, the sea cucumbers need to stop moving. Again consider the first example:

Initial state:
v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>

After 1 step:
....>.>v.>
v.v>.>v.v.
>v>>..>v..
>>v>v>.>.v
.>v.v...v.
v>>.>vvv..
..v...>>..
vv...>>vv.
>.v.v..v.v

After 2 steps:
>.v.v>>..v
v.v.>>vv..
>v>.>.>.v.
>>v>v.>v>.
.>..v....v
.>v>>.v.v.
v....v>v>.
.vv..>>v..
v>.....vv.

After 3 steps:
v>v.v>.>v.
v...>>.v.v
>vv>.>v>..
>>v>v.>.v>
..>....v..
.>.>v>v..v
..v..v>vv>
v.v..>>v..
.v>....v..

After 4 steps:
v>..v.>>..
v.v.>.>.v.
>vv.>>.v>v
>>.>..v>.>
..v>v...v.
..>>.>vv..
>.v.vv>v.v
.....>>vv.
vvv>...v..

After 5 steps:
vv>...>v>.
v.v.v>.>v.
>.v.>.>.>v
>v>.>..v>>
..v>v.v...
..>.>>vvv.
.>...v>v..
..v.v>>v.v
v.v.>...v.

...

After 10 steps:
..>..>>vv.
v.....>>.v
..v.v>>>v>
v>.>v.>>>.
..v>v.vv.v
.v.>>>.v..
v.v..>v>..
..v...>v.>
.vv..v>vv.

...

After 20 steps:
v>.....>>.
>vv>.....v
.>v>v.vv>>
v>>>v.>v.>
....vv>v..
.v.>>>vvv.
..v..>>vv.
v.v...>>.v
..v.....v>

...

After 30 steps:
.vv.v..>>>
v>...v...>
>.v>.>vv.>
>v>.>.>v.>
.>..v.vv..
..v>..>>v.
....v>..>v
v.v...>vv>
v.v...>vvv

...

After 40 steps:
>>v>v..v..
..>>v..vv.
..>>>v.>.v
..>>>>vvv>
v.....>...
v.v...>v>>
>vv.....v>
.>v...v.>v
vvv.v..v.>

...

After 50 steps:
..>>v>vv.v
..v.>>vv..
v.>>v>>v..
..>>>>>vv.
vvv....>vv
..v....>>>
v>.......>
.vv>....v>
.>v.vv.v..

...

After 55 steps:
..>>v>vv..
..v.>>vv..
..>>v>>vv.
..>>>>>vv.
v......>vv
v>v....>>v
vvv...>..>
>vv.....>.
.>v.vv.v..

After 56 steps:
..>>v>vv..
..v.>>vv..
..>>v>>vv.
..>>>>>vv.
v......>vv
v>v....>>v
vvv....>.>
>vv......>
.>v.vv.v..

After 57 steps:
..>>v>vv..
..v.>>vv..
..>>v>>vv.
..>>>>>vv.
v......>vv
v>v....>>v
vvv.....>>
>vv......>
.>v.vv.v..

After 58 steps:
..>>v>vv..
..v.>>vv..
..>>v>>vv.
..>>>>>vv.
v......>vv
v>v....>>v
vvv.....>>
>vv......>
.>v.vv.v..

In this example, the sea cucumbers stop moving after _58_ steps.

Find somewhere safe to land your submarine. What is the first step on which no sea cucumbers move?

Proposed solution: setup a map for the positions with the different direction sea cucumbers, and loop until the sea cucumbers reach a stable state

Time complexity: O(n) where n is the area of the river

Space complexity: O(n)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

field = {}
herds = [">", "v"]
for y, line in enumerate(file_input):
    if line == "":
        break
    for x, char in enumerate(line):
        if char == ".":
            continue
        field[x,y] = char

width, height = len(file_input[0]), len(file_input)
def print_field(field):
    for y in range(height):
        result = ""
        for x in range(width):
            if (x,y) not in field:
                result += "."
            else:
                result += field[x,y]
        print(result)
    print("")

num_steps, moves = 0, -1
while moves != 0:
    moves = 0
    for herd in herds:
        field_copy = dict(field)
        for pos, val in field_copy.items():
            if val == herd:
                x, y = 0, 0
                if herd == ">":
                    x = 1
                if herd == "v":
                    y = 1
                next_pos = (pos[0] + x) % width, (pos[1] + y) % height
                if next_pos in field_copy:
                    continue
                moves += 1
                field[next_pos] = herd
                field.pop(pos)
    num_steps += 1
    #print_field(field)

print("Number of steps: {}".format(num_steps))

❯ time python3 solution25.py input25
Number of steps: 337
python3 solution25.py input25  1.86s user 0.02s system 99% cpu 1.878 total

Part 2

Suddenly, the experimental antenna control console lights up:

Sleigh keys detected!

According to the console, the keys are directly under the submarine. You landed right on them! Using a robotic arm on the submarine, you move the sleigh keys into the airlock.

Now, you just need to get them to Santa in time to save Christmas! You check your clock - it is Christmas. There's no way you can get them back to the surface in time.

Just as you start to lose hope, you notice a button on the sleigh keys: remote start. You can start the sleigh from the bottom of the ocean! You just need some way to boost the signal from the keys so it actually reaches the sleigh. Good thing the submarine has that experimental antenna! You'll definitely need 50 stars to boost it that far, though.

The experimental antenna control console lights up again:

Energy source detected.
Integrating energy source from device "sleigh keys"...done.
Installing device drivers...done.
Recalibrating experimental antenna...done.
Boost strength due to matching signal phase: 1 star

Only 49 stars to go.

You have enough stars to [Remotely Start The Sleigh].

I have uploaded all of my 2021 solutions to GitHub: https://github.com/elveskevtar/AdventOfCode/

Part 1

Magic smoke starts leaking from the submarine's arithmetic logic unit (ALU). Without the ability to perform basic arithmetic and logic functions, the submarine can't produce cool patterns with its Christmas lights!

It also can't navigate. Or run the oxygen system.

Don't worry, though - you probably have enough oxygen left to give you enough time to build a new ALU.

The ALU is a four-dimensional processing unit: it has integer variables w, x, y, and z. These variables all start with the value 0. The ALU also supports six instructions:

• inp a - Read an input value and write it to variable a.
• add a b - Add the value of a to the value of b, then store the result in variable a.
• mul a b - Multiply the value of a by the value of b, then store the result in variable a.
• div a b - Divide the value of a by the value of b, truncate the result to an integer, then store the result in variable a. (Here, "truncate" means to round the value toward zero.)
• mod a b - Divide the value of a by the value of b, then store the remainder in variable a. (This is also called the modulo operation.)
• eql a b - If the value of a and b are equal, then store the value 1 in variable a. Otherwise, store the value 0 in variable a.

In all of these instructions, a and b are placeholders; a will always be the variable where the result of the operation is stored (one of w, x, y, or z), while b can be either a variable or a number. Numbers can be positive or negative, but will always be integers.

The ALU has no jump instructions; in an ALU program, every instruction is run exactly once in order from top to bottom. The program halts after the last instruction has finished executing.

(Program authors should be especially cautious; attempting to execute div with b=0 or attempting to execute mod with a<0 or b<=0 will cause the program to crash and might even damage the ALU. These operations are never intended in any serious ALU program.)

For example, here is an ALU program which takes an input number, negates it, and stores it in x:

inp x
mul x -1

Here is an ALU program which takes two input numbers, then sets z to 1 if the second input number is three times larger than the first input number, or sets z to 0 otherwise:

inp z
inp x
mul z 3
eql z x

Here is an ALU program which takes a non-negative integer as input, converts it into binary, and stores the lowest (1's) bit in z, the second-lowest (2's) bit in y, the third-lowest (4's) bit in x, and the fourth-lowest (8's) bit in w:

inp w
add z w
mod z 2
div w 2
add y w
mod y 2
div w 2
add x w
mod x 2
div w 2
mod w 2

Once you have built a replacement ALU, you can install it in the submarine, which will immediately resume what it was doing when the ALU failed: validating the submarine's model number. To do this, the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).

Submarine model numbers are always fourteen-digit numbers consisting only of digits 1 through 9. The digit 0 cannot appear in a model number.

When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate inp instructions, each expecting a single digit of the model number in order of most to least significant. (So, to check the model number 13579246899999, you would give 1 to the first inp instruction, 3 to the second inp instruction, 5 to the third inp instruction, and so on.) This means that when operating MONAD, each input instruction should only ever be given an integer value of at least 1 and at most 9.

Then, after MONAD has finished running all of its instructions, it will indicate that the model number was valid by leaving a 0 in variable z. However, if the model number was invalid, it will leave some other non-zero value in z.

MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a tanuki. You'll need to figure out what MONAD does some other way.

To enable as many submarine features as possible, find the largest valid fourteen-digit model number that contains no 0 digits. What is the largest model number accepted by MONAD?

Proposed solution: at first I created an ALU simulator to run the program but quickly realized that brute forcing the answer was not going to work very well; instead I opted for reverse engineering the problem and figured it out with just pen and paper – the simulator still helped for validation

#!/usr/bin/env python3
import sys

if len(sys.argv) != 3:
    print("Usage: {} <input file> <model #>".format(sys.argv[0]))
    sys.exit(1)

model_num = sys.argv[2]
if len(model_num) != 14 or not model_num.isnumeric() or "0" in model_num:
    print("Model number must be 14 digits with no 0's")
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

i = 0
variables = {var: 0 for var in ["w", "x", "y", "z"]}
for line in file_input:
    if line == "":
        continue
    instr = line.split()
    if instr[0] == "inp":
		print(variables)
        variables[instr[1]] = model_num[i]
        i += 1
    if instr[0] == "add":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] += int(operand)
    if instr[0] == "mul":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] *= int(operand)
    if instr[0] == "div":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        if int(operand) == 0:
            print("Divide by zero error")
            sys.exit(1)
        variables[instr[1]] //= int(operand)
    if instr[0] == "mod":
        if variables[instr[1]] < 0:
            print("Modulo dividend < 0")
            sys.exit(1)
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        if int(operand) <= 0:
            print("Modulo divisor <= 0")
            sys.exit(1)
        variables[instr[1]] %= int(operand)
    if instr[0] == "eql":
        operand = instr[2] if instr[2].strip("-").isnumeric() else variables[instr[2]]
        variables[instr[1]] = int(variables[instr[1]] == int(operand))

print(variables)

❯ python3 solution24.py input24 11111111111111
...
...
{'w': '1', 'x': 1, 'y': 10, 'z': 3118601834}

What I discovered about the input program is that there were 14 segments that looked very similar to each other: one for each number in the model number. However, there are two distinct operations that were being performed based on the position within the model number.

inp w
mul x 0
add x z
mod x 26
div z 1
add x 15
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 9
mul y x
add z y

The first type of block multiplies z by 26 and adds the next digit in the model number and some offset. In the above example, this offset is 9.

inp w
mul x 0
add x z
mod x 26
div z 26
add x -6
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 7
mul y x
add z y

This second type of block is basically the reverse of the first. Some lines in particular which make this not trivial:

mul y 0
add y 25
mul y x
add y 1
mul z y

x here is 1 if (z % 26) + offset != w and 0 otherwise. In the example block above, this offset is -6. We want x to be 0, meaning that (z % 26) + offset == w otherwise, this ends up resulting in z *= 26 instead of z *= 1 which reverses the z /= 26 performed earlier in the same block. Basically, we need to choose numbers in the respective first block type which results in x becoming 0 in the respective second block type.

Here, I am saying respective because this multiplication/division by 26 is like a stack operation. There are 7 numbers which have respective blocks like the first section and 7 numbers which have the second section – but not necessarily in that order. For example, my input program has the blocks in the following order:

first  (offset: 9)    >
first  (offset: 1)     >
first  (offset: 11)     >
first  (offset: 3)       >
second (offset: -11)      <
first  (offset: 5)       >
first  (offset: 0)        >
second (offset: -6)        <
first  (offset: 9)        >
second (offset: -6)        <
second (offset: -6)       <
second (offset: -16)     <
second (offset: -4)     <
second (offset: -2)    <

I tried to represent the stack growing and shrinking based on the first/second blocks. Of course the "stack" in this case is the value of the z register and each second block only divides the number by 26 successfully if that condition is met. Our goal is to craft the largest model number that satisfies all of these conditions for all second blocks. This will produce a z value of 0 at the end of the program.

I try this with pen and paper by setting each first block with the model digit as 9 and when hitting a second block, calculating what digit would satisfy the condition to set x as 0. If no digit will satisfy this (because the number needed is more than a single digit), I backtracked to the respective first block and lowered the digit until we could use a single digit for the second block.

z=0
w=9 z = 26*z+9+w = 18
w=9 z = 26*18+1+w = 478
w=9 z = 26*478+11+w = 12448
w=9 z = 26*12448+3+w = 323660
w=1 (323660 % 26) - 11 == 1
w=9 z = 26*12448+5+w = 323662
w=9 z = 26*323662+0+w = 8415221
w=3 (8415221 % 26) - 6 == 3
w=9 z = 26*323662+9+w = 8415230
w=? (8415230 % 26) - 6 == 12

We hit a problem with the 10th digit since we need w to be 12 but this comes from inp w which just takes a single digit from the model number. We have to backtrack to the 9th digit. If we set the 9th digit to 6, we should be able to set the 10th digit as 9 and continue.

z=0
w=9 z = 26*z+9+w = 18
w=9 z = 26*18+1+w = 478
w=9 z = 26*478+11+w = 12448
w=9 z = 26*12448+3+w = 323660
w=1 (323660 % 26) - 11 == 1
w=9 z = 26*12448+5+w = 323662
w=9 z = 26*323662+0+w = 8415221
w=3 (8415221 % 26) - 6 == 3
w=6 z = 26*323662+9+w = 8415227
w=9 (8415227 % 26) - 6 == 9
w=8 (323662 % 26) - 6 == 8
w=4 (12448 % 26) - 16 == 4
w=6 (478 % 26) - 4 == 6
w=? (18 % 26) - 2 == 16

We have to backtrack one more time. For the 14th digit, the condition resolves to 16 which is too large. We have to decrement the first digit by 7 in order to have the 14th digit work out to be a single digit 9. This will be the largest valid model number that passes the program resulting in z = 0.

z=0
w=2 z = 26*z+9+w = 11
w=9 z = 26*11+1+w = 296
w=9 z = 26*296+11+w = 7716
w=9 z = 26*7716+3+w = 200628
w=1 (200628 % 26) - 11 == 1
w=9 z = 26*7716+5+w = 200630
w=9 z = 26*200630+0+w = 5216389
w=3 (5216389 % 26) - 6 == 3
w=6 z = 26*200630+9+w = 5216395
w=9 (5216395 % 26) - 6 == 9
w=8 (200630 % 26) - 6 == 8
w=4 (7716 % 26) - 16 == 4
w=6 (296 % 26) - 4 == 6
w=9 (11 % 26) - 2 == 9

And some validation with our simulator:

❯ python3 solution24.py input24 29991993698469
{'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'w': '2', 'x': 1, 'y': 11, 'z': 11}
{'w': '9', 'x': 1, 'y': 10, 'z': 296}
{'w': '9', 'x': 1, 'y': 20, 'z': 7716}
{'w': '9', 'x': 1, 'y': 12, 'z': 200628}
{'w': '1', 'x': 0, 'y': 0, 'z': 7716}
{'w': '9', 'x': 1, 'y': 14, 'z': 200630}
{'w': '9', 'x': 1, 'y': 9, 'z': 5216389}
{'w': '3', 'x': 0, 'y': 0, 'z': 200630}
{'w': '6', 'x': 1, 'y': 15, 'z': 5216395}
{'w': '9', 'x': 0, 'y': 0, 'z': 200630}
{'w': '8', 'x': 0, 'y': 0, 'z': 7716}
{'w': '4', 'x': 0, 'y': 0, 'z': 296}
{'w': '6', 'x': 0, 'y': 0, 'z': 11}
{'w': '9', 'x': 0, 'y': 0, 'z': 0}

Part 2

As the submarine starts booting up things like the Retro Encabulator, you realize that maybe you don't need all these submarine features after all.

What is the smallest model number accepted by MONAD?

Proposed solution: same solution but picking the smallest numbers for each digit which make a valid model number

❯ python3 solution24.py input24 14691271141118
{'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'w': '1', 'x': 1, 'y': 10, 'z': 10}
{'w': '4', 'x': 1, 'y': 5, 'z': 265}
{'w': '6', 'x': 1, 'y': 17, 'z': 6907}
{'w': '9', 'x': 1, 'y': 12, 'z': 179594}
{'w': '1', 'x': 0, 'y': 0, 'z': 6907}
{'w': '2', 'x': 1, 'y': 7, 'z': 179589}
{'w': '7', 'x': 1, 'y': 7, 'z': 4669321}
{'w': '1', 'x': 0, 'y': 0, 'z': 179589}
{'w': '1', 'x': 1, 'y': 10, 'z': 4669324}
{'w': '4', 'x': 0, 'y': 0, 'z': 179589}
{'w': '1', 'x': 0, 'y': 0, 'z': 6907}
{'w': '1', 'x': 0, 'y': 0, 'z': 265}
{'w': '1', 'x': 0, 'y': 0, 'z': 10}
{'w': '8', 'x': 0, 'y': 0, 'z': 0}

Part 1

A group of amphipods notice your fancy submarine and flag you down. "With such an impressive shell," one amphipod says, "surely you can help us with a question that has stumped our best scientists."

They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types of amphipods live there: Amber (A), Bronze (B), Copper (C), and Desert (D). They live in a burrow that consists of a hallway and four side rooms. The side rooms are initially full of amphipods, and the hallway is initially empty.

They give you a diagram of the situation (your puzzle input), including locations of each amphipod (A, B, C, or D, each of which is occupying an otherwise open space), walls (#), and open space (.).

For example:

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

The amphipods would like a method to organize every amphipod into side rooms so that each side room contains one type of amphipod and the types are sorted A-D going left to right, like this:

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open space. Each type of amphipod requires a different amount of energy to move one step: Amber amphipods require 1 energy per step, Bronze amphipods require 10 energy, Copper amphipods require 100, and Desert ones require 1000. The amphipods would like you to find a way to organize the amphipods that requires the least total energy.

However, because they are timid and stubborn, the amphipods have some extra rules:

• Amphipods will never stop on the space immediately outside any room. They can move into that space so long as they immediately continue moving. (Specifically, this refers to the four open spaces in the hallway that are directly above an amphipod starting position.)
• Amphipods will never move from the hallway into a room unless that room is their destination room and that room contains no amphipods which do not also have that room as their own destination. If an amphipod's starting room is not its destination room, it can stay in that room until it leaves the room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and will only move into the leftmost room if that room is empty or if it only contains other Amber amphipods.)
• Once an amphipod stops moving in the hallway, it will stay in that spot until it can move into a room. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are locked in place and will not move again until they can move fully into a room.)

In the above example, the amphipods can be organized using a minimum of _12521_ energy. One way to do this is shown below.

Starting configuration:

#############
#...........#
###B#C#B#D###
  #A#D#C#A#
  #########

One Bronze amphipod moves into the hallway, taking 4 steps and using 40 energy:

#############
#...B.......#
###B#C#.#D###
  #A#D#C#A#
  #########

The only Copper amphipod not in its side room moves there, taking 4 steps and using 400 energy:

#############
#...B.......#
###B#.#C#D###
  #A#D#C#A#
  #########

A Desert amphipod moves out of the way, taking 3 steps and using 3000 energy, and then the Bronze amphipod takes its place, taking 3 steps and using 30 energy:

#############
#.....D.....#
###B#.#C#D###
  #A#B#C#A#
  #########

The leftmost Bronze amphipod moves to its room using 40 energy:

#############
#.....D.....#
###.#B#C#D###
  #A#B#C#A#
  #########

Both amphipods in the rightmost room move into the hallway, using 2003 energy in total:

#############
#.....D.D.A.#
###.#B#C#.###
  #A#B#C#.#
  #########

Both Desert amphipods move into the rightmost room using 7000 energy:

#############
#.........A.#
###.#B#C#D###
  #A#B#C#D#
  #########

Finally, the last Amber amphipod moves into its room, using 8 energy:

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #########

What is the least energy required to organize the amphipods?

Proposed solution: make copies of the map for every possible move given a certain state and repeat for all possible moves until no more moves – keep track of already visited states to prevent simulating all of the resulting branches multiple times

#!/usr/bin/env python3
from collections import deque
from copy import deepcopy
from heapq import heappush
from math import copysign
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

multiplier = {"A": 1, "B": 10, "C": 100, "D": 1000}
amphipod_dst = {"A": 2, "B": 4, "C": 6, "D": 8}

class Amphipod:
    def __init__(self, label, pos):
        self.label = label
        self.pos = pos
        self.moved = False
        self.points = 0

    def move(self, new_pos, field):
        self.moved = True
        moves = abs(self.pos[0] - new_pos[0]) + abs(self.pos[1] - new_pos[1])
        self.points += moves * multiplier[self.label]
        field[new_pos] = self
        field[self.pos] = None
        self.pos = new_pos

    def __repr__(self):
        return "Amphipod({})".format(self.label)

    def __eq__(self, other):
        return other and self.label == other.label \
                and self.pos == other.pos and self.moved == other.moved \
                and self.points == other.points

    def __hash__(self):
        return hash((self.label, self.pos, self.moved, self.points))

def field_score(field):
    points = 0
    for pod in field.values():
        if pod is not None:
            points += pod.points
    return points

def hash_field(field):
    states = []
    for pod in field.values():
        if pod is not None:
            states.append(hash(pod))
    states.sort()
    return hash(tuple(states))

def field_solved(field):
    return field[2,1] and field[2,2] and field[4,1] and field[4,2] \
            and field[6,1] and field[6,2] and field[8,1] and field[8,2] \
            and field[2,1].label == "A" and field[2,2].label == "A" \
            and field[4,1].label == "B" and field[4,2].label == "B" \
            and field[6,1].label == "C" and field[6,2].label == "C" \
            and field[8,1].label == "D" and field[8,2].label == "D"

def print_field(field):
    for y in range(3):
        result = ""
        for x in range(11):
            if (x,y) not in field:
                result += "#"
            elif field[x,y] is None:
                result += "."
            else:
                result += field[x,y].label
        print(result)
    print("")

field = {(x,0):None for x in range(11)}

for x in range(4):
    x = x*2 + 3
    field[x-1,1] = Amphipod(file_input[2][x], (x-1,1))
    field[x-1,2] = Amphipod(file_input[3][x], (x-1,2))

visited_states = set()
queue = deque()
queue.append(field)
room_rows = [2,4,6,8]
min_energy_cost = sys.maxsize
while len(queue) != 0:
    field = queue.pop()
    field_hash = hash_field(field)
    if field_hash in visited_states or field_score(field) > min_energy_cost:
        continue
    visited_states.add(field_hash)
    if field_solved(field):
        min_energy_cost = min(min_energy_cost, field_score(field))
        print(min_energy_cost)
        continue
    for y in range(1,3):
        for x in range(4):
            x = x*2 + 2
            if field[x,y-1]: continue
            if field[x,y] and not field[x,y].moved:
                for x2 in range(x-1, -1, -1):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field)
                    amphipod = new_field[x,y]
                    amphipod.move((x2,0), new_field)
                    queue.append(new_field)
                for x2 in range(x+1, 11):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field)
                    amphipod = new_field[x,y]
                    amphipod.move((x2,0), new_field)
                    queue.append(new_field)
    for x in range(11):
        if not field[x,0]: continue
        dest = amphipod_dst[field[x,0].label]
        if field[dest,1]: continue
        if field[dest,2] and field[dest,2].label != field[x,0].label: continue
        direction = int(copysign(1, dest-x))
        for x2 in range(x+direction, dest+direction, direction):
            if field[x2,0]: break
            if x2 != dest: continue
            if field[x2,2]:
                new_field = deepcopy(field)
                amphipod = new_field[x,0]
                amphipod.move((x2,1), new_field)
                queue.append(new_field)
            else:
                new_field = deepcopy(field)
                amphipod = new_field[x,0]
                amphipod.move((x2,2), new_field)
                queue.append(new_field)

This gives the right solution for part 1 but it takes about 2 minutes to run. Here is a quick breakdown of this initial solution.

multiplier = {"A": 1, "B": 10, "C": 100, "D": 1000}
amphipod_dst = {"A": 2, "B": 4, "C": 6, "D": 8}

multiplier outlines the respective multipliers for each amphipod type. amphipod_dst outlines the x position that each amphipod needs to reach. The "field" object I create does not include the walls so the hallway is y=0 and the first room is at x=2.

class Amphipod:
    def __init__(self, label, pos):
        self.label = label
        self.pos = pos
        self.moved = False
        self.points = 0

    def move(self, new_pos, field):
        self.moved = True
        moves = abs(self.pos[0] - new_pos[0]) + abs(self.pos[1] - new_pos[1])
        self.points += moves * multiplier[self.label]
        field[new_pos] = self
        field[self.pos] = None
        self.pos = new_pos

    def __repr__(self):
        return "Amphipod({})".format(self.label)

    def __eq__(self, other):
        return other and self.label == other.label \
                and self.pos == other.pos and self.moved == other.moved \
                and self.points == other.points

    def __hash__(self):
        return hash((self.label, self.pos, self.moved, self.points))

Each amphipod has a label, a position (which is also tracked by the field dictionary), and a flag to track if it's already moved into the hallway – this last one when set to True means that the amphipod can only move once more, straight into its destination room. I override __repr__ for nice printing of the object and I override __eq__ and __hash__ so that these objects can be hashed based on all of the class level attributes. I did this to create a good hashing function for tracking already visited states. See below.

The move function updates the amphipods position & moved flag, the respective field dictionary, and the amphipod's points accumulator. Also, the points are being stored per amphipod object but I end up moving this to the field object in the next iteration so we don't have to count the number of points across the field dictionary everytime we need to get the number of points.

def print_field(field):
    for y in range(3):
        result = ""
        for x in range(11):
            if (x,y) not in field:
                result += "#"
            elif field[x,y] is None:
                result += "."
            else:
                result += field[x,y].label
        print(result)
    print("")

This function prints the field like this:

...........
##D#B#B#A##
##C#C#D#A##

This was convenient for debugging some issues with the actual solution logic. I'm going to skip over the other field functions since these end up simplified or moved to a field class in the next iteration of my solution.

visited_states = set()
queue = deque()
queue.append(field)
room_rows = [2,4,6,8]
min_energy_cost = sys.maxsize
while len(queue) != 0:
    field = queue.pop()
    field_hash = hash_field(field)
    if field_hash in visited_states or field_score(field) > min_energy_cost:
        continue
    visited_states.add(field_hash)
    if field_solved(field):
        min_energy_cost = min(min_energy_cost, field_score(field))
        print(min_energy_cost)
        continue

The queue object contains copies of the field dictionary in different states which it iterates over in the main loop. During each iteration, it takes the field at the top of the queue, pops it off, and pushes all possible resulting states from the intial state onto the stack. This is repeated until all possible states have been visited. visited_states is a set of the field hashes (the amphipod hashes turned into a sorted tuple) which is used to make sure we don't address a whole branch of states multiple times – this would be expensive.

The remaining part of the loop is just addressing all possible moves that the amphipods can make given the current field dictionary.

    for y in range(1,3):
        for x in range(4):
            x = x*2 + 2
            if field[x,y-1]: continue
            if field[x,y] and not field[x,y].moved:
                for x2 in range(x-1, -1, -1):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field)
                    amphipod = new_field[x,y]
                    amphipod.move((x2,0), new_field)
                    queue.append(new_field)
                for x2 in range(x+1, 11):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field)
                    amphipod = new_field[x,y]
                    amphipod.move((x2,0), new_field)
                    queue.append(new_field)

This last section is broken into two parts, moving from the room to the hallway, and moving from the hallway to the destination room. Above is the former, and it checks for any blocking amphipods and tries every position in the hallway that each amphipod in a room (that has not already moved and is not properly placed in its destination room) can go to.

If it finds a non-blocked position in the hallway, it makes a copy of the field dictionary and moves the amphipod in the new copy and pushes that copy to the stack. This block assumes that all amphipods that have already moved and are in a room have followed the rules defined in the problem and are in their destination room without needing to move again so that another amphipod in the room can get to its destination.

    for x in range(11):
        if not field[x,0]: continue
        dest = amphipod_dst[field[x,0].label]
        if field[dest,1]: continue
        if field[dest,2] and field[dest,2].label != field[x,0].label: continue
        direction = int(copysign(1, dest-x))
        for x2 in range(x+direction, dest+direction, direction):
            if field[x2,0]: break
            if x2 != dest: continue
            if field[x2,2]:
                new_field = deepcopy(field)
                amphipod = new_field[x,0]
                amphipod.move((x2,1), new_field)
                queue.append(new_field)
            else:
                new_field = deepcopy(field)
                amphipod = new_field[x,0]
                amphipod.move((x2,2), new_field)
                queue.append(new_field)

The second, and last, block moves amphipods in the hallway to their destination rooms assuming that no other amphipod is blocking their way and only their matching counterpart is in the respective destination room. Again, if it finds such a move, it makes a deep copy of the field dictionary and moves the amphipod in the copy before pushing the copy to the stack.

Throughout this loop, if a solved state is found, the field points are calculated and the minimum points for a solved state is being tracked. The first large optimization I make is to use a heap instead of a stack for the pending fields. The heap will use the field points as the sorting key and we will look at the fields with the smallest points first. If we find a solution with a certain energy, we can end up skipping a lot of the options and their respective branches if we already know they will produce a larger point total.

class Amphipod:
    def __init__(self, label, pos):
        self.label = label
        self.pos = pos
        self.moved = False

    def move(self, new_pos, field):
        self.moved = True
        moves = abs(self.pos[0] - new_pos[0]) + abs(self.pos[1] - new_pos[1])
        field.field[new_pos] = self
        field.field[self.pos] = None
        self.pos = new_pos
        field.points += moves * multiplier[self.label]

    def __repr__(self):
        return "Amphipod({})".format(self.label)

    def __eq__(self, other):
        return other and self.label == other.label \
                and self.pos == other.pos and self.moved == other.moved

    def __hash__(self):
        return hash((self.label, self.pos, self.moved))

We moved the points attributes to the field which is the major difference to the amphipod class.

class Field:
    def __init__(self, field, points):
        self.field = field
        self.points = points

    def __lt__(self, other):
        return self.points < other.points

    def __eq__(self, other):
        return self.field == other.field and self.points == other.points

    def __hash__(self):
        states = []
        for pod in self.field.values():
            if pod:
                states.append(hash(pod))
        states.sort()
        return hash(tuple(states))

    def solved(self):
        field = self.field
        return field[2,1] and field[2,2] and field[4,1] and field[4,2] \
            and field[6,1] and field[6,2] and field[8,1] and field[8,2] \
            and field[2,1].label == "A" and field[2,2].label == "A" \
            and field[4,1].label == "B" and field[4,2].label == "B" \
            and field[6,1].label == "C" and field[6,2].label == "C" \
            and field[8,1].label == "D" and field[8,2].label == "D"

The field class has two class level attributes: the field dictionary that maps the coordinates of the map to an optional amphipod (or null if no amphipod is occupying the space). The __eq__ and __hash__ functions are overriden again this time taking the amphipod objects, hashing them individually and taking the resulting list of 8 hashes, sorting them, transforming it into a tuple, and taking the hash of the tuple. The sorting is important here since iterating through the field dictionary could produce a different order even if the state has already been visited.

The solved function is what you might expect. It returns True only if all rooms are populated with the correct amphipods. The __lt__ function is for using the field objects in a heap. Here, we only care about the points in terms of sorting the fields because of the reason explained above.

field = {(x,0):None for x in range(11)}
for x in range(4):
    x = x*2 + 3
    field[x-1,1] = Amphipod(file_input[2][x], (x-1,1))
    field[x-1,2] = Amphipod(file_input[3][x], (x-1,2))
field = Field(field, 0)

queue = []
heappush(queue, field)
visited_states = set()
room_rows = [2,4,6,8]
min_energy_cost = sys.maxsize
while len(queue) != 0:
    field_obj = heappop(queue)
    field_hash, field, score = hash(field_obj), field_obj.field, field_obj.points
    if field_hash in visited_states or score > min_energy_cost:
        continue
    visited_states.add(field_hash)
    if field_obj.solved():
        min_energy_cost = min(min_energy_cost, score)
        print(min_energy_cost)
        continue
    for y in range(1,3):
        for x in range(4):
            x = x*2 + 2
            if field[x,y-1]: continue
            if field[x,y] and not field[x,y].moved:
                for x2 in range(x-1, -1, -1):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field_obj)
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
                for x2 in range(x+1, 11):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = deepcopy(field_obj)
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
    for x in range(11):
        if not field[x,0]: continue
        dest = amphipod_dst[field[x,0].label]
        if field[dest,1]: continue
        if field[dest,2] and field[dest,2].label != field[x,0].label: continue
        direction = int(copysign(1, dest-x))
        for x2 in range(x+direction, dest+direction, direction):
            if field[x2,0]: break
            if x2 != dest: continue
            if field[x2,2]:
                new_field = deepcopy(field_obj)
                new_field.field[x,0].move((x2,1), new_field)
                heappush(queue, new_field)
            else:
                new_field = deepcopy(field_obj)
                new_field.field[x,0].move((x2,2), new_field)
                heappush(queue, new_field)

This brings the solution for part 1 down to ~22 seconds:

❯ time python3 solution23.py input23
15472
python3 solution23.py input23  22.77s user 0.02s system 99% cpu 22.799 total

I pulled out the cProfiler to see what calls were taking the most time. I think you can probably guess what it is.

❯ python3 -m cProfile solution23.py input23
15472
         232307975 function calls (192139718 primitive calls) in 64.252 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:1002(_find_and_load)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:112(release)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:152(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:156(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:160(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:166(_get_module_lock)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:185(cb)
        2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:220(_call_with_frames_removed)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:231(_verbose_message)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:241(_requires_builtin_wrapper)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:351(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:398(parent)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:406(has_location)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:415(spec_from_loader)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:486(_init_module_attrs)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:558(module_from_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:58(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:659(_load_unlocked)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:736(find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:757(create_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:765(exec_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:782(is_package)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:87(acquire)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:874(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:878(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:901(_find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:967(_find_and_load_unlocked)
        1    0.000    0.000    0.000    0.000 _bootlocale.py:33(getpreferredencoding)
        1    0.000    0.000    0.000    0.000 codecs.py:260(__init__)
        1    0.000    0.000    0.000    0.000 codecs.py:309(__init__)
        1    0.000    0.000    0.000    0.000 codecs.py:319(decode)
33405220/204940   25.224    0.000   58.382    0.000 copy.py:128(deepcopy)
 23977980    1.640    0.000    1.640    0.000 copy.py:182(_deepcopy_atomic)
  5533380    5.778    0.000   18.299    0.000 copy.py:209(_deepcopy_tuple)
  5533380    2.337    0.000   12.156    0.000 copy.py:210(<listcomp>)
2049400/204940    4.862    0.000   56.003    0.000 copy.py:226(_deepcopy_dict)
  3893860    1.744    0.000    2.412    0.000 copy.py:242(_keep_alive)
1844460/204940    4.039    0.000   57.399    0.000 copy.py:258(_reconstruct)
  3688920    0.736    0.000    2.583    0.000 copy.py:263(<genexpr>)
        2    0.000    0.000    0.000    0.000 copyreg.py:103(_slotnames)
  1844460    0.510    0.000    0.761    0.000 copyreg.py:94(__newobj__)
        1    0.000    0.000    0.000    0.000 solution23.py:16(Amphipod)
        8    0.000    0.000    0.000    0.000 solution23.py:17(__init__)
        1    2.074    2.074   64.252   64.252 solution23.py:2(<module>)
   204940    0.339    0.000    0.384    0.000 solution23.py:22(move)
  1639528    0.532    0.000    0.717    0.000 solution23.py:37(__hash__)
        1    0.000    0.000    0.000    0.000 solution23.py:40(Field)
        1    0.000    0.000    0.000    0.000 solution23.py:41(__init__)
  3432138    0.643    0.000    0.643    0.000 solution23.py:45(__lt__)
   204941    0.720    0.000    2.023    0.000 solution23.py:51(__hash__)
    80584    0.028    0.000    0.028    0.000 solution23.py:59(solved)
        1    0.000    0.000    0.000    0.000 solution23.py:81(<dictcomp>)
  1844460    0.251    0.000    0.251    0.000 {built-in method __new__ of type object at 0x8f32e0}
        1    0.000    0.000    0.000    0.000 {built-in method _codecs.utf_8_decode}
   204941    0.437    0.000    1.003    0.000 {built-in method _heapq.heappop}
   204941    0.112    0.000    0.190    0.000 {built-in method _heapq.heappush}
        3    0.000    0.000    0.000    0.000 {built-in method _imp.acquire_lock}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.create_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.exec_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.is_builtin}
        3    0.000    0.000    0.000    0.000 {built-in method _imp.release_lock}
        1    0.000    0.000    0.000    0.000 {built-in method _locale.nl_langinfo}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.__build_class__}
   409880    0.045    0.000    0.045    0.000 {built-in method builtins.abs}
        1    0.000    0.000   64.252   64.252 {built-in method builtins.exec}
  3688924    0.462    0.000    0.462    0.000 {built-in method builtins.getattr}
  1844466    0.211    0.000    0.211    0.000 {built-in method builtins.hasattr}
3688938/204941    0.617    0.000    2.108    0.000 {built-in method builtins.hash}
 46931260    3.257    0.000    3.257    0.000 {built-in method builtins.id}
  3688920    0.427    0.000    0.427    0.000 {built-in method builtins.isinstance}
  1844460    0.215    0.000    0.215    0.000 {built-in method builtins.issubclass}
   204943    0.025    0.000    0.025    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.min}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {built-in method io.open}
   206436    0.047    0.000    0.047    0.000 {built-in method math.copysign}
        2    0.000    0.000    0.000    0.000 {method '__exit__' of '_thread.lock' objects}
  1844460    0.832    0.000    0.832    0.000 {method '__reduce_ex__' of 'object' objects}
    80584    0.012    0.000    0.012    0.000 {method 'add' of 'set' objects}
  5328448    0.497    0.000    0.497    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
 68654902    4.899    0.000    4.899    0.000 {method 'get' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 {method 'get' of 'mappingproxy' objects}
  2049400    0.214    0.000    0.214    0.000 {method 'items' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'pop' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'read' of '_io.TextIOWrapper' objects}
        2    0.000    0.000    0.000    0.000 {method 'rpartition' of 'str' objects}
   204941    0.103    0.000    0.103    0.000 {method 'sort' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'strip' of 'str' objects}
  1844460    0.359    0.000    0.359    0.000 {method 'update' of 'dict' objects}
   204941    0.026    0.000    0.026    0.000 {method 'values' of 'dict' objects}

As expected, the deep copies are taking the most time since it has to copy the entire field for every single possible move. A really cool revelation I had is that we don't need to deep copy the entire field after each move. We can do a shallow copy of the field object (the dictionary and points) and do a deep copy of the single amphipod that is moving. This means that each amphipod object will only be copied once it moves the first time and then again when it moves the second time. The same amphipod objects will be referenced in many copies of the fields until it actually moves. This greatly reduces the amount of copying that we have to do.

class Field:
    ...
    def custom_copy(self, pos):
        # shallow copy field dict and points
        field = copy(self.field)
        points = copy(self.points)
        obj = Field(field, points)
        # deepcopy single amphipod object at position
        obj.field[pos] = deepcopy(obj.field[pos])
        return obj

This custom_copy function takes the position of the amphipod that is moving as an argument. This is the only object which a deep copy is created for. The new field object is returned.

field = {(x,0):None for x in range(11)}
for x in range(4):
    x = x*2 + 3
    field[x-1,1] = Amphipod(file_input[2][x], (x-1,1))
    field[x-1,2] = Amphipod(file_input[3][x], (x-1,2))
field = Field(field, 0)

queue = []
heappush(queue, field)
visited_states = set()
room_rows = [2,4,6,8]
min_energy_cost = sys.maxsize
while len(queue) != 0:
    field_obj = heappop(queue)
    field_hash, field, score = hash(field_obj), field_obj.field, field_obj.points
    if field_hash in visited_states or score > min_energy_cost:
        continue
    visited_states.add(field_hash)
    if field_obj.solved():
        min_energy_cost = min(min_energy_cost, score)
        continue
    for y in range(1,3):
        for x in range(4):
            x = x*2 + 2
            if field[x,y-1]: continue
            if field[x,y] and not field[x,y].moved:
                for x2 in range(x-1, -1, -1):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = field_obj.custom_copy((x,y))
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
                for x2 in range(x+1, 11):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = field_obj.custom_copy((x,y))
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
    for x in range(11):
        if not field[x,0]: continue
        dest = amphipod_dst[field[x,0].label]
        if field[dest,1]: continue
        if field[dest,2] and field[dest,2].label != field[x,0].label: continue
        direction = int(copysign(1, dest-x))
        for x2 in range(x+direction, dest+direction, direction):
            if field[x2,0]: break
            if x2 != dest: continue
            if field[x2,2]:
                new_field = field_obj.custom_copy((x,0))
                new_field.field[x,0].move((x2,1), new_field)
                heappush(queue, new_field)
            else:
                new_field = field_obj.custom_copy((x,0))
                new_field.field[x,0].move((x2,2), new_field)
                heappush(queue, new_field)

print("Minimum energy cost: {}".format(min_energy_cost))

Again, not much changes for the solution loop except the use of the custom copy.

❯ time python3 solution23.py input23
Minimum energy cost: 15472
python3 solution23.py input23  4.66s user 0.02s system 99% cpu 4.685 total

Part 2

As you prepare to give the amphipods your solution, you notice that the diagram they handed you was actually folded up. As you unfold it, you discover an extra part of the diagram.

Between the first and second lines of text that contain amphipod starting positions, insert the following lines:

  #D#C#B#A#
  #D#B#A#C#

So, the above example now becomes:

#############
#...........#
###B#C#B#D###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

The amphipods still want to be organized into rooms similar to before:

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

In this updated example, the least energy required to organize these amphipods is _44169_:

#############
#...........#
###B#C#B#D###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#..........D#
###B#C#B#.###
  #D#C#B#A#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A.........D#
###B#C#B#.###
  #D#C#B#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A........BD#
###B#C#.#.###
  #D#C#B#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#A......B.BD#
###B#C#.#.###
  #D#C#.#.#
  #D#B#A#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#C#.#.###
  #D#C#.#.#
  #D#B#.#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#.#.#.###
  #D#C#.#.#
  #D#B#C#C#
  #A#D#C#A#
  #########

#############
#AA.....B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#B#C#C#
  #A#D#C#A#
  #########

#############
#AA...B.B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#D#C#A#
  #########

#############
#AA.D.B.B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#.#C#A#
  #########

#############
#AA.D...B.BD#
###B#.#.#.###
  #D#.#C#.#
  #D#.#C#C#
  #A#B#C#A#
  #########

#############
#AA.D.....BD#
###B#.#.#.###
  #D#.#C#.#
  #D#B#C#C#
  #A#B#C#A#
  #########

#############
#AA.D......D#
###B#.#.#.###
  #D#B#C#.#
  #D#B#C#C#
  #A#B#C#A#
  #########

#############
#AA.D......D#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#A#
  #########

#############
#AA.D.....AD#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#.#
  #########

#############
#AA.......AD#
###B#.#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#D#
  #########

#############
#AA.......AD#
###.#B#C#.###
  #D#B#C#.#
  #D#B#C#.#
  #A#B#C#D#
  #########

#############
#AA.......AD#
###.#B#C#.###
  #.#B#C#.#
  #D#B#C#D#
  #A#B#C#D#
  #########

#############
#AA.D.....AD#
###.#B#C#.###
  #.#B#C#.#
  #.#B#C#D#
  #A#B#C#D#
  #########

#############
#A..D.....AD#
###.#B#C#.###
  #.#B#C#.#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#...D.....AD#
###.#B#C#.###
  #A#B#C#.#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#.........AD#
###.#B#C#.###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#..........D#
###A#B#C#.###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

#############
#...........#
###A#B#C#D###
  #A#B#C#D#
  #A#B#C#D#
  #A#B#C#D#
  #########

Using the initial configuration from the full diagram, what is the least energy required to organize the amphipods?

Proposed solution: same solution but the room size is a little bigger and there is a hard coded section to add to our input, the solution just needs some generalization

#!/usr/bin/env python3
from copy import copy, deepcopy
from heapq import heappush, heappop
from math import copysign
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

multiplier = {"A": 1, "B": 10, "C": 100, "D": 1000}
amphipod_dst = {"A": 2, "B": 4, "C": 6, "D": 8}

class Amphipod:
    def __init__(self, label, pos):
        self.label = label
        self.pos = pos
        self.moved = False

    def move(self, new_pos, field):
        self.moved = True
        moves = abs(self.pos[0] - new_pos[0]) + abs(self.pos[1] - new_pos[1])
        field.field[new_pos] = self
        field.field[self.pos] = None
        self.pos = new_pos
        field.points += moves * multiplier[self.label]

    def __repr__(self):
        return "Amphipod({})".format(self.label)

    def __eq__(self, other):
        return other and self.label == other.label \
                and self.pos == other.pos and self.moved == other.moved

    def __hash__(self):
        return hash((self.label, self.pos, self.moved))

class Field:
    def __init__(self, field, points):
        self.field = field
        self.points = points

    def __lt__(self, other):
        return self.points < other.points

    def __eq__(self, other):
        return self.field == other.field and self.points == other.points

    def __hash__(self):
        states = []
        for pod in self.field.values():
            if pod:
                states.append(hash(pod))
        states.sort()
        return hash(tuple(states))

    def custom_copy(self, pos):
        # shallow copy field dict and points
        field = copy(self.field)
        points = copy(self.points)
        obj = Field(field, points)
        # deepcopy single amphipod object at position
        obj.field[pos] = deepcopy(obj.field[pos])
        return obj

    def solved(self):
        field = self.field
        for y in range(1,5):
            for x in range(4):
                x = x*2 + 2
                if not field[x,y]: return False
                if amphipod_dst[field[x,y].label] != x: return False
        return True

def print_field(field):
    for y in range(5):
        result = ""
        for x in range(11):
            if (x,y) not in field:
                result += "#"
            elif field[x,y] is None:
                result += "."
            else:
                result += field[x,y].label
        print(result)
    print("")

field = {(x,0):None for x in range(11)}
field[2,2] = Amphipod("D", (2,2))
field[2,3] = Amphipod("D", (2,3))
field[4,2] = Amphipod("C", (4,2))
field[4,3] = Amphipod("B", (4,3))
field[6,2] = Amphipod("B", (6,2))
field[6,3] = Amphipod("A", (6,3))
field[8,2] = Amphipod("A", (8,2))
field[8,3] = Amphipod("C", (8,3))
for x in range(4):
    x = x*2 + 3
    field[x-1,1] = Amphipod(file_input[2][x], (x-1,1))
    field[x-1,4] = Amphipod(file_input[3][x], (x-1,4))
field = Field(field, 0)

queue = []
heappush(queue, field)
visited_states = set()
room_rows = [2,4,6,8]
min_energy_cost = sys.maxsize
while len(queue) != 0:
    field_obj = heappop(queue)
    field_hash, field, score = hash(field_obj), field_obj.field, field_obj.points
    if field_hash in visited_states or score > min_energy_cost:
        continue
    visited_states.add(field_hash)
    if field_obj.solved():
        min_energy_cost = min(min_energy_cost, score)
        continue
    for y in range(1,5):
        for x in range(4):
            x = x*2 + 2
            if field[x,y] and not field[x,y].moved:
                blocked = False
                for y2 in range(y-1, 0, -1):
                    if field[x,y2]:
                        blocked = True
                        break
                if blocked: continue
                for x2 in range(x-1, -1, -1):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = field_obj.custom_copy((x,y))
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
                for x2 in range(x+1, 11):
                    if x2 in room_rows: continue
                    if field[x2,0]: break
                    new_field = field_obj.custom_copy((x,y))
                    new_field.field[x,y].move((x2,0), new_field)
                    heappush(queue, new_field)
    for x in range(11):
        if not field[x,0]: continue
        dest = amphipod_dst[field[x,0].label]
        if field[dest,1]: continue
        room_available = True
        for y in range(4, 1, -1):
            if field[dest,y] and field[dest,y].label != field[x,0].label:
                room_available = False
        if not room_available: continue
        direction = int(copysign(1, dest-x))
        for x2 in range(x+direction, dest+direction, direction):
            if field[x2,0]: break
            if x2 != dest: continue
            for y in range(4, 0, -1):
                if not field[x2,y]:
                    new_field = field_obj.custom_copy((x,0))
                    new_field.field[x,0].move((x2,y), new_field)
                    heappush(queue, new_field)
                    break

print("Minimum energy cost: {}".format(min_energy_cost))

And it performs so well!

❯ time python3 solution23.py input23
Minimum energy cost: 46182
python3 solution23.py input23  5.93s user 0.02s system 99% cpu 5.949 total

Part 1

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?

Proposed solution: brute force seems to be achievable for part 1 but probably not for part 2, I do it anyway – using a set of size-3 tuples for the coordinates

Time complexity: O(V) where V is the "volume" or the total number of points/cubes in the input

Space complexity: O(V)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

cubes = set()
init_range = range(-50,51)
for line in file_input:
    if line == "":
        continue
    instr, ranges = line.split()
    _x, _y, _z = ranges.split(",")
    x1, x2 = [int(x) for x in _x.split("=")[1].split("..")]
    y1, y2 = [int(y) for y in _y.split("=")[1].split("..")]
    z1, z2 = [int(z) for z in _z.split("=")[1].split("..")]
    for x in range(x1, x2+1):
        if x < -50 or x > 50:
            break
        for y in range(y1, y2+1):
            for z in range(z1, z2+1):
                if instr == "on":
                    cubes.add((x,y,z))
                else:
                    cubes.discard((x,y,z))

print("Number of cubes lit: {}".format(len(cubes)))

❯ python3 solution22.py input22
Number of cubes lit: 588120

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?

Proposed solution: instead of counting individual "cubes," or points, use the dimensions of the cubes and split the cubes as they intersect to make sure that the volumes are not overlapping – this is important when calculating the final volume

Time complexity: O(n) where n is the number of instructions

Space complexity: O(n)

#!/usr/bin/env python3
from math import prod
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

class Cube:
    def __init__(self, dims):
        self.dims = dims

    def intersects(self, other):
        return not (other.dims[0] < self.dims[0] and other.dims[1] < self.dims[0]) \
            and not (other.dims[0] > self.dims[1] and other.dims[1] > self.dims[1]) \
            and not (other.dims[2] < self.dims[2] and other.dims[3] < self.dims[2]) \
            and not (other.dims[2] > self.dims[3] and other.dims[3] > self.dims[3]) \
            and not (other.dims[4] < self.dims[4] and other.dims[5] < self.dims[4]) \
            and not (other.dims[4] > self.dims[5] and other.dims[5] > self.dims[5])

    def volume(self):
        return prod([self.dims[i+1] - self.dims[i] + 1 for i in range(0, 6, 2)])

    def __str__(self):
        return str(self.dims)

def split(cubes, cube1, cube2):
    """
    If cube2 intersects cube1, this functions splits cube1 into new cubes
    and adds them to the cubes set.
    """
    x_start, y_start, z_start = cube1.dims[0], cube1.dims[2], cube1.dims[4]
    x_end, y_end, z_end = cube1.dims[1], cube1.dims[3], cube1.dims[5]
    if x_start < cube2.dims[0]:
        cubes.add(Cube((x_start, cube2.dims[0]-1, y_start, y_end, z_start, z_end)))
        x_start = cube2.dims[0]
    if y_start < cube2.dims[2]:
        cubes.add(Cube((x_start, x_end, y_start, cube2.dims[2]-1, z_start, z_end)))
        y_start = cube2.dims[2]
    if z_start < cube2.dims[4]:
        cubes.add(Cube((x_start, x_end, y_start, y_end, z_start, cube2.dims[4]-1)))
        z_start = cube2.dims[4]
    x_start2, y_start2, z_start2 = cube2.dims[1] + 1, cube2.dims[3] + 1, cube2.dims[5] + 1
    if x_start2 <= x_end:
        cubes.add(Cube((x_start2, x_end, y_start, y_end, z_start, z_end)))
        x_end = cube2.dims[1]
    if y_start2 <= y_end:
        cubes.add(Cube((x_start, x_end, y_start2, y_end, z_start, z_end)))
        y_end = cube2.dims[3]
    if z_start2 <= z_end:
        cubes.add(Cube((x_start, x_end, y_start, y_end, z_start2, z_end)))
        z_end = cube2.dims[5]

cubes = set()
for line in file_input:
    if line == "":
        continue
    instr, ranges = line.split()
    _x, _y, _z = ranges.split(",")
    x1, x2 = [int(x) for x in _x.split("=")[1].split("..")]
    y1, y2 = [int(y) for y in _y.split("=")[1].split("..")]
    z1, z2 = [int(z) for z in _z.split("=")[1].split("..")]
    new_cube = Cube((x1, x2, y1, y2, z1, z2))
    for cube in list(cubes):
        if cube.intersects(new_cube):
            cubes.remove(cube)
            split(cubes, cube, new_cube)
    if instr == "on":
        cubes.add(new_cube)

total = sum([cube.volume() for cube in cubes])
print("Number of cubes lit: {}".format(total))

I am not going to go over it to deeply, but you need to be careful when splitting the cube to make sure the split regions do not overlap. This split function can split the original cube anywhere from 1 smaller cube (if the comparison cube covers a whole face of the original with some intersecting depth) to 6 smaller cubes (if the comparison cube is fully contained within the original cube). Once I split the cube once, I adjust the start position for the respective axis to make sure this overlap does not happen with the remaining splits, if any.

Once the splitting functionality works, it's just a matter of iterating through the instructions and using each volume as a comparison cube to the ones that have already been processed. If any two cubes intersect, remove the original from the set and split it x ways based on the type of intersection. Add the new splits to the set. Only add the comparison cube to the set if the instruction is "on." If it's "off," then just continue to the next instruction.

❯ time python3 solution22.py input22
Number of cubes lit: 1134088247046731
python3 solution22.py input22  0.23s user 0.01s system 99% cpu 0.243 total

Part 1

There's not much to do as you slowly descend to the bottom of the ocean. The submarine computer challenges you to a nice game of Dirac Dice.

This game consists of a single die, two pawns, and a game board with a circular track containing ten spaces marked 1 through 10 clockwise. Each player's starting space is chosen randomly (your puzzle input). Player 1 goes first.

Players take turns moving. On each player's turn, the player rolls the die three times and adds up the results. Then, the player moves their pawn that many times forward around the track (that is, moving clockwise on spaces in order of increasing value, wrapping back around to 1 after 10). So, if a player is on space 7 and they roll 2, 2, and 1, they would move forward 5 times, to spaces 8, 9, 10, 1, and finally stopping on 2.

After each player moves, they increase their score by the value of the space their pawn stopped on. Players' scores start at 0. So, if the first player starts on space 7 and rolls a total of 5, they would stop on space 2 and add 2 to their score (for a total score of 2). The game immediately ends as a win for any player whose score reaches at least 1000.

Since the first game is a practice game, the submarine opens a compartment labeled deterministic dice and a 100-sided die falls out. This die always rolls 1 first, then 2, then 3, and so on up to 100, after which it starts over at 1 again. Play using this die.

For example, given these starting positions:

Player 1 starting position: 4
Player 2 starting position: 8

This is how the game would go:

• Player 1 rolls 1+2+3 and moves to space 10 for a total score of 10.
• Player 2 rolls 4+5+6 and moves to space 3 for a total score of 3.
• Player 1 rolls 7+8+9 and moves to space 4 for a total score of 14.
• Player 2 rolls 10+11+12 and moves to space 6 for a total score of 9.
• Player 1 rolls 13+14+15 and moves to space 6 for a total score of 20.
• Player 2 rolls 16+17+18 and moves to space 7 for a total score of 16.
• Player 1 rolls 19+20+21 and moves to space 6 for a total score of 26.
• Player 2 rolls 22+23+24 and moves to space 6 for a total score of 22.

...after many turns...

• Player 2 rolls 82+83+84 and moves to space 6 for a total score of 742.
• Player 1 rolls 85+86+87 and moves to space 4 for a total score of 990.
• Player 2 rolls 88+89+90 and moves to space 3 for a total score of 745.
• Player 1 rolls 91+92+93 and moves to space 10 for a final score, 1000.

Since player 1 has at least 1000 points, player 1 wins and the game ends. At this point, the losing player had 745 points and the die had been rolled a total of 993 times; 745 * 993 = _739785_.

Play a practice game using the deterministic 100-sided die. The moment either player wins, what do you get if you multiply the score of the losing player by the number of times the die was rolled during the game?

Proposed solution: take the starting positions and play the game out with the defined rules until a player wins – keep track of the rolls and each players score

Time complexity: O(1) since the input is really not a scaling factor if we are just considering the single game

Space complexity: O(1)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")
p1start, p2start = tuple(map(lambda l: int(l[-1]), file_input[0:2]))

p1, p2 = p1start, p2start
turn, rolls, die = 0, 0, 1
p1score, p2score = 0, 0
while p1score < 1000 and p2score < 1000:
    roll = 0
    for _ in range(3):
        roll += die
        rolls += 1
        die = (die % 100) + 1
    if not turn:
        p1 = ((p1+roll-1) % 10) + 1
        p1score += p1
    else:
        p2 = ((p2+roll-1) % 10) + 1
        p2score += p2
    turn = (turn + 1) % 2

print("min(p1score,p2score) * rolls = {}".format(min(p1score, p2score) * rolls))

❯ python3 solution21.py input21
min(p1score,p2score) * rolls = 711480

Part 2

Now that you're warmed up, it's time to play the real game.

A second compartment opens, this time labeled Dirac dice. Out of it falls a single three-sided die.

As you experiment with the die, you feel a little strange. An informational brochure in the compartment explains that this is a quantum die: when you roll it, the universe splits into multiple copies, one copy for each possible outcome of the die. In this case, rolling the die always splits the universe into three copies: one where the outcome of the roll was 1, one where it was 2, and one where it was 3.

The game is played the same as before, although to prevent things from getting too far out of hand, the game now ends when either player's score reaches at least _21_.

Using the same starting positions as in the example above, player 1 wins in _444356092776315_ universes, while player 2 merely wins in 341960390180808 universes.

Using your given starting positions, determine every possible outcome. Find the player that wins in more universes; in how many universes does that player win?

Proposed solution: the number of states is rather limited since the score can only go up to 21 now and the dice are only 3 sided, making dynamic programming and memoization really useful to not count the same state

Time complexity: O(n * m) where n is the max score and m is the number of possible split universes

Space complexity: O(n * m)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")
p1start, p2start = tuple(map(lambda l: int(l[-1]), file_input[0:2]))

game_states = {}
def count_wins(p1, p2, p1score=0, p2score=0):
    if p1score >= 21:
        return (1,0)
    if p2score >= 21:
        return (0,1)
    if (p1, p2, p1score, p2score) in game_states:
        return game_states[p1, p2, p1score, p2score]
    result = (0,0)
    for d1 in range(1, 4):
        for d2 in range(1, 4):
            for d3 in range(1, 4):
                _p1 = ((p1 + d1 + d2 + d3 - 1) % 10) + 1
                _p1score = p1score + _p1
                swap = count_wins(p2, _p1, p2score, _p1score)
                result = (result[0] + swap[1], result[1] + swap[0])
    game_states[p1, p2, p1score, p2score] = result
    return result

print("max(count_wins(p1start, p2start)): {}".format(max(count_wins(p1start, p2start))))

❯ python3 solution21.py input21
max(count_wins(p1start, p2start)): 265845890886828

Part 1

With the scanners fully deployed, you turn their attention to mapping the floor of the ocean trench.

When you get back the image from the scanners, it seems to just be random noise. Perhaps you can combine an image enhancement algorithm and the input image (your puzzle input) to clean it up a little.

For example:

..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##
#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###
.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#.
.#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#.....
.#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#..
...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.....
..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#

#..#.
#....
##..#
..#..
..###

The first section is the image enhancement algorithm. It is normally given on a single line, but it has been wrapped to multiple lines in this example for legibility. The second section is the input image, a two-dimensional grid of light pixels (#) and dark pixels (.).

The image enhancement algorithm describes how to enhance an image by simultaneously converting all pixels in the input image into an output image. Each pixel of the output image is determined by looking at a 3x3 square of pixels centered on the corresponding input image pixel. So, to determine the value of the pixel at (5,10) in the output image, nine pixels from the input image need to be considered: (4,9), (4,10), (4,11), (5,9), (5,10), (5,11), (6,9), (6,10), and (6,11). These nine input pixels are combined into a single binary number that is used as an index in the image enhancement algorithm string.

For example, to determine the output pixel that corresponds to the very middle pixel of the input image, the nine pixels marked by [...] would need to be considered:

# . . # .
#[. . .].
#[# . .]#
.[. # .].
. . # # #

Starting from the top-left and reading across each row, these pixels are ..., then #.., then .#.; combining these forms ...#...#.. By turning dark pixels (.) into 0 and light pixels (#) into 1, the binary number 000100010 can be formed, which is 34 in decimal.

The image enhancement algorithm string is exactly 512 characters long, enough to match every possible 9-bit binary number. The first few characters of the string (numbered starting from zero) are as follows:

0         10        20        30  34    40        50        60        70
|         |         |         |   |     |         |         |         |
..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##

In the middle of this first group of characters, the character at index 34 can be found: #. So, the output pixel in the center of the output image should be #, a light pixel.

This process can then be repeated to calculate every pixel of the output image.

Through advances in imaging technology, the images being operated on here are infinite in size. Every pixel of the infinite output image needs to be calculated exactly based on the relevant pixels of the input image. The small input image you have is only a small region of the actual infinite input image; the rest of the input image consists of dark pixels (.). For the purposes of the example, to save on space, only a portion of the infinite-sized input and output images will be shown.

The starting input image, therefore, looks something like this, with more dark pixels (.) extending forever in every direction not shown here:

...............
...............
...............
...............
...............
.....#..#......
.....#.........
.....##..#.....
.......#.......
.......###.....
...............
...............
...............
...............
...............

By applying the image enhancement algorithm to every pixel simultaneously, the following output image can be obtained:

...............
...............
...............
...............
.....##.##.....
....#..#.#.....
....##.#..#....
....####..#....
.....#..##.....
......##..#....
.......#.#.....
...............
...............
...............
...............

Through further advances in imaging technology, the above output image can also be used as an input image! This allows it to be enhanced a second time:

...............
...............
...............
..........#....
....#..#.#.....
...#.#...###...
...#...##.#....
...#.....#.#...
....#.#####....
.....#.#####...
......##.##....
.......###.....
...............
...............
...............

Truly incredible - now the small details are really starting to come through. After enhancing the original input image twice, _35_ pixels are lit.

Start with the original input image and apply the image enhancement algorithm twice, being careful to account for the infinite size of the images. How many pixels are lit in the resulting image?

Proposed solution: there is a "working region" that expands by a pixel in each direction on every step – this is the key to not having to address infinite pixels; everything outside of the working region is always either on or off depending on the first and last bit of the enhancement algorithm string – we can keep track of this with one variable

Time complexity: O(n) where n is the area of the original image size

Space complexity: O(n)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")
enhance = lambda x: 0 if enhancement[x] == "." else 1
enhancement = file_input[0]

default = 0
pixel_map = {}
for y, line in enumerate(file_input[2:]):
    if line == "":
        continue
    for x, char in enumerate(line):
        result = 0 if char == "." else 1
        pixel_map[x,y] = result
        for dx in range(-1,2):
            for dy in range(-1,2):
                if dx == 0 and dy == 0 or (x+dx,y+dy) in pixel_map:
                    continue
                pixel_map[x+dx,y+dy] = default

for i in range(2):
    new_default = enhance(int(str(default) * 9, 2))
    pixel_map_old = dict(pixel_map)
    for pos, val in pixel_map_old.items():
        x, y = pos
        result = ""
        for dy in range(-1,2):
            for dx in range(-1,2):
                if (x+dx,y+dy) not in pixel_map_old:
                    pixel_map[x+dx,y+dy] = new_default
                    result += str(default)
                    continue
                result += str(pixel_map_old[x+dx,y+dy])
        result = int(result, 2)
        pixel_map[x,y] = enhance(result)
    default = new_default

num_pixels = len(list(filter(lambda x: x == 1, pixel_map.values())))
print("Number Pixel Lit: {}".format(num_pixels))

Here default is to track on or off outside of the working area.

❯ python3 solution20.py input20
Number Pixel Lit: 5359

Part 2

You still can't quite make out the details in the image. Maybe you just didn't enhance it enough.

If you enhance the starting input image in the above example a total of 50 times, _3351_ pixels are lit in the final output image.

Start again with the original input image and apply the image enhancement algorithm 50 times. How many pixels are lit in the resulting image?

Proposed solution: same solution but increasing the number of steps from 2 to 50

Time complexity: O(n)

Space complexity: O(n)

There is probably a geometric function that addresses the growing working area which impacts both time and space complexity; however, I'm moving on since part 2 was simple enough.

❯ time python3 solution20.py input20
Number Pixel Lit: 12333
python3 solution20.py input20  6.36s user 0.01s system 99% cpu 6.372 total

Part 1

As your probe drifted down through this area, it released an assortment of beacons and scanners into the water. It's difficult to navigate in the pitch black open waters of the ocean trench, but if you can build a map of the trench using data from the scanners, you should be able to safely reach the bottom.

The beacons and scanners float motionless in the water; they're designed to maintain the same position for long periods of time. Each scanner is capable of detecting all beacons in a large cube centered on the scanner; beacons that are at most 1000 units away from the scanner in each of the three axes (x, y, and z) have their precise position determined relative to the scanner. However, scanners cannot detect other scanners. The submarine has automatically summarized the relative positions of beacons detected by each scanner (your puzzle input).

For example, if a scanner is at x,y,z coordinates 500,0,-500 and there are beacons at -500,1000,-1500 and 1501,0,-500, the scanner could report that the first beacon is at -1000,1000,-1000 (relative to the scanner) but would not detect the second beacon at all.

Unfortunately, while each scanner can report the positions of all detected beacons relative to itself, the scanners do not know their own position. You'll need to determine the positions of the beacons and scanners yourself.

The scanners and beacons map a single contiguous 3d region. This region can be reconstructed by finding pairs of scanners that have overlapping detection regions such that there are at least 12 beacons that both scanners detect within the overlap. By establishing 12 common beacons, you can precisely determine where the scanners are relative to each other, allowing you to reconstruct the beacon map one scanner at a time.

For a moment, consider only two dimensions. Suppose you have the following scanner reports:

--- scanner 0 ---
0,2
4,1
3,3

--- scanner 1 ---
-1,-1
-5,0
-2,1

Drawing x increasing rightward, y increasing upward, scanners as S, and beacons as B, scanner 0 detects this:

...B.
B....
....B
S....

Scanner 1 detects this:

...B..
B....S
....B.

For this example, assume scanners only need 3 overlapping beacons. Then, the beacons visible to both scanners overlap to produce the following complete map:

...B..
B....S
....B.
S.....

Unfortunately, there's a second problem: the scanners also don't know their rotation or facing direction. Due to magnetic alignment, each scanner is rotated some integer number of 90-degree turns around all of the x, y, and z axes. That is, one scanner might call a direction positive x, while another scanner might call that direction negative y. Or, two scanners might agree on which direction is positive x, but one scanner might be upside-down from the perspective of the other scanner. In total, each scanner could be in any of 24 different orientations: facing positive or negative x, y, or z, and considering any of four directions "up" from that facing.

For example, here is an arrangement of beacons as seen from a scanner in the same position but in different orientations:

--- scanner 0 ---
-1,-1,1
-2,-2,2
-3,-3,3
-2,-3,1
5,6,-4
8,0,7

--- scanner 0 ---
1,-1,1
2,-2,2
3,-3,3
2,-1,3
-5,4,-6
-8,-7,0

--- scanner 0 ---
-1,-1,-1
-2,-2,-2
-3,-3,-3
-1,-3,-2
4,6,5
-7,0,8

--- scanner 0 ---
1,1,-1
2,2,-2
3,3,-3
1,3,-2
-4,-6,5
7,0,8

--- scanner 0 ---
1,1,1
2,2,2
3,3,3
3,1,2
-6,-4,-5
0,7,-8

By finding pairs of scanners that both see at least 12 of the same beacons, you can assemble the entire map. For example, consider the following report:

--- scanner 0 ---
404,-588,-901
528,-643,409
-838,591,734
390,-675,-793
-537,-823,-458
-485,-357,347
-345,-311,381
-661,-816,-575
-876,649,763
-618,-824,-621
553,345,-567
474,580,667
-447,-329,318
-584,868,-557
544,-627,-890
564,392,-477
455,729,728
-892,524,684
-689,845,-530
423,-701,434
7,-33,-71
630,319,-379
443,580,662
-789,900,-551
459,-707,401

--- scanner 1 ---
686,422,578
605,423,415
515,917,-361
-336,658,858
95,138,22
-476,619,847
-340,-569,-846
567,-361,727
-460,603,-452
669,-402,600
729,430,532
-500,-761,534
-322,571,750
-466,-666,-811
-429,-592,574
-355,545,-477
703,-491,-529
-328,-685,520
413,935,-424
-391,539,-444
586,-435,557
-364,-763,-893
807,-499,-711
755,-354,-619
553,889,-390

--- scanner 2 ---
649,640,665
682,-795,504
-784,533,-524
-644,584,-595
-588,-843,648
-30,6,44
-674,560,763
500,723,-460
609,671,-379
-555,-800,653
-675,-892,-343
697,-426,-610
578,704,681
493,664,-388
-671,-858,530
-667,343,800
571,-461,-707
-138,-166,112
-889,563,-600
646,-828,498
640,759,510
-630,509,768
-681,-892,-333
673,-379,-804
-742,-814,-386
577,-820,562

--- scanner 3 ---
-589,542,597
605,-692,669
-500,565,-823
-660,373,557
-458,-679,-417
-488,449,543
-626,468,-788
338,-750,-386
528,-832,-391
562,-778,733
-938,-730,414
543,643,-506
-524,371,-870
407,773,750
-104,29,83
378,-903,-323
-778,-728,485
426,699,580
-438,-605,-362
-469,-447,-387
509,732,623
647,635,-688
-868,-804,481
614,-800,639
595,780,-596

--- scanner 4 ---
727,592,562
-293,-554,779
441,611,-461
-714,465,-776
-743,427,-804
-660,-479,-426
832,-632,460
927,-485,-438
408,393,-506
466,436,-512
110,16,151
-258,-428,682
-393,719,612
-211,-452,876
808,-476,-593
-575,615,604
-485,667,467
-680,325,-822
-627,-443,-432
872,-547,-609
833,512,582
807,604,487
839,-516,451
891,-625,532
-652,-548,-490
30,-46,-14

Because all coordinates are relative, in this example, all "absolute" positions will be expressed relative to scanner 0 (using the orientation of scanner 0 and as if scanner 0 is at coordinates 0,0,0).

Scanners 0 and 1 have overlapping detection cubes; the 12 beacons they both detect (relative to scanner 0) are at the following coordinates:

-618,-824,-621
-537,-823,-458
-447,-329,318
404,-588,-901
544,-627,-890
528,-643,409
-661,-816,-575
390,-675,-793
423,-701,434
-345,-311,381
459,-707,401
-485,-357,347

These same 12 beacons (in the same order) but from the perspective of scanner 1 are:

686,422,578
605,423,415
515,917,-361
-336,658,858
-476,619,847
-460,603,-452
729,430,532
-322,571,750
-355,545,-477
413,935,-424
-391,539,-444
553,889,-390

Because of this, scanner 1 must be at 68,-1246,-43 (relative to scanner 0).

Scanner 4 overlaps with scanner 1; the 12 beacons they both detect (relative to scanner 0) are:

459,-707,401
-739,-1745,668
-485,-357,347
432,-2009,850
528,-643,409
423,-701,434
-345,-311,381
408,-1815,803
534,-1912,768
-687,-1600,576
-447,-329,318
-635,-1737,486

So, scanner 4 is at -20,-1133,1061 (relative to scanner 0).

Following this process, scanner 2 must be at 1105,-1205,1229 (relative to scanner 0) and scanner 3 must be at -92,-2380,-20 (relative to scanner 0).

The full list of beacons (relative to scanner 0) is:

-892,524,684
-876,649,763
-838,591,734
-789,900,-551
-739,-1745,668
-706,-3180,-659
-697,-3072,-689
-689,845,-530
-687,-1600,576
-661,-816,-575
-654,-3158,-753
-635,-1737,486
-631,-672,1502
-624,-1620,1868
-620,-3212,371
-618,-824,-621
-612,-1695,1788
-601,-1648,-643
-584,868,-557
-537,-823,-458
-532,-1715,1894
-518,-1681,-600
-499,-1607,-770
-485,-357,347
-470,-3283,303
-456,-621,1527
-447,-329,318
-430,-3130,366
-413,-627,1469
-345,-311,381
-36,-1284,1171
-27,-1108,-65
7,-33,-71
12,-2351,-103
26,-1119,1091
346,-2985,342
366,-3059,397
377,-2827,367
390,-675,-793
396,-1931,-563
404,-588,-901
408,-1815,803
423,-701,434
432,-2009,850
443,580,662
455,729,728
456,-540,1869
459,-707,401
465,-695,1988
474,580,667
496,-1584,1900
497,-1838,-617
527,-524,1933
528,-643,409
534,-1912,768
544,-627,-890
553,345,-567
564,392,-477
568,-2007,-577
605,-1665,1952
612,-1593,1893
630,319,-379
686,-3108,-505
776,-3184,-501
846,-3110,-434
1135,-1161,1235
1243,-1093,1063
1660,-552,429
1693,-557,386
1735,-437,1738
1749,-1800,1813
1772,-405,1572
1776,-675,371
1779,-442,1789
1780,-1548,337
1786,-1538,337
1847,-1591,415
1889,-1729,1762
1994,-1805,1792

In total, there are _79_ beacons.

Assemble the full map of beacons. How many beacons are there?

Proposed solution: so there are 24 different possible rotations for the 3 axes (x, y, z); I will brute force by setting scanner 0 as the standard rotation and consider it to be at (0, 0, 0) in this relative space; then, for every other scanner, iterate through every possible rotation, and iterate through every beacon for that scanner, and for each of those beacons rotate + translate to every other point found by scanner 0 until one of these other scanners ends up mapping to at least 12 beacons from scanner 0 – this is when the rotation and offset from 0 can be confirmed for the scanner; then, once another scanner's rotation + relative position has been found, rotate + translate the beacon points so that it is uniform with scanner 0; then, you can use these properly rotated + translated scanners as a reference to find the orientation of other scanners

rotation_funcs = [lambdas for all 24 possible rotations]
scanners = {
	0: {
    	"beacons": set(position tuples of the beacons)
        "position": None # translated position tuple when found and (0,0,0) for scanner 0
    },
    1: {
    ...
    ...
    },
    ...
}

missing = set(of scanners that have not been located (position=None))
while len(missing) != 0:
	for scanners not missing:
    	for func in rotation_funcs:
        	rotated_set = set()
            for coord in other_scanner["beacons"]:
            	rotated_set.add(func(*coord))
            
            for coord in reference_scanner["beacons"]:
            	for other_coord in rotated_set:
                	delta = other_coord - coord
                    translated_set = set()
                    for rotated_coord in rotated_set:
                    	translated_set.add(rotated_coord - delta)
                    intersection = translated_set.intersection(reference_scanner["beacons"])
                    if len(insersection) >= 12:
                    	other_scanner["position"] = delta
                        other_scanner["beacons"] = translated_set
                        missing.remove(other_scanner)
                        # jmp to next for while loop

beacons = set()
for vals in scanners.values():
	beacons |= vals["beacons"]
answer = len(beacons)

Time complexity: O(n²) where n is the number of beacons

Space complexity: O(n)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

rotation_funcs = [
    lambda x,y,z: ( x, y, z),
    lambda x,y,z: ( x, z,-y),
    lambda x,y,z: ( x,-y,-z),
    lambda x,y,z: ( x,-z, y),
    lambda x,y,z: (-x,-y, z),
    lambda x,y,z: (-x, z, y),
    lambda x,y,z: (-x, y,-z),
    lambda x,y,z: (-x,-z,-y),
    lambda x,y,z: ( y,-x, z),
    lambda x,y,z: ( y, z, x),
    lambda x,y,z: ( y, x,-z),
    lambda x,y,z: ( y,-z,-x),
    lambda x,y,z: (-y, x, z),
    lambda x,y,z: (-y, z,-x),
    lambda x,y,z: (-y,-x,-z),
    lambda x,y,z: (-y,-z, x),
    lambda x,y,z: ( z, y,-x),
    lambda x,y,z: ( z,-x,-y),
    lambda x,y,z: ( z,-y, x),
    lambda x,y,z: ( z, x, y),
    lambda x,y,z: (-z, y, x),
    lambda x,y,z: (-z, x,-y),
    lambda x,y,z: (-z,-y,-x),
    lambda x,y,z: (-z,-x, y)
]

scanners = {}
for line in file_input:
    if line == "":
        continue
    if "scanner" in line:
        i = int(line.split()[2])
        scanners[i] = {
            "beacons": set(),
            "position": None
        }
        continue
    x, y, z = tuple(map(lambda x: int(x), line.split(",")))
    scanners[i]["beacons"].add((x,y,z))
scanners[0]["position"] = (0,0,0)

scanner = 0
rotated_set, translated_set = set(), set()
not_located = lambda elem: elem[1]["position"] is None
missing = {k for k,v in list(filter(not_located, scanners.items()))}
while len(missing) > 0:
    found = False
    i = list(missing)[scanner]
    for j in set(scanners.keys()) - missing:
        for func in rotation_funcs:
            rotated_set.clear()
            for coord in scanners[i]["beacons"]:
                rotated_set.add(func(*coord))

            for init_coord in scanners[j]["beacons"]:
                for compare_coord in rotated_set:
                    delta = tuple(compare_coord[i] - init_coord[i] for i in range(3))
                    translated_set.clear()
                    for coord in rotated_set:
                        translated_set.add(tuple(coord[i] - delta[i] for i in range(3)))
                    intersection = translated_set.intersection(scanners[j]["beacons"])
                    if len(intersection) >= 12:
                        delta = tuple(-delta[i] for i in range(3))
                        print("Scanner {} position discovered: {}".format(i, delta))
                        scanners[i]["position"] = delta
                        scanners[i]["beacons"] = set(translated_set)
                        missing.remove(i)
                        found = True
                    if found: break
                if found: break
            if found: break
        if found: break
    scanner = 0 if found else (scanner + 1) % len(missing)

beacons = set()
for vals in scanners.values():
    beacons |= vals["beacons"]

print("Number of unique beacons: {}".format(len(beacons)))

This took about 15 minutes to run for my input. It's pretty slow finding new positions and there are serious optimizations to be made if I have time.

❯ python3 solution19.py input19
Scanner 38 position discovered: (147, 155, -1150)
Scanner 15 position discovered: (-1111, -15, -1172)
Scanner 17 position discovered: (84, -12, -2408)
Scanner 4 position discovered: (152, 57, -3678)
Scanner 10 position discovered: (140, 1336, -2439)
Scanner 6 position discovered: (73, 2415, -2429)
Scanner 29 position discovered: (130, 2535, -3661)
Scanner 8 position discovered: (-1166, 2471, -3551)
Scanner 23 position discovered: (-7, 2465, -4812)
Scanner 28 position discovered: (61, 1318, -4788)
Scanner 3 position discovered: (-1230, 1218, -4909)
Scanner 21 position discovered: (1189, 1325, -4821)
Scanner 25 position discovered: (1176, 1237, -5981)
Scanner 30 position discovered: (1182, 2551, -6086)
Scanner 31 position discovered: (-1172, 1211, -2375)
Scanner 2 position discovered: (-2296, 1210, -2351)
Scanner 33 position discovered: (91, 1367, -3627)
Scanner 35 position discovered: (-1069, 1334, -1335)
Scanner 5 position discovered: (-1125, 2470, -1239)
Scanner 18 position discovered: (-2300, 2420, -1172)
Scanner 26 position discovered: (-1061, 3690, -1300)
Scanner 7 position discovered: (-1041, 3750, -2376)
Scanner 16 position discovered: (-1168, 4811, -2507)
Scanner 34 position discovered: (37, 3619, -1177)
Scanner 14 position discovered: (86, 4852, -1290)
Scanner 12 position discovered: (10, 4959, 1)
Scanner 19 position discovered: (51, 6081, -1202)
Scanner 24 position discovered: (139, 7342, -1144)
Scanner 27 position discovered: (-1201, 6159, -1249)
Scanner 32 position discovered: (4, 6024, -123)
Scanner 36 position discovered: (25, -1081, -3562)
Scanner 22 position discovered: (40, -2227, -3679)
Scanner 1 position discovered: (39, -3432, -3735)
Scanner 13 position discovered: (-1133, -2226, -3620)
Scanner 9 position discovered: (-2428, -2405, -3634)
Scanner 20 position discovered: (43, -2315, -2539)
Scanner 37 position discovered: (30, 2407, -5973)
Scanner 39 position discovered: (-1091, 4964, -52)
Scanner 11 position discovered: (-2393, 4828, -81)
Number of unique beacons: 483

Part 2

Sometimes, it's a good idea to appreciate just how big the ocean is. Using the Manhattan distance, how far apart do the scanners get?

In the above example, scanners 2 (1105,-1205,1229) and 3 (-92,-2380,-20) are the largest Manhattan distance apart. In total, they are 1197 + 1175 + 1249 = _3621_ units apart.

_What is the largest Manhattan distance between any two scanners?

Proposed solution: nothing changes to find the scanner positions but now we need to calculate the Manhattan distance for every pair of two scanners

Time complexity: O(n² + m²) where n is the number of beacons and m is the number of scanners

Space complexity: O(n)

max_dist = 0
beacons = set()
for vals1 in scanners.values():
    beacons |= vals1["beacons"]
    for vals2 in scanners.values():
        if vals1 == vals2:
            continue
        pos1, pos2 = vals1["position"], vals2["position"]
        max_dist = max(max_dist, sum([abs(pos1[i]-pos2[i]) for i in range(3)]))

print("Number of unique beacons: {}".format(len(beacons)))
print("Maximum manhattan distance: {}".format(max_dist))

Again, brute force calculation for the positions of every distinct pair of scanners.

❯ python3 solution19.py input19
Scanner 38 position discovered: (147, 155, -1150)
Scanner 15 position discovered: (-1111, -15, -1172)
Scanner 17 position discovered: (84, -12, -2408)
Scanner 4 position discovered: (152, 57, -3678)
Scanner 10 position discovered: (140, 1336, -2439)
Scanner 6 position discovered: (73, 2415, -2429)
Scanner 29 position discovered: (130, 2535, -3661)
Scanner 8 position discovered: (-1166, 2471, -3551)
Scanner 23 position discovered: (-7, 2465, -4812)
Scanner 28 position discovered: (61, 1318, -4788)
Scanner 3 position discovered: (-1230, 1218, -4909)
Scanner 21 position discovered: (1189, 1325, -4821)
Scanner 25 position discovered: (1176, 1237, -5981)
Scanner 30 position discovered: (1182, 2551, -6086)
Scanner 31 position discovered: (-1172, 1211, -2375)
Scanner 2 position discovered: (-2296, 1210, -2351)
Scanner 33 position discovered: (91, 1367, -3627)
Scanner 35 position discovered: (-1069, 1334, -1335)
Scanner 5 position discovered: (-1125, 2470, -1239)
Scanner 18 position discovered: (-2300, 2420, -1172)
Scanner 26 position discovered: (-1061, 3690, -1300)
Scanner 7 position discovered: (-1041, 3750, -2376)
Scanner 16 position discovered: (-1168, 4811, -2507)
Scanner 34 position discovered: (37, 3619, -1177)
Scanner 14 position discovered: (86, 4852, -1290)
Scanner 12 position discovered: (10, 4959, 1)
Scanner 19 position discovered: (51, 6081, -1202)
Scanner 24 position discovered: (139, 7342, -1144)
Scanner 27 position discovered: (-1201, 6159, -1249)
Scanner 32 position discovered: (4, 6024, -123)
Scanner 36 position discovered: (25, -1081, -3562)
Scanner 22 position discovered: (40, -2227, -3679)
Scanner 1 position discovered: (39, -3432, -3735)
Scanner 13 position discovered: (-1133, -2226, -3620)
Scanner 9 position discovered: (-2428, -2405, -3634)
Scanner 20 position discovered: (43, -2315, -2539)
Scanner 37 position discovered: (30, 2407, -5973)
Scanner 39 position discovered: (-1091, 4964, -52)
Scanner 11 position discovered: (-2393, 4828, -81)
Number of unique beacons: 483
Maximum manhattan distance: 14804

Part 1

You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys! They'll even tell you which direction the keys went if you help one of the smaller snailfish with his math homework.

Snailfish numbers aren't like regular numbers. Instead, every snailfish number is a pair - an ordered list of two elements. Each element of the pair can be either a regular number or another pair.

Pairs are written as [x,y], where x and y are the elements within the pair. Here are some example snailfish numbers, one snailfish number per line:

[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]

This snailfish homework is about addition. To add two snailfish numbers, form a pair from the left and right parameters of the addition operator. For example, [1,2] + [[3,4],5] becomes [[1,2],[[3,4],5]].

There's only one problem: snailfish numbers must always be reduced, and the process of adding two snailfish numbers can result in snailfish numbers that need to be reduced.

To reduce a snailfish number, you must repeatedly do the first action in this list that applies to the snailfish number:

• If any pair is nested inside four pairs, the leftmost such pair explodes.
• If any regular number is 10 or greater, the leftmost such regular number splits.

Once no action in the above list applies, the snailfish number is reduced.

During reduction, at most one action applies, after which the process returns to the top of the list of actions. For example, if split produces a pair that meets the explode criteria, that pair explodes before other splits occur.

To explode a pair, the pair's left value is added to the first regular number to the left of the exploding pair (if any), and the pair's right value is added to the first regular number to the right of the exploding pair (if any). Exploding pairs will always consist of two regular numbers. Then, the entire exploding pair is replaced with the regular number 0.

Here are some examples of a single explode action:

• [[[[_[9,8]_,1],2],3],4] becomes [[[[_0_,_9_],2],3],4] (the 9 has no regular number to its left, so it is not added to any regular number).
• [7,[6,[5,[4,_[3,2]_]]]] becomes [7,[6,[5,[_7_,_0_]]]] (the 2 has no regular number to its right, and so it is not added to any regular number).
• [[6,[5,[4,_[3,2]_]]],1] becomes [[6,[5,[_7_,_0_]]],_3_].
• [[3,[2,[1,_[7,3]_]]],[6,[5,[4,[3,2]]]]] becomes [[3,[2,[_8_,_0_]]],[_9_,[5,[4,[3,2]]]]] (the pair [3,2] is unaffected because the pair [7,3] is further to the left; [3,2] would explode on the next action).
• [[3,[2,[8,0]]],[9,[5,[4,_[3,2]_]]]] becomes [[3,[2,[8,0]]],[9,[5,[_7_,_0_]]]].

To split a regular number, replace it with a pair; the left element of the pair should be the regular number divided by two and rounded down, while the right element of the pair should be the regular number divided by two and rounded up. For example, 10 becomes [5,5], 11 becomes [5,6], 12 becomes [6,6], and so on.

Here is the process of finding the reduced result of [[[[4,3],4],4],[7,[[8,4],9]]] + [1,1]:

after addition: [[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]
after explode:  [[[[0,7],4],[7,[[8,4],9]]],[1,1]]
after explode:  [[[[0,7],4],[15,[0,13]]],[1,1]]
after split:    [[[[0,7],4],[[7,8],[0,13]]],[1,1]]
after split:    [[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]
after explode:  [[[[0,7],4],[[7,8],[6,0]]],[8,1]]

Once no reduce actions apply, the snailfish number that remains is the actual result of the addition operation: [[[[0,7],4],[[7,8],[6,0]]],[8,1]].

The homework assignment involves adding up a list of snailfish numbers (your puzzle input). The snailfish numbers are each listed on a separate line. Add the first snailfish number and the second, then add that result and the third, then add that result and the fourth, and so on until all numbers in the list have been used once.

For example, the final sum of this list is [[[[1,1],[2,2]],[3,3]],[4,4]]:

[1,1]
[2,2]
[3,3]
[4,4]

The final sum of this list is [[[[3,0],[5,3]],[4,4]],[5,5]]:

[1,1]
[2,2]
[3,3]
[4,4]
[5,5]

The final sum of this list is [[[[5,0],[7,4]],[5,5]],[6,6]]:

[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6]

Here's a slightly larger example:

[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
[7,[5,[[3,8],[1,4]]]]
[[2,[2,2]],[8,[8,1]]]
[2,9]
[1,[[[9,3],9],[[9,0],[0,7]]]]
[[[5,[7,4]],7],1]
[[[[4,2],2],6],[8,7]]

The final sum [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] is found after adding up the above snailfish numbers:

  [[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+ [7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
= [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]

  [[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]
+ [[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
= [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]

  [[[[6,7],[6,7]],[[7,7],[0,7]]],[[[8,7],[7,7]],[[8,8],[8,0]]]]
+ [[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
= [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]

  [[[[7,0],[7,7]],[[7,7],[7,8]]],[[[7,7],[8,8]],[[7,7],[8,7]]]]
+ [7,[5,[[3,8],[1,4]]]]
= [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]

  [[[[7,7],[7,8]],[[9,5],[8,7]]],[[[6,8],[0,8]],[[9,9],[9,0]]]]
+ [[2,[2,2]],[8,[8,1]]]
= [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]

  [[[[6,6],[6,6]],[[6,0],[6,7]]],[[[7,7],[8,9]],[8,[8,1]]]]
+ [2,9]
= [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]

  [[[[6,6],[7,7]],[[0,7],[7,7]]],[[[5,5],[5,6]],9]]
+ [1,[[[9,3],9],[[9,0],[0,7]]]]
= [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]

  [[[[7,8],[6,7]],[[6,8],[0,8]]],[[[7,7],[5,0]],[[5,5],[5,6]]]]
+ [[[5,[7,4]],7],1]
= [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]

  [[[[7,7],[7,7]],[[8,7],[8,7]]],[[[7,0],[7,7]],9]]
+ [[[[4,2],2],6],[8,7]]
= [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]

To check whether it's the right answer, the snailfish teacher only checks the magnitude of the final sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.

For example, the magnitude of [9,1] is 3*9 + 2*1 = _29_; the magnitude of [1,9] is 3*1 + 2*9 = _21_. Magnitude calculations are recursive: the magnitude of [[9,1],[1,9]] is 3*29 + 2*21 = _129_.

Here are a few more magnitude examples:

• [[1,2],[[3,4],5]] becomes _143_.
• [[[[0,7],4],[[7,8],[6,0]]],[8,1]] becomes _1384_.
• [[[[1,1],[2,2]],[3,3]],[4,4]] becomes _445_.
• [[[[3,0],[5,3]],[4,4]],[5,5]] becomes _791_.
• [[[[5,0],[7,4]],[5,5]],[6,6]] becomes _1137_.
• [[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]] becomes _3488_.

So, given this example homework assignment:

[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]

The final sum is:

[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]

The magnitude of this final sum is _4140_.

Add up all of the snailfish numbers from the homework assignment in the order they appear. What is the magnitude of the final sum?

Proposed solution: use a binary tree while holding true specific invariants: each node either has no value (this represents a set of square brackets) and both left & right are non-null OR it has a non-null value and both left & right are null — this means that only leaf nodes have values and all other nodes should have both a left and a right

Time complexity: O(n²)

Space complexity: O(n)

Since the initial snailfish lines seem to already be fully reduced, each individual addition of the numbers has a limited number of reduction actions needed.

#!/usr/bin/env python3
from collections import deque
from math import floor, ceil
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

class SnailfishNode:
    def __init__(self, val=None, left=None, right=None, parent=None):
        """
        Invariants:
        1. Each node has either a data value or has left and right, never both
        2. A pair node (no value) should have both left and right != None
        3. A value node (value != None) should always have a parent (always in pair)
        """
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

    def depth(self):
        node, depth = self, 1
        while node.parent:
            node = node.parent
            depth += 1
        return depth

    def find_left(self):
        node = self.parent
        if self == node.left:
            while node.parent and node == node.parent.left:
                node = node.parent
            if not node.parent:
                return None
            node = node.parent

        node = node.left
        while node.val is None:
            node = node.right
        return node

    def find_right(self):
        node = self.parent
        if self == node.right:
            while node.parent and node == node.parent.right:
                node = node.parent
            if not node.parent:
                return None
            node = node.parent

        node = node.right
        while node.val is None:
            node = node.left
        return node

    def explode(self):
        """
        Preconditions:
        1. Node is a pair node
        2. Node points to two value nodes
        3. Occurs if only if depth > 4
        """
        left = self.find_left()
        right = self.find_right()
        if left:
            left.val += self.left.val
        if right:
            right.val += self.right.val
        self.left = None
        self.right = None
        self.val = 0

    def split(self):
        """
        Preconditions:
        1. Node is a value node
        2. Occurs only if value is >= 10
        """
        left_val = floor(self.val / 2)
        right_val = ceil(self.val / 2)
        left_node = SnailfishNode(val=left_val, parent=self)
        right_node = SnailfishNode(val=right_val, parent=self)
        self.val, self.left, self.right = None, left_node, right_node

    def reduce(self):
        """
        Fully reduces tree by exploding heavily nested pairs and splitting large nums
        """
        stack = deque()
        while True:
            exploded, splitted = False, False
            stack.clear()
            stack.append(self)
            while len(stack) != 0:
                node = stack.pop()
                if node.val is not None:
                    continue
                stack.append(node.right)
                stack.append(node.left)
                if node.left.val is not None and node.right.val is not None \
                        and node.depth() > 4:
                    node.explode()
                    exploded = True
                    break
            if exploded:
                continue
            
            stack.clear()
            stack.append(self)
            while len(stack) != 0:
                node = stack.pop()
                if node.val is None:
                    stack.append(node.right)
                    stack.append(node.left)
                    continue
                if node.val >= 10:
                    node.split()
                    splitted = True
                    break
            if not splitted:
                break

    def magnitude(self):
        """
        Calculate the magnitude of the entire tree
        """
        if self.val is not None:
            return self.val
        return 3 * self.left.magnitude() + 2 * self.right.magnitude()


trees = deque()
for line in file_input[::-1]:
    if line == "":
        continue
    line = line[1:-1]
    root = curr = SnailfishNode()
    for char in line:
        if char == "[":
            node = SnailfishNode(parent=curr)
            if not curr.left:
                curr.left = node
            else:
                curr.right = node
            curr = node
        elif char.isnumeric():
            node = SnailfishNode(val=int(char), parent=curr)
            if not curr.left:
                curr.left = node
            else:
                curr.right = node
        elif char == "]":
            curr = curr.parent
    trees.append(root)

while len(trees) > 1:
    tree1 = trees.pop()
    tree2 = trees.pop()
    new_node = SnailfishNode(left=tree1, right=tree2)
    tree1.parent = new_node
    tree2.parent = new_node
    new_node.reduce()
    trees.append(new_node)

print("Final Magnitude: {}".format(trees[0].magnitude()))

Breaking this down, the constructor takes a value, left, right, and a parent all of which are null by default. Keeping track of the parent in this case makes the operations that we have to do easier.

class SnailfishNode:
    def __init__(self, val=None, left=None, right=None, parent=None):
        """
        Invariants:
        1. Each node has either a data value or has left and right, never both
        2. A pair node (no value) should have both left and right != None
        3. A value node (value != None) should always have a parent (always in pair)
        """
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

Skipping forward, we need to create our trees for each line in the input.

trees = deque()
for line in file_input[::-1]:
    if line == "":
        continue
    line = line[1:-1]
    root = curr = SnailfishNode()
    for char in line:
        if char == "[":
            node = SnailfishNode(parent=curr)
            if not curr.left:
                curr.left = node
            else:
                curr.right = node
            curr = node
        elif char.isnumeric():
            node = SnailfishNode(val=int(char), parent=curr)
            if not curr.left:
                curr.left = node
            else:
                curr.right = node
        elif char == "]":
            curr = curr.parent
    trees.append(root)

I start with the last line of the input and work backwards to populate the stack. I could have done this by treating the deque as a FIFO queue instead but the important thing is that we need to "add" these snailfish numbers in the same order provided in the input.

I ignore the first and last characters (should always be start and end brackets) and initialize the first node. This represents the first pair and will always have a left and right. Maintaining a curr node, we loop through the character in the input to populate the tree. If we encounter a [ then we create a new empty node with parent=curr. This will either be curr's left node, or right node if the left node is already non-null. curr is then set to the new node to continue building the tree.

For any numeric value, we can assume it is a single digit since the input numbers are fully reduced. Create a new node with that value and again parent=curr. Set as left, or right if left is already defined. Hitting a ] means that we are done processing a pair and can set curr to curr.parent to continue building. This is repeated until the snailfish tree is fully built for every line.

    def depth(self):
        node, depth = self, 1
        while node.parent:
            node = node.parent
            depth += 1
        return depth

Tree depth can be easily calculated with the parent field since you can traverse up the tree until hitting the root node. This functionality will be important for the reduction step.

    def find_left(self):
        node = self.parent
        if self == node.left:
            while node.parent and node == node.parent.left:
                node = node.parent
            if not node.parent:
                return None
            node = node.parent

        node = node.left
        while node.val is None:
            node = node.right
        return node

    def find_right(self):
        node = self.parent
        if self == node.right:
            while node.parent and node == node.parent.right:
                node = node.parent
            if not node.parent:
                return None
            node = node.parent

        node = node.right
        while node.val is None:
            node = node.left
        return node

Finding the left and right nodes respectively will be important will be important for "exploding" in the reduction steps. We need to find the leaf nodes that are directly left or right of the current node. These work the same way but in opposite directions. For example, when finding the left nearest leaf node, move up the tree at least once until you hit a node where you can move left (without going back down the same branch). Once you find this, move left once and then move right until you hit a leaf node. Because of the properties of this specific binary tree, this will always be the nearest leaf node to the left. Same thing can be accomplished for the right by just flipping the directions.

    def explode(self):
        """
        Preconditions:
        1. Node is a pair node
        2. Node points to two value nodes
        3. Occurs if only if depth > 4
        """
        left = self.find_left()
        right = self.find_right()
        if left:
            left.val += self.left.val
        if right:
            right.val += self.right.val
        self.left = None
        self.right = None
        self.val = 0

The exploding reduction step that we just discussed. This will be called for the node directly parenting two leaf nodes. This node's left node's value will be added to the nearest leaf node to the left node and same thing in reverse for the right. This parent node then becomes a new leaf node with a value of zero and left & right set to null.

    def split(self):
        """
        Preconditions:
        1. Node is a value node
        2. Occurs only if value is >= 10
        """
        left_val = floor(self.val / 2)
        right_val = ceil(self.val / 2)
        left_node = SnailfishNode(val=left_val, parent=self)
        right_node = SnailfishNode(val=right_val, parent=self)
        self.val, self.left, self.right = None, left_node, right_node

The splitting reduction step is called from a leaf node with a value >= 10. Halving the value and taking the floor will go into a new left node of the current, and same thing (but the ceiling after halving) will go into a new right node. The current node's value becomes null.

    def reduce(self):
        """
        Fully reduces tree by exploding heavily nested pairs and splitting large nums
        """
        stack = deque()
        while True:
            exploded, splitted = False, False
            stack.clear()
            stack.append(self)
            while len(stack) != 0:
                node = stack.pop()
                if node.val is not None:
                    continue
                stack.append(node.right)
                stack.append(node.left)
                if node.left.val is not None and node.right.val is not None \
                        and node.depth() > 4:
                    node.explode()
                    exploded = True
                    break
            if exploded:
                continue
            
            stack.clear()
            stack.append(self)
            while len(stack) != 0:
                node = stack.pop()
                if node.val is None:
                    stack.append(node.right)
                    stack.append(node.left)
                    continue
                if node.val >= 10:
                    node.split()
                    splitted = True
                    break
            if not splitted:
                break

The reduction step repeats until no reduction steps need to be performed. It prioritizes explosions first and then looks for splitting after it has ruled out the former. If an explosion occurs, it restarts the process. If splitting occurs it also restarts the process by first looking for any resulting explosions. For explosions, the non-leaf node parenting two leaf nodes is used for calling the explode function while the split function is called for the leaf node.

    def magnitude(self):
        """
        Calculate the magnitude of the entire tree
        """
        if self.val is not None:
            return self.val
        return 3 * self.left.magnitude() + 2 * self.right.magnitude()

The magniatude calculation is simple recursion, all left values are bubbled up and multiplied by 3 while right values are multiplied by 2.

while len(trees) > 1:
    tree1 = trees.pop()
    tree2 = trees.pop()
    new_node = SnailfishNode(left=tree1, right=tree2)
    tree1.parent = new_node
    tree2.parent = new_node
    new_node.reduce()
    trees.append(new_node)

print("Final Magnitude: {}".format(trees[0].magnitude()))

The final step is to take the stack/queue of trees that we generated and adding each of them together, in order, (by creating a new root node and setting the left node as the first on the stack and the right as the second on the stack) and then reducing after each of these steps. The new root node is placed back on the stack until the stack contains only one node – the fully added and reduced snailfish number. Calculate the magnitude of the final number.

❯ python3 solution18.py input18
Final Magnitude: 3763

Part 2

You notice a second question on the back of the homework assignment:

What is the largest magnitude you can get from adding only two of the snailfish numbers?

Note that snailfish addition is not commutative - that is, x + y and y + x can produce different results.

Again considering the last example homework assignment above:

[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]

The largest magnitude of the sum of any two snailfish numbers in this list is _3993_. This is the magnitude of [[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] + [[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]], which reduces to [[[[7,8],[6,6]],[[6,0],[7,7]]],[[[7,8],[8,8]],[[7,9],[0,6]]]].

What is the largest magnitude of any sum of two different snailfish numbers from the homework assignment?

Proposed solution: all the functionality of the tree stays the same but a new last section to add every number to itself; deepcopy's need to be made, otherwise the original tree will be changed and cannot be used to add to all other numbers

Time complexity: O(n³)

Space complexity: O(n)

max_magnitude = 0
for _tree1 in trees:
    for _tree2 in trees:
        if _tree1 == _tree2:
            continue
        tree1 = deepcopy(_tree1)
        tree2 = deepcopy(_tree2)
        new_node = SnailfishNode(left=tree1, right=tree2)
        tree1.parent = new_node
        tree2.parent = new_node
        new_node.reduce()
        max_magnitude = max(max_magnitude, new_node.magnitude())

print("Maximum Magnitude: {}".format(max_magnitude))

This is a brute force technique. I commented out the loop to add all snailfish numbers together and wrote this. It's O(n³) but it's more than fast enough.

❯ time python3 solution18.py input18
Maximum Magnitude: 4664
python3 solution18.py input18  3.50s user 0.01s system 99% cpu 3.509 total

Part 1

You finally decode the Elves' message. HI, the message says. You continue searching for the sleigh keys.

Ahead of you is what appears to be a large ocean trench. Could the keys have fallen into it? You'd better send a probe to investigate.

The probe launcher on your submarine can fire the probe with any integer velocity in the x (forward) and y (upward, or downward if negative) directions. For example, an initial x,y velocity like 0,10 would fire the probe straight up, while an initial velocity like 10,-1 would fire the probe forward at a slight downward angle.

The probe's x,y position starts at 0,0. Then, it will follow some trajectory by moving in steps. On each step, these changes occur in the following order:

• The probe's x position increases by its x velocity.
• The probe's y position increases by its y velocity.
• Due to drag, the probe's x velocity changes by 1 toward the value 0; that is, it decreases by 1 if it is greater than 0, increases by 1 if it is less than 0, or does not change if it is already 0.
• Due to gravity, the probe's y velocity decreases by 1.

For the probe to successfully make it into the trench, the probe must be on some trajectory that causes it to be within a target area after any step. The submarine computer has already calculated this target area (your puzzle input). For example:

target area: x=20..30, y=-10..-5

This target area means that you need to find initial x,y velocity values such that after any step, the probe's x position is at least 20 and at most 30, and the probe's y position is at least -10 and at most -5.

Given this target area, one initial velocity that causes the probe to be within the target area after any step is 7,2:

.............#....#............
.......#..............#........
...............................
S........................#.....
...............................
...............................
...........................#...
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTT#TT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

In this diagram, S is the probe's initial position, 0,0. The x coordinate increases to the right, and the y coordinate increases upward. In the bottom right, positions that are within the target area are shown as T. After each step (until the target area is reached), the position of the probe is marked with #. (The bottom-right # is both a position the probe reaches and a position in the target area.)

Another initial velocity that causes the probe to be within the target area after any step is 6,3:

...............#..#............
...........#........#..........
...............................
......#..............#.........
...............................
...............................
S....................#.........
...............................
...............................
...............................
.....................#.........
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................T#TTTTTTTTT
....................TTTTTTTTTTT

Another one is 9,0:

S........#.....................
.................#.............
...............................
........................#......
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTT#
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT

One initial velocity that doesn't cause the probe to be within the target area after any step is 17,-4:

S..............................................................
...............................................................
...............................................................
...............................................................
.................#.............................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT................................
....................TTTTTTTTTTT..#.............................
....................TTTTTTTTTTT................................
...............................................................
...............................................................
...............................................................
...............................................................
................................................#..............
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
...............................................................
..............................................................#

The probe appears to pass through the target area, but is never within it after any step. Instead, it continues down and to the right - only the first few steps are shown.

If you're going to fire a highly scientific probe out of a super cool probe launcher, you might as well do it with style. How high can you make the probe go while still reaching the target area?

In the above example, using an initial velocity of 6,9 is the best you can do, causing the probe to reach a maximum y position of _45_. (Any higher initial y velocity causes the probe to overshoot the target area entirely.)

Find the initial velocity that causes the probe to reach the highest y position and still eventually be within the target area after any step. What is the highest y position it reaches on this trajectory?

Proposed solution: pick various start velocities up until a point where the initial velocity will cause the probe to never land in the target area; brute force the max height with these initial velocities

Time complexity: O(n) where n is the difference between the minimum and maximum y coordinate for the target area

Space complexity: O(1)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")
temp = file_input[0].split("target area: ")[1].split(", ")
min_x, max_x = list(map(lambda x: int(x), temp[0].split("=")[1].split("..")))
min_y, max_y = list(map(lambda x: int(x), temp[1].split("=")[1].split("..")))

range_y = max_y - min_y

result = 0
for dy_init in range(range_y, range_y*100):
    dy, y, ymax = dy_init, 0, 0
    while y >= min_y:
        if y <= max_y:
            result = max(result, ymax)
            break
        y += dy
        dy -= 1
        ymax = max(ymax, y)

print("Max y: {}".format(result))

I picked a magnitude of 100 times the initial range_y. I figured this should be good enough since the target in my input was in the negative y quadrant and anything above that starting velocity should never hit the target area – it's velocity would be too large by the time it got to near the same y coordinate on the way down.

❯ python3 solution17.py input17
Max y: 5050

Part 2

Maybe a fancy trick shot isn't the best idea; after all, you only have one probe, so you had better not miss.

To get the best idea of what your options are for launching the probe, you need to find every initial velocity that causes the probe to eventually be within the target area after any step.

In the above example, there are _112_ different initial velocity values that meet these criteria:

23,-10  25,-9   27,-5   29,-6   22,-6   21,-7   9,0     27,-7   24,-5
25,-7   26,-6   25,-5   6,8     11,-2   20,-5   29,-10  6,3     28,-7
8,0     30,-6   29,-8   20,-10  6,7     6,4     6,1     14,-4   21,-6
26,-10  7,-1    7,7     8,-1    21,-9   6,2     20,-7   30,-10  14,-3
20,-8   13,-2   7,3     28,-8   29,-9   15,-3   22,-5   26,-8   25,-8
25,-6   15,-4   9,-2    15,-2   12,-2   28,-9   12,-3   24,-6   23,-7
25,-10  7,8     11,-3   26,-7   7,1     23,-9   6,0     22,-10  27,-6
8,1     22,-8   13,-4   7,6     28,-6   11,-4   12,-4   26,-9   7,4
24,-10  23,-8   30,-8   7,0     9,-1    10,-1   26,-5   22,-9   6,5
7,5     23,-6   28,-10  10,-2   11,-1   20,-9   14,-2   29,-7   13,-3
23,-5   24,-8   27,-9   30,-7   28,-5   21,-10  7,9     6,6     21,-5
27,-10  7,2     30,-9   21,-8   22,-7   24,-9   20,-6   6,9     29,-5
8,-2    27,-8   30,-5   24,-7

How many distinct initial velocity values cause the probe to be within the target area after any step?

Proposed solution: iterate over all pairs of initial velocities (considering both x and y initial) and keep track of all that make it into the target area

Time complexity: O(n)

Space complexity: O(n)

I think we could represent time complexity in terms of the actual parabolic function but I'm not going to do that. Instead, just consider n the total length of the set of initial velocities that will be tested.

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")
temp = file_input[0].split("target area: ")[1].split(", ")
min_x, max_x = list(map(lambda x: int(x), temp[0].split("=")[1].split("..")))
min_y, max_y = list(map(lambda x: int(x), temp[1].split("=")[1].split("..")))

range_x = max_x - min_x
range_y = max_y - min_y

result = 0
uniq_velocities = set()
for dx_init in range(1, max_x+1):
    for dy_init in range(min_y, range_y*10):
        dx, x = dx_init, 0
        dy, y, ymax = dy_init, 0, 0
        while x <= max_x and y >= min_y:
            if x >= min_x and y <= max_y:
                uniq_velocities.add((dx_init, dy_init))
                result = max(result, ymax)
                break
            y += dy
            dy -= 1
            ymax = max(ymax, y)
            x += dx
            dx = max(0, dx - 1)

print("Max y: {}".format(result))
print("Unique velocities: {}".format(len(uniq_velocities)))

In this case, I selected initial dx in the range 1 to max_x and an initial dy from min_y to range_y * 10 for every dx_init value. For x, this is because anything above max_x would already be past the target after step 1. For y, this is because anything lower than min_y will be past the target by step 1 and in part 1 I discovered that anything past range_y * 10 will not reach the target, even just isolated to the y-axis.

❯ python3 solution17.py input17
Max y: 5050
Unique velocities: 2223

Part 1

As you leave the cave and reach open waters, you receive a transmission from the Elves back on the ship.

The transmission was sent using the Buoyancy Interchange Transmission System (BITS), a method of packing numeric expressions into a binary sequence. Your submarine's computer has saved the transmission in hexadecimal (your puzzle input).

The first step of decoding the message is to convert the hexadecimal representation into binary. Each character of hexadecimal corresponds to four bits of binary data:

0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
A = 1010
B = 1011
C = 1100
D = 1101
E = 1110
F = 1111

The BITS transmission contains a single packet at its outermost layer which itself contains many other packets. The hexadecimal representation of this packet might encode a few extra 0 bits at the end; these are not part of the transmission and should be ignored.

Every packet begins with a standard header: the first three bits encode the packet version, and the next three bits encode the packet type ID. These two values are numbers; all numbers encoded in any packet are represented as binary with the most significant bit first. For example, a version encoded as the binary sequence 100 represents the number 4.

Packets with type ID 4 represent a literal value. Literal value packets encode a single binary number. To do this, the binary number is padded with leading zeroes until its length is a multiple of four bits, and then it is broken into groups of four bits. Each group is prefixed by a 1 bit except the last group, which is prefixed by a 0 bit. These groups of five bits immediately follow the packet header. For example, the hexadecimal string D2FE28 becomes:

110100101111111000101000
VVVTTTAAAAABBBBBCCCCC

Below each bit is a label indicating its purpose:

• The three bits labeled V (110) are the packet version, 6.
• The three bits labeled T (100) are the packet type ID, 4, which means the packet is a literal value.
• The five bits labeled A (10111) start with a 1 (not the last group, keep reading) and contain the first four bits of the number, 0111.
• The five bits labeled B (11110) start with a 1 (not the last group, keep reading) and contain four more bits of the number, 1110.
• The five bits labeled C (00101) start with a 0 (last group, end of packet) and contain the last four bits of the number, 0101.
• The three unlabeled 0 bits at the end are extra due to the hexadecimal representation and should be ignored.

So, this packet represents a literal value with binary representation 011111100101, which is 2021 in decimal.

Every other type of packet (any packet with a type ID other than 4) represent an operator that performs some calculation on one or more sub-packets contained within. Right now, the specific operations aren't important; focus on parsing the hierarchy of sub-packets.

An operator packet contains one or more packets. To indicate which subsequent binary data represents its sub-packets, an operator packet can use one of two modes indicated by the bit immediately after the packet header; this is called the length type ID:

• If the length type ID is 0, then the next 15 bits are a number that represents the total length in bits of the sub-packets contained by this packet.
• If the length type ID is 1, then the next 11 bits are a number that represents the number of sub-packets immediately contained by this packet.

Finally, after the length type ID bit and the 15-bit or 11-bit field, the sub-packets appear.

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB

• The three bits labeled V (001) are the packet version, 1.
• The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
• The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
• The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
• The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
• The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

After reading 11 and 16 bits of sub-packet data, the total length indicated in L (27) is reached, and so parsing of this packet stops.

As another example, here is an operator packet (hexadecimal string EE00D40C823060) with length type ID 1 that contains three sub-packets:

11101110000000001101010000001100100000100011000001100000
VVVTTTILLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCC

• The three bits labeled V (111) are the packet version, 7.
• The three bits labeled T (011) are the packet type ID, 3, which means the packet is an operator.
• The bit labeled I (1) is the length type ID, which indicates that the length is a 11-bit number representing the number of sub-packets.
• The 11 bits labeled L (00000000011) contain the number of sub-packets, 3.
• The 11 bits labeled A contain the first sub-packet, a literal value representing the number 1.
• The 11 bits labeled B contain the second sub-packet, a literal value representing the number 2.
• The 11 bits labeled C contain the third sub-packet, a literal value representing the number 3.

After reading 3 complete sub-packets, the number of sub-packets indicated in L (3) is reached, and so parsing of this packet stops.

For now, parse the hierarchy of the packets throughout the transmission and add up all of the version numbers.

Here are a few more examples of hexadecimal-encoded transmissions:

• 8A004A801A8002F478 represents an operator packet (version 4) which contains an operator packet (version 1) which contains an operator packet (version 5) which contains a literal value (version 6); this packet has a version sum of _16_.
• 620080001611562C8802118E34 represents an operator packet (version 3) which contains two sub-packets; each sub-packet is an operator packet that contains two literal values. This packet has a version sum of _12_.
• C0015000016115A2E0802F182340 has the same structure as the previous example, but the outermost packet uses a different length type ID. This packet has a version sum of _23_.
• A0016C880162017C3686B18A3D4780 is an operator packet that contains an operator packet that contains an operator packet that contains five literal values; it has a version sum of _31_.

Decode the structure of your hexadecimal-encoded BITS transmission; what do you get if you add up the version numbers in all packets?

Proposed solution: packets representing literals have a looped structure where the first bit in every 5 bits indicates whether it is the last block; operation packets can indicate either the number of sub-packets (immediately nested in the current packet) or the number of bytes of the sub-packets (all nested sub-packets); the idea is to keep a stack indicating this nesting of operator packets with the length_type and then the corresponding length

Time complexity: O(n)

Space complexity: O(n)

#!/usr/bin/env python3
from collections import deque
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

decode_table = {
    "0": "0000",
    "1": "0001",
    "2": "0010",
    "3": "0011",
    "4": "0100",
    "5": "0101",
    "6": "0110",
    "7": "0111",
    "8": "1000",
    "9": "1001",
    "A": "1010",
    "B": "1011",
    "C": "1100",
    "D": "1101",
    "E": "1110",
    "F": "1111"
}

file_input = open(sys.argv[1], "r").read().strip().split("\n")
hex_string = file_input[0]
#print(hex_string)

bin_string = ""
for char in hex_string:
    bin_string += decode_table[char]
#print(bin_string)

Another way to create the binary string is by using the built-in bin function after converting the hex string into an integer. Something like bin(int("deadbeef", 16))[2:].

i = 0
stack = deque()
version_total = 0
unbin = lambda x: int(x, 2)
while i < len(bin_string):
    if len(stack) != 0:
        if stack[-1][0] == 1:
            elem = stack.pop()
            if elem[1] > 1:
                stack.append((elem[0], elem[1]-1))
        else:
            if i == stack[-1][1]:
                stack.pop()
    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        break
    version = unbin(bin_string[i:i+3])
    version_total += version
    type_id = unbin(bin_string[i+3:i+6])
    if type_id == 4:
        i += 6
        literal = ""
        while unbin(bin_string[i]) == 1:
            literal += bin_string[i+1:i+5]
            i += 5
        literal += bin_string[i+1:i+5]
        i += 5
        continue
    length_type = unbin(bin_string[i+6])
    if length_type:
        length = 11
        num_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, num_subpackets))
    else:
        length = 15
        length_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, i+7+length+length_subpackets))
    i += 7 + length

print("Version Total: {}".format(version_total))

I constructed this just to count the version numbers and sum them together. Each step is just parsing until the binary string is completely enumerated while keeping a stack due to the nested nature of the packets.

    if len(stack) != 0:
        if stack[-1][0] == 1:
            elem = stack.pop()
            if elem[1] > 1:
                stack.append((elem[0], elem[1]-1))
        else:
            if i == stack[-1][1]:
                stack.pop()

Each loop through the outer while loop goes through a single packet (not including respective sub-packets). This first block updates the top element of the stack. These elements in the stack are tuples with the first element being the length type (0 is for number of packets and 1 is for number of bits) and the second it the actual length. For number of packets, this length is decremented and placed back on the stack until the number of sub-packets reaches zero – then it is just popped off. For number of bits, this is actually pushed to the stack with the length + the starting position of the sub-packets which is effectively the end of the packet.

if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        break

If the iterator is not at the end of the bit string and the rest of the bin string is all 0s and smaller than the minimum packet length, just break out since this is just padding.

    version = unbin(bin_string[i:i+3])
    version_total += version
    type_id = unbin(bin_string[i+3:i+6])
    if type_id == 4:
        i += 6
        literal = ""
        while unbin(bin_string[i]) == 1:
            literal += bin_string[i+1:i+5]
            i += 5
        literal += bin_string[i+1:i+5]
        i += 5
        continue

This first section parses the version, packet type, and if the packet type is a literal (has a value of 4) then, loop through blocks of 5 bits until hitting the last block.

    length_type = unbin(bin_string[i+6])
    if length_type:
        length = 11
        num_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, num_subpackets))
    else:
        length = 15
        length_subpackets = unbin(bin_string[i+7:i+7+length])
        stack.append((length_type, i+7+length+length_subpackets))
    i += 7 + length

The last block is for operation packets. Based on length-type, push the corresponding length value to the stack. Again, for bit length we calculate the end of the packet before pushing.

❯ python3 solution16.py input16
Version Total: 873

Part 2

Now that you have the structure of your transmission decoded, you can calculate the value of the expression it represents.

Literal values (type ID 4) represent a single number as described above. The remaining type IDs are more interesting:

• Packets with type ID 0 are sum packets - their value is the sum of the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.
• Packets with type ID 1 are product packets - their value is the result of multiplying together the values of their sub-packets. If they only have a single sub-packet, their value is the value of the sub-packet.
• Packets with type ID 2 are minimum packets - their value is the minimum of the values of their sub-packets.
• Packets with type ID 3 are maximum packets - their value is the maximum of the values of their sub-packets.
• Packets with type ID 5 are greater than packets - their value is 1 if the value of the first sub-packet is greater than the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.
• Packets with type ID 6 are less than packets - their value is 1 if the value of the first sub-packet is less than the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.
• Packets with type ID 7 are equal to packets - their value is 1 if the value of the first sub-packet is equal to the value of the second sub-packet; otherwise, their value is 0. These packets always have exactly two sub-packets.

Using these rules, you can now work out the value of the outermost packet in your BITS transmission.

For example:

• C200B40A82 finds the sum of 1 and 2, resulting in the value _3_.
• 04005AC33890 finds the product of 6 and 9, resulting in the value _54_.
• 880086C3E88112 finds the minimum of 7, 8, and 9, resulting in the value _7_.
• CE00C43D881120 finds the maximum of 7, 8, and 9, resulting in the value _9_.
• D8005AC2A8F0 produces 1, because 5 is less than 15.
• F600BC2D8F produces 0, because 5 is not greater than 15.
• 9C005AC2F8F0 produces 0, because 5 is not equal to 15.
• 9C0141080250320F1802104A08 produces 1, because 1 + 3 = 2 * 2.

What do you get if you evaluate the expression represented by your hexadecimal-encoded BITS transmission?

Proposed solution: same idea but now having to do actual calculations based on the literals and operation packets; we have to store more information for each operation packet on the stack (like the cumulative result and the number of bits already iterated over)

Time complexity: O(n)

Space complexity: O(n)

#!/usr/bin/env python3
from collections import deque
from math import prod
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

decode_table = {
    "0": "0000",
    "1": "0001",
    "2": "0010",
    "3": "0011",
    "4": "0100",
    "5": "0101",
    "6": "0110",
    "7": "0111",
    "8": "1000",
    "9": "1001",
    "A": "1010",
    "B": "1011",
    "C": "1100",
    "D": "1101",
    "E": "1110",
    "F": "1111"
}

operator_map = {
    0: lambda x: sum(x),
    1: lambda x: prod(x),
    2: lambda x: min(x),
    3: lambda x: max(x),
    5: lambda x: int(x[0] > x[1]),
    6: lambda x: int(x[0] < x[1]),
    7: lambda x: int(x[0] == x[1])
}

file_input = open(sys.argv[1], "r").read().strip().split("\n")
hex_string = file_input[0]
#print(hex_string)

bin_string = ""
for char in hex_string:
    bin_string += decode_table[char]
#print(bin_string)

stack = deque()
unbin = lambda x: int(x, 2)
result, num_packets, version_total, i = 0, 0, 0, 0
while i < len(bin_string):
    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        # break out of loop when we hit trailing zeroes less than minimum packet length
        break
    start_i = i
    version = unbin(bin_string[i:i+3]) # first three bits are version
    version_total += version
    type_id = unbin(bin_string[i+3:i+6]) # next three bits are packet type id
    if type_id != 4:
        # process operator packets
        length_type = unbin(bin_string[i+6])
        length = 11 if length_type else 15
        length_num = unbin(bin_string[i+7:i+7+length])
        i += 7 + length # move i to start of first sub-packet
        if len(stack) != 0:
            # track new bits and sub-packets in parent packet
            stack[-1]["num_bits"] += i - start_i
            stack[-1]["num_packets"] += 1
        stack.append({
            "result": [],
            "length_type": length_type,
            "length_num": length_num,
            "type_id": type_id,
            "num_bits": 0,
            "num_packets": 0
        })
        continue
    # process literals and stack reduction
    i += 6 # move i to the start of the literal
    literal = ""
    while unbin(bin_string[i]) == 1:
        # loop until we hit the last block
        literal += bin_string[i+1:i+5]
        i += 5
    literal += bin_string[i+1:i+5]
    literal = unbin(literal)
    i += 5
    if len(stack) == 0:
        # if packet is just a literal, we're done
        result = literal
        break
    stack[-1]["result"].append(literal) # track literal in top of operator stack

    if len(stack) != 0:
        # track new bits and sub-packets in parent operator packet
        stack[-1]["num_bits"] += i - start_i
        stack[-1]["num_packets"] += 1
    while len(stack) != 0:
        top = stack[-1]
        if not (top["length_type"] and top["length_num"] == top["num_packets"]) \
                and not (not top["length_type"] and top["length_num"] == top["num_bits"]):
            # if we are not finished with the top operator packet, continue
            break
        top = stack.pop()
        operation_result = operator_map[top["type_id"]](top["result"])
        if len(stack) == 0:
            # when done with our top-level operator packet, we are done
            result = operation_result
        else:
            # bubble up new bits to parent operator packet
            # note: no need to bubble up num_packets since we care about immediate children
            stack[-1]["num_bits"] += top["num_bits"]
            # take operation result from current packet and append to parent operator
            stack[-1]["result"].append(operation_result)

print("Version Total: {}".format(version_total))
print("Packet Result: {}".format(result))

I defined some lambdas in a map to easily call operations based on which operator packet is being dealt with.

operator_map = {
    0: lambda x: sum(x),
    1: lambda x: prod(x),
    2: lambda x: min(x),
    3: lambda x: max(x),
    5: lambda x: int(x[0] > x[1]),
    6: lambda x: int(x[0] < x[1]),
    7: lambda x: int(x[0] == x[1])
}

We maintain the same check for extra padding 0s to break out early instead of interpreting the 0s as another packet.

    if len(bin_string) - i < 11 and unbin(bin_string[i:len(bin_string)]) == 0:
        # break out of loop when we hit trailing zeroes less than minimum packet length
        break

I switched it around for part 2 and processed operator packets earlier in the loop. It is straight forward with the new stack elements (dictionaries to store some additional information).

    start_i = i
    version = unbin(bin_string[i:i+3]) # first three bits are version
    version_total += version
    type_id = unbin(bin_string[i+3:i+6]) # next three bits are packet type id
    if type_id != 4:
        # process operator packets
        length_type = unbin(bin_string[i+6])
        length = 11 if length_type else 15
        length_num = unbin(bin_string[i+7:i+7+length])
        i += 7 + length # move i to start of first sub-packet
        if len(stack) != 0:
            # track new bits and sub-packets in parent packet
            stack[-1]["num_bits"] += i - start_i
            stack[-1]["num_packets"] += 1
        stack.append({
            "result": [],
            "length_type": length_type,
            "length_num": length_num,
            "type_id": type_id,
            "num_bits": 0,
            "num_packets": 0
        })
        continue

For the new elements, result is a list of literals from resulting sub-packets. These will be passed to the actual operation lambda once the end of the packet has been reached (these will bubble up until all packets have been processed). length_type, length_num, and type_id are the respective values from the operation packet. num_bits and num_packets track the number of bits and packets coming from sub-packets of the element added to the stack. Even the operation packets will update these values for the nested opeartion above it – only if the stack is not empty meaning that it is not the first packet.

    # process literals and stack reduction
    i += 6 # move i to the start of the literal
    literal = ""
    while unbin(bin_string[i]) == 1:
        # loop until we hit the last block
        literal += bin_string[i+1:i+5]
        i += 5
    literal += bin_string[i+1:i+5]
    literal = unbin(literal)
    i += 5
    if len(stack) == 0:
        # if packet is just a literal, we're done
        result = literal
        break
    stack[-1]["result"].append(literal) # track literal in top of operator stack

    if len(stack) != 0:
        # track new bits and sub-packets in parent operator packet
        stack[-1]["num_bits"] += i - start_i
        stack[-1]["num_packets"] += 1

The last blocks of the while loop are skipping for operator packets, meaning that these blocks are only run while processing literals. This calculates the value of the current literal and sets it as the result if the stack is empty – meaning that it is the only packet in the input. Otheriwse, it appends the literal value to the parent operation's result list. Also, track the number of bits and packets in the parent operation's element on the stack.

    while len(stack) != 0:
        top = stack[-1]
        if not (top["length_type"] and top["length_num"] == top["num_packets"]) \
                and not (not top["length_type"] and top["length_num"] == top["num_bits"]):
            # if we are not finished with the top operator packet, continue
            break
        top = stack.pop()
        operation_result = operator_map[top["type_id"]](top["result"])
        if len(stack) == 0:
            # when done with our top-level operator packet, we are done
            result = operation_result
        else:
            # bubble up new bits to parent operator packet
            # note: no need to bubble up num_packets since we care about immediate children
            stack[-1]["num_bits"] += top["num_bits"]
            # take operation result from current packet and append to parent operator
            stack[-1]["result"].append(operation_result)

The last section bubbles up the result from the stack. If the operation at the top of the stack has all of its sub-packets processed, then it runs the corresponding operation lambda on the result list and the operational_result is added to the parent operator's result list – also the num_bits. The num_packets does not need to be bubbled up since only the immediate (one layer nested) sub-packets matter for that length type. This process is repeated until hitting an operation that is not done being processed on the stack or the stack is empty meaning that the entire packet has been processed.

❯ python3 solution16.py input16
Version Total: 873
Packet Result: 402817863665

Part 1

You've almost reached the exit of the cave, but the walls are getting closer together. Your submarine can barely still fit, though; the main problem is that the walls of the cave are covered in chitons, and it would be best not to bump any of them.

The cavern is large, but has a very low ceiling, restricting your motion to two dimensions. The shape of the cavern resembles a square; a quick scan of chiton density produces a map of risk level throughout the cave (your puzzle input). For example:

1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581

You start in the top left position, your destination is the bottom right position, and you cannot move diagonally. The number at each position is its risk level; to determine the total risk of an entire path, add up the risk levels of each position you enter (that is, don't count the risk level of your starting position unless you enter it; leaving it adds no risk to your total).

Your goal is to find a path with the lowest total risk. In this example, a path with the lowest total risk is highlighted here:

1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581

The total risk of this path is _40_ (the starting position is never entered, so its risk is not counted).

What is the lowest total risk of any path from the top left to the bottom right?

Proposed solution: using dynamic programming, we can keep track of the most optimal risk score of each point on the map – if we can calculate a more optimal path for a given point (eliminating many non-optimal paths), we update the minimum risk score

Time complexity: O(V²) where V is the number of "vertices" (or points) in the map

Space complexity: O(V)

This is technically Dijkstra's algorithm where the graph is the map and each vertex is a number on the map which connects to its 2-4 adjacent neighbors.

#!/usr/bin/env python3
from collections import deque
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

class Cell:
    def __init__(self, x, y, weight=None):
        self.x = x
        self.y = y
        self.weight = weight

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

graph = {}
for y, line in enumerate(file_input):
    for x, weight in enumerate(line):
        graph[x,y] = Cell(x, y, int(weight))

dx = [-1,0,1,0]
dy = [0,1,0,-1]

x_length = len(file_input[0])
y_length = len(file_input)

st = set()
st.add(Cell(0, 0, 0))
dist = {(0,0): 0}
while len(st) != 0:
    cell = st.pop()
    for i in range(4):
        x = cell.x + dx[i]
        y = cell.y + dy[i]

        if x < 0 or y < 0 or y >= y_length or x >= x_length:
            continue

        if (x,y) not in dist or dist[x,y] > dist[cell.x,cell.y] + graph[x,y].weight:
            check = Cell(x,y)
            if check in st:
                st.remove(check)

            dist[x,y] = dist[cell.x,cell.y] + graph[x,y].weight
            st.add(Cell(x, y, dist[x,y]))

print("Shortest Path Length: {}".format(dist[x_length-1,y_length-1]))

Not too much to explain here. Dijkstra's algorithm with some specific checks because of the 2d map nature of the problem.

❯ python3 solution15.py input15
Shortest Path Length: 363

Part 2

Now that you know how to find low-risk paths in the cave, you can try to find your way out.

The entire cave is actually five times larger in both dimensions than you thought; the area you originally scanned is just one tile in a 5x5 tile area that forms the full map. Your original map tile repeats to the right and downward; each time the tile repeats to the right or downward, all of its risk levels are 1 higher than the tile immediately up or left of it. However, risk levels above 9 wrap back around to 1. So, if your original map had some position with a risk level of 8, then that same position on each of the 25 total tiles would be as follows:

8 9 1 2 3
9 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

Each single digit above corresponds to the example position with a value of 8 on the top-left tile. Because the full map is actually five times larger in both dimensions, that position appears a total of 25 times, once in each duplicated tile, with the values shown above.

Here is the full five-times-as-large version of the first example above, with the original map in the top left corner highlighted:

11637517422274862853338597396444961841755517295286
13813736722492484783351359589446246169155735727126
21365113283247622439435873354154698446526571955763
36949315694715142671582625378269373648937148475914
74634171118574528222968563933317967414442817852555
13191281372421239248353234135946434524615754563572
13599124212461123532357223464346833457545794456865
31254216394236532741534764385264587549637569865174
12931385212314249632342535174345364628545647573965
23119445813422155692453326671356443778246755488935
22748628533385973964449618417555172952866628316397
24924847833513595894462461691557357271266846838237
32476224394358733541546984465265719557637682166874
47151426715826253782693736489371484759148259586125
85745282229685639333179674144428178525553928963666
24212392483532341359464345246157545635726865674683
24611235323572234643468334575457944568656815567976
42365327415347643852645875496375698651748671976285
23142496323425351743453646285456475739656758684176
34221556924533266713564437782467554889357866599146
33859739644496184175551729528666283163977739427418
35135958944624616915573572712668468382377957949348
43587335415469844652657195576376821668748793277985
58262537826937364893714847591482595861259361697236
96856393331796741444281785255539289636664139174777
35323413594643452461575456357268656746837976785794
35722346434683345754579445686568155679767926678187
53476438526458754963756986517486719762859782187396
34253517434536462854564757396567586841767869795287
45332667135644377824675548893578665991468977611257
44961841755517295286662831639777394274188841538529
46246169155735727126684683823779579493488168151459
54698446526571955763768216687487932779859814388196
69373648937148475914825958612593616972361472718347
17967414442817852555392896366641391747775241285888
46434524615754563572686567468379767857948187896815
46833457545794456865681556797679266781878137789298
64587549637569865174867197628597821873961893298417
45364628545647573965675868417678697952878971816398
56443778246755488935786659914689776112579188722368
55172952866628316397773942741888415385299952649631
57357271266846838237795794934881681514599279262561
65719557637682166874879327798598143881961925499217
71484759148259586125936169723614727183472583829458
28178525553928963666413917477752412858886352396999
57545635726865674683797678579481878968159298917926
57944568656815567976792667818781377892989248891319
75698651748671976285978218739618932984172914319528
56475739656758684176786979528789718163989182927419
67554889357866599146897761125791887223681299833479

Equipped with the full map, you can now find a path from the top left corner to the bottom right corner with the lowest total risk:

11637517422274862853338597396444961841755517295286
13813736722492484783351359589446246169155735727126
21365113283247622439435873354154698446526571955763
36949315694715142671582625378269373648937148475914
74634171118574528222968563933317967414442817852555
13191281372421239248353234135946434524615754563572
13599124212461123532357223464346833457545794456865
31254216394236532741534764385264587549637569865174
12931385212314249632342535174345364628545647573965
23119445813422155692453326671356443778246755488935
22748628533385973964449618417555172952866628316397
24924847833513595894462461691557357271266846838237
32476224394358733541546984465265719557637682166874
47151426715826253782693736489371484759148259586125
85745282229685639333179674144428178525553928963666
24212392483532341359464345246157545635726865674683
24611235323572234643468334575457944568656815567976
42365327415347643852645875496375698651748671976285
23142496323425351743453646285456475739656758684176
34221556924533266713564437782467554889357866599146
33859739644496184175551729528666283163977739427418
35135958944624616915573572712668468382377957949348
43587335415469844652657195576376821668748793277985
58262537826937364893714847591482595861259361697236
96856393331796741444281785255539289636664139174777
35323413594643452461575456357268656746837976785794
35722346434683345754579445686568155679767926678187
53476438526458754963756986517486719762859782187396
34253517434536462854564757396567586841767869795287
45332667135644377824675548893578665991468977611257
44961841755517295286662831639777394274188841538529
46246169155735727126684683823779579493488168151459
54698446526571955763768216687487932779859814388196
69373648937148475914825958612593616972361472718347
17967414442817852555392896366641391747775241285888
46434524615754563572686567468379767857948187896815
46833457545794456865681556797679266781878137789298
64587549637569865174867197628597821873961893298417
45364628545647573965675868417678697952878971816398
56443778246755488935786659914689776112579188722368
55172952866628316397773942741888415385299952649631
57357271266846838237795794934881681514599279262561
65719557637682166874879327798598143881961925499217
71484759148259586125936169723614727183472583829458
28178525553928963666413917477752412858886352396999
57545635726865674683797678579481878968159298917926
57944568656815567976792667818781377892989248891319
75698651748671976285978218739618932984172914319528
56475739656758684176786979528789718163989182927419
67554889357866599146897761125791887223681299833479

The total risk of this path is _315_ (the starting position is still never entered, so its risk is not counted).

Using the full map, what is the lowest total risk of any path from the top left to the bottom right?

Proposed solution: exactly the same but update to the in-memory graph generation

Time complexity: O(V²)

Space complexity: O(V)

graph = {}
x_length = len(file_input[0])
y_length = len(file_input)
for y, line in enumerate(file_input):
    for x, weight in enumerate(line):
        for ry in range(5):
            for rx in range(5):
                graph_x = rx * x_length + x
                graph_y = ry * y_length + y
                new_weight = ((int(weight) + (ry + rx) - 1) % 9) + 1
                graph[graph_x,graph_y] = Cell(graph_x, graph_y, new_weight)

❯ python3 solution15.py input15
Shortest Path Length: 2835

Part 1

The incredible pressures at this depth are starting to put a strain on your submarine. The submarine has polymerization equipment that would produce suitable materials to reinforce the submarine, and the nearby volcanically-active caves should even have the necessary input elements in sufficient quantities.

The submarine manual contains instructions for finding the optimal polymer formula; specifically, it offers a polymer template and a list of pair insertion rules (your puzzle input). You just need to work out what polymer would result after repeating the pair insertion process a few times.

For example:

NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C

The first line is the polymer template - this is the starting point of the process.

The following section defines the pair insertion rules. A rule like AB -> C means that when elements A and B are immediately adjacent, element C should be inserted between them. These insertions all happen simultaneously.

So, starting with the polymer template NNCB, the first step simultaneously considers all three pairs:

• The first pair (NN) matches the rule NN -> C, so element _C_ is inserted between the first N and the second N.
• The second pair (NC) matches the rule NC -> B, so element _B_ is inserted between the N and the C.
• The third pair (CB) matches the rule CB -> H, so element _H_ is inserted between the C and the B.

Note that these pairs overlap: the second element of one pair is the first element of the next pair. Also, because all pairs are considered simultaneously, inserted elements are not considered to be part of a pair until the next step.

After the first step of this process, the polymer becomes N_C_N_B_C_H_B.

Here are the results of a few steps using the above rules:

Template:     NNCB
After step 1: NCNBCHB
After step 2: NBCCNBBBCBHCB
After step 3: NBBBCNCCNBBNBNBBCHBHHBCHB
After step 4: NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB

This polymer grows quickly. After step 5, it has length 97; After step 10, it has length 3073. After step 10, B occurs 1749 times, C occurs 298 times, H occurs 161 times, and N occurs 865 times; taking the quantity of the most common element (B, 1749) and subtracting the quantity of the least common element (H, 161) produces 1749 - 161 = _1588_.

Apply 10 steps of pair insertion to the polymer template and find the most and least common elements in the result. What do you get if you take the quantity of the most common element and subtract the quantity of the least common element?

Proposed solution: create an insertion map for the polymers from the input data, take the initial template and apply 10 steps of the process; generate a new string each round with the inserted values

Time complexity: O(2ⁿ) where n is the number of steps in the process

Space complexity: O(2ⁿ)

Each step of the process roughly doubles the length of the string. Both time and space complexity are exponential functions.

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

insertion_map = {}
for line in file_input[2:]:
    if line == "":
        continue
    template, insertion = line.split()[0], line.split()[-1]
    insertion_map[template] = insertion

start = file_input[0]
for i in range(10):
    result = ""
    for j in range(len(str(start)) - 1):
        template = start[j:j+2]
        if j == 0:
            result += template[0]
        result += insertion_map[template] + template[1]
    start = result

freq_count = {char:start.count(char) for char in set(start)}

least = min(freq_count.values())
most = max(freq_count.values())
print("Most - Least common = {}".format(most - least))

This works fine mainly because the number of steps is relatively small and 2¹⁰ is only 1024. The first block is populating the insertion dictionary mapping the input chars to their respective output characters.

insertion_map = {}
for line in file_input[2:]:
    if line == "":
        continue
    template, insertion = line.split()[0], line.split()[-1]
    insertion_map[template] = insertion

The next block iterates through the steps; during the first step the first character of the string is added to the final result. Each step including the first, the insertion character is appended followed by the second character in the template.

start = file_input[0]
for i in range(10):
    result = ""
    for j in range(len(str(start)) - 1):
        template = start[j:j+2]
        if j == 0:
            result += template[0]
        result += insertion_map[template] + template[1]
    start = result

freq_count = {char:start.count(char) for char in set(start)}

least = min(freq_count.values())
most = max(freq_count.values())

Calculate the least and most frequent characters in the final string.

❯ python3 solution14.py input14
Most - Least common = 2937

Part 2

The resulting polymer isn't nearly strong enough to reinforce the submarine. You'll need to run more steps of the pair insertion process; a total of 40 steps should do it.

In the above example, the most common element is B (occurring 2192039569602 times) and the least common element is H (occurring 3849876073 times); subtracting these produces _2188189693529_.

Apply 40 steps of pair insertion to the polymer template and find the most and least common elements in the result. What do you get if you take the quantity of the most common element and subtract the quantity of the least common element?

Proposed solution: the previous solution will not work as we might encounter the heat death of the universe before the calculation is complete – or just run out of memory; however, similar to what I did in day 6, we can keep track of the individual states and their frequencies instead of the entire string; each single two-letter state will map to two individual two-letter states as output for a single step

Time complexity: O(n)

Space complexity: O(1)

The number of unique characters that can appear in the polymer has some impact on the space/time but it is by definition not a scaling factor within this problem so we consider this constant.

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

insertion_map = {}
for line in file_input[2:]:
    if line == "":
        continue
    template, insertion = line.split()[0], line.split()[-1]
    insertion_map[template] = insertion

start = file_input[0]
templates = {}
for j in range(len(start)-1):
    template = start[j:j+2]
    templates[template] = templates.get(template, 0) + 1

freq_count = {char:start.count(char) for char in set(start)}
for i in range(40):
    for template, freq in dict(templates).items():
        templates[template] -= freq
        insertion = insertion_map[template]
        first, second = template[0] + insertion, insertion + template[1]
        templates[first] = templates.get(first, 0) + freq
        templates[second] = templates.get(second, 0) + freq
        freq_count[insertion] = freq_count.get(insertion, 0) + freq

least = min(freq_count.values())
most = max(freq_count.values())
print("Most - Least common = {}".format(most - least))

Our new frequency count dictionary contains the mapping between any two adjacent characters (in the polymer) and their frequencies. Each step, these frequencies are negated in favor of their respective outputs. For example, if the string "AB" appeared 30 times in the current step for the polymer, "AB" maps to "C" for the insertion character, and no other strings produce "AB" this step, then our freq_count dictionary would contain the following:

{
  ...
  "AB": 0,
  "AC": 30,
  "CB": 30,
  ...
}

This solution is very similar to the other exponential growth problem in Advent of Code 2021 Day 6 – Lanternfish. Instead of keeping track of all copies of the objects, the number of distinct states are limited so it's more efficient to track these and their respective frequencies. This only works because each state has a single path to the next state.

❯ python3 solution14.py input14
Most - Least common = 3390034818249

Part 1

You reach another volcanically active part of the cave. It would be nice if you could do some kind of thermal imaging so you could tell ahead of time which caves are too hot to safely enter.

Fortunately, the submarine seems to be equipped with a thermal camera! When you activate it, you are greeted with:

Congratulations on your purchase! To activate this infrared thermal imaging
camera system, please enter the code found on page 1 of the manual.

Apparently, the Elves have never used this feature. To your surprise, you manage to find the manual; as you go to open it, page 1 falls out. It's a large sheet of transparent paper! The transparent paper is marked with random dots and includes instructions on how to fold it up (your puzzle input). For example:

6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0

fold along y=7
fold along x=5

The first section is a list of dots on the transparent paper. 0,0 represents the top-left coordinate. The first value, x, increases to the right. The second value, y, increases downward. So, the coordinate 3,0 is to the right of 0,0, and the coordinate 0,7 is below 0,0. The coordinates in this example form the following pattern, where # is a dot on the paper and . is an empty, unmarked position:

...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
...........
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........

Then, there is a list of fold instructions. Each instruction indicates a line on the transparent paper and wants you to fold the paper up (for horizontal y=... lines) or left (for vertical x=... lines). In this example, the first fold instruction is fold along y=7, which designates the line formed by all of the positions where y is 7 (marked here with -):

...#..#..#.
....#......
...........
#..........
...#....#.#
...........
...........
-----------
...........
...........
.#....#.##.
....#......
......#...#
#..........
#.#........

Because this is a horizontal line, fold the bottom half up. Some of the dots might end up overlapping after the fold is complete, but dots will never appear exactly on a fold line. The result of doing this fold looks like this:

#.##..#..#.
#...#......
......#...#
#...#......
.#.#..#.###
...........
...........

Now, only 17 dots are visible.

Notice, for example, the two dots in the bottom left corner before the transparent paper is folded; after the fold is complete, those dots appear in the top left corner (at 0,0 and 0,1). Because the paper is transparent, the dot just below them in the result (at 0,3) remains visible, as it can be seen through the transparent paper.

Also notice that some dots can end up overlapping; in this case, the dots merge together and become a single dot.

The second fold instruction is fold along x=5, which indicates this line:

#.##.|#..#.
#...#|.....
.....|#...#
#...#|.....
.#.#.|#.###
.....|.....
.....|.....

Because this is a vertical line, fold left:

#####
#...#
#...#
#...#
#####
.....
.....

The instructions made a square!

The transparent paper is pretty big, so for now, focus on just completing the first fold. After the first fold in the example above, _17_ dots are visible - dots that end up overlapping after the fold is completed count as a single dot.

How many dots are visible after completing just the first fold instruction on your transparent paper?

Proposed solution: represent dots as x, y tuples in a set and add + remove dot after translation to other side of the fold – e.g. for a fold on the y-axis, points with y greater than y fold will have a new position of (x, 2*(y-fold) - y) where (x, y) was the initial position

Time complexity: O(n) where n is the number of dots

Space complexity: O(1)

Assuming that the number of dots are distributed evenly on average across the two sides of the fold, we get O(n) time complexity since half of the dots will be removed from the set and their new coordinates will be added to the set. Addition/removal set operations are O(1) operations on average.

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

i = 0
line = file_input[i]
dots = set()
while line != "":
    x, y = [int(x) for x in line.split(",")]
    dots.add((x,y))
    i += 1
    line = file_input[i]

plane, num = file_input[i+1].split()[-1].split("=")
num = int(num)

for x, y in set(dots):
    if plane == "y":
        if y > num:
            dots.add((x,2*num-y))
            dots.remove((x,y))
    else:
        if x > num:
            dots.add((2*num-x,y))
            dots.remove((x,y))

print("Number Dots: {}".format(len(dots)))

❯ python3 solution13.py input13
Number Dots: 802

Part 2

Finish folding the transparent paper according to the instructions. The manual says the code is always eight capital letters.

What code do you use to activate the infrared thermal imaging camera system?

Proposed solution: same solution but iterating through all folds this time – also some extra code to print the dots

Time complexity: O(f log(n)) where f is the number of folds

Space complexity: O(1)

#!/usr/bin/env python3
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

i = 0
line = file_input[i]
dots = set()
while line != "":
    x, y = [int(x) for x in line.split(",")]
    dots.add((x,y))
    i += 1
    line = file_input[i]

for i in range(i+1, len(file_input)):
    if file_input[i] == "":
        continue
    plane, num = file_input[i].split()[-1].split("=")
    num = int(num)
    for x, y in set(dots):
        if plane == "y":
            if y > num:
                dots.add((x,2*num-y))
                dots.remove((x,y))
        else:
            if x > num:
                dots.add((2*num-x,y))
                dots.remove((x,y))

print("Number Dots: {}".format(len(dots)))

for y in range(10):
    result = ""
    for x in range(50):
        if (x, y) in dots:
            result += "#"
        else:
            result += "."
    print(result)

Solution is now O(f log(n)). We can expect that some fraction of the dots are overlapping on every fold, reducing the total number of dots. Every fold will split the search space roughly in half making this fraction more likely to be larger after every fold.

❯ python3 solution13.py input13
Number Dots: 103
###..#..#.#..#.####.####..##..#..#.###............
#..#.#.#..#..#.#.......#.#..#.#..#.#..#...........
#..#.##...####.###....#..#....#..#.###............
###..#.#..#..#.#.....#...#.##.#..#.#..#...........
#.#..#.#..#..#.#....#....#..#.#..#.#..#...........
#..#.#..#.#..#.#....####..###..##..###............
..................................................
..................................................
..................................................
..................................................

Part 1

With your submarine's subterranean subsystems subsisting suboptimally, the only way you're getting out of this cave anytime soon is by finding a path yourself. Not just a path - the only way to know if you've found the best path is to find all of them.

Fortunately, the sensors are still mostly working, and so you build a rough map of the remaining caves (your puzzle input). For example:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

This is a list of how all of the caves are connected. You start in the cave named start, and your destination is the cave named end. An entry like b-d means that cave b is connected to cave d - that is, you can move between them.

So, the above cave system looks roughly like this:

    start
    /   \
c--A-----b--d
    \   /
     end

Your goal is to find the number of distinct paths that start at start, end at end, and don't visit small caves more than once. There are two types of caves: big caves (written in uppercase, like A) and small caves (written in lowercase, like b). It would be a waste of time to visit any small cave more than once, but big caves are large enough that it might be worth visiting them multiple times. So, all paths you find should visit small caves at most once, and can visit big caves any number of times.

Given these rules, there are _10_ paths through this example cave system:

start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end

(Each line in the above list corresponds to a single path; the caves visited by that path are listed in the order they are visited and separated by commas.)

Note that in this cave system, cave d is never visited by any path: to do so, cave b would need to be visited twice (once on the way to cave d and a second time when returning from cave d), and since cave b is small, this is not allowed.

Here is a slightly larger example:

dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc

The 19 paths through it are as follows:

start,HN,dc,HN,end
start,HN,dc,HN,kj,HN,end
start,HN,dc,end
start,HN,dc,kj,HN,end
start,HN,end
start,HN,kj,HN,dc,HN,end
start,HN,kj,HN,dc,end
start,HN,kj,HN,end
start,HN,kj,dc,HN,end
start,HN,kj,dc,end
start,dc,HN,end
start,dc,HN,kj,HN,end
start,dc,end
start,dc,kj,HN,end
start,kj,HN,dc,HN,end
start,kj,HN,dc,end
start,kj,HN,end
start,kj,dc,HN,end
start,kj,dc,end

Finally, this even larger example has 226 paths through it:

fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW

How many paths through this cave system are there that visit small caves at most once?

Proposed solution: since this is a graph with only the unique name of the nodes as attributes we can represent this as a dictionary of node names to a list of connections; then breadth-first search while using memoization to keep track of unique paths until running out of unique paths

Time complexity: O(E + V) where E is the number of edges and V is the number of vertices

Space complexity: O(N) where N is the number of unique valid paths from start to end

#!/usr/bin/env python3
from collections import defaultdict, deque
import sys

if len(sys.argv) != 2:
    print("Usage: {} <input file>".format(sys.argv[0]))
    sys.exit(1)

file_input = open(sys.argv[1], "r").read().strip().split("\n")

connections = defaultdict(list)
for line in file_input:
    first, second = line.split("-")
    connections[first].append(second)
    connections[second].append(first)

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()
    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if "{},".format(move) not in check or move.isupper():
            queue.append("{},{}".format(check, move))

print("Total Unique Paths: {}".format(len(paths)))

Let's break this down. The first part is just taking each line and populating the graph being represented by a dictionary. Each key is an individual node's name e.g. "start", "dc", "end", etc. And the corresponding values are lists of connections to other nodes.

connections = defaultdict(list)
for line in file_input:
    first, second = line.split("-")
    connections[first].append(second)
    connections[second].append(first)

Next, make a data structure for the final unique paths (already visited) and a queue for unique paths being traversed. We can populate the queue beginning with start.

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()

For each working path in the queue, we are representing them by the string delimited by commas (exactly like they are represented in the description of the problem). If the last visited node is "end" then it's a valid path and we can add it to the unique paths. Otherwise, iterate through the possible connections to the last node. Valid moves for part 1 are those that are not already in the working path or the connection is back to a big cave (uppercase).

    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if "{},".format(move) not in check or move.isupper():
            queue.append("{},{}".format(check, move))

Our final paths set contains all unique paths represented as comma-delimited strings.

❯ python3 solution12.py example
Total Unique Paths: 10
❯ python3 solution12.py example2
Total Unique Paths: 19
❯ python3 solution12.py example3
Total Unique Paths: 226
❯ python3 solution12.py input12
Total Unique Paths: 5104

Part 2

After reviewing the available paths, you realize you might have time to visit a single small cave twice. Specifically, big caves can be visited any number of times, a single small cave can be visited at most twice, and the remaining small caves can be visited at most once. However, the caves named start and end can only be visited exactly once each: once you leave the start cave, you may not return to it, and once you reach the end cave, the path must end immediately.

Now, the 36 possible paths through the first example above are:

start,A,b,A,b,A,c,A,end
start,A,b,A,b,A,end
start,A,b,A,b,end
start,A,b,A,c,A,b,A,end
start,A,b,A,c,A,b,end
start,A,b,A,c,A,c,A,end
start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,d,b,A,c,A,end
start,A,b,d,b,A,end
start,A,b,d,b,end
start,A,b,end
start,A,c,A,b,A,b,A,end
start,A,c,A,b,A,b,end
start,A,c,A,b,A,c,A,end
start,A,c,A,b,A,end
start,A,c,A,b,d,b,A,end
start,A,c,A,b,d,b,end
start,A,c,A,b,end
start,A,c,A,c,A,b,A,end
start,A,c,A,c,A,b,end
start,A,c,A,c,A,end
start,A,c,A,end
start,A,end
start,b,A,b,A,c,A,end
start,b,A,b,A,end
start,b,A,b,end
start,b,A,c,A,b,A,end
start,b,A,c,A,b,end
start,b,A,c,A,c,A,end
start,b,A,c,A,end
start,b,A,end
start,b,d,b,A,c,A,end
start,b,d,b,A,end
start,b,d,b,end
start,b,end

The slightly larger example above now has 103 paths through it, and the even larger example now has 3509 paths through it.

Given these new rules, how many paths through this cave system are there?

Proposed solution: the same solution except the rules for a valid move have changed slightly; I abstract this into a function to check if another small cave has already been moved to twice in the current path being checked

Time complexity: O(E + V)

Space complexity: O(N)

def valid_path(check, move):
    if move == "start":
        return False
    double_small = None
    frequencies = {name:check.count("{}".format(name)) for name in check.split(",")}
    for name, frequency in frequencies.items():
        if frequency == 2 and name.islower():
            double_small = name
    if double_small is not None and (double_small == move or move in frequencies):
        return False
    return True

paths = set()
queue = deque()
queue.append("start")
while len(queue) != 0:
    check = queue.popleft()
    last_node = check.split(",")[-1]
    if last_node == "end":
        paths.add(check)
        continue
    for move in connections[last_node]:
        if valid_path(check, move) or move.isupper():
            queue.append("{},{}".format(check, move))

print("Total Unique Paths: {}".format(len(paths)))

There are optimizations to be made here but the results speak for themselves.

❯ python3 solution12.py example
Total Unique Paths: 36
❯ python3 solution12.py example2
Total Unique Paths: 103
❯ python3 solution12.py example3
Total Unique Paths: 3509
❯ time python3 solution12.py input12
Total Unique Paths: 149220
python3 solution12.py input12  6.79s user 0.06s system 98% cpu 6.950 total