1193: Externalities

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

teelo
Posts: 782
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1193: Externalities

Postby teelo » Tue Apr 02, 2013 12:51 am UTC

So I'm banned, right...
http://en.wikipedia.org/wiki/User_talk:111.69.153.152

This blocked user is asking that his or her block be reviewed:

111.69.153.152 (block log • active blocks • global blocks • autoblocks • contribs • deleted contribs • abuse filter log • creation log • change block settings • unblock • checkuser (log))

Request reason:
I just donated $250 to wikipedia, and Jimmy Wales told me that this is a sufficient bribe to get unbanned and gain ban immunity for life.


*grabs popcorn*

bugstomper
Posts: 40
Joined: Mon Aug 18, 2008 6:03 am UTC

Re: 1193: Externalities

Postby bugstomper » Tue Apr 02, 2013 12:55 am UTC

KarMann wrote:No, it doesn't mean that they have hashed that many. That's just a rough average of how many they ought to have hashed to get there


I guess you are right - If you assume that the top ten contenders in the list are running about the same number of trials per second, then it is not unreasonable for one of them to luck on a result in one-tenth the time that you would expect just from the average. In other words, speaking very roughly, if on the average it should take 10 trillion trials to get a result, then when 10 schools are working on it all at once at the same rate you would expect one of them to hit the result after they have done only 1 trillion trials, because that means that 10 trillion hashes have been tried overall.

I guess all we can be pretty sure about it is that the schools who are swapping for the top three or five places are probably the ones who are computing the most hashes per second and are probably all doing so at about the same rate. We can also be pretty sure that at least some tens of trillions of hashes have been computed so far.

bugstomper
Posts: 40
Joined: Mon Aug 18, 2008 6:03 am UTC

Re: 1193: Externalities

Postby bugstomper » Tue Apr 02, 2013 1:01 am UTC

pitareio wrote:Took about 20 million tries to get down to 428


Thanks for helping me validate my calculations, since I don't really think I know what I am talking about :)

My very rough approximation for probability of getting a score of n is 1 out of 1/erfc(((512 - n)/16)/sqrt(2))/2)
which google calculator says for n=428 rounds to 13,149,312 which is close enough to your 20 million to make me happy.

Edit: I just noticed the typo long after I posted this, I had n instead of (512 - n) there, i.e., it should be how much better you did than the expected average of 512.
Last edited by bugstomper on Wed Apr 03, 2013 12:50 am UTC, edited 1 time in total.

User avatar
Latent22
Posts: 622
Joined: Mon Apr 01, 2013 11:57 pm UTC
Location: NZ

Re: 1193: Externalities

Postby Latent22 » Tue Apr 02, 2013 1:11 am UTC

Code: Select all

from skein import skein1024
import string
import random

def bitCount(int_type):
   count = 0
   while (int_type):
      count += (int_type & 1)
      int_type >>= 1
   return count

def hexxor(a, b):    # xor two hex strings of the same length
    return "".join(["%x" % (int(x,16) ^ int(y,16)) for (x, y) in zip(a, b)])

g='5b4da95f5fa08280fc9879df44f418c8f9f12ba424b7757de02bbdfbae0d4c4fdf9317c80cc5fe04c6429073466cf29706b8c25999ddd2f6540d4475cc977b87f4757be023f19b8f4035d7722886b78869826de916a79cf9c94cc79cd4347d24b567aa3e2390a573a373a48a5e676640c79cc70197e1c5e7f902fb53ca1858b6'
c=''
d=1024
for x in range(0,100000):
   a=bytes(''.join(random.choice(string.printable) for x in range(100)), 'utf-8');b=bitCount(int(hexxor(skein1024(a, digest_bits=1024).hexdigest(),g),16));c = a if b < d else c;d = b if b < d else d


c
d


here is my quick and dirty python program to try random hash's. Never really used python before so its fun to learn anyway. Their are so many things that are bad about this code I'm sorry. have to keep running the for loop and the line below again to make it do another batch. Need python and pyskien to use

Michael
Last edited by Latent22 on Tue Apr 02, 2013 1:51 am UTC, edited 1 time in total.

User avatar
huntster
Posts: 1
Joined: Tue Apr 02, 2013 12:38 am UTC

Re: 1193: Externalities

Postby huntster » Tue Apr 02, 2013 1:19 am UTC

