Some math about the Engineyard contest

1) you are right, I and a lot of other guys are already doing this.

2) Indeed Cuda can be used with success, and this is probably the way to go. Unfortunately I don't have any board at hand, but I'll buy one later in order to experiment with this technology.

3) This is not going to save you any time. Basically the part that alters the five chars at the end is nothing compared to the rest of the computation.

There are other tricks that can be used, like to compute a fast hamming distance, just xor the bytes of the two strings and count the bits using a lookup table. Or even use some specific asm instruction for bit counting. But again unless you are doing this stuff of the xor in a very slow way this is a negligible amount of work: I commented out the hammer distance computation in my code and the numbers are exactly the smae, 3.5 million comparison per second per core more or less.

Another obvious optimization is of course to avoid doing too much permutations of the words. For every permutation there are a lot of tries to do just altering the final five chars.

Basically there is no way to win without to resort to fast hardware and parallelization, being it a large set of computers, CUDA, or a very lucky run that outputs in 30 hours an entry with an hamming distance of 31 or 32 just... against the probabilities ;)

The only reason I'm running the contest is that it's funny and a very good way to teach something interesting to the programmers working in my company. We care a lot about having fun programming.

I've done some work with CUDA, so I'll just tell you ahead of time: it will probably be decently fast, but not nearly the kind of speeds you'd get from something like matrix multiplication. The problem is going to be that you need to fit the data to hash in "shared memory" (which is sort of like an L2 cache on the GPU). The standard shared memory size in CUDA is 16kb. Also, because of the way that data must be allocated in shared memory, you're not going to be able to get many string permutations into shared memory at once.

However, I think a good solution (if you're going to use CUDA, which I was thinking about doing as well) might be to load one permuation of words from the dictionary into the shared memory, and then have each thread compute one permuation of the various capitalizations for that string. This way you're mostly working out of the "cache" and that's about the best thing you can do on CUDA.

Actually, if anyone has a good cuda card and wants to team up on the code writing email me: sophacles@gmail.com. We an use different random seeds when it comes time to running the stuff or whatever... I just think it would be fun!

here's that program for you, in shitty perl: http://gist.github.com/149173

He was computing the probability of a Hamming distance of exactly D instead of at most D. To get the "at most" version, you could just add up the exact ones, but it's better to just use the central limit theorem instead.

As for your math, I think you are over counting a little :). The problem is, 100...0 is counted by both ??0...0 and ?0?00...0, where ? marks a digit that you've allowed to be free, and 0 marks a "chosen" 0.

What would you suggest they do? Your follow-on indicates that you think ties should be adjudicated on the basis of the "best" algorithm, but how do you objectively define that?