Google Code Jam Google String problem: a sequence resulting from bit flips and reversals

I'm currently having a go at some past Google Code Jam problems to help me practice my programming skills.

One of these problems is Problem A ("Googol String") from Round A APAC Test 2016. Here is the problem for reference (you can find the details via the link):


Problem


A "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.


Input


The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.


Output


For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the Kth character of Sgoogol.

After an hour (probably too long to spend on one problem, but it's practice!), I developed a solution.

Here it is:

```
def switch(num):
newnum = ""
for char in num:
newnum += ("1" if char == "0" else "0")
return newnum

def reverse(num):
newnum = ""
for i in range(len(num)-1, -1, -1):
newnum += num[i]
return newnum

def find(digits):
googol = (10**100)
s = ["", ""]

for n in range(1, googol + 1):
s[1] = s[0] + "0" + switch(reverse(s[0]))

if len(s[1]) >= digits:
return s[1]

s[0] = s[1]

r_fname = "A-small-practice.in"
w_fname = "output-small.txt"

with open(r_fname, "r") as file:
contents = file.readlines()

with open(w_fname, "w+") as file:
t = int(contents[0].strip("\n"))

for case in range(1, t+1):
k = int

Instead of trying to actually calculate Sgoogol, let's try to figure out some properties of the general case Sn and see if that can help.

\$S_n\$ has an odd number of digits

It is obviously of the form \$2k+1\$

\$S_n\$ has length \$2^n - 1\$

This is easily proved with recursion

\$S_n[\frac{2^n}{2} + 1] = S_n[2^{n-1} + 1] = 0\$

From the definition. I'm assuming 0-based indexing.

If \$k > 2^{n-1} + 1\$, then \$S_n[k] = switch(S_n[(2^n - 1) - 1 - k])\$

From the definition. This allows us to convert between halves of the string.

This suggests a simpler algorithm.

def find_value(index, n):
    if n == 2:
        return [True, True, False][index] 
    if k == 2 ** (n-1) + 1:
        return True
    if k > 2 ** (n-1) + 1:
        return not find_value((2^n - 1) - 1 - k, n-1)
    return find_value(k, n-1)

And you can convert to 0 or 1 afterwards. (This may blow the stack, so you may have to rewrite iteratively)

StackExchange Code Review Q#128312, answer score: 3