I gotta say, I find it hilarious that some commenters think that Wiki admins get paid for their work. They are volunteers, and will not see a dime of the money donated. That money goes to the Wikimedia Foundation to pay for servers/tech, education outreach, etc. As a wiki admin, however, I feel kind of bad...I've been blissfully unaware of this happening, as none of the hundreds of pages I watch have seen any of this editing/vandalism/stupidity. Ah well.

Also, if this was coordinated with the Foundation, I'm highly disappointed in them. No notification was ever given to the community beforehand that I'm aware of, which says they cared more about the possibility of donations rolling in than keeping their editor base happy. Rather sad, considering the amount donated (while appreciated) is minuscule compared to the $10 million donated during the regular fundraiser effort.

User avatar
FunkyTuba
Posts: 6
Joined: Wed Nov 11, 2009 3:59 pm UTC

Re: 1193: Externalities

Postby FunkyTuba » Tue Apr 02, 2013 1:32 am UTC

Is there any one place where each company that has been discovered is listed? Was going to try for Berkshire Hathaway Dollar Tree at some point but I'd rather do one we haven't seen yet.
Last edited by FunkyTuba on Tue Apr 02, 2013 1:45 am UTC, edited 1 time in total.

vollkorn
Posts: 2
Joined: Mon Apr 01, 2013 11:50 pm UTC

Re: 1193: Externalities

Postby vollkorn » Tue Apr 02, 2013 1:33 am UTC

SecondTalon wrote:From the third post as I'm disapproving it

vollkorn wrote:Darn, do my posts need to be approved first or am I too stupid to use forums? I think I know why I don't really like forums...


The message you get when you post your first few posts literally tells you your messages are going in a queue.

So yes, your first two need approval. And if you'd read the rules, you'd also know why your URL links keep getting barked at as spam and rejected.

As for how to tell Randall ... he doesn't read the forums. Hasn't in years. And he doesn't take submissions.

So.. uh.. contact AT xkcd DOT com? Or press AT xkcd DOT com?


Ah, contact AT xkcd DOT com wasn't mentioned on xkcd's about page so I just tried sending an email there. Thanks for this advice.
Also I only read the FAQ and found only this about spam rules at topic number f=10 t=98046 (ARGH, I hate not to be able to post links!) But only after I ran into problems since it wasn't mentioned noticeably in the registration progress. So I guess I wasn't good enough at collecting all the information needed. Yes, I do not have experience with forums.
And yes, I didn't read the message after the post until the third time b/c it wasn't marked as important by a yellow question mark or similar as is expect for important messages. My mind seems to filter out messages that look like expected confirmations.
So sorry again for being an unexperienced forum user. And thanks for the help.

User avatar
FunkyTuba
Posts: 6
Joined: Wed Nov 11, 2009 3:59 pm UTC

Re: 1193: Externalities

Postby FunkyTuba » Tue Apr 02, 2013 1:40 am UTC

Just noticed I'm looking at the wrong list ... it's the nasdaq 100 not the fortune 100 ... carry on

bugefun
Posts: 4
Joined: Mon Nov 12, 2012 5:15 pm UTC

Re: 1193: Externalities

Postby bugefun » Tue Apr 02, 2013 1:41 am UTC

There is also a strange competition going on for last place. I entered an unused domain and used "b" for the data to hash (it gives 550 bits wrong). I was in last for a few seconds until the domain jumped up to 482 bits wrong.

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: 1193: Externalities

Postby ThemePark » Tue Apr 02, 2013 1:53 am UTC

So now the mouseover text uses hints for the current Wikipedia article. But did it say specifically what article it was looking at before then?

And also, as some people have posted it's limited to certain TLDs. But considering the full names show up in the comic, wouldn't it be further limited to certain universities, that he has in a list on the server?

Edit:
Seems like he did add a list at some point, or he checks whether the urls actually exist. Tried some of the last ones and it didn't recognize them as schools.

bugefun, that's just because someone else used the same domain as you, but found a better hash.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

collinstocks
Posts: 11
Joined: Wed Apr 02, 2008 7:52 pm UTC

Re: 1193: Externalities

Postby collinstocks » Tue Apr 02, 2013 2:03 am UTC

Currently, my school is doing better than this (cooper.edu), but I thought I'd give away a little something:
Spoiler:
c975e63a883660ebfc374612b42c0651

That gets you 421.

