Złożoność Kołmogorowa napisu S jest długość najkrótszego programu P , napisany w jakimś języku programowania L , którego wyjście jest dokładnie S .
_{(Tak, prawdziwa definicja jest bardziej formalna, ale wystarczy na wyzwanie.)}

Twoim zadaniem w tym wyzwaniu jest napisanie możliwie najkrótszego „solvera złożoności Kołmogorowa”, to znaczy programu napisanego w samym L , który przyjmuje ciąg S i zwraca najkrótsze P napisane w L tego wyjść S .

Naiwne podejście polega na iteracji wszystkich programów długości 1, następnie wszystkich programów długości 2, następnie wszystkich programów długości 3 itd., Uruchamiając każdy z nich i mierząc wynik aż do znalezienia programu, który wyprowadza S. Problem z tym podejściem polega na tym, że niektóre z tych programów mogą nigdy nie przestać działać, co oznacza, że ​​sam solver może nigdy się nie zatrzymać. A ze względu na problem z zatrzymaniem nie ma pewnego sposobu na uniknięcie programów, które się nie zatrzymują.

Prosty, choć niedoskonałym rozwiązaniem jest wprowadzenie limitu czasowego na czas wykonania każdego potencjalnego P „s. Programy, które nie zatrzymują się w czasie, mogą zostać pominięte, ale solver na pewno się zatrzyma (zakładając, że program w L rzeczywiście może wydać S w wyznaczonym terminie).

Wyzwanie

Napisz swój solver jako program lub funkcję, która przyjmuje trzy rzeczy:

• Ciąg S .
• Dodatnia liczba całkowita T, która jest limitem czasu w sekundach lub w mniejszym przedziale czasu (np. Milisekund).
• Ciąg alfabetu znaków użyć do potencjalnego P „s.

I wyprowadza najkrótszą P , który zawiera tylko znaki A , biegnie w czasie krótszym niż T jednostek czasu i wyjścia S .

To jest ogólny pseudokod:

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

Detale

• Można założyć, że nie zawsze będzie to P wykonany ze znaków A , która działa w czasie T , które wyjścia S .
• Możesz założyć, że wykonanie potencjalnych P nie wywoła skutków ubocznych, które uniemożliwiłyby poprawne działanie lub działanie solvera (jak np. Bałagan w przydzielonej pamięci solvera).
• Być może nie przyjąć, że potencjalni P „s są wolne od błędów. Pamiętaj, aby dołączyćtry / catchbloki lub cokolwiek stosownego wokół wezwania do wykonania.
• Jeśli występuje wiele najkrótszych P , to wystarczy. „Krótkość” mierzona jest w znakach, a nie bajtach.
• Wyjście potencjalnych P jest tym, co jest wypisywane na standardowe wyjście (lub zwykle w obszarze wyjściowym twojego języka). Pusty ciąg jest potencjalnym P. .
• Idealnie twój solver pozwoli A zawierać dowolne znaki. Koniecznością przynajmniej móc zawierać druku ASCII znaków Plus Pearls i nowe linie.
• Dane wejściowe mogą pochodzić z argumentów file / stdin / wiersza poleceń / funkcji. Dane wyjściowe są przesyłane do standardowego lub podobnego albo mogą zostać zwrócone jako ciąg znaków, jeśli napisałeś funkcję.

Punktacja

Zgłoszenie z najmniejszą liczbą bajtów wygrywa. Tiebreaker przechodzi do najwcześniej opublikowanego zgłoszenia.

Python 3, 240 236 bajtów

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

Nie uruchamiaj tego. Przynajmniej na moim komputerze trudno mi było zatrzymać program, gdy zaczął działać z powodu okien wyskakujących tworzonych dla każdego procesu.

timeoutZostały dodane tylko subprocess.check_outputw Pythonie 3, dlatego używamy tego zamiast Python 2.

Oto alternatywna wersja z, time.sleepktóra drukuje również wszystkie prawidłowe programy znalezione po drodze, a także odpowiadające im dane wyjściowe:

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

Program używa nazwy pliku adla każdego programu, Pktóry ma być testowany, więc jeśli go uruchomisz, upewnij się, że nie masz jeszcze pliku o tej nazwie. Zastąp ["py","-3","a"]je odpowiednim poleceniem dla twojej konfiguracji (np. ["python","a"]Lub ["python3","a"]).

Zmień sleepczas trwania na własne ryzyko :). Zadzwoń jak f("1\r\n",1,"1()print"), gdzie Tjest limit czasu w sekundach.

Kilka pierwszych wierszy wyjścia z testera z powyższym wywołaniem:

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

^{(Jeśli chcesz nieco pomóc programowi, możesz zmienić P="".join(P)na P="print"+"".join(P))}

Ponieważ wszystkie powyższe programy nie mają danych wyjściowych, oto wynik dla f("1\r\n",1,["print","(",")","1"])(tokeny nie są częścią wyzwania, ale chciałem pokazać, co się stanie):

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

Zwracana wartość to ciąg 'print(1)'.

Wreszcie, dla zabawy, oto co się stanie, jeśli alfabet jest string.printable, tj

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

Wklej link do wszystkich prawidłowych programów w języku Python 3 o wielkości 0-2 znaków