Engineyard Challenge Python Code • Hacker News Board

Re: Engineyard Challenge Python Code

#11

Post by TriinT » Wed, Jul 15, 2009, 9:00 AM UTC

herrherr wrote: post #6

Theoretically I'm having around 500 CPUs with 3gHz each and 2000GB RAM at my disposal. Maybe I should give it a try. Hint: University Cluster =) Anyway thanks for the code examples, I'm pretty sure I can learn something from them.

Apparently, I am not the only one who is into using the university cluster for my own personal projects ;-)

Be careful. This is not "exactly" legal, and it could hurt you. Make sure you also throw some legitimate computational work at the clusters so you have an alibi at least.

Re: Engineyard Challenge Python Code

#12

Post by eru » Wed, Jul 15, 2009, 11:12 AM UTC

ighost wrote: post #8

jacquesm wrote: post #7

Earlier quoted context omitted.

Lotto tickets aren't nearly as much fun as coding, so what's another 10 bucks. Personally I'd run through a thousand bucks of computer time to play around with something or test a hunch before considering a lotto ticket. Lotto tickets are taxes for people that are not good in mathematics.

or they just play for fun

Alas, being good in mathematics spoils the fun.

Re: Engineyard Challenge Python Code

#13

Post by danielh » Wed, Jul 15, 2009, 11:28 AM UTC

ighost wrote: post #9

Is this supposed to run on Unladen Swallow? Or does the GIL not come into play here?

It uses the multiprocessing package, which is new in Python 2.6. From the docs:

The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. http://docs.python.org/library/multiprocessing.html

Re: Engineyard Challenge Python Code

#14

Post by tsally » Wed, Jul 15, 2009, 12:37 PM UTC

herrherr wrote: post #6

Theoretically I'm having around 500 CPUs with 3gHz each and 2000GB RAM at my disposal. Maybe I should give it a try. Hint: University Cluster =) Anyway thanks for the code examples, I'm pretty sure I can learn something from them.

I have an account on this: http://www.cse.illinois.edu/turing/

Had very similar thinking, but decided against it because of usage policies. :-p

Re: Engineyard Challenge Python Code

#15

Post by bcl » Wed, Jul 15, 2009, 2:06 PM UTC

danielh wrote: post #13

ighost wrote: post #9

Is this supposed to run on Unladen Swallow? Or does the GIL not come into play here?

It uses the multiprocessing package, which is new in Python 2.6. From the docs: The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. http://docs.python.org/library/multiprocessing.html

multiprocessing is also available in 2.5, which is what I used, just do: easy_install multiprocessing

Re: Engineyard Challenge Python Code

#16

Post by bcl » Wed, Jul 15, 2009, 2:11 PM UTC

jamesotron wrote: post #3

Ahh, I see that you're generating an entirely new random string each iteration. Interesting. I've done mine in Pike, which will be faster (though not as fast as C). http://github.com/jamesotron/HashChallenge/tree/master

I'm being lazy about the search, depending on the random distribution to keep work from overlapping too much instead of taking the time to keep track of what has been done, or implementing a systematic search of the possible combinations.

My thought is that there are so many possibilities and so few CPU cycles available to me that making random guesses is a better way to approach it. Kinda like winning the lottory, except harder.

Re: Engineyard Challenge Python Code

#17

Post by ErrantX » Wed, Jul 15, 2009, 3:29 PM UTC

herrherr wrote: post #6

Theoretically I'm having around 500 CPUs with 3gHz each and 2000GB RAM at my disposal. Maybe I should give it a try. Hint: University Cluster =) Anyway thanks for the code examples, I'm pretty sure I can learn something from them.

500 cores gives you no really higher chance of getting a good combination over someone with one PC.

Yes you get 500 times the attempts in the 30hr period. But if you run the figures it's something like 0.00000001% difference in the amount of keyspace you can cover :)

AKA just run it on a couple of PC's an hope you get lucky!

Re: Engineyard Challenge Python Code

#18

Post by decode » Wed, Jul 15, 2009, 6:43 PM UTC

ErrantX wrote: post #10

I dont wish to be, umm, mean. But I know of at least 3 companies (ours included) that could run this in a few minutes. this is my code (using mighty, our python based cluster service): import mighty word_generator = mighty.word_generator("wordlist",(mighty.APPEND_NUMERALS,5)) phrase_generator = mighty.word_concentate(word_generator,' ') job = mighty.match_to_hash('PROVIDEDHASH',mighty.SHA1,phrase_generator.iterate_al…

This isn't actually correct, is it? Assuming an average 6-letter word length, there are about 10^67 valid combinations that your iterate_all() can go through: (((2^6) * 1000) ^ 12) * (94 ^ 5) = 3.5 * 10^67

Since this is much larger than the total hash space (2^160 = 10^48), you can hope you'll get a collision after the number of tries equal to half of the hashspace (10^48 / 2). That means you'll have to generate 10^47 hashes. At 5 minutes of runtime, you'll have to generate 10^45 hashes per second.

Bottom line: if you can run this on 200,000 cores, you'll have to generate 10^40 hashes per second per core, and that seems impossible to me.

Re: Engineyard Challenge Python Code

#19

Post by jamie_ca » Wed, Jul 15, 2009, 6:52 PM UTC

ErrantX wrote: post #10

I dont wish to be, umm, mean. But I know of at least 3 companies (ours included) that could run this in a few minutes. this is my code (using mighty, our python based cluster service): import mighty word_generator = mighty.word_generator("wordlist",(mighty.APPEND_NUMERALS,5)) phrase_generator = mighty.word_concentate(word_generator,' ') job = mighty.match_to_hash('PROVIDEDHASH',mighty.SHA1,phrase_generator.iterate_al…

I think it unlikely you have a compute cluster that can generate 3.3 million, billion, billion, billion SHA1 hashes per second (edit: and that assumes not adding the random 5 characters to the end). The actual contest will have a word list of a thousand words.

Also, (a) you're allowed to permute case of letters, exploding the search space even more, which is handy because (b) I presume the target sha1 will come from words not on the word list, making an exact match unlikely (hence score based on hamming distance).

Re: Engineyard Challenge Python Code

#20

Post by ErrantX » Wed, Jul 15, 2009, 9:45 PM UTC

decode wrote: post #18

ErrantX wrote: post #10

I dont wish to be, umm, mean. But I know of at least 3 companies (ours included) that could run this in a few minutes. this is my code (using mighty, our python based cluster service): import mighty word_generator = mighty.word_generator("wordlist",(mighty.APPEND_NUMERALS,5)) phrase_generator = mighty.word_concentate(word_generator,' ') job = mighty.match_to_hash('PROVIDEDHASH',mighty.SHA1,phrase_generator.iterate_al…

This isn't actually correct, is it? Assuming an average 6-letter word length, there are about 10^67 valid combinations that your iterate_all() can go through: (((2^6) * 1000) ^ 12) * (94 ^ 5) = 3.5 * 10^67 Since this is much larger than the total hash space (2^160 = 10^48), you can hope you'll get a collision after the number of tries equal to half of the hashspace (10^48 / 2). That means you'll have to generate 10^4…

Weeell we have 20,023 computers (that fluctuates a tad). That's probably about 30,000 cores in the end.

I cant iterate the whole lot - but I can cover a substantial portion more of the keyspace in 5 mins than most could in the 30hrs. I bet 5 minutes will easily get me damn close :)