Link to Advent of Code day 8

Still riding your camel in the desert, the Elf you were with disappeared. You need to use the maps she left to figure how to navigate in the desert.

Part 1

Rules

The input of this day consists of 2 parts: the first line is a series of instructions being left or right.

The second part is a list of node, have a left and a right connection to another node:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

We need to start from AAA, and iter on each instruction (looping back if come to the end of them) until we reach ZZZ.

For example, with the following input, we would reach ZZZ in 6 steps.

LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)

Code

I chose a naive data structure: a string for the instructions, and a dictionary for the nodes:

def parse_input(input_file: str) -> tuple[str, dict]:
    with open(input_file) as f:
        split_file = f.read().split("\n\n")
        instructions = split_file[0].strip()
        nodes = dict()
        for line in split_file[1].splitlines():
            key, connections = line.split(" = ")
            left, right = connections[1:-1].split(", ")
            nodes[key] = (left, right)
    return instructions, nodes

Then I use itertools.cycle to iterate on the instructions as long as required, with a basic logic to compute the steps.

from itertools import cycle


def part_one(input_file: str) -> int:
    instructions, nodes = parse_input(input_file)
    instructions = cycle(instructions)
    current_node = "AAA"
    counter = 0
    while current_node != "ZZZ":
        current_instruction = next(instructions)
        if current_instruction == "L":
            current_node = nodes[current_node][0]
        else:
            current_node = nodes[current_node][1]
        counter += 1
    return counter

I know it won't be enough for part 2, were I'm betting we'll have some repeating pattern to detect, but it allows me to get part 1 out of the way quickly.

Part 2

Rules

As expected, the part 2 is more complex.

We now need to start from all nodes which ends with A, and simultaneously use the instructions for each node. We'll stop when all of the starting nodes ends on a node ending with Z as the same time.

LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)

With this example, there are two starting nodes: 11A and 22A. They would both end up on nodes ending with Z after 6 steps.

Code

Turns out we won't have to simulate everything at the same time: instead, we can count the steps for each starting node until it ends on a node ending in Z. Once we have all these steps, we can just find the lowest common multiple for them. It will be the minimum amount of steps for them to converge.

The only tricky part is if a number can stop on multiple nodes ending with Z. I'll just cross my fingers on this one, and start with this implementation.

Let's start by rewriting the part 1 so it can handle part 2. We extract the part which counts the steps from a node to another in a function, and we replace the stop condition by a regex pattern:

def part_one(input_file: str) -> int:
    instructions, nodes = parse_input(input_file)
    return get_steps_until_z(instructions, nodes, "AAA", r"^ZZZ$")


def get_steps_until_z(
    instructions: str, nodes: dict, node: str, end_pattern: str
) -> int:
    instructions = cycle(instructions)
    counter = 0
    while not re.search(end_pattern, node):
        current_instruction = next(instructions)
        if current_instruction == "L":
            node = nodes[node][0]
        else:
            node = nodes[node][1]
        counter += 1
    return counter

Once done, I found a snippet online to get the least common multiple for a list of numbers:

from functools import reduce
from math import gcd

def lcm_of_list(numbers: list[int]) -> int:
    return reduce((lambda x, y: int(x * y / gcd(x, y))), numbers)

We can now write the core logic of the part 2:

def part_two(input_file: str) -> int:
    instructions, nodes = parse_input(input_file)
    steps_until_z_list = []
    for node in nodes.keys():
        if node.endswith("A"):
            steps_until_z = get_steps_until_z(instructions, nodes, node, r"Z$")
            steps_until_z_list.append(steps_until_z)
    return lcm_of_list(steps_until_z_list)

And the day 8 is now done !

The full code is available here