[Day 8] Haunted Wasteland // Advent of Code 2023 (Python)

Haunted Wasteland (via DALL-E 3)

Advent of Code
You’re still riding a camel across Desert Island when you spot a sandstorm quickly approaching. When you turn to warn…adventofcode.com

---

Part One

You’re still riding a camel across Desert Island when you spot a sandstorm quickly approaching. When you turn to warn the Elf, she disappears before your eyes! To be fair, she had just finished warning you about ghosts a few minutes ago.

One of the camel’s pouches is labeled “maps” — sure enough, it’s full of documents (your puzzle input) about how to navigate the desert. At least, you’re pretty sure that’s what they are; one of the documents contains a list of left/right instructions, and the rest of the documents seem to describe some kind of network of labeled nodes.

It seems like you’re meant to use the left/right instructions to navigate the network. Perhaps if you have the camel follow the same instructions, you can escape the haunted wasteland!

After examining the maps for a bit, two nodes stick out: AAA and ZZZ. You feel like AAA is where you are now, and you have to follow the left/right instructions until you reach ZZZ.

This format defines each node of the network individually. For example:

RL

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

Starting with AAA, you need to look up the next element based on the next left/right instruction in your input. In this example, start with AAA and go right (R) by choosing the right element of AAA, CCC. Then, L means to choose the left element of CCC, ZZZ. By following the left/right instructions, you reach ZZZ in 2 steps.

Of course, you might not find ZZZ right away. If you run out of left/right instructions, repeat the whole sequence of instructions as necessary: RLreally means RLRLRLRLRLRLRLRL... and so on. For example, here is a situation that takes 6 steps to reach ZZZ:

LLR

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

Starting at AAA, follow the left/right instructions. How many steps are required to reach ZZZ?

---

Ah! The good old map and input problem. It seems like we are given a list of maps which is a list of left and right directions and then there is a network of labeled nodes which looks like an adjacency list where each node points to the left or right node.

In first glance it looks like a binary tree but not really as it can point back and forth to any node, so it’s more or less like a graph where you can either go left or go right and then sometimes you can jump around.

Let’s see the base case example and try to visualize it:

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

with direction of RL i.e. -> Right -> Left …. -> Right -> Left.

We can draw this like this and we can see the path is 2 steps:

• AAA[R] → CCC[L] → ZZZ

💡 But the caveat is that we have to reach to ZZZ using the given directions (in loop) only and that can be a little difficult when the puzzle input will be quite large.

Let’s start with creating with both the test cases in our code:

As always, this is the best way I know to start looking at the problem. The absolute first step should be to thread the problem to a solution and then rest of optimizations should follow.

