Googol string
I stumbled across this programming challenge. I thought it was easy but spent some hours on it instead! You can find the problem description and the output checker at https://code.google.com/codejam/contest/4284486/dashboard
ProblemA “0/1 string” is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011".reverse: The string is reversed. For example, “100” becomes “001”.Consider this infinite sequence of 0/1 strings:S0 = “”S1 = “0”S2 = “001”S3 = “0010011”S4 = “001001100011011”…SN = SN-1 + “0” + switch(reverse(SN-1)).You need to figure out the Kth character of Sgoogol, where googol = 10100.
The problem requires you to deal with a sequence. The rule to generate new elements is part of the problem description: SN = SN-1 + “0” + switch(reverse(SN-1)).
The tricky part is that the element of the sequence to generate it’s the 10**100'th!
If you have no idea whether your computer can handle computations the order of 10**100 (I hadn’t) you can do a small test: try to run
>>> for _ in range(10**100): pass
...and you will see that even just pass is too much to execute that many number of times. It’s unrealistic to build the whole sequence up to the googol’th element.
Having no idea on how to make progress, I started to try to answer another question: is it possible to compute the number of bits in S_googol without generating the element?
Sure. You know that the nth element is just the n-1th element, a 0, and the n-1th element reversed and NOT’d. That is
If you keep on expanding this recursive expression you start to notice patterns and you can deduce that
So, the googol’th element of the sequence is circa 2**10**100 bits long.
That’s a lot! I started to doubt that any efficient procedure to compute the whole string exist — or that I could have found it.
An idea: you know the middle element of S_googol is 0. In fact, S_googol is built using S_googol-1, a 0, and (some bit manipulation on) S_googol-1. The middle is 0 then. For the same reason, at 1/4 of the pattern it must have another 0. While at 3/4 of the pattern, …a 1, since it’s the same 0 at 1/4, but flipped.
Can I exploit this idea to jump around the pattern until I know the digit at position K?
Yes. It turns out that I can. I run the code on S4 and it worked! Except…the complexity of the procedure is logarithmic to the size of the pattern, meaning that in the case of S_googol the order is 10**100\! As explained above …that’s too much.
Even an idea that feels clever it’s no more efficient than the first, brutal approach!
Another idea: the problem description states that K will be no larger than 10**18. If that’s true, why not moving from the middle of the pattern to smallest power of two that’s the closest to 10**18, and reuse the idea above? Being the size of the problem much smaller, it could work!
But. To find the required power of two, you either have to solve
or you have to start from 10**18 and add +1, checking at each iteration if the result is a power of 2 or not.
Both approaches failed. The first because Wolfram Alpha didn’t want to solve it; the second because powers of 2 apparently are not dense — the algorithm hangs for too much time.
Another idea: why not starting from the beginning of the pattern (knowing you’ll be always on the left side of the whole S_googol), expanding until you reach a point where reusing the initial idea of jumping around becomes feasible?
Using this approach I was able to finally solve the problem.