Adamah
Posts: 85
Joined: Mon Oct 27, 2008 1:40 am UTC
Location: DC

Re: 1193: Externalities

Postby Adamah » Tue Apr 02, 2013 2:15 am UTC

Has anyone gotten the C implementation to match the almamater results? I've spent hours trying to get it working but my results still don't match. I would love to see just a short program that demonstrates a successful hash. I have no clue why there isn't one included with the source code.

bugefun
Posts: 4
Joined: Mon Nov 12, 2012 5:15 pm UTC

Re: 1193: Externalities

Postby bugefun » Tue Apr 02, 2013 2:21 am UTC

ThemePark wrote:So now the mouseover text uses hints for the current Wikipedia article. But did it say specifically what article it was looking at before then?

And also, as some people have posted it's limited to certain TLDs. But considering the full names show up in the comic, wouldn't it be further limited to certain universities, that he has in a list on the server?

Edit:
Seems like he did add a list at some point, or he checks whether the urls actually exist. Tried some of the last ones and it didn't recognize them as schools.

bugefun, that's just because someone else used the same domain as you, but found a better hash.

Before I entered it I made sure the domain was not on the list. Then I entered the 550-bit hash and quickly reloaded the list, the domain was now at the bottom. I reloaded it a few seconds later and it was much farther up at 482 bits. There is some script repeatedly checking the list and if any domains show up below a certain threshold, it submits a better hash to get them off the bottom.


pitareio wrote:Not sure if it's just me, but the font substition works with Chrome, not with Firefox:
Spoiler:
Image

Image

(note : due to madness, these might not be the actual browser names)

It works in Firefox if you are on xkcd.com but not if you are on www.xkcd.com. On Chrome it works on both.

bugstomper
Posts: 40
Joined: Mon Aug 18, 2008 6:03 am UTC

Re: 1193: Externalities

Postby bugstomper » Tue Apr 02, 2013 2:25 am UTC

Latent22 wrote:here is my quick and dirty python program to try random hash's. Never really used python before so its fun to learn anyway. Their are so many things that are bad about this code I'm sorry. have to keep running the for loop and the line below again to make it do another batch. Need python and pyskien to use


Here are some suggestions - Not that they would get you into the top ten, but I feel like thinking out loud about this :)

There is no need to compute a random input every time. Since any input is likely to produce a good or bad result as any other, all you really have to do is to pick some random starting point and then you are just as well off incrementing by one for the next input to the hash. Also, while in theory you are exploring a 1024 bit search space, and you would have to if your goal was to find an exact match for the hash, realistically you don't have time for trying 2^1024 numbers. So start out with deciding what is the maximum number of trials you are going to ever get to. Let's very optimistically say you are going to generate a trillion trials per second for a year. That is "only" about 1e19 trials in all. Since the hash function is a good one, you can choose any 1e19 numbers you want for those inputs. It might as well be all the 19 digit base 10 integers. So your simpler loop could start by picking a 19 digit number at random, then incrementing it and feeding it to the hash. I just now realized that 1e19 fits in 64 bit. You can get equivalent results by starting with a random 64 bit string and loop hashing it and doing a 64 bit increment. That should be quite fast. You could distribute the task amongst many processors by either distributing a list of evenly separated 64 bit strings to each of them, or have each one generate a random 64 bit initial string and rely on probability to avoid overlap between the values processed by them in the time you have available to generate trials.

chris857
Posts: 100
Joined: Thu Dec 02, 2010 5:04 pm UTC

Re: 1193: Externalities

Postby chris857 » Tue Apr 02, 2013 2:43 am UTC

Has anyone been trying strongly for the worst hash, and keeping a list? "b" was posted earlier at 550 bits; I just found that "anti-clockwise" is 555 bits.

And PS, the dog grew again.

uaswell
Posts: 6
Joined: Fri Jun 15, 2012 4:02 pm UTC

Re: 1193: Externalities

Postby uaswell » Tue Apr 02, 2013 2:46 am UTC

I'm assuming no one has found the wikipedia article it is currently looking at because the comic hasn't changed for a while.

User avatar
(╯°□°)╯︵ ┻━┻
As the Arbiter of Everything, Everything Sucks
Posts: 8314
Joined: Mon Jun 18, 2007 6:17 pm UTC
Location: I FUCKING MOVED TO THE WOODS

Re: 1193: Externalities

