Die Kolmogorov-Komplexität eines Strings s ist definiert als die Länge des kürzesten Programms P, das s ausgibt. Ist die Länge von P kürzer als die Länge von s, so spricht man von komprimierbarem s, andernfalls ist s inkomprimierbar . Die meisten Saiten sind inkompressibel ...

Schreiben Sie das kürzeste Programm, das diesen String ausgibt (ohne Leerzeichen und ohne Zeilenumbruch):

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 

Die Ausgabe sollte folgendermaßen aussehen:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Hinweis: Es sind keine Benutzereingaben, kein Webzugriff und keine Bibliotheken zulässig (außer denen, die zum Drucken der Ausgabe erforderlich sind).

Edit I: Die Sequenz scheint zufällig zu sein ... aber es stellt sich heraus, dass sie sehr komprimierbar ist, wenn man ein bisschen Primzahlen verarbeitet ...

Edit II: Gut gemacht! Ich werde die Antworten in den nächsten Stunden überprüfen und dann das Kopfgeld zuweisen. Dies ist meine Idee, wie es gelöst werden könnte:

1. Wenn Sie versuchen, die Daten zu komprimieren, gehen Sie nicht weit weg ...
2. Im Internet finden Sie die (bekannte?) Online-Enzyklopädie der Integer-Sequenzen (OEIS);
3. Das Ausprobieren der ersten hexadezimalen Ziffern d9, a6, b6, 33, ...(oder ihrer dezimalen Darstellung) führt zu keinem Ergebnis.
4. Wenn Sie jedoch die Zahlen in binary ( 1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) konvertieren und sie in OEIS suchen, erhalten Sie dieses Ergebnis .
5. Wie von Claudiu angemerkt, habe ich auch einen kleinen Hinweis in der Frage (Edit I oben) gegeben ... :-)

Der Gewinner ist : Peter Taylor (GolfScript, 50), mit einer besonderen Erwähnung für Claudiu (Python, 92), der es als erster "gelöst" hat.

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

Da jetzt alle anderen ihren Code enthüllen, werde ich auch die Aufforderung von OP, die Verschleierung aufzuheben, vorwegnehmen:

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

Übersicht Dissektion

• Berechne Primzahlen kleiner als N mit N = 38200: Dies ergibt die ersten 4032 Primzahlen:38200,{:x,{)x\%!},,2=},
• Wir wollen ein Bit pro Primzahl mit einer Hexadezimalumwandlung, also teilen Sie sie in 4er-Gruppen auf: 4/
• Ordnen Sie für jede Gruppe jede Primzahl pzu p&2 != 0und führen Sie eine Konvertierung von Basis 2 zu Basis 16 durch: {3\{2&!!1$++}/.57>39*+}%(hier sind die interessanten Tricks)
• Wir haben jetzt ein Array von ASCII-Werten und die leere Zeichenfolge von stdin. Verketten Sie sie, um eine einzelne Zeichenfolge für die Ausgabe zu erhalten:+

Detailliertere Aufteilung der Basisumwandlung

Bei einem Stapel mit einer leeren Zeichenfolge und einer Liste von Primzahlen müssen zwei Konvertierungen durchgeführt werden:

1. Wandle jede Primzahl in ein Bit um, das angibt, ob sie gleich 2 oder 3 ist (Mod 4)
2. Konvertieren Sie die Bits in hexadezimale Ziffern

Es gibt viele gleich lange Möglichkeiten 1; z.B

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

oder auch

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

Für 2 ist der offensichtliche Ansatz

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

Aber base ist ein langes Wort, und da 16 = 2 ⁴ , können wir mit leicht ein paar Zeichen sparen

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

Die offensichtlichste Verschwendung sind jetzt die 18 Zeichen, die dieser Saite gewidmet sind. Wir wollen nur eine Funktion von Ziffern zu ASCII-Code. Wir wollen Karte 0zu '0' = 48, ..., 9auf '9' = 57, 10zu 'a' = 97, ... 15zu 'f' = 102.

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

Aber jetzt werfen Sie in die Mischung ein Verbot auf base. Wir müssen es selbst implementieren. Die naheliegende Implementierung (in dieser Richtung die einfache) k baseist eine Falte {\k*+}*. Die etwas längere Alternative ist eine einfache Iteration, die einen Basisfall benötigt: 0\{\k*+}/. Die Basis 2 ist etwas Besonderes: 1$++entspricht \2*+der gleichen Länge, und ich habe diesen Ansatz gewählt.

Beide sind länger als die 5-Zeichen 2base, aber da wir jetzt über die Werte iterieren, können wir in Teil 1 eine einzelne Schleife erstellen. Wir ersetzen

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

mit

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

für eine schöne 1-Zeichen-Einsparung oder

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

für einen 1-Zeichen-Verlust.

Aber obwohl dieser 1-Zeichen-Verlust wie ein Rückschritt aussieht, überlegen Sie, was mit dieser 0 passiert. Sie wird mit 16 multipliziert und zum Ausgangssignal der Basisumwandlung addiert. Und das Letzte, was wir tun, ist, der Ausgabe ein Vielfaches von 16 hinzuzufügen. So können wir die beiden als kombinieren

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

