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]) &gt;= 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(contents[case])
        print("Case {0}: finding the {1}th digit".format(str(case), str(k)))

        string = find(k)
        solution = string[k-1]

        print("Case #{0}: {1}".format(str(case), solution))
        file.write("Case #{0}: {1}\n".format(str(case), solution))


The above can successfully generate an output for the small input file, but the main issue I am having is that it runs far too slow for the large input file (almost as if not running at all).

I have already tried to improve the code a little - I thought adding the line:

s[0] = s[1]


in the for loop would mean that the list will always only consist of two items, reducing memory allocation.

My other fear is that I have coded too much for something that could be written in a more concise way (I'm not sure about this one).
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 &gt; 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 &gt; 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)