So, now let’s use some parsing magic to make our puzzle input more traversable! We can directly parse the directions as it is the first line, for network, we can just tranform it into a python dict: {NODE: (LEFT_NODE, RIGHT_NODE} format.

Playing a bit with ipython3 as always:

Converting to proper code:

💭 The traversal code looks pretty straight forward IMO as once we have translated the puzzle_input to a dict like structure, all we need to do is to start with AAA and then based on direction, just keep moving ahead while counting the steps and break out of the loop once my node == ZZZ !

Here’s a quick dirty implementation of the logic:

dir_idx % len(directions) take care of looping back once we run out of directions

Let’s run it against both the base test cases..!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_8/haunted_wasteland.py"
Test Case 1 - Passed!
Test Case 2 - Passed!

Looks good, right? Let’s take the puzzle_input and try to run our code on that?

And let’s run it…and we get a number, let’s see if that is the correct answer?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_8/haunted_wasteland.py"
Test Case 1 - Passed!
Test Case 2 - Passed!
Part 1: XXXXXXX

Woah! First try 🥲

This is usually a rare occasion to get something right on first try, but then again, years of practise! Let’s pimp up our code to be pythonic:

# Day 8: Haunted Wasteland

# --- Part One ---

class DesertNavigator:
    START_LOCATION = "AAA"
    DESTINATION = "ZZZ"

    def __init__(self):
        self.navigation_map = {}
        self.navigation_instructions = []

    def add_location(self, location, left_choice, right_choice):
        self.navigation_map[location] = (left_choice, right_choice)

    def load_navigation_data(self, navigation_data):
        instructions, location_data = navigation_data.strip().split("\n\n")
        self.navigation_instructions = [0 if direction == 'L' else 1 for direction in instructions]

        for data in location_data.split("\n"):
            location, choices = data.split(" = ")
            left, right = choices.strip("()").split(", ")
            self.add_location(location, left, right)

    def navigate_desert(self):
        current_location, steps, instruction_idx = self.START_LOCATION, 0, 0

        while current_location != self.DESTINATION:
            direction = self.navigation_instructions[instruction_idx % len(self.navigation_instructions)]
            current_location = self.navigation_map[current_location][direction]
            steps += 1
            instruction_idx += 1

        return steps

def test_desert_navigation():
    test_cases = [
        ("RL\n\nAAA = (BBB, CCC)\nBBB = (DDD, EEE)\nCCC = (ZZZ, GGG)\nDDD = (DDD, DDD)\nEEE = (EEE, EEE)\nGGG = (GGG, GGG)\nZZZ = (ZZZ, ZZZ)", 2),
        ("LLR\n\nAAA = (BBB, BBB)\nBBB = (AAA, ZZZ)\nZZZ = (ZZZ, ZZZ)", 6)
    ]

    for navigation_data, expected_steps in test_cases:
        navigator = DesertNavigator()
        navigator.load_navigation_data(navigation_data)
        assert navigator.navigate_desert() == expected_steps, f"Test failed with input: {navigation_data}"

    print("All tests passed!")

def navigate_through_desert():
    with open("day_8/input.txt") as file:
        navigation_data = file.read()

    navigator = DesertNavigator()
    navigator.load_navigation_data(navigation_data)
    steps = navigator.navigate_desert()
    print(f"Steps to reach destination: {steps}")

if __name__ == "__main__":
    test_desert_navigation()
    navigate_through_desert()

Now it looks good! ✨

---

Part Two

The sandstorm is upon you and you aren’t any closer to escaping the wasteland. You had the camel follow the instructions, but you’ve barely left your starting position. It’s going to take significantly more steps to escape!

What if the map isn’t for people — what if the map is for ghosts? Are ghosts even bound by the laws of spacetime? Only one way to find out.

After examining the maps a bit longer, your attention is drawn to a curious fact: the number of nodes with names ending in A is equal to the number ending in Z! If you were a ghost, you’d probably just start at every node that ends with A and follow all of the paths at the same time until they all simultaneously end up at nodes that end with Z.

For example:

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)

Here, there are two starting nodes, 11A and 22A (because they both end with A). As you follow each left/right instruction, use that instruction to simultaneously navigate away from both nodes you’re currently on. Repeat this process until all of the nodes you’re currently on end with Z. (If only some of the nodes you’re on end with Z, they act like any other node and you continue as normal.) In this example, you would proceed as follows:

Step 0: You are at 11A and 22A.

Step 1: You choose all of the left paths, leading you to 11B and 22B.

Step 2: You choose all of the right paths, leading you to 11Z and 22C.

Step 3: You choose all of the left paths, leading you to 11B and 22Z.

Step 4: You choose all of the right paths, leading you to 11Z and 22B.

Step 5: You choose all of the left paths, leading you to 11B and 22C.

Step 6: You choose all of the right paths, leading you to 11Z and 22Z.

So, in this example, you end up entirely on nodes that end in Z after 6steps.

Simultaneously start on every node that ends with A. How many steps does it take before you’re only on nodes that end with Z?

---

Now this is a curve ball! Instead of just following a single path by starting with AAA we now have to follow all the paths from nodes that end with **A till all of these nodes reach nodes ending with **Z in same number of steps!

💡This is fun! Well, a quick dirty approach I can think off is to just maintain a list of my starting nodes **A as paths and then for each steps, navigate into a direction and update all nodes and then check if all nodes looks like **Z if yes, break, else keep going!

Let’s write some code to navigate through desert as ghosts!

Was able to run through all the eligible nodes with some debugging!

Let’s see if we are able to run through our base test case!

And…yes!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_8/haunted_wasteland.py"
test_navigate_desert_as_ghosts passed!

Let’s now run this against our puzzle input?

.
.
.

⏳

Well… 2 minutes later, it’s still going on! I should have taken the warning in question much more seriously:

