-
How naive? When I saw the sample output was 2 trillion I didn't even bother trying mine (a list of chars). It would've required 10 TB of memory
frankenbike-
The hint was in "semi-naive".
I initially solved part 2 with a meet-in-the-middle solution.
My part1 could do up to 10 steps easily, and trying it with 20 steps showed it would complete in under a second.
So I computed the final letter frequencies of each of the 100 possible input pairs (my final input/rules had 10 unique elements) when taken to step 20 (since each of those would take under a second), and then the step 20 output of my proper input and then worked out the step 40 frequencies from the combination of those.
My guess for part 2 was going to be something like "What is the difference in frequencies between the 1,000,000,000th and 1,000,000,001st elements in the output after 40 steps?" which would have required a lot different jiggery to get to than my eventual solution for the day.
Greenbank
Day 14: Semi-naive solution got there in the end (2m11s execution time) just to get the answer.
Rewrote it properly (think lanternfish) and it's near instantaneous (under 0.01s).