Shortest program to print "Never gonna give you up..."

http://codegolf.stackexchange.com/questions/6043/were-no-strangers-to-code-golf-you-know-the-rules-and-so-do-i

by lini • 14 years ago

128 19 14 years ago

codegolf.stackexchange.com

ibotty• 14 years ago

the sed one is great!

blauwbilgorgel• 14 years ago

Joke answer

  $h = "549d9635795ef37857e0b3dc02e52e53";
  $v = 0;
  while( $v == 0 ){
    $n = "";
    for( $i=0; $i<1943; $i++ ){
      $n .= chr(rand(0, 127));
    }
    if( md5($n) == $h ){
      echo $n;
      $v = 42;
    }
  }

By the time we have our answer (or a collision), we forgot what the question was.

krisoft• 14 years ago

Is there a way to tell approximately how many 1943 character long string are expected to have the same md5 hash? A lot, or just a few? Or it's not possible to tell because of the properties of md5?

Sorry for all the silly questions, I'm curious, but my cryto knowledge is weak.

simcop2387• 14 years ago

Probably not truly possible to calculate. But if we can probably figure out a rough estimate.

Let's setup what is valid in the string and we can go from there.

  a-z | 26 characters
  A-Z | 26 characters again
  \x20| 1  character, space
  .,' | 3 characters for punctuation
  ()  | 2 characters
  \n  | 1 more character

Now these describe just a string that is very similar to the original pastebin (with a few extra characters). If we were to consider all possible 1943 byte strings it'd be fairly different.

So we've now got that we're looking at strings with 59 distinct characters in them. That means we can consider that it encodes log2[59^1943] bits of information, which comes out to 11429.975..., let's just call that 11430 bits. An md5sum contains 128bits, and we're after ones that match just the string we're after. We've already figured out that there should be 2^11430 possible 1943 character strings. So let's divide the possible choices by the number of possible md5sums and we can get a rough idea.

  (2^11430)/(2^128) => 2^(11430-128) => 2^11302

Throwing this in a calculator since I don't want to flood HN with a gigantic number, that comes out to about 1.74 * 10^3402 possible strings that will match the MD5.

This is just an approximation and I bet I made a mistake on the math somewhere.

nthitz• 14 years ago

Nice touch setting $v = 42

Animus7• 14 years ago

Awesome, I wouldn't have thought of this.

But to pick nits, it could be argued that you're using md5 as a trial/error "compression algorithm" without including its source.

btilly2• 14 years ago

It is only funny because it is true.

Change your loop to only loop while $v < 42, and then when the md5 matches, set $v to be the number of copies of "gonna" in the text. ( * ) Print the final string at the end.

If you had a good random generator then with very high probability this program would be correct, although it is unable to run in any reasonable time.

* There are exactly 42 copies of "gonna" in that text. Did God speaking through Douglas Adams subtly rickroll all of us?

christiangenco• 14 years ago

Could this not also theoretically colide with a string with the same hash and more than 42 occurrences of "gonna"? Better set the flag to `$v==42` just to be safe.

x1• 14 years ago

The thing I find interesting is this simple task highlights a constant problem with programming: clarification. Looking at the utf8 example, who wins, the fewest bytes or the fewest characters? It's always those little details that tend to cause the biggest issues.

Akram• 14 years ago

I wonder how long the program would be if written in Malbolge. http://www.99-bottles-of-beer.net/language-malbolge-995.html

ColinWright2• 14 years ago

597 bytes of Python:

    : d="""ou@on@he@ell@ w@ay it
    : @ otUr@BVna @make4 @ve@'re@ing@t's been@ a@
    : (Ooh@o @ g@
    : YX@ t@ know@nd @
    : N2@ how I'm feelJ
    : @iL4 up@6)E)8giL, n2giL
    : (G@ yX@
    : I justSannaxT47Gotta Munderstand0@eLrP@
    : 
    : We'Lqn eachQ for sClVgzr UarHFchJ butzKxoCshyxCsRInsideSe bothqShaHBoJ V
    : WeqxUBameF9weKPplR@
    : 8g68let4 down8runFrX9a9desert48Mcry8sayBoodbye8tTF lieF9hurt4@WeK nCstrangersxCloLzqxU rulesF9sCdCI
    : A full commitment'sShat I'mxhinkJ ofzSXldn'tBetxhis fromFnyQBuy31A9if4Fsk me7DV'txT me4KxoCbli9tCsee00
    : E,B6)E,B556)1300
    : """
    : for s in 'XVUTSRQPMLKJHFECBzxq9876543210':
    :  a,b=d.split('@',1)
    :  d=b.replace(s,a)
    : print d

I could make it a little better, but could only spend 30 minutes or so.

Added in edit: a small tweak gets it to 594 bytes - not included here.

goatforce5• 14 years ago

"not included here."

Didn't we learn anything from Fermat?

ColinWright2• 14 years ago

OK, 589 bytes:

    : d="""ellU wTay it
    : S otherRConna Qmake4 PveMndL aK'reJingHt's beenFo E gC
    : (OohB
    : Youz txKL q know9
    : N28 how I'm feelH
    : 7iM4 up66)B)8giM, n2giM
    : (G5 you4
    : I justTannaxU47Gotta PuLerstaL03eMrQ2
    : 
    : We'M9n eachR for sElongzr hearFKchH butzJxoEshyxEsSInsideTe both9ThaFCoH on
    : We9xheCameqweJQplS1
    : 8g68let4 down8runKrouLqdesert48Pcry8sayCoodbye8tUK lieqhurt40WeJ nEstrangersxEloMz9xhe rulesqsEdEI
    : A full commitment'sThat I'mxhinkH ofzTouldn'tCetxhis fromKnyRCuy31AL if4Ksk me7Don'txU me4JxoEbliLxEsee00
    : B,C6)B,C556)1300"""
    : for s in'UTSRQPMLKJHFECBzxq9876543210':a,b=d.split(s,1);d=b.replace(s,a)
    : print d

jholman• 14 years ago

You can hardly blame ColinWright; although his tweak is truly marvelous, it is one which this textfield is too narrow to contain.

n-gauge2• 14 years ago

104 bytes:

kapitalx• 14 years ago

no external sources allowed :)

n-gauge2• 14 years ago

Doesn't say that in this thread! (prior to your reply)

ctdonath• 14 years ago

I started writing a solution in Google Blockly, but alas it does not yet save programs, and procedures have incomplete implementation.

Shortest program to print "Never gonna give you up..."

Related Stories