Plutonian Pebbles: Advent of Code 2024 (Day 11)

Today’s challenge takes us to an ancient civilization on Pluto, where strange stones defy the laws of physics. Each stone is engraved with a number that changes every time you blink. Our goal is to predict the state of these stones after a given number of blinks.

Plutonian Pebbles

Check out the story here and code on my GitHub.

Processing the data

The puzzle input is a string of numbers separated by spaces. Each number represents a stone. To handle the input, we store the stones in a map, which keeps track of the frequency of each unique stone. This is useful because the stones can multiply and repeat as they change.

map<string, long int> stones;

void loadData() {
  string line = "";
  ifstream ip("ip.txt");
  if(ip.is_open()) {
    while(getline(ip, line, ' ')) {
      stones[line]++;
    }
    ip.close();
  }
}

This function reads the input file, splitting it by spaces, and updates the map to count occurrences of each stone.

Puzzle

The stones transform based on these rules:

• If the stone is engraved with 0, it transforms into a stone engraved with 1
• If the stone has an even number of digits, it splits into two stones. The first half of the digits becomes one stone, and the second half becomes the other. Remove if there are any leading zeroes.
• For all other cases, the stone transforms into a single stone with its number multiplied by 2024

The order of stones doesn’t matter for the final result, so we focus only on the count of each type of stone.

We can iterate through the map of stones, apply the transformation rules, and build a new map of stones. Once all stones are processed, we can replace the old map with the new one.

void getTransformation() {
    map<string, long int> newStones;
    for(auto& [stone, number] : stones) {
        if(stol(stone) == 0) {
            newStones["1"] += number;
        } else if(stone.size() % 2 == 0) {
            newStones[stone.substr(0, stone.size() / 2)] += number;
            newStones[to_string(stol(stone.substr(stone.size() / 2, stone.size())))] += number;
        } else {
            newStones[to_string(stol(stone) * 2024)] += number;
        }
    }

    stones = newStones;
}

Part 1: After 25 Blinks

To solve Part 1, we apply the transformations 25 times and count the total number of stones at the end.

size_t BLINKS = 25;

int main() {
    loadData();

    for(int i = 0; i < BLINKS; i++) {
        getTransformation();
    }

    long long int totalStones = 0;
    for(auto& [stone, number] : stones) {
        totalStones += number;
    }

    cout << totalStones << endl;

    return 0;
}

This code performs the transformations 25 times, and calculates the total number of stones by summing their counts from the map.

Part 2: After 75 Blinks

Part 2 extends the challenge by requiring the state of the stones after 75 blinks. The only change is increasing the number of transformations to 75.

size_t BLINKS = 75;

int main() {
    loadData();

    for (int i = 0; i < BLINKS; i++) {
        getTransformation();
    }

    long long int totalStones = 0;
    for (auto& [stone, count] : stones) {
        totalStones += count;
    }

    cout << totalStones << endl;

    return 0;
}

The logic remains the same, but the output for 75 blinks demonstrates the efficiency of using a map to handle exponential growth in stone transformations.

Conclusion

Initially, I used a simple vector-based approach that preserved the order of stones. While this worked for 25 blinks, it couldn’t handle the massive number of stones generated after 75 blinks. Switching to a map-based solution significantly reduced the number of transformations needed, making the program efficient enough to handle the challenge.