Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Kolmogorov complexity of a string s is defined as the length of the shortest program P that outputs s. If the length of P is shorter than the length of s, then s is said to be compressible, otherwise s is incompressible. Most strings are incompressible ...

Write the shortest program that outputs this string (without spaces and without newlines):

d9 a6 b6 33 56 a7 95 4b 29 b0 ac 7f 2a aa 6d 19 b8 4b 4c f8 b6 2a ac 95 
a1 4b 4e a5 9d b3 e7 c9 4c 49 59 ec 94 b3 aa 6c 93 8f 11 5a 4d 39 75 82 
ec ea 24 cc d3 2d c3 93 38 4e b7 a6 0d d2 b5 37 23 54 ad 1b 79 aa 6e 49 
55 52 94 5a a7 3a 6a e9 e4 52 cd 2d 79 ad c6 12 b5 99 5b b4 76 51 17 4e 
94 f3 9a a2 e7 15 6a 55 14 4d 4e 4a a3 5c 2f ab 63 cc b5 a6 a4 92 96 8a 
2e c3 d8 88 9b 8c a9 16 f5 33 22 5b a2 e2 cc 1b 27 d4 e8 db 17 a4 39 85 
ca aa 5b 4f 36 24 d3 c6 f6 94 ad d7 0f 71 24 e1 b1 c5 ef 65 35 6c 8d d7 
1a 87 1e 25 df 5d c0 13 b2 6f 5a 57 28 98 bd 41 66 04 ed a2 52 c9 ac 83 
b3 6c 56 7e d1 c6 cc 53 4a 62 c5 59 a9 b2 d4 af 22 a5 a9 f4 b2 99 23 32 
f8 fb ae 48 6a 8a 9a b5 46 7a 36 59 9f 92 d3 25 b5 19 bd 8a 4a 49 62 a5 
e4 59 fb e5 ba a2 35 dd a9 36 1d a9 c9 69 89 77 6a b2 34 2d 1d 22 61 c5 
c2 66 1c e2 76 74 52 a5 d9 84 b9 8a a6 b5 14 ec 29 58 b2 bc 96 16 16 48 
f5 c5 bd 2f 32 1b 3d 4f 4b 2e b2 6b 9a d9 32 a4 4b 5c bc 92 b7 b3 26 39 
fa 42 2d 64 ed 1a 79 49 4c a3 b7 85 b2 a6 e2 8c d9 55 90 e1 a8 87 4b 60 
a6 e1 ba c4 bb ec 32 39 76 90 a6 b4 c6 65 79 61 91 aa 3d 54 b7 18 3d 15 
4b 06 db 30 8a 4d 4a a1 35 75 5d 3b d9 98 ac 55 5b 10 dd b3 e2 cc f1 5e 
b3 2b 53 90 b6 ee 2b ac 8f 88 8d 95 5a 75 df 59 2d 1c 5a 4c e8 f4 ea 48 
b9 56 de a0 92 91 a9 15 4c 55 d5 e9 3a 76 8e 04 ba e7 b2 aa e9 ab 2a d6 
23 33 45 3d c4 e9 52 e3 6a 47 50 ba af e4 e5 91 a3 14 63 95 26 b3 8b 4c 
bc aa 5a 92 7a ab ad a6 db 53 2e 97 06 6d ba 3a 66 49 4d 95 d7 65 c2 aa 
c3 1a 92 93 3f ca c2 6c 2b 37 55 13 c9 88 4a 5c 62 6b a6 ae cc de 72 94 

The output should look like:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Note: no user input is allowed, nor web access, nor libraries (except the one required for printing the output).

Edit I: the sequence seems random ... but it turns out to be highly compressible handling a little bit of prime numbers ...

Edit II: Well done! I'll review the answers in the next hours, then assign the bounty. This is my idea on how it could be solved:

  1. If you try to compress the data you don't go far away ...
  2. In internet you can find the (well-known?) On-Line Encyclopedia of Integer Sequences (OEIS) ;
  3. trying the first hexadecimal digits d9, a6, b6, 33, ... (or their decimal representation) give no result;
  4. but if you convert the numbers to binary (1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) and searching them on OEIS, you get this result.
  5. As noted by Claudiu, I also gave a little hint in the question (Edit I above) ... :-)

The winner is: Peter Taylor (GolfScript, 50), with a special mention for Claudiu (Python, 92), the first who "solved" it.

