Thinking Outside the Box with Python

[Motoma]

This article is cross posted from my personal blog. You can find the original article, in all its splendor, at http://motomastyle.com/thinking-outs...x-with-python/ .

Introduction:
I recently came across this job posting in the forums. It has an interesting brain teaser as a requirement for applying. The brain teaser was stated as: "What is the exponent of the largest power of two whose base seven representation doesn't contain three zeros in a row?" The only stipulation was that the applicant use Python to solve the problem.

My Initial Approach:
My inital approach to the problem is blunt and straight forward. I build three functions, BaseSeven which takes a number and convert it to base seven, HasThreeZeros which takes a number and checks if it has three zeros in it, and FindWithoutZero s which was the main loop of my program. The code for my problem is listed below:

def BaseSeven(num):
    powersOfSeven = 1;
    res = 0;
    while num / powersOfSeven > 6: powersOfSeven = powersOfSeven * 7
    while powersOfSeven != 1:
        res = res * 10 + int(num / powersOfSeven)
        num = num - int(num / powersOfSeven) * powersOfSeven
        powersOfSeven = powersOfSeven / 7
    res = res * 10 + num
    return res
 
def HasThreeZeros(num):
    return str(num).find("000") != -1
 
def FindWithoutZeros(power):
    lastWithoutThreeZeros = power
    failures = -1
    num = pow(2, power)
    while failures <= lastWithoutThreeZeros:
        if HasThreeZeros(BaseSeven(num)):
           failures = failures + 1
        else:
            failures = 0
            lastWithoutThreeZeros = power
            print power
        power = power + 1
        num = num * 2
        if (float(power) / 100) == int(power / 100): print "CheckPoint:", power
    return lastWithoutThreeZeros
 
print FindWithoutZeros(1)

The solution is quick and dirty, though severely lacking in elegance and speed. The biggest problem with this solution is that the program is constantly performing arithmetic operations on a huge number; when the exponent climbs into the upper thousands, it takes well over a minute to build, convert, and check a single number.

"There is no need for this," I say to myself, "There is a better way to do it."

Round 2:
With a new cup of coffee in hand, I begin to further analyze the problem. Rereading the problem, I begin to think about the properties of powers of two: the most important property being that each successive power of two is double the previous. I know this is a pretty rudementary conclusion, however, realizing that the same will hold true for the base seven equivalent is the key to solving this problem efficiently.

I begin constructing a class, titled BaseSevenNumber . I give it a list, named digits, whose elements will contain a single base seven digit. I build a constructor to initialize this list to [1], and a member function titled Double which will handle my "exponentiation ." I finish off the class by creating another member, aptly titled HasThreeZeros, to give me the current status of number.

The Double Function:
BaseSevenNumber 's Double function would hold the key to solving this problem in a timely manner. Rather than perform one arithmetic operation on a huge number, I design my second program to perform many arithmetic operations on a handful of tiny numbers. Iterating through the list, Double doubles each digit in the digits list, and in a second pass, performs all base seven carry operations. the HasThreeZeros function can now quickly traverse the digits list, and return the appropriate status for the current base seven number.

class BaseSevenNumber:
 
    def __init__(self):
        self.digits = [1]
 
    def Double(self):
        for i in range(0, len(self.digits)):
            self.digits[i] = self.digits[i] * 2
        for i in range(len(self.digits) - 1, -1, -1):
            if self.digits[i] > 6:
                self.digits[i] = self.digits[i] - 7
                if i == 0: self.digits.insert(0,1)
                else: self.digits[i - 1] = self.digits[i - 1] + 1
 
    def HasThreeZeros(self):
        for i in range(0, len(self.digits) - 2):
            if self.digits[i] == 0 and self.digits[i + 1] == 0 and self.digits[i + 2] == 0: return True
        return False
 
def SolveRiddle(maxFailuresAssumeFound):
    bsn = BaseSevenNumber()
    failures = 0
    power = 1
    while failures < maxFailuresAssumeFound:
        bsn.Double()
        if bsn.HasThreeZeros(): failures = failures + 1
        else:
            failures = 0
            print power
        power = power + 1
 
SolveRiddle(10000)

Thoroughly pleased with my ability to think my way around the problem, I put the code to the test. In a meager 16 seconds, it has given me the answer I am looking for. Talk about using the wrong tools for the job; just because the problem stated "power of two" and "base seven representation" does not mean one should restrict oneself to these methods. A careful and thorough analysis of a problem can give one an efficient, elegant, and fast solution to some of the trickiest of problems.

[bvdet]

Motoma - Excellent solution! I need to be producing but could not get this problem off my mind. Here's a top down approach:

def ConvDecToBaseVar(num, base):
    if base > 10 or base < 2:
        raise ValueError, 'The base number must be between 2 and 10.'
    if num == 0: return '0'
    ans = ''
    while num != 0:
        num, rem = divmod(num, base)
        ans =  str(rem)+ans
    return ans
 
def solve_test1(max):
    for i in xrange(max, 0, -1):
        if '000' not in ConvDecToBaseVar(2**i, 7):
            return i
        else:
            print 'Checked power %s, FAILED TEST' % (i)

It took a while, but found that the highest number below 20000 is 8833. It's not nearly as efficient as yours. Now I can get back to work.

[dazzler]

so, did you get the job? :D

[Motoma]

so, did you get the job? :D

Pffftt...I never applied. I have no Python experience :D