La complejidad de Kolmogorov de una cadena S es la longitud del programa más corto P , escrito en algún lenguaje de programación L , cuya salida es exactamente S .
_{(Sí, la definición real es más formal, pero esto será suficiente para el desafío).}

Su tarea en este reto es escribir el más breve posible "la complejidad de Kolmogorov solucionador", es decir, un programa escrito en L misma que lleva en una cadena S y devuelve el menor P escrito en L que las salidas S .

El enfoque ingenuo para esto es iterar sobre todos los programas de longitud 1, luego todos los programas de longitud 2, luego todos los programas de longitud 3, y así sucesivamente, ejecutando cada uno de ellos y midiendo la salida hasta que se encuentre un programa que produzca S. El problema con este enfoque es que es posible que algunos de estos programas nunca dejen de ejecutarse, lo que significa que el solucionador mismo nunca se detendrá. Y debido al problema de detención, no hay una forma segura de evitar los programas que no se detienen.

Una solución simple, aunque imperfecta, es poner un límite de tiempo al tiempo de ejecución de cada una de las P potenciales . Los programas que no se detienen a tiempo pueden pasarse por alto, pero el solucionador definitivamente se detendrá (suponiendo que un programa en L pueda generar S dentro del límite de tiempo).

Desafío

Escriba su solucionador como un programa o función que abarca tres cosas:

• La cadena S .
• Un entero positivo T que es el límite de tiempo en segundos o un lapso de tiempo menor (por ejemplo, milisegundos).
• Una cadena A del alfabeto de caracteres para usar para potenciales P 's.

Y da salida a la más corta P que sólo contiene caracteres de A , se ejecuta en menos de T unidades de tiempo, y las salidas S .

Este es el pseudocódigo general:

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

Detalles

• Usted puede asumir que siempre habrá un P hechos de los personajes en una que se ejecuta en el tiempo t que las salidas S .
• Puede suponer que la ejecución de las P potenciales no tendrá efectos secundarios que eviten que el solucionador se ejecute o funcione correctamente (como jugar con la memoria asignada del solucionador).
• Es posible que no asuma que los potenciales P 's son libres de error. Asegúrese de incluir try/ catchblocks o lo que sea aplicable alrededor de la llamada de ejecución.
• Si hay múltiples P más cortas , entonces cualquiera será suficiente. La "brevedad" se mide en caracteres, no en bytes.
• La salida de P potenciales es lo que se imprime en stdout (o el área de salida habitual de su idioma). La cadena vacía es una P potencial .
• Idealmente, su solucionador permitirá que A contenga cualquier carácter. Al menos debe ser capaz de contener caracteres ASCII imprimibles más pestañas y líneas nuevas.
• La entrada puede provenir de file / stdin / command line / function args. La salida va a stdout o similar, o puede devolverse como una cadena si escribió una función.

Puntuación

El envío con la menor cantidad de bytes gana. Tiebreaker va a la presentación más temprana publicada.

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

No corras esto. Al menos en mi computadora, encontré el programa realmente difícil de detener una vez que comenzó a ejecutarse debido a las ventanas emergentes creadas por proceso.

timeoutsolo se agregaron subprocess.check_outputen Python 3, por lo que estamos usando esto en lugar de Python 2.

Aquí hay una versión alternativa con una time.sleepque también imprime todos los programas válidos encontrados en el camino, así como su salida correspondiente:

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

El programa usa el nombre ade archivo para cada programa Pque se probará, por lo que si ejecuta esto, asegúrese de no tener un archivo con ese nombre. Reemplácelo ["py","-3","a"]con el comando apropiado para su configuración (p . Ej. ["python","a"]O ["python3","a"]).

Siéntase libre de cambiar la sleepduración bajo su propio riesgo :). Llame como f("1\r\n",1,"1()print"), donde Tes el tiempo de espera en segundos.

Primeras líneas de salida del probador con la llamada anterior:

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

^{(Si desea ayudar un poco al programa, puede cambiar P="".join(P)a P="print"+"".join(P))}

Dado que los programas anteriores no tienen salida, aquí está el resultado f("1\r\n",1,["print","(",")","1"])(los tokens no son parte del desafío, pero quería mostrar lo que sucede):

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

El valor de retorno es la cadena 'print(1)'.

Finalmente, solo por diversión, esto es lo que sucede si el alfabeto es string.printable, es decir

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

Enlace Pastebin de todos los programas válidos de 0-2 char Python 3