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

Question

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:

S₀ = ""

S₁ = "0"

S₂ = "001"

S₃ = "0010011"

S₄ = "001001100011011"

...

S_N = S_N-1 + "0" + switch(reverse(S_N-1)).

You need to figure out the Kth character of S_googol, where googol = 10¹⁰⁰.

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 S_googol.

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(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).

Answer 1

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

\$S_n\$ has an odd number of digits

It is obviously of the form \2ドルk+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)

• Insane: You had a perfect chance to say 'this may stack overflow'. Shame you didn't take it ;)
• Peter Taylor: This is still far more complicated than necessary.

Answer 2

 googol = (10**100)
 ...
 for n in range(1, googol + 1):

Red flag! If you're potentially iterating over more than \10ドル^9\$ elements then time-limit-exceeded is virtually guaranteed.

Consider an alternative string defined by

def S(n):
 return S(n-1) + [n] + [-x for x in reversed(S(n-1))] if n > 0 else []

You should observe firstly that the absolute values form a comb function; and secondly that the signs of the same value alternate. Both of these are easy to prove, and lead to the following algorithm:

def char_at(k):
 while (k & 1) == 0:
 k >>= 1
 k >>= 1
 return k & 1

By using some standard bitwise manipulations it can even be written as a very fast one-liner:

char_at = lambda k: 0 if k & ((k & -k) << 1) == 0 else 1