A complexidade de Kolmogorov de uma string S é o comprimento do programa mais curto P , escrito em alguma linguagem de programação L , cuja saída é exatamente S .
_{(Sim, a definição real é mais formal, mas isso será suficiente para o desafio.)}

Sua tarefa neste desafio é escrever o mais curto possível "Kolmogorov solver complexidade", isto é, um programa escrito em L em si que leva em uma série S e retorna o menor P escrito em L que as saídas S .

A abordagem ingênua para isso é iterar sobre todos os programas de comprimento 1, então todos os 2 programas de comprimento, em seguida, todos os 3 programas de comprimento, e assim por diante, correndo cada um deles e medir a saída até que um programa que saídas S é encontrado. O problema dessa abordagem é que alguns desses programas podem nunca parar de funcionar, o que significa que o solucionador em si nunca pode parar. E devido ao problema de interrupção, não existe uma maneira infalível de evitar os programas que não param.

Uma solução simples, embora imperfeita, é colocar um limite de tempo no tempo de execução de cada um dos P 's em potencial . Programas que não são interrompidos no tempo podem ser ignorados, mas o solucionador definitivamente irá parar (supondo que um programa em L possa realmente gerar S dentro do prazo).

Desafio

Escreva seu solucionador como um programa ou função que aceite três coisas:

• A string S .
• Um número inteiro positivo T que é o limite de tempo em segundos ou em um período menor (por exemplo, milissegundos).
• Uma sequência A do alfabeto de caracteres a ser usado para possíveis P 's.

E emite o mais curto P que contém apenas caracteres em Um , é executado em menos do que t unidades de tempo, e as saídas S .

Este é o pseudocódigo geral:

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

Detalhes

• Você pode assumir que sempre haverá um P feita a partir dos personagens em A que executa em tempo T que as saídas S .
• Você pode supor que a execução dos P 's em potencial não terá efeitos colaterais que impedem que o solucionador funcione ou funcione corretamente (como mexer com a memória alocada do solucionador).
• Você não pode presumir que os P potenciais estão livres de erros. Certifique-se de incluir try/ catchbloqueia ou o que for aplicável na chamada de execução.
• Se houver vários P mais curtos , qualquer um será suficiente. "Shortness" é medido em caracteres, não em bytes.
• A saída de P potenciais é o que é impresso no stdout (ou na área de saída usual do seu idioma). A cadeia vazia é um potencial P .
• Idealmente, o seu solucionador permitirá que A contenha qualquer caractere. A deve pelo menos ser capaz de conter caracteres ASCII imprimíveis , além de guias e novas linhas.
• A entrada pode vir do arquivo / stdin / linha de comando / função args. A saída vai para stdout ou similar ou pode ser retornada como uma sequência se você escreveu uma função.

Pontuação

O envio com o menor número de bytes vence. O desempatador vai para a primeira submissão postada.

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

Não execute isso. No meu computador, pelo menos, achei muito difícil parar o programa depois que ele começou a ser executado devido às janelas pop-up criadas por processo.

timeouts foram adicionados apenas subprocess.check_outputno Python 3, e é por isso que estamos usando isso em vez do Python 2.

Aqui está uma versão alternativa com uma time.sleepque também imprime todos os programas válidos encontrados ao longo do caminho, bem como a saída correspondente:

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

O programa usa o nome do arquivo apara cada programa Pa ser testado; portanto, se você o executar, verifique se ainda não possui um arquivo com esse nome. Substitua ["py","-3","a"]pelo comando apropriado para sua configuração (por exemplo, ["python","a"]ou ["python3","a"]).

Sinta-se livre para alterar a sleepduração por seu próprio risco :). Ligue como f("1\r\n",1,"1()print"), onde Testá o tempo limite em segundos.

Primeiras linhas de saída do testador com a chamada acima:

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

^{(Se você quiser ajudar o programa um pouco, pode mudar P="".join(P)para P="print"+"".join(P))}

Como todos os programas acima não têm saída, eis o resultado f("1\r\n",1,["print","(",")","1"])(os tokens não fazem parte do desafio, mas eu queria mostrar o que acontece):

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

O valor de retorno é a sequência 'print(1)' .

Finalmente, apenas por diversão, eis o que acontece se o alfabeto for string.printable, ou seja,

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

Pastebin link de todos os programas 0-2 char Python 3 válidos