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:
[code=python]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(n um):
return str(num).find(" 000") != -1
def FindWithoutZero s(power):
lastWithoutThre eZeros = power
failures = -1
num = pow(2, power)
while failures <= lastWithoutThre eZeros:
if HasThreeZeros(B aseSeven(num)):
failures = failures + 1
else:
failures = 0
lastWithoutThre eZeros = power
print power
power = power + 1
num = num * 2
if (float(power) / 100) == int(power / 100): print "CheckPoint :", power
return lastWithoutThre eZeros
print FindWithoutZero s(1)[/code]
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.
[code=python]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.ins ert(0,1)
else: self.digits[i - 1] = self.digits[i - 1] + 1
def HasThreeZeros(s elf):
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(max FailuresAssumeF ound):
bsn = BaseSevenNumber ()
failures = 0
power = 1
while failures < maxFailuresAssu meFound:
bsn.Double()
if bsn.HasThreeZer os(): failures = failures + 1
else:
failures = 0
print power
power = power + 1
SolveRiddle(100 00)[/code]
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.
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:
[code=python]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(n um):
return str(num).find(" 000") != -1
def FindWithoutZero s(power):
lastWithoutThre eZeros = power
failures = -1
num = pow(2, power)
while failures <= lastWithoutThre eZeros:
if HasThreeZeros(B aseSeven(num)):
failures = failures + 1
else:
failures = 0
lastWithoutThre eZeros = power
print power
power = power + 1
num = num * 2
if (float(power) / 100) == int(power / 100): print "CheckPoint :", power
return lastWithoutThre eZeros
print FindWithoutZero s(1)[/code]
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.
[code=python]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.ins ert(0,1)
else: self.digits[i - 1] = self.digits[i - 1] + 1
def HasThreeZeros(s elf):
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(max FailuresAssumeF ound):
bsn = BaseSevenNumber ()
failures = 0
power = 1
while failures < maxFailuresAssu meFound:
bsn.Double()
if bsn.HasThreeZer os(): failures = failures + 1
else:
failures = 0
print power
power = power + 1
SolveRiddle(100 00)[/code]
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.
Comment