[Tutor] Suggestions for more efficient and optimized coding technique,

[Robert Berman]

Thank you again. I now have enough to keep me happily busy for days.

Robert

Michael Langford wrote:
> I understand that each response is unique Robert and no caching is
> required to solve the problem at hand. However in a real program, the
> chance you're brute forcing just one password is small (usually you
> would brute force many); additionally, the question posted
> specifically asked that the trials be cached, which is why I suggest
> you do so, not out of any real need for just testing on the "loner"
> testcase.
>
> Additionally, the reason the aaaaa->zzzzz method is suggested is that
> it a much faster algorithm to test every available combination than
> the random method. The random method may never find the data.
>
> I've created a frame work for you to play around with on this problem.
> It shows how long different methods take in a more realistic scenario.
> Try some other methods if you want, as well play around with password
> length, the aaaaa->zzzzz method, etc. I've shorted then password
> length to 3 to make it run faster  as well. Enough procrastination,
> back to google app engine stuff.
>
>                --Michael
>
> #!/usr/bin/env python
> import string
> import random
>
> # test code to simulate a computer system under
> #    attack, no need to understand now
> class Computer(object):
>     def __init__(self):
>       self.reset_password()
>
>     def reset_password(self,length=3):
>       self.secret_password=''.join(random.sample(string.ascii_lowercase,length))
>       print('The new password is: ' + self.secret_password)
>
>     def enter_password(self,teststr):
>       """returns true if the password was correct"""
>       return teststr==self.secret_password
>
> # end test code
>
>
> def rand_string(length = 3):
>   """generates a random string of the given length"""
>   return ''.join(random.sample(string.ascii_lowercase,length))
>
> passcache = list()
>
> def crack_password(comp):
>   """repeatedly tries passwords on the given computer"""
>   tries = 0
>   while True:
>        tries += 1
>        if comp.enter_password(rand_string()):
>            print( 'Password found in ' + str(tries) + ' tries.')
>            return
>
> def crack_password_cached(comp):
>   """repeatedly tries passwords on the given computer"""
>   for password in passcache:
>       if comp.enter_password(password):
>           print 'Password found in cache'
>           return
>
>   tries = 0
>   while True:
>        tries += 1
>        s = rand_string()
>        passcache.append(s)
>        if comp.enter_password(s):
>            print( 'Password found in ' + str(tries) + ' tries.')
>            return
>
>
> def hack():
>     """hacks a computer via a brute force method"""
>     my_computer = Computer()
>     crack_password(my_computer)
>
> def hack_cached():
>     """hacks a computer via a brute force method with cached results"""
>     my_computer = Computer()
>     crack_password_cached(my_computer)
>
>
> def mean(ls):
>     """finds the mean of a list of numbers"""
>     return sum(ls)/len(ls)
>
>
> def test_case(funcname, repeats):
>     """
>      timeit is a python library for timing code. No need to
>      understand how this works, just that its repeating the
>      command given the number times specified by repeats. It's
>      returning a list of the execution times of each of the trials
>     """
>     import timeit
>     timer = timeit.Timer("%s()"%funcname,"from __main__ import %s"%funcname)
>     return timer.repeat(number=repeats)
>
>
> if __name__ == '__main__':
>
>
>     times_to_repeat = 100
>
>     uc_results = test_case("hack",times_to_repeat)
>     c_results = test_case("hack_cached", times_to_repeat)
>
>     print( "Cached mean time: "  + repr(mean(c_results)) )
>     print( "Cached min. time: "  + repr(min(c_results)) )
>     print( "Uncached mean time: "  + repr(mean(uc_results)) )
>     print( "Uncached min. time: "  + repr(min(uc_results)) )
>
>
>
>
>
>
>
>
>
> On Thu, Jan 8, 2009 at 1:31 PM, Robert Berman <bermanrl at cfl.rr.com> wrote:
>   
>> Michael,
>>
>> Thank you for your code and your commentary. The code tells me this is
>> really an ongoing learning process; almost as convoluted as linguistics and
>> certainly every bit as interesting.
>>
>> Your concept of brute force in this example is intriguing. It is as if I
>> have five cogs spinning, 'a' the slowest and 'e' flying as fast as its
>> spokes can engage, and every click of every wheel produces a viable but
>> possibly wrong response. However, each response is unique and in the nth
>> iteration where password is found, all previous iterations are unique so
>> there is certainly no need to carry the previous responses in either a list
>> or a dictionary. They do not duplicate since they cannot repeat. Other than
>> to include extraneous code, why include repetitive checking at all?
>>
>> In spite of that, your code and your remarks are most appreciated.
>>
>> Robert
>>
>> Michael Langford wrote:
>>
>> Here is your algorithm made more pythonic. Notice the use of default
>> parameters, doc strings, not abbreviated variable names,  unix C style
>> capitolization (very subjective, but often the one found in python
>> libs), the avoidance of control variables when possible, the use of
>> ascii_lowercase instead of your own string and  the not calling
>> functions main that aren't __main__.
>>
>> #!/usr/bin/env python
>> import string
>> import random
>>
>> def rand_string(length = 5):
>>   """returns a random string of numbers"""
>>   return ''.join(random.sample(string.ascii_lowercase,length))
>>
>> def try_password(match="loner"):
>>   """randomly tries 5 letter long passwords until the user finds the
>> correct one"""
>>   tries = 0
>>   while True:
>>        tries += 1
>>        if rand_string()  == match:
>>            print 'Password found in ' + str(tries) + ' tries.'
>>            return
>>
>> if __name__ == '__main__':
>>   try_password()
>>
>>
>> Note: I do not think you're doing the problem the way the author
>> intended. As it wants you to try all combinations, and it's about
>> brute force, not finding it quickly, you most likely should start at
>> "aaaaa" and move to "zzzzz", and cache the results in a list like they
>> ask you too. At the very least, you should be saving these
>> combinations you are generating randomly in a list (as it asks you to)
>> and not testing the password if the generated string was already in
>> the list (as in a real application, that is the time consuming or
>> dangerous operation).
>>
>>              --Michael
>>
>> PS: If you wish to assure direct replies reach me
>>
>> On Thu, Jan 8, 2009 at 10:49 AM, Robert Berman <bermanrl at cfl.rr.com> wrote:
>>
>>
>> Hi,
>>
>> One of the challenges on the challenge you web page appropriately titled
>> 'Brute force' reads as follows:
>>
>> "The password you have to guess is 'loner' . Try all combinations of
>> lowercase letters until you guess it.  Try not to loop much for example,
>> save all used combinations in an array so you don't repeat."
>>
>> My code is as follows:
>>
>> #!/usr/bin/env python
>>
>> import random
>>
>> def GetString():
>>   alphabet='abcdefghijklmnopqrstuvwxyz'
>>   return ''.join(random.sample(alphabet,5))
>> def main():
>>   password='loner'
>>   errknt = 0
>>   control = True
>>   while control is True:
>>       if GetString() != password:
>>           errknt +=1
>>       else:
>>           print 'Password found in ',errknt,' tries.'
>>           control = False
>>
>>          if __name__ == '__main__': main()
>> The code does work. I am looking for suggestions to learn more about both
>> efficiency  and optimization of code.
>>
>> Since the challenge revolves around the use of randomized retrieval, I'm not
>> too sure how to optimize the process. The authors concept of using arrays
>> seem a bit superfluous as I think it takes longer to add an item to a
>> dictionary and retrieve an item from a dictionary than it does to do an if
>> compare of two 5 character strings. So, I left that code out of the program
>> entirely. If that was wrong, or there is a better way to avoid duplication,
>> please point me in the right direction.
>>
>> I think, perhaps, I could make it a tad more efficient if I changed
>> 'alphabet' from a string to a list as I remember reading  that lists are
>> significantly faster to manipulate than are strings. Is that true and is it
>> a viable change.
>>
>> I realize my code looks like modified C++ structured code. I am trying to
>> become more Python concise but I think that is  a matter of writing more and
>> more python code.
>>
>> All suggestions, ideas, critiques are most welcome.
>>
>> Thank you,
>>
>> Robert
>> _______________________________________________
>> Tutor maillist  -  Tutor at python.org
>> http://mail.python.org/mailman/listinfo/tutor
>>
>>
>>
>>
>>     
>
>
>
>