Postby (╯°□°)╯︵ ┻━┻ » Tue Apr 02, 2013 2:47 am UTC

I hope that someone who's *not* a wiki vandal changes the XKCD page to reflect how much money XKCD generated for Wikimedia in the 24 hours after it was posted. I'm sure I'll want to refer to that later, but I won't be awake.
Heyyy baby wanna kill all humans?

PotHotato
Posts: 1
Joined: Tue Apr 02, 2013 2:36 am UTC

Re: 1193: Externalities

Postby PotHotato » Tue Apr 02, 2013 2:51 am UTC

Code: Select all

import skein
from random import choice
 
target = '5b4da95f5fa08280fc9879df44f418c8f9f12ba424b7757de02bbdfbae0d4c4fdf9317c80cc5fe04c6429073466cf29706b8c25999ddd2f6540d4475cc977b87f4757be023f19b8f4035d7722886b78869826de916a79cf9c94cc79cd4347d24b567aa3e2390a573a373a48a5e676640c79cc70197e1c5e7f902fb53ca1858b6'
 
def bitcount(v):
    if v > 0:
        return (v & 1) + bitcount(v>>1)
    else:
        return 0
 
def check_hash(hash):
    hashed = skein.skein1024(hash.encode('ascii')).hexdigest()
    difference = 0
    for idx, char in enumerate(target):
        difference += bitcount(int(char, 16) ^ int(hashed[idx], 16))
    return difference
     
chars = 'abcdefghijklmnopqrstuvwxyz1234567890'
 
def random_string(length):
    c = ''
    for i in range(length):
        c += choice(chars)
    return c

best = 1025
for i in range(10, 100):
    for j in range(100000):
        s = random_string(i)
        r = check_hash(s)
        if r < best:
            best = r
            print(s, r)


Just a quick code using python

any suggestions for ways to improve it are welcome... I'm a relative newbie at python but hopefully this isn't too bad.

For anyone looking, I have a 429 so far
Spoiler:
gg9mfduewbagu72bg6f9ktm7bmkzp2ddtk

Hexxeh
Posts: 2
Joined: Tue Apr 02, 2013 2:53 am UTC

Re: 1193: Externalities

Postby Hexxeh » Tue Apr 02, 2013 2:55 am UTC

Posted a nice entry for my university in at 11th using a threaded C implementation.

Curious as to what approach the top 10 are taking, or whether they've just been at it a while and hit lucky with a similar approach.

chris857
Posts: 100
Joined: Thu Dec 02, 2010 5:04 pm UTC

Re: 1193: Externalities

Postby chris857 » Tue Apr 02, 2013 3:00 am UTC

uaswell wrote:I'm assuming no one has found the wikipedia article it is currently looking at because the comic hasn't changed for a while.


I've seen three articles edited for this clue, but the traffic is very light compared to other clues.

uaswell
Posts: 6
Joined: Fri Jun 15, 2012 4:02 pm UTC

Re: 1193: Externalities

Postby uaswell » Tue Apr 02, 2013 3:03 am UTC

chris857 wrote:
uaswell wrote:I'm assuming no one has found the wikipedia article it is currently looking at because the comic hasn't changed for a while.


I've seen three articles edited for this clue, but the traffic is very light compared to other clues.

Which ones have you seen? I've already figured out its not "Inflation."

collinstocks
Posts: 11
Joined: Wed Apr 02, 2008 7:52 pm UTC

Re: 1193: Externalities

Postby collinstocks » Tue Apr 02, 2013 3:13 am UTC

Adamah wrote:Has anyone gotten the C implementation to match the almamater results? I've spent hours trying to get it working but my results still don't match. I would love to see just a short program that demonstrates a successful hash. I have no clue why there isn't one included with the source code.


Make sure you have version 1.3 of the library. It is hidden most of the way down the http://www.skein-hash.info/downloads page.