share|improve this question
2  
How is this more interesting than other komogorov-complexity questions? –  Doorknob Mar 26 at 12:07
2  
@Doorknob: perhaps nothing ... at least until someone will post an answer :-) –  Marzio De Biasi Mar 26 at 12:13
5  
Is this supposed to be a game of "Guess the constant"? –  Peter Taylor Mar 26 at 12:26
7  
Don't give the solution! People are working on it :-) –  Mau Mar 26 at 14:37
3  
I think the contest should be in two parts. First part is a prize given to those who found the answer. Second part is a prize given to those who really know how to compress the code and generate the smallest. Right now, it's more of a "guess my algorithm" question, which excludes dullards like me, but also real code golfing pros, (which I'm not either), and those who know APL and the other terse languages (still not me). –  Yimin Rong Mar 27 at 14:10

9 Answers 9

up vote 10 down vote accepted
+100

GolfScript (50 bytes)

$ wc -c codegolf24909.min.gs 
50 codegolf24909.min.gs
$ md5sum codegolf24909.min.gs 
ce652060039fba071d17333a1199fd72  codegolf24909.min.gs
$ time golfscript.rb codegolf24909.min.gs 
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

real    365m11.938s
user    364m45.620s
sys     0m6.520s

Since everyone else is now revealing their code, I will also pre-empt OP's request to unobfuscate:

38200,{:x,{)x\%!},,2=},4/{3\{2&!!1$++}/.57>39*+}%+

Overview dissection

  • Compute primes smaller than N with N=38200: this gives the first 4032 primes: 38200,{:x,{)x\%!},,2=},
  • We want one bit per prime, with a hex conversion, so split them into groups of 4: 4/
  • For each group, map each prime p to p&2 != 0, and do a base-2 to base-16 conversion: {3\{2&!!1$++}/.57>39*+}% (this is where the interesting tricks are)
  • We now have an array of ASCII values, plus the empty string from stdin; concatenate them to get a single string for output: +

More detailed dissection of the base conversion

Given a stack holding an empty string and a list of primes, we need to do two conversions:

  1. Convert each prime to a bit indicating whether it's equal to 2 or 3 (mod 4)
  2. Convert the bits into hex digits

There are lots of equally long ways to do 1; e.g.

{4%1>}%
{4%2/}%
{2/1&}%
{2/2%}%
{2&!!}%

or even

{2&}% followed by a 2/ after the base conversion

For 2, the obvious approach is

2base 16base{'0123456789abcdef'=}%+

But base is a long word, and since 16 = 24 we can easily save a few chars with

4/{2base'0123456789abcdef'=}%+

Now the most obvious waste is the 18 chars devoted to that string. We just want a function from digit to ASCII code. We want to map 0 to '0' = 48, ..., 9 to '9' = 57, 10 to 'a' = 97, ... 15 to 'f' = 102.

4/{2base.9>39*+48+}%+

But now throw into the mix a ban on base. We need to implement it ourselves. The obvious implementation (in this direction, the easy one) is that k base is a fold {\k*+}*. The slightly longer alternative is a straightforward iteration, which needs a base case: 0\{\k*+}/. Base 2 is slightly special: 1$++ is equivalent to \2*+ for the same length, and I've taken that approach.

Both of those are longer than the 5-char 2base, but since we're now iterating over the values we can pull in part 1 to have a single loop. We replace

{2&!!}%4/{2base.9>39*+48+}%+

with

4/{{2&!!1$++}*.9>39*+48+}%+

for a nice 1-char saving, or

4/{0\{2&!!1$++}/.9>39*+48+}%+

for a 1-char loss.

But although that 1-char loss looks like a step backwards, consider what happens to that 0. It's multiplied by 16 and added to the base-conversion output. And the final thing we do is to add a multiple of 16 to the output. So we can combine the two as

4/{3\{2&!!1$++}/.57>39*+}%+

Joint shortest and the bonus cleverness makes it more interesting.

share|improve this answer
1  
360 minutes! That's quite a while. Wonder what approach you took.. mine takes <1 min –  Claudiu Apr 1 at 15:28
3  
@Claudiu, I could make it a lot faster, but it would add about 5 characters, and this is kolmogorov-complexity rather than code-golf with time constraints. –  Peter Taylor Apr 1 at 15:31
    
How much could you get it down if you used base? All the other solutions use an equivalent (mine uses hex, the C one uses printf("%x"), haskell uses showHex) –  Claudiu Apr 2 at 22:28
1  
@Claudiu, actually my current best approach with base is longer than this one, because I did most of the optimisation after clarifying that I couldn't use it. base gives me a value from 0 to 15, so it still needs some work to convert to 0-9a-f. I might revisit using base at some point, but not tonight. –  Peter Taylor Apr 2 at 23:00

Python, 92 characters

Here it is ladies and gentlemen, the code itself!

>>> code = "R=range;print hex(int(''.join(`i/2%2`for i in R(38198)if all(i%x for x in R(2,i))),2))[2:-1]"
>>> len(code)
92
>>> exec code
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294
>>> import hashlib; hashlib.sha256(code).hexdigest()
'60fa293bbe895f752dfe208b7b9e56cae4b0c8e4cdf7c5cf82bf7bab60af3db6'