Das kürzeste Gelenk und die zusätzliche Cleverness machen es interessanter.

Python, 92 Zeichen

Hier ist es meine Damen und Herren, der Code selbst!

>>> 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 hinterließ einen klugen Hinweis: "Es stellt sich heraus, dass es sehr komprimierbar ist, ein bisschen Primzahlen zu verarbeiten." Ich war mir sicher, dass das "kleine Bit" nicht aus Versehen kursiv geschrieben wurde, also habe ich die Hex-Zeichenfolge in Bits konvertiert und versucht, Muster zu finden. Zuerst dachte ich, er würde alle Primzahlen als Teile darstellen und zusammenfügen, aber das hat nicht geklappt. Dann nehmen Sie vielleicht nur ein paar Ziffern oder lassen alle Nullen in der Bitfolge fallen - immer noch nein. Vielleicht ist es eine Bitfolge des niedrigstwertigen Teils der ersten Primzahlen? Nicht ganz. Aber irgendwann fand ich die, die funktionierte - es ist eine Bitfolge des zweitniedrigstwertigen Bits aus den ersten, aber vielen Primzahlen.

Mein Code macht genau das: Erzeuge gerade genug Primzahlen, nehme das zweite Bit von jeder ( i/2%2), verkette sie als binäre Zeichenkette, konvertiere sie dann in base-10 ( int(..., 2)) und dann in base-16 ().hex(...) ).

Haskell, 105

SHA1-Hash: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Ausgabe:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5

Bearbeiten: 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)""

Ich habe die Regel übersehen, keine Bibliotheksfunktionen außer dem Drucken (putStr) zu verwenden. Ich würde annehmen, dass mathematische Operatoren, obwohl sie technisch funktionieren, erlaubt sind.

C, 136 116 109 103 Zeichen

OK, hier ist meine Anstrengung:

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

JS, 764

Wenn wir diesen String als base64 betrachten, können wir eine kleinere Version mit der un-base-64-ed-Version haben:

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")

Aber ich denke, der Autor möchte, dass wir stattdessen die Logik hinter dieser nicht zufälligen Zeichenfolge finden.

Mathetmatica - 56

Das Rätsel ist schon gelöst, also einfach die Idee umsetzen

⌊.5Prime@Range@4032⌋~Mod~2~FromDigits~2~IntegerString~16

J - 46 Zeichen

Es macht mir nichts aus, nur den J-Golf hier für die Nachwelt zu protokollieren. War nicht klug genug, um den Trick herauszufinden.

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

Erklärt:

• p:i.1007 4- Erstellen Sie eine 1007-Zeilen-, 4-Spalten-Matrix der Ganzzahlen aus 0 und nehmen Sie dann die Primzahlen, die diesen Ganzzahlen entsprechen. Ja, p:ist ein J eingebaut. Ja, wir haben vier Primzahlen zu wenig.

• 2|<.-: - Halbiere jede Zahl (-: ), lege sie auf den Boden ( <.) und nimm das Modulo 2 ( 2|). Dies ist dasselbe, als würde man das nächstnotwendige Bit nehmen.

• #.- Konvertieren Sie jede Zeile des Ergebnisses von Basis 2 in eine Ganzzahl. Dies gibt uns 1007 Zahlen von 0 bis einschließlich 15.

• '0123456789abcdef'{~#.- Nehmen Sie jede Zeile dieser Bitmatrix als Binärzahl für eine Zahl und wählen Sie diese Zahl aus der Liste der Hexadezimalziffern aus. Dies konvertiert alle vier Bits in das Hex.

• 1!:2&4- Der J-Interpreter hat ein Problem mit der Ausgabe von Zeichenfolgen, die länger als 256 Zeichen sind. Daher müssen wir diese Daten direkt an stdout senden. Du gewinnst etwas, du verlierst etwas.

• 4[- Verwerfen Sie abschließend das Ergebnis von 1!:2und geben Sie stattdessen die fehlenden 4 aus. Wir tun dies, weil es kürzer als die letzten vier Primzahlen ist und hier ein leeres Ergebnis zurückgibt.

JS, 503

Folgende @xem Idee:

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)

Mathematica, 55

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

Getestet auf Mathematica 8. Dabei werden zwei Beobachtungen verwendet:

• Mathematica FromDigitsüberprüft den Bereich der angegebenen Ziffern nicht wirklich. Wenn Sie ihn also auf eine Liste des Formulars {2,0,2,2,0,...}anwenden, erhalten Sie nur das Doppelte des Ergebnisses, als wenn Sie auf zutreffen {1,0,1,1,0,...}. Aber das ist genau die Form, die von erzeugt wirdBitAnd die Primzahlen mit 2 erzeugt wird.
• Das letzte Bit der Zahl, deren hexadezimale Darstellung wir wollen, ist zufällig Null (wie durch die Zeichenfolge belegt wird, die mit einer geraden Ziffer endet). Es ist also nur das Zweifache der Zahl, die Sie mit einer Primzahl weniger erhalten würden. Aber ein Faktor zwei ist genau das, was wir aus der vorherigen Beobachtung erhalten, so dass alles perfekt zusammen passt.