C code (this agrees with Randall's hash of the empty string):
Spoiler:

Code: Select all

#include <stdlib.h>
#include <stdio.h>

#include "skein.h"



int main (int argc, char *argv[]) {
    size_t i;
    char c;
    u08b_t hashval[128];
    Skein1024_Ctxt_t ctx;
    Skein1024_Init(&ctx, 1024);
    Skein1024_Update(&ctx, "", 0);
    Skein1024_Final(&ctx, hashval);
    for (i = 0; i < 128; ++i) {
        c = hashval[i];
        putchar("0123456789abcdef"[(c >> 4) & 0xf]);
        putchar("0123456789abcdef"[c & 0xf]);
    }
    putchar('\n');
    return 0;
}

User avatar
Latent22
Posts: 622
Joined: Mon Apr 01, 2013 11:57 pm UTC
Location: NZ

Re: 1193: Externalities

Postby Latent22 » Tue Apr 02, 2013 3:13 am UTC

bugstomper wrote:
Latent22 wrote:here is my quick and dirty python program to try random hash's. Never really used python before so its fun to learn anyway. Their are so many things that are bad about this code I'm sorry. have to keep running the for loop and the line below again to make it do another batch. Need python and pyskien to use


Here are some suggestions - Not that they would get you into the top ten, but I feel like thinking out loud about this :)

There is no need to compute a random input every time. Since any input is likely to produce a good or bad result as any other, all you really have to do is to pick some random starting point and then you are just as well off incrementing by one for the next input to the hash. Also, while in theory you are exploring a 1024 bit search space, and you would have to if your goal was to find an exact match for the hash, realistically you don't have time for trying 2^1024 numbers. So start out with deciding what is the maximum number of trials you are going to ever get to. Let's very optimistically say you are going to generate a trillion trials per second for a year. That is "only" about 1e19 trials in all. Since the hash function is a good one, you can choose any 1e19 numbers you want for those inputs. It might as well be all the 19 digit base 10 integers. So your simpler loop could start by picking a 19 digit number at random, then incrementing it and feeding it to the hash. I just now realized that 1e19 fits in 64 bit. You can get equivalent results by starting with a random 64 bit string and loop hashing it and doing a 64 bit increment. That should be quite fast. You could distribute the task amongst many processors by either distributing a list of evenly separated 64 bit strings to each of them, or have each one generate a random 64 bit initial string and rely on probability to avoid overlap between the values processed by them in the time you have available to generate trials.


yeah there are many many ways to generate the hash to check. It seems to me though that if he has set a random input string then while we can slowly get closer it would take till the end of the universe to stumble on a hash that matches exactly. This may be his purpose that it is not possible to solve it and all you can do is hope to find a closer and closer hash. The other option is he has set a human generated guessable input and then it would be possible to use dictionary attacks etc to find the exact answer. The funny thing if he did make it guessable instead of random is that up until the moment you found the correct input you would still be 300+ bits wrong on every single guess and suddenly you are at zero. So that would suggest that for this to work it would have to be very random. And if its random then my guess is that someone will eventually stumble on a crazy lucky guess that is so much closer than anyone else at which point most others may give up as the chance of them bettering it is so low. Or maybe one of our great grand children will stumble on this again in the future and break it with the chip in his dog's bark collar...

User avatar
SecondTalon
SexyTalon
Posts: 26519
Joined: Sat May 05, 2007 2:10 pm UTC
Location: Louisville, Kentucky, USA, Mars. HA!
Contact:

Re: 1193: Externalities

Postby SecondTalon » Tue Apr 02, 2013 3:14 am UTC

vollkorn wrote:
SexyTalon wrote:From the third post as I'm disapproving it

vollkorn wrote:Darn, do my posts need to be approved first or am I too stupid to use forums? I think I know why I don't really like forums...


The message you get when you post your first few posts literally tells you your messages are going in a queue.

So yes, your first two need approval. And if you'd read the rules, you'd also know why your URL links keep getting barked at as spam and rejected.

As for how to tell Randall ... he doesn't read the forums. Hasn't in years. And he doesn't take submissions.

So.. uh.. contact AT xkcd DOT com? Or press AT xkcd DOT com?


Ah, contact AT xkcd DOT com wasn't mentioned on xkcd's about page so I just tried sending an email there. Thanks for this advice.
Also I only read the FAQ and found only this about spam rules at topic number f=10 t=98046 (ARGH, I hate not to be able to post links!) But only after I ran into problems since it wasn't mentioned noticeably in the registration progress. So I guess I wasn't good enough at collecting all the information needed. Yes, I do not have experience with forums.
And yes, I didn't read the message after the post until the third time b/c it wasn't marked as important by a yellow question mark or similar as is expect for important messages. My mind seems to filter out messages that look like expected confirmations.
So sorry again for being an unexperienced forum user. And thanks for the help.

Yellow question mark or other similar flashing messages.

