Die Kolmogorov-Komplexität eines Strings S ist die Länge des kürzesten Programms P , das in einer Programmiersprache L geschrieben ist und dessen Ausgabe genau S ist .
_{(Ja, die eigentliche Definition ist formeller, aber dies wird für die Herausforderung ausreichen.)}

Ihre Aufgabe bei dieser Herausforderung besteht darin, den kürzestmöglichen "Kolmogorov-Komplexitätslöser" zu schreiben, dh ein in L selbst geschriebenes Programm , das eine Zeichenfolge S aufnimmt und das kürzeste in L geschriebene P zurückgibt , das S ausgibt .

Der naive Ansatz besteht darin, über alle Programme der Länge 1, dann alle Programme der Länge 2, dann alle Programme der Länge 3 usw. zu iterieren, jedes von ihnen auszuführen und die Ausgabe zu messen, bis ein Programm gefunden wird, das S ausgibt . Das Problem bei diesem Ansatz ist, dass einige dieser Programme möglicherweise nie aufhören zu laufen, was bedeutet, dass der Solver selbst möglicherweise nie aufhört. Und aufgrund des Halteproblems gibt es keinen sicheren Weg, Programme zu vermeiden, die nicht anhalten.

Eine einfache, wenn auch unvollständige Lösung besteht darin, die Ausführungszeit jedes der potenziellen Ps zeitlich zu begrenzen . Programme, die nicht rechtzeitig anhalten, werden möglicherweise übergangen, der Solver wird jedoch definitiv angehalten (vorausgesetzt, ein Programm in L kann tatsächlich S innerhalb des Zeitlimits ausgeben ).

Herausforderung

Schreiben Sie Ihren Solver als ein Programm oder eine Funktion, die drei Dinge beinhaltet:

• Der String S .
• Eine positive ganze Zahl T , die das Zeitlimit in Sekunden oder eine kleinere Zeitspanne (z. B. Millisekunden) darstellt.
• Eine Zeichenfolge A aus dem Alphabet der Zeichen, die für potenzielle Ps verwendet werden sollen .

Und gibt das kürzeste P aus , das nur Zeichen in A enthält , in weniger als T Zeiteinheiten ausgeführt wird, und gibt S aus .

Dies ist der allgemeine Pseudocode:

Function KolmogorovComplexitySolver(S, T, A):
    Assign N to 0
    Loop until function returns:
        In any order, iterate over all strings of length N that only contain characters from *A*. Call the current string P:
            Execute P, saving the output to O, stopping the execution if it takes longer than time T
            If (P did not throw any errors) and (P did not timeout) and (O and S are identical):
                Return P
        Add 1 to N

Einzelheiten

• Sie können davon ausgehen, dass immer ein P aus den Zeichen in A erstellt wird , das zur Zeit T abläuft und S ausgibt .
• Sie können davon ausgehen, dass die Ausführung der potenziellen P keine Nebenwirkungen hat, die verhindern, dass der Solver ausgeführt wird oder ordnungsgemäß funktioniert (wie z. B. das Durcheinander mit dem zugewiesenen Speicher des Solvers).
• Sie können nicht davon ausgehen, dass die potenziellen P fehlerfrei sind. Achten Sie darauf, try/ catchblocks oder was auch immer für den Ausführungsaufruf relevant ist, einzuschließen.
• Wenn es mehrere kürzeste P gibt , reicht jedes aus. "Shortness" wird in Zeichen gemessen, die keine Bytes sind.
• Der Ausgang des Potential P ‚ist s , was zu stdout gedruckt ist (oder üblichen Ausgabebereich Ihrer Sprache). Der leere String ist ein Potential P .
• Idealerweise lässt Ihr Löser zu, dass A beliebige Zeichen enthält. A muss mindestens druckbare ASCII- Zeichen sowie Tabulatoren und Zeilenumbrüche enthalten können.
• Die Eingabe kann von file / stdin / command line / function args stammen. Die Ausgabe erfolgt nach stdout oder ähnlich oder kann als Zeichenfolge zurückgegeben werden, wenn Sie eine Funktion geschrieben haben.

Wertung

Die Einsendung mit den wenigsten Bytes gewinnt. Tiebreaker geht zum frühesten geposteten Beitrag.

Python 3, 240 236 Bytes

import subprocess as s,itertools as i
def f(S,T,A,N=0):
 while 1:
  for P in i.product(A,repeat=N):
   try:
    P="".join(P);open("a","w").write(P)
    if s.check_output(["py","-3","a"],timeout=T).decode()==S:return P
   except:1
  N+=1

Lass das nicht laufen. Zumindest auf meinem Computer war es aufgrund der pro Prozess erstellten Popup-Fenster sehr schwierig, das Programm zu stoppen, sobald es gestartet wurde.

timeouts wurden nur subprocess.check_outputin Python 3 hinzugefügt, weshalb wir dies anstelle von Python 2 verwenden.

Hier ist eine alternative Version mit einem time.sleep, die auch alle gültigen Programme druckt, die auf dem Weg gefunden wurden, sowie deren entsprechende Ausgabe:

import subprocess as s,itertools as i
import time
def f(S,T,A,N=0):
 while 1:
  for P in i.product(A,repeat=N):
   time.sleep(0.2)
   try:
    P="".join(P);open("a","w").write(P);C=s.check_output(["py","-3","a"],timeout=T).decode()
    print(P,repr(C))
    if C==S:return P
   except:1
  N+=1

Das Programm verwendet den Dateinamen afür jedes Pzu testende Programm. Wenn Sie dies ausführen, stellen Sie sicher, dass Sie noch keine Datei mit diesem Namen haben. Ersetzen Sie ["py","-3","a"]durch den entsprechenden Befehl für Ihr Setup (z . B. ["python","a"]oder ["python3","a"]).

Fühlen Sie sich frei, die sleepDauer auf eigenes Risiko zu ändern :). Rufe gerne an f("1\r\n",1,"1()print"), wo Tist Timeout in Sekunden.

Erste Ausgabezeilen des Testers mit dem obigen Aufruf:

 ''
1 ''
11 ''
() ''
111 ''
(1) ''
int ''
1111 ''

^{(Wenn Sie das Programm entlang ein bisschen helfen möchten , können Sie ändern P="".join(P)zu P="print"+"".join(P))}

Da die oben genannten Programme alle keine Ausgabe haben, ist hier das Ergebnis für f("1\r\n",1,["print","(",")","1"])(Token sind nicht Teil der Herausforderung, aber ich wollte zeigen, was passiert):

 ''
print ''
1 ''
() ''
11 ''
print() '\r\n'
(print) ''
(1) ''
111 ''
print(print) '<built-in function print>\r\n'
print(1) '1\r\n'

Der Rückgabewert ist die Zeichenfolge 'print(1)'.

Zum Schluss, nur zum Spaß, hier ist was passiert, wenn das Alphabet ist string.printable, dh

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c

Pastebin-Link aller gültigen 0-2 char Python 3-Programme