It’s going to take significantly more steps to escape!

Let’s break out of our code and see how many current_nodes are we talking about in puzzle_input :

Looks like it’s only 6 nodes, but seems like a lot of traversal is needed to ensure all the nodes look like **Z.

Let’s add some logging to see how quickly we are iterating through as we are using python dict and to get values for 6 nodes, it should be pretty quick?

Oh well…this is going to be a long answer!

Let’s see if we can find any way to speed this up?

.

<wasted 2 hours here>

.

💡After thorough analyis of the input data and current_nodes I was able to find cycles in each of the node.

💭 So, to effectively track these cycles and find the looping points, we can try monitoring each ghost’s journey through the network. The key idea here is to recognize that once a ghost reaches a ‘Z’ node, it will eventually loop back to a ‘Z’ node again, following the given instructions. This repetition forms a cycle, and the number of steps in each cycle can vary depending on the starting node and the network’s structure.

To implement this, we will need two lists: first_z_steps and cycle_lengths to record for each node:

• the first ‘Z’ node it reaches the step count when it reaches this node for the first time.
• cycle_length, on the other hand, captures the number of steps between the first and second time each ghost reaches a ‘Z’ node, effectively measuring the length of each cycle.

This process can be repeated for each ghost, eventually providing a comprehensive view of the cycles in the network.

The final piece of the puzzle was to determine the earliest step at which all these cycles align, meaning every ghost would be at a ‘Z’ node simultaneously.

💡The solution to this lies in finding the least common multiple (LCM) of all the cycle lengths recorded in loop_list. The LCM represents the smallest number of steps after which all individual cycles coincide, aligning every ghost at a ‘Z’ node simultaneously.

Let’s run the code against the base test case to validate along with some logging:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_8/haunted_wasteland.py"
Current nodes: ['11A', '22A'] Steps: 0
Current nodes: ['11B', '22B'] Steps: 1
Current nodes: ['11Z', '22C'] Steps: 2
Current nodes: ['11B', '22Z'] Steps: 3
Current nodes: ['11Z', '22B'] Steps: 4
Current nodes: ['11B', '22C'] Steps: 5
Current nodes: ['11Z', '22Z'] Steps: 6
test_navigate_desert_as_ghosts passed!

Now let’s do it for the input.txt ? 🤞

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_8/haunted_wasteland.py"
Steps to reach destination as ghosts: xxxxxxx

[Done] exited with code=0 in 0.094 seconds

Look at that! Just 0.094 seconds 💀

Let’s put this number of steps in our answer box and …..

Phew!

Here’s our final pythonic code:

# Day 8: Haunted Wasteland

# --- Part One ---
import math