... might work. Or maybe we need a copy-protection style Prove You're Human question.... "What's the fifth word of the eighth rule" sort of thing.
heuristically_alone wrote:I want to write a DnD campaign and play it by myself and DM it myself.
heuristically_alone wrote:I have been informed that this is called writing a book.

chris857
Posts: 100
Joined: Thu Dec 02, 2010 5:04 pm UTC

Re: 1193: Externalities

Postby chris857 » Tue Apr 02, 2013 3:18 am UTC

uaswell wrote:
chris857 wrote:
uaswell wrote:I'm assuming no one has found the wikipedia article it is currently looking at because the comic hasn't changed for a while.


I've seen three articles edited for this clue, but the traffic is very light compared to other clues.

Which ones have you seen? I've already figured out its not "Inflation."

Lead poisoning, Fall of the Western Roman Empire, Decline of the Roman Empire
I should probably make it difficult to prevent vandalism (as I like to positively contribute to Wikipedia), so here are the hashes of the titles:

Code: Select all

399eab71b1f67277f3d01f5f2cf2c45538082cbaddeb0ca16ef8cb4a00d760bf01b3277f5dfe09f62e618aee4579c7f3dbfe49c4ca80f82a7ded29755e0999afa714098b44659423fe716f3f05e6268099aa8867a8e808e78311abba15dca09ebb0640e4409dfeb696c3a2163391f8cb973c3d8a8ad2752772b19744c1d1e381

c4a04ac829166f417ebf4a6a530eb9b945fe3b139bc342a79bb7742a81eeb2ad67d72b18d55a1065f3ec6256c830a108d34e750c78317fbf6c2c26856d4fdf1d0112a73062e3b73de8cb302b6897004a2062d22a8e8b7cec8f8278e267b3906cd36a562499320056704a052ecd88b2e9124af45d22ae9a33d55231a3ebce662c

0fb90eaa9c8ef99b8de97c3f774075f0d231959c00493aced7204830a7e01e5fc8a6c6c09cb0d0d3081712bec01dfa0748896fdbb6db33ac805d991d7239f3ae99cd40606c22d42007fd1624b0feff9ff8b95106ad56e987bebb7669eee48d8ea9041772843290bce4138dc6e4067602a362527f3fa3799bdc85644645626ce0

collinstocks
Posts: 11
Joined: Wed Apr 02, 2008 7:52 pm UTC

Re: 1193: Externalities

Postby collinstocks » Tue Apr 02, 2013 3:18 am UTC

PotHotato wrote:

Code: Select all

import skein
from random import choice
 
target = '5b4da95f5fa08280fc9879df44f418c8f9f12ba424b7757de02bbdfbae0d4c4fdf9317c80cc5fe04c6429073466cf29706b8c25999ddd2f6540d4475cc977b87f4757be023f19b8f4035d7722886b78869826de916a79cf9c94cc79cd4347d24b567aa3e2390a573a373a48a5e676640c79cc70197e1c5e7f902fb53ca1858b6'
 
def bitcount(v):
    if v > 0:
        return (v & 1) + bitcount(v>>1)
    else:
        return 0
 
def check_hash(hash):
    hashed = skein.skein1024(hash.encode('ascii')).hexdigest()
    difference = 0
    for idx, char in enumerate(target):
        difference += bitcount(int(char, 16) ^ int(hashed[idx], 16))
    return difference
     
chars = 'abcdefghijklmnopqrstuvwxyz1234567890'
 
def random_string(length):
    c = ''
    for i in range(length):
        c += choice(chars)
    return c

best = 1025
for i in range(10, 100):
    for j in range(100000):
        s = random_string(i)
        r = check_hash(s)
        if r < best:
            best = r
            print(s, r)


Just a quick code using python

any suggestions for ways to improve it are welcome... I'm a relative newbie at python but hopefully this isn't too bad.

For anyone looking, I have a 429 so far
Spoiler:
gg9mfduewbagu72bg6f9ktm7bmkzp2ddtk


This is the code I've been using:
Spoiler:

Code: Select all

#!/usr/bin/python3



import sys
import multiprocessing
from multiprocessing import Pool
import skein
import random
rand = random.SystemRandom()