Marzio left a clever hint by saying that "it turns out to be highly compressible handling a little bit of prime numbers". I was sure the "little bit" wasn't italicized by accident, so I converted the hex string to bits and tried to find patterns. I thought that at first he was representing all the primes as bits and concatenating them together, but that didn't work out. Then maybe taking only a few digits, or dropping all the zeroes in the bit string - still no. Maybe it's a bitstring of the least-significant-bit of the first few primes? Not quite. But eventually I found the one that worked - it's a bitstring of the second-least-significant bit from the first however-many primes.

So, my code does just that: generate just enough primes, take the second bit of each (i/2%2), concatenate them as a binary string, then convert it to base-10 (int(..., 2)) and then to base-16 (hex(...)).

share|improve this answer
1  
Great! I'm new to code golf, but the hash stuff is a good way to let other people have fun in discovering "how to do it". I'll wait two days, then open a bounty (that I'll reward on trust :). –  Marzio De Biasi Mar 26 at 23:19
5  
@MarzioDeBiasi: Sure that works! Or maybe better to say you'll reward it on the day before the bounty is due, and if the winner doesn't reveal his answer the 2nd in place wins, etc... why rely on trust when you don't have to? –  Claudiu Mar 27 at 6:01
    
Why has code in hashlib not been counted? Isn't it code being run to generate output? –  philcolbourn Apr 1 at 13:12
2  
@philcolbourn: No the code doesn't use hashlib. It's just to generate the sha256 hash so tomorrow I can prove I wrote the code when I first posted this. You will see tomorrow! –  Claudiu Apr 1 at 14:27
    
@Claudiu: Now you should explain me how did you crack the problem! Well done! –  rubik Apr 2 at 17:22

Haskell, 105

SHA1 hash: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Output:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

Edit: Code:

import Numeric;f(x:z)s=f[y|y<-z,0/=mod y x]$s*2+quot(mod x 4)2;f[]s=s;main=putStr$showHex(f[2..38198]0)""

I missed the rule about not using any library functions except for printing (putStr). I would assume that mathematical operators, while they're technically functions, are allowed.

share|improve this answer

C, 136 116 109 103 characters

OK then, here's my effort:

i;p;q;main(n){for(;n++,q<4032;){for(i=1;++i<n&&n%i;);if(i==n)p+=p+(n&2)/2,p=++q&3?p:printf("%x",p)*0;}}

MD5 hash = f638552ef987ca302d1b6ecbf0b50e66
share|improve this answer
1  
Since printf returns the number of character written, which is always non-zero here, you can use !printf(...) instead of printf(...)*0 to save one char. –  ace Apr 3 at 11:12
    
@ace *slaps forehead* Ah, why didn't I think of that?? Thanks ace, as always :-) (May as well leave the code as it is, since it's supposed to match the MD5 hash.) –  squeamish ossifrage Apr 3 at 12:30

JS, 764

if we consider this string as base64, we can have a smaller version using the un-base-64-ed version:

btoa("wÖºo­÷离÷ÛÖôiÎßÙ¦éÝ}oÎáÇüo­iÏyk^áæ¹õÖ÷{·=áÎ=ç×÷÷i®÷×^ZáÝýï6yÇÛw}swßÎo¶ºÑ×voûÛ~xiÝ[ïÖéî=çv÷Zk½Ú駽{vqÝïÖs­vo}å¶øï®u×¾÷÷õ¦¶{½yé®y×áîk~\Ùöëwoºkv÷¯Ùç7wÏ<õ¿kÝz÷Ûn[kg¶qÍ[Û·x{Ç[׶¸ßß9q¦å¾ß­¸ww:¯xi×{ÑþõÛµoW9yþ¹ßñ×{Õ¯;Õí¹uþ]sMwonå®{ÛÏ|mÞ5ë­8yÖ¶çg=iÏ7o~ç®ÞwW:qÎw᮶s}kÖöwÛf¹k×øoo}Û}öÇÛiî<é¯õ¦ùã®Úß®}õÿvw}¹o}mßá®=ëf¹{}}·¹m¦¶ß]kÝúÕÖ½sÞ½óÞûé¦ößÕݶëW9snºÕǶï®øçf¹wß8oßk¦ù×ÛÞ|ofÜ÷­z×®<9mÝßm[ÝÞá½onõ§}ßf¸á¾\mÏvo¶÷Û­ý}®6ÙÞ¸yÝZïÞ=áÆ·o¿9ofº{owÞy÷GµkÏ;á¾´k§µm§8m·ßmýï¯tk¦øs®¹ïÞµ÷VÝÞxo½|ÝÝyá½:u½ôñ®á¦µßùåÝÛwß|iÎyå½tuÖ÷{g^^o}çto§Ù¶ñÿ<ñßyå®ùuþ}ÙÝ\å®{Çøy®<oÞzuæ´÷oukÝyáÎyw½Ý®úñí8m§»of{ÖÙ§zÛ}÷ãÝs½çg·é®;çFÚi÷¸{uk}xëyÛ¦÷ñ¾mÆå¯ví¦iÖºu¾wÙï{Ó®m­Úë®=áßyw¾¹sfs}Z÷owÝ÷snÙ½ûçwsß<á®\ënk¦qÇ^ïox")

