Thought Process

This problem was quite fun!

I made a function, seq_finder, which recursively finds the number of steps in the sequence that are correct for a given number and sequence.

Then I start searching, I find a number that satisfies the first step and then use seq_finder to see if it makes it to the end, if it doesn't I increment the original number by 3 and try again. This alone was enough to solve the test case, but not the final answer.

That's when I realised that if I find a number that satisfies the first n steps on the sequence, I can increment 3^n from that number each time because with every step of that size I am maintaining the current sequence I already have.

For example 1,000,002 satisfies D but not Dd, so I now increment by 3, 1,000,005 satisfies Dd but now DdD, so I can now increment by 9. This is because 1,000,005 + 3 = 1,000,008 will now satisfy D but not Dd again, because we are in the wrong cycle. Using this we make the following jumps 1,000,002 -> 1,000,005 ->1,000,014 -> 1,000,095 -> 1,000,176 -> 1,000,419 -> 1,001,148 ->1,001,877 ->1,004,064, so instead of checking 1354 numbers we check 9.

For the actual answer we save around 4*10^13 checks, not a bad speed up.

I can keep track of the largest amount of steps I have found and increment by 3^max_steps, this instantly solves the problem!