class DesertNavigator:
    START_LOCATION = "AAA"
    DESTINATION = "ZZZ"

    def __init__(self):
        self.navigation_map = {}
        self.navigation_instructions = []

    def add_location(self, location, left_choice, right_choice):
        self.navigation_map[location] = (left_choice, right_choice)

    def load_navigation_data(self, navigation_data):
        instructions, location_data = navigation_data.strip().split("\n\n")
        self.navigation_instructions = [
            0 if direction == "L" else 1 for direction in instructions
        ]

        for data in location_data.split("\n"):
            location, choices = data.split(" = ")
            left, right = choices.strip("()").split(", ")
            self.add_location(location, left, right)

    # for part 1
    def navigate_desert(self):
        current_location, steps, instruction_idx = self.START_LOCATION, 0, 0

        while current_location != self.DESTINATION:
            direction = self.navigation_instructions[
                instruction_idx % len(self.navigation_instructions)
            ]
            current_location = self.navigation_map[current_location][direction]
            steps += 1
            instruction_idx += 1

        return steps

    # for part 2
    def navigate_desert_as_ghosts(self):
        current_nodes, steps, instruction_idx = [], 0, 0

        # init current nodes with all nodes with A as their last letter
        for node in self.navigation_map.keys():
            if node[-1] == "A":
                current_nodes.append(node)

        while not self.have_reached_destination(current_nodes):
            print(f"Current nodes: {current_nodes}\tSteps: {steps}")
            next_nodes = []
            direction = self.navigation_instructions[
                instruction_idx % len(self.navigation_instructions)
            ]
            for node in current_nodes:
                next_nodes.append(self.navigation_map[node][direction])

            current_nodes = next_nodes
            steps += 1
            instruction_idx += 1

        print(f"Current nodes: {current_nodes}\tSteps: {steps}")
        return steps

    # check if all nodes have Z as last letter
    def have_reached_destination(self, current_nodes):
        for node in current_nodes:
            if node[-1] != "Z":
                return False

        return True
    
    # part 2 - optimised
    def navigate_through_desert_as_ghosts_lcm(self):
        current_nodes = [node for node in self.navigation_map if node.endswith('A')]
        first_z_steps = [""] * (len(current_nodes) * 2)
        cycle_lengths = [""] * len(current_nodes)
        steps = 0
        max_steps = 1

        cycles_complete = False
        instruction_length = len(self.navigation_instructions)

        while not cycles_complete:
            direction = self.navigation_instructions[steps % instruction_length]
            steps += 1
            for index, node in enumerate(current_nodes):
                if node.endswith('Z'):
                    if first_z_steps[index] != "" and cycle_lengths[index] == "":
                        cycle_lengths[index] = steps - first_z_steps[index + len(current_nodes)]
                    if first_z_steps[index] == "":
                        first_z_steps[index] = node
                        first_z_steps[index + len(current_nodes)] = steps
                
                current_nodes[index] = self.navigation_map[node][direction]

            # Check if all cycles are complete
            cycles_complete = all(cycle_length != "" for cycle_length in cycle_lengths)

        for cycle_length in cycle_lengths:
            max_steps = math.lcm(cycle_length, max_steps)

        return max_steps

def test_navigate_desert():
    test_cases = [
        (
            "RL\n\nAAA = (BBB, CCC)\nBBB = (DDD, EEE)\nCCC = (ZZZ, GGG)\nDDD = (DDD, DDD)\nEEE = (EEE, EEE)\nGGG = (GGG, GGG)\nZZZ = (ZZZ, ZZZ)",
            2,
        ),
        ("LLR\n\nAAA = (BBB, BBB)\nBBB = (AAA, ZZZ)\nZZZ = (ZZZ, ZZZ)", 6),
    ]

    for navigation_data, expected_steps in test_cases:
        navigator = DesertNavigator()
        navigator.load_navigation_data(navigation_data)
        assert (
            navigator.navigate_desert() == expected_steps
        ), f"Test failed with input: {navigation_data}"

    print("test_navigate_desert passed!")

def test_navigate_desert_as_ghosts():
    navigation_data = """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)"""
    navigator = DesertNavigator()
    navigator.load_navigation_data(navigation_data)
    # number_of_steps = navigator.navigate_desert_as_ghosts()
    number_of_steps = navigator.navigate_through_desert_as_ghosts_lcm()
    assert number_of_steps == 6, f"Expected 6 steps, got {number_of_steps}"
    print("test_navigate_desert_as_ghosts passed!")

# part 1
def navigate_through_desert():
    with open("day_8/input.txt") as file:
        navigation_data = file.read()

    navigator = DesertNavigator()
    navigator.load_navigation_data(navigation_data)
    steps = navigator.navigate_desert()
    print(f"Steps to reach destination: {steps}")

# part 2
def navigate_through_desert_as_ghosts():
    with open("day_8/input.txt") as file:
        navigation_data = file.read()

    navigator = DesertNavigator()
    navigator.load_navigation_data(navigation_data)
    # steps = navigator.navigate_desert_as_ghosts()
    steps = navigator.navigate_through_desert_as_ghosts_lcm()
    print(f"Steps to reach destination as ghosts: {steps}")

if __name__ == "__main__":
    test_navigate_desert()
    navigate_through_desert()

    test_navigate_desert_as_ghosts()
    navigate_through_desert_as_ghosts()

---

Part 2 of the question was an elegenat example of how we can combine the cyclic nature of the problem with a mathematical solution to find the synchronization point.

It underscores the importance of understanding the underlying patterns and structures in a complex problem and demonstrates how a seemingly daunting task can be tackled with the right strategy and a bit of creative thinking!

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: This is my live attempt to solve all 25 problems of…
This is my live attempt to solve all 25 problems of Advent of Code 2023 with Python! - GitHub …github.com