baseline = int('''
    5b4da95f5fa08280fc9879df44f418c8f9f12ba424b7757de02bbdfbae0d4c4fdf931
    7c80cc5fe04c6429073466cf29706b8c25999ddd2f6540d4475cc977b87f4757be023
    f19b8f4035d7722886b78869826de916a79cf9c94cc79cd4347d24b567aa3e2390a57
    3a373a48a5e676640c79cc70197e1c5e7f902fb53ca1858b6
'''.replace(' ', '').replace('\n', '').replace('\r', ''), 0x10)



def run (number):
   word = hex(number)[2:].encode('utf-8', 'replace')
   hashval = int(skein.skein1024(word).hexdigest(), 0x10)
   score = bin(hashval ^ baseline)[2:].count('1')
   return word, score



def sequence ():
    randstart = rand.getrandbits(128)
    for i in range(randstart, randstart + (1 << 16)):
        yield i



if __name__ == '__main__':
    pool = Pool(multiprocessing.cpu_count())
    bestword = None
    bestscore = 1024
    while True:
        result = pool.map(run, sequence())
        words, scores = zip(*result)
        bestroundscore = min(scores)
        if bestroundscore < bestscore:
            bestscore = bestroundscore
            bestword = words[scores.index(bestroundscore)]
            output = '%s : %i' % (bestword, bestscore)
            print(output)
            print(output, file = sys.stderr)



So far, the best I've gotten is 399 (see cooper.edu on the list). It's taken about 500 virtual-core-hours (I had it running on 12 computers, each with 8 cores).

davidy22
Posts: 39
Joined: Sat Jan 26, 2013 9:29 am UTC

Re: 1193: Externalities

Postby davidy22 » Tue Apr 02, 2013 3:24 am UTC

FunkyTuba wrote:Is there any one place where each company that has been discovered is listed? Was going to try for Berkshire Hathaway Dollar Tree at some point but I'd rather do one we haven't seen yet.


Yes, actually! The explainxkcd wiki! We've done a good job of documenting frames already, still chugging away right now.

sygnathid
Posts: 7
Joined: Fri Mar 08, 2013 4:45 pm UTC

Re: 1193: Externalities

Postby sygnathid » Tue Apr 02, 2013 3:25 am UTC

Slide #4 is amazing. ;) It took me a few seconds to understand what was happening...

zxcs
Posts: 3
Joined: Wed Jan 18, 2012 6:03 am UTC

Re: 1193: Externalities

Postby zxcs » Tue Apr 02, 2013 3:27 am UTC

collinstocks wrote:So far, the best I've gotten is 399 (see cooper.edu on the list). It's taken about 500 virtual-core-hours (I had it running on 12 computers, each with 8 cores).



your resources make me jealous. i only have 412 using my laptop

collinstocks
Posts: 11
Joined: Wed Apr 02, 2008 7:52 pm UTC

Re: 1193: Externalities

Postby collinstocks » Tue Apr 02, 2013 3:31 am UTC

zxcs wrote:
collinstocks wrote:So far, the best I've gotten is 399 (see cooper.edu on the list). It's taken about 500 virtual-core-hours (I had it running on 12 computers, each with 8 cores).



your resources make me jealous. i only have 412 using my laptop

Well, they're university resources, but they weren't really being used, so...

User avatar
Icalasari
Posts: 107
Joined: Wed May 26, 2010 5:11 am UTC

Re: 1193: Externalities

Postby Icalasari » Tue Apr 02, 2013 3:33 am UTC

if I was rich, I'd donate $10,000,000 just to see the dog get massive

RainbowDashh
Posts: 4
Joined: Wed Mar 27, 2013 5:12 am UTC

Re: 1193: Externalities

Postby RainbowDashh » Tue Apr 02, 2013 4:05 am UTC

Icalasari wrote:if I was rich, I'd donate $10,000,000 just to see the dog get massive


You would make Wikimedia very rich and will make some people sickened on your reason of donation.

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: 1193: Externalities

Postby phlip » Tue Apr 02, 2013 4:12 am UTC

Icalasari wrote:if I was rich, I'd donate $10,000,000 just to see the dog get massive

Conversely, though, if you were the sort of person who'd pay $10M just to see a drawing of a dog get massive, you probably wouldn't be rich, or at the very least wouldn't stay that way long.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

DBPZ
Posts: 28
Joined: Mon Aug 31, 2009 5:17 am UTC

Re: 1193: Externalities

Postby DBPZ » Tue Apr 02, 2013 4:23 am UTC

I have generated tons of CO2 this morning, merely for some valueless hash values. Now I just reached 407. The guys <400 must have generated thousands of tons of the gas.

Good work XKCD!

xymostech
Posts: 6
Joined: Wed Mar 24, 2010 5:06 am UTC

Re: 1193: Externalities

Postby xymostech » Tue Apr 02, 2013 4:31 am UTC

DBPZ wrote:I have generated tons of CO2 this morning, merely for some valueless hash values. Now I just reached 407. The guys <400 must have generated thousands of tons of the gas.


We just reached 402, CO2 a-blazin. Anyone have any idea when this contest will stop? I imagine my department won't be happy with me hogging all the computers for the next indefinite period of time.

User avatar
walkerm930
Posts: 69
Joined: Wed Apr 07, 2010 3:53 am UTC
Location: Canada: Ontario: Toronto

Re: 1193: Externalities

Postby walkerm930 » Tue Apr 02, 2013 4:31 am UTC

Is it just me or is it almost always Qualcomm? Anybody think they know why?
In the gospel according to trig there are 3 primary rules: sin θ = x/h , cos θ = y/h and tan θ = x/y. These rules are not open to interpretation and are to be treated as law.

DBPZ
Posts: 28
Joined: Mon Aug 31, 2009 5:17 am UTC

Re: 1193: Externalities

Postby DBPZ » Tue Apr 02, 2013 4:39 am UTC

xymostech wrote:
DBPZ wrote:I have generated tons of CO2 this morning, merely for some valueless hash values. Now I just reached 407. The guys <400 must have generated thousands of tons of the gas.


We just reached 402, CO2 a-blazin. Anyone have any idea when this contest will stop? I imagine my department won't be happy with me hogging all the computers for the next indefinite period of time.


I'm using 10 cpus in a super at institute, and 14 cpus at home. The institute cpus have found nothing.

Is there any gpgpu or meet-at-middle solutions? It's boring to just buy/rent/"borrow" cpus and do the stupid exhaustive search.

Tigga
Posts: 10
Joined: Fri Oct 10, 2008 7:57 pm UTC

Re: 1193: Externalities

Postby Tigga » Tue Apr 02, 2013 4:42 am UTC

Stuck on 406... have been for three hours. It's very depressing.

I seem to be getting ~250 thousand hashes per second calculated per core using my C implementation, currently running on 16 cores, so about 4 million hashes/second. Should I be looking to optimise? What are other people getting?

A GPGPU solution certainly seems possible, but I can't find a library, so it'd have to be coded. I wouldn't be suprised if that's what some of the very top people are doing by now. I couldn't say for sure though - I don't know the algorithm well enough to be able to say if GPGPU would work well on it.

xymostech
Posts: 6
Joined: Wed Mar 24, 2010 5:06 am UTC

Re: 1193: Externalities

Postby xymostech » Tue Apr 02, 2013 4:46 am UTC

Tigga wrote:I seem to be getting ~250 thousand hashes per second calculated per core using my C implementation, currently running on 16 cores, so about 4 million hashes/second. Should I be looking to optimise? What are other people getting?


Just timed it, that's about what I'm getting. I'm running it on significantly more cores, though (about 220 in total). I'd imagine that some of the best ones are just using a lot more computers. For example, a couple of my machines are amazon instances, 50 cents an hour for 8 cores. If you ran about 100 of those, it'd run pretty fast.

DBPZ
Posts: 28
Joined: Mon Aug 31, 2009 5:17 am UTC

Re: 1193: Externalities

Postby DBPZ » Tue Apr 02, 2013 4:48 am UTC

Tigga wrote:Stuck on 406... have been for three hours. It's very depressing.

I seem to be getting ~250 thousand hashes per second calculated per core using my C implementation, currently running on 16 cores, so about 4 million hashes/second. Should I be looking to optimise? What are other people getting?

A GPGPU solution certainly seems possible, but I can't find a library, so it'd have to be coded. I wouldn't be suprised if that's what some of the very top people are doing by now. I couldn't say for sure though - I don't know the algorithm well enough to be able to say if GPGPU would work well on it.


The 407 was actually an accident -- the second best I reached was 412.

My program searches 100K values a second at a single AMD opt 854 CPU. I bought the machine 2 yrs ago from ebay, but the machine must have been built before 2005. This is the best CPU I have. The library I'm using is skein3fish.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Google [Bot], Rule110 and 46 guests