🎄 Advent of Code 2'023 - Day 08

Published data: 8 December 2023

Day 08: Haunted Wasteland

* Cf. aoc. d. viii xxiii

Abridged Problem Description: Picture yourself lost in a haunted wasteland, with only a map of cryptic instructions and a tangled network of nodes to guide you. Your ultimate goal? To escape this spooky realm by reaching the node labeled ZZZ, starting from the ominous AAA.

Parsing The Input

I’ve decided to use a map<string, pair<string, string>> to store the graph. The key is the node’s name, p.first represents the left node and p.second represents the right node.

map<string, pair<string, string>> M;

To populate the map, we just need to parse the input. The input looks like this:

for (int i = 2; i < lines.size(); ++i) {
    string key = lines[i].substr(0, 3);

    M[key] = {lines[i].substr(7, 3), lines[i].substr(12, 3)};
}

Bene Nota: I’m ignoring the first line because that is our instructions.

string instructions = lines[0];

PARS I

The first part of this challenge is straightforward – we just need to keep following the instructions until we reach ZZZ. It’s like being trapped in a labyrinth where you only have one direction to go – forward.

int64 ans = 0;

const string NEEDLE = "ZZZ";
string haystack = "AAA";

while (haystack != NEEDLE) {
    for (const char &c: instructions) {
        if (c == 'R') haystack = M[haystack].second;
        else haystack = M[haystack].first;
        ans++;
    }

    if (haystack == NEEDLE) break;
}

That was an easy star 🌟

PARS II

Abridged Problem Description: Now, for the real challenge – We should find the number of steps required to make sure every node **A ends up in the **Z position simultaneously.

Part two is where things get spooky. As you might have guessed, the second part of the challenge is a bit more tricky. The same algorithm won’t work here, because it would take too long to finish. We need to find a way to optimize it.

First, let’s make sure to find all nodes that follow the **A pattern. We could do it while we’re parsing the input. I’ve decided to store them in a vector<string> ans.

string instructions = lines[0];

map<string, pair<string, string>> M;

vector<string> ans;
for (int i = 2; i < lines.size(); ++i) {
    string key = lines[i].substr(0, 3);

    if (key[2] == 'A') ans.push_back(key);
    M[key] = {lines[i].substr(7, 3), lines[i].substr(12, 3)};
}

With that in place, we should calculate the cycles for each of these nodes.

* using int64 = long long;

vector<int64> step_counts;

for (const auto &k: ans) {
    string current = k;
    while (true) {
        for (const char &c: instructions) {
            if (c == 'R') current = M[current].second;
            else current = M[current].first;
            steps++;
        }

        if (current.ends_with('Z')) {
            step_counts.push_back(steps);
            steps = 0;
            break;
        }
    }
}

Now we just need to find the least common multiple of all these cycles. I’ve used the gcd function to help with the calculation.

int64 lcm = step_counts[0];
for (int i = 1; i < step_counts.size(); ++i) {
    lcm = lcm * step_counts[i] / gcd(lcm, step_counts[i]);
}

return lcm;

Awesome! We solved the spooky puzzle! 🌟🌟