But I think that the author wants us to find the logic behind this non-random string instead.

share|improve this answer
1  
to avoid the "downvotes rush" I added some details in the question :-) –  Marzio De Biasi Mar 26 at 14:08

Mathetmatica - 56

The mystery is already solved, so just implementing the idea

⌊.5Prime@Range@4032⌋~Mod~2~FromDigits~2~IntegerString~16
share|improve this answer
    
Nice. I'm curious what the shortest possibility is now that the cat's out of the bag –  Claudiu Apr 2 at 22:28
    
Do you call that "no libraries (except the one required for printing the output)"? –  Peter Taylor Apr 2 at 23:06
    
@PeterTaylor Yep, no imports - no libraries. –  swish Apr 2 at 23:12
    
Judging by the comments, I don't think that's how OP intended it to be interpreted. –  Peter Taylor Apr 2 at 23:15

J - 46 char

Don't mind me, just logging the J golf here for posterity. Wasn't clever enough to figure out the trick.

4[1!:2&4'0123456789abcdef'{~#.2|<.-:p:i.1007 4

Explained:

  • p:i.1007 4 - Create a 1007-row, 4-column matrix of the integers from 0, then take the prime numbers corresponding to those integers. Yes, p: is a J builtin. Yes, we're four primes short.

  • 2|<.-: - Halve each number (-:), floor it (<.), and take that modulo 2 (2|). This is the same as taking the next-to-lease significant bit.

  • #. - Convert each row of the result from base 2 into an integer. This gives us 1007 numbers from 0 to 15 inclusive.

  • '0123456789abcdef'{~#. - Take each row of this matrix of bits as the binary for a number, and use that number to select from the list of hex digits. This converts every four bits into the hex.

  • 1!:2&4 - The J interpreter has a problem with outputting strings longer than 256 chars, so we have to send this data directly to stdout. You win some, you lose some.

  • 4[ - Finally, discard the result from 1!:2 and instead output the missing 4 from the output. We do this because it's shorter than including those last four primes and returning an empty result here.

share|improve this answer

JS, 503

Following @xem idea:

s='Ù¦¶3V§K)°¬*ªm¸KLø¶*¬¡KN¥³çÉLIY쳪lZM9uìê$ÌÓ-Ã8N·¦\nÒµ7#T­yªnIURZ§:jéäRÍ-y­Æµ[´vQNó¢çjUMNJ£\/«c̵¦¤.ÃØ©õ3"[¢âÌ'+"'"+'ÔèÛ¤9ʪ[O6$ÓÆö­×q$á±Åïe5l×%ß]À²oZW(½Afí¢Rɬ³lV~ÑÆÌSJbÅY©²Ô¯"¥©ô²#2øû®HjµFz6YÓ%µ½JIb¥äYûåº\n5Ý©6©Éiwj²4-"aÅÂfâvtR¥Ù¹¦µì)X²¼HõŽ/2=OK.²kÙ2¤K\¼·³&9úB-díyIL£·²¦âÙUá¨K`¦áºÄ»ì29v¦´Æeyaª=T·=KÛ0MJ¡5u];Ù¬U[ݳâÌñ^³+S¶î+¬ZußY-ZLèôêH¹VÞ ©LUÕé:vºç²ªé«*Ö#3E=ÄéRãjGPº¯äå£c&³L¼ªZz«­¦ÛS.mº:fIM×eªÃ?ÊÂl+7UÉJ\bk¦®ÌÞr'
r=''
for(var i=0;i<s.length;i++) r+=s.charCodeAt(i).toString(16);
console.log(r)
share|improve this answer

Mathematica, 55

Prime~Array~4031~BitAnd~2~FromDigits~2~IntegerString~16

Tested on Mathematica 8. This makes use of two observations:

  • Mathematica's FromDigits doesn't actually check the range of the digits given, so if you apply it to a list of the form {2,0,2,2,0,...} you just get twice the result as if applying to {1,0,1,1,0,...}. But that's exactly the form generated by BitAnding the primes with 2.
  • The last bit of the number whose hexadecimal representation we want happens to be zero (as evidenced by the string ending in an even digit), so it is just two times the number you'd get with one prime less. But a factor of two is exactly what we get from using the previous observation, so everything perfectly fits together.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.