473,320 Members | 1,887 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 473,320 developers and data experts.

Thinking Outside the Box with Python

Motoma
3,237 Expert 2GB
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 FindWithoutZeros which was the main loop of my program. The code for my problem is listed below:


Expand|Select|Wrap|Line Numbers
  1. def BaseSeven(num):
  2.     powersOfSeven = 1;
  3.     res = 0;
  4.     while num / powersOfSeven > 6: powersOfSeven = powersOfSeven * 7
  5.     while powersOfSeven != 1:
  6.         res = res * 10 + int(num / powersOfSeven)
  7.         num = num - int(num / powersOfSeven) * powersOfSeven
  8.         powersOfSeven = powersOfSeven / 7
  9.     res = res * 10 + num
  10.     return res
  11.  
  12. def HasThreeZeros(num):
  13.     return str(num).find("000") != -1
  14.  
  15. def FindWithoutZeros(power):
  16.     lastWithoutThreeZeros = power
  17.     failures = -1
  18.     num = pow(2, power)
  19.     while failures <= lastWithoutThreeZeros:
  20.         if HasThreeZeros(BaseSeven(num)):
  21.            failures = failures + 1
  22.         else:
  23.             failures = 0
  24.             lastWithoutThreeZeros = power
  25.             print power
  26.         power = power + 1
  27.         num = num * 2
  28.         if (float(power) / 100) == int(power / 100): print "CheckPoint:", power
  29.     return lastWithoutThreeZeros
  30.  
  31. 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.

Expand|Select|Wrap|Line Numbers
  1. class BaseSevenNumber:
  2.  
  3.     def __init__(self):
  4.         self.digits = [1]
  5.  
  6.     def Double(self):
  7.         for i in range(0, len(self.digits)):
  8.             self.digits[i] = self.digits[i] * 2
  9.         for i in range(len(self.digits) - 1, -1, -1):
  10.             if self.digits[i] > 6:
  11.                 self.digits[i] = self.digits[i] - 7
  12.                 if i == 0: self.digits.insert(0,1)
  13.                 else: self.digits[i - 1] = self.digits[i - 1] + 1
  14.  
  15.     def HasThreeZeros(self):
  16.         for i in range(0, len(self.digits) - 2):
  17.             if self.digits[i] == 0 and self.digits[i + 1] == 0 and self.digits[i + 2] == 0: return True
  18.         return False
  19.  
  20. def SolveRiddle(maxFailuresAssumeFound):
  21.     bsn = BaseSevenNumber()
  22.     failures = 0
  23.     power = 1
  24.     while failures < maxFailuresAssumeFound:
  25.         bsn.Double()
  26.         if bsn.HasThreeZeros(): failures = failures + 1
  27.         else:
  28.             failures = 0
  29.             print power
  30.         power = power + 1
  31.  
  32. 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.
May 18 '07 #1
3 6046
bvdet
2,851 Expert Mod 2GB
Motoma - Excellent solution! I need to be producing but could not get this problem off my mind. Here's a top down approach:
Expand|Select|Wrap|Line Numbers
  1. def ConvDecToBaseVar(num, base):
  2.     if base > 10 or base < 2:
  3.         raise ValueError, 'The base number must be between 2 and 10.'
  4.     if num == 0: return '0'
  5.     ans = ''
  6.     while num != 0:
  7.         num, rem = divmod(num, base)
  8.         ans =  str(rem)+ans
  9.     return ans
  10.  
  11. def solve_test1(max):
  12.     for i in xrange(max, 0, -1):
  13.         if '000' not in ConvDecToBaseVar(2**i, 7):
  14.             return i
  15.         else:
  16.             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.
May 18 '07 #2
dazzler
75
so, did you get the job? :D
Dec 12 '07 #3
Motoma
3,237 Expert 2GB
so, did you get the job? :D
Pffftt...I never applied. I have no Python experience :D
Dec 12 '07 #4

Sign in to post your reply or Sign up for a free account.

Similar topics

3
by: Alexander Eberts | last post by:
I'm new to python so appologies to the group if this question is asked often. I'm wondering if it's possible to query an object instance to find out what arguments the instance's __init__ function...
1
by: Chris Perkins | last post by:
Is there a reason why the ... notation as a literal for Ellipsis is only allowed inside a slice? Would allowing it elsewhere frighten the parser? Chris Perkins
17
by: Mike Hofer | last post by:
While I'd toyed with C, C++, and Java over the last 20 years or so, my principal language has been BASIC, QBASIC, then Visual Basic, and finally Visual Basic .NET. But lately, I've been using C#...
3
by: Alex Pavluck | last post by:
Hello. On page 124 of "Thinking like a Computer Scientist". There is an exercise to take the following code and with the use of TRY: / EXCEPT: handle the error. Can somone help me out? Here is...
16
by: Sébastien Boisgérault | last post by:
Hi, Could anyone explain me how the python string "é" is mapped to the binary code "\xe9" in my python interpreter ? "é" is not present in the 7-bit ASCII table that is the default encoding,...
0
by: Fabiano Sidler | last post by:
Hi folks! I'm trying to implement a python function that returns the current stack depth of its frame. Unfortunately, I don't see any possibility to get this value outside of PyEval_EvalFrameEx....
6
by: Aggelos | last post by:
Hello, Is it possible to run a script that will be used from all the websites on the server outside of the web dir ? At the moment for every site I have I upload the script in the web dir of the...
5
by: riverhorus | last post by:
I'm new to Python. I got this Python script from a friend. When I run it, I get an error message for line 7, "return None" saying "SyntaxError: 'return' outside function" Can someone explain what...
11
by: Hussein B | last post by:
Hey, Well, as you all know by now, I'm learning Python :) One thing that is annoying my is the OOP in Python. Consider this code in Java: -- public class Car { private int speed; private...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.