Competition: Find a duplicate code map

[mopa42]

hey, mopa, I can't seem to be able to get the right hashes for this in java, how're you doing it?

(I'm assuming you're asking about how to compute the hash of a code)

Here's what I used for my score fetcher (in Java)

Code Select Expand


public static long getSeedFromString(String str) {
    str = str.toLowerCase().trim();
    String hex = DigestUtils.md5Hex(str).substring(0, 8);
    return Long.parseLong(hex, 16);
}

It uses this module for ease: org.apache.commons.codec.digest.DigestUtils
I use a long (64 bits) since java ints are signed and I needed the full unsigned 32 bits to store the hash without hassle.

I actually wrote my program in C++ since I knew I would need speed and large amounts of memory (I ended up getting about 150k hashes per sec). I used MD5 from here. I can show my source code if that would help, but I'd have to go clean it up first.

(And as a side note, I have successfully completed a reverse mapping of hash to code for all 2^32 seeds. If anyone needs a seed looked up for some reason just ask.)

[Cavemaniac]

If you're curious I've attached the list of all ~45 thousand duplicates I found.

Holy smoke - you're amazing/crazy!

Your next challenges:

The back porch on my house is collapsing - should I re-pile it, or just bodge it up?

I've got this shooting pain in my left arm - could it be a heart attack?

;D

[Echo51]

And thus has the challenge most probably ended since mopa found all the hashes for each and every possible seed :P

[Grauniad]

I think you (Echo51) are the winner for the first duplication found, Mopa42 for the most duplicates. However, by my reckoning we have barely scratched the surface, since there may be more duplicates per map than there are maps. See my first post for my estimation.

[Echo51]

Well there are 2^32 different maps, but strings are limited to 60^however many different symbols you can enter into the field. So you could probably find like 5 unique strings for each map if you would bother ;)

[Kithros]

Well there are 2^32 different maps, but strings are limited to 60^however many different symbols you can enter into the field. So you could probably find like 5 unique strings for each map if you would bother ;)

*MUCH* more than just 5 strings per map - you would have (number of symbols)^60 possible strings, and roughly 2^32 different maps - so even if there were just 32 different symbols (obviously there are more than that - just numbers and letters gives 36 symbols completely ignoring all the strange symbols) you would then have 2^300 different strings ((2^5)^60 = 2^300) - which means you would have on average about 2^268 ((2^300)/(2^32)) duplicates of each map. Since there are more than 32 symbols, the number will be even bigger than that.

[Grauniad]

*Sigh* Yes, initially I calcualted that somewhere on the order of 2 x10¹⁰⁰ strings will result in the same map. Is my first post not clear?

Let me say it in another way. For each and every one of the actual 4 billion code maps, there are two duotrigintillion different code strings that can generate that particular map.

Of course, I may be off by one or two zeros, but whose counting? :)

[Echo51]

More like who cares, we've found plenty of maps with several strings each, why bother hunting for more :D

[Grauniad]

Absolutely. it would be rather tedious to continue.