4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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)

\$\endgroup\$
  • 3
    \$\begingroup\$ You had a perfect chance to say 'this may stack overflow'. Shame you didn't take it ;) \$\endgroup\$ – Insane May 14 '16 at 8:02
  • \$\begingroup\$ This is still far more complicated than necessary. \$\endgroup\$ – Peter Taylor Dec 20 '18 at 15:36
0
\$\begingroup\$
    googol = (10**100)
    ...
    for n in range(1, googol + 1):

Red flag! If you're potentially iterating over more than \$10^9\$ elements then 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.