Plutonian Pebbles

Advent of Code 2024, Day 11: Pebble Proliferation

Part 1: Mapping Pebble Cycles

This problem involves tracking the evolution of pebbles through a series of transformations. The initial approach, simulating 25 iterations, proved feasible for Part 1. However, the exponential growth of pebbles suggests a different strategy will be needed for Part 2, where far more iterations are required. The key is to understand the pebble transformation rules and how they affect the overall pebble count.

Pebble Transformation Rules:

Rule 1: A pebble with the value 0 transforms into a pebble with the value 1.

Rule 2: Even-length numbered pebbles split into two new pebbles, each half the original number's length.

Rule 3: Odd-length numbered pebbles multiply their value by 2024.

Implementation and Testing:

The blink() function implements the transformation rules:

function blink(num) {
    let str = String(num);
    if (num === 0) {
        return 1;
    } else if (str.length % 2 === 0) {
        return [+(str.slice(0, str.length / 2)), +(str.slice(str.length / 2))];
    } else {
        return num * 2024;
    }
}

Note the use of to convert string slices back to numbers. Initial testing with example inputs confirmed the function's accuracy. Iterative processing using flatMap efficiently handles the splitting of pebbles. The solution successfully processed 25 iterations for the puzzle input, yielding the correct answer.

Part 2: Conquering Exponential Growth

Part 2 presents a significant computational challenge due to the rapid increase in the number of pebbles. My initial approach of direct simulation proved computationally infeasible. The number of pebbles explodes beyond manageable limits after only a few dozen iterations.

Exploring Optimization Strategies:

To address this, I investigated several strategies:

1. Cycle Detection: I explored the possibility of detecting repeating patterns in pebble values to avoid redundant computations. While some numbers exhibited limited, finite sets of generated values, this pattern wasn't universally applicable, rendering this approach insufficient.

2. Pebble Catalog: I attempted to create a catalog of pebble values and their subsequent transformations. The goal was to reuse pre-computed results to speed up the process. While the catalog did reduce computation for some pebbles, the overall improvement was not significant enough to handle the scale of Part 2.

Roadblock and Reflection:

Despite exploring these optimization techniques, I was unable to find a solution that efficiently handles the exponential growth of pebbles in Part 2. The computational complexity of the problem, combined with the lack of easily identifiable patterns, proved insurmountable within the constraints of my current approach. The challenge highlighted the importance of considering computational complexity when designing algorithms for problems with potentially explosive growth. While I successfully solved Part 1, Part 2 remains unsolved.

The above is the detailed content of Plutonian Pebbles. For more information, please follow other related articles on the PHP Chinese website!