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
/catch
bloki 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.
źródło
Odpowiedzi:
Python 3,
240236 bajtówNie 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.
timeout
Zostały dodane tylkosubprocess.check_output
w Pythonie 3, dlatego używamy tego zamiast Python 2.Oto alternatywna wersja z,
time.sleep
która drukuje również wszystkie prawidłowe programy znalezione po drodze, a także odpowiadające im dane wyjściowe:Program używa nazwy pliku
a
dla każdego programu,P
któ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ń
sleep
czas trwania na własne ryzyko :). Zadzwoń jakf("1\r\n",1,"1()print")
, gdzieT
jest limit czasu w sekundach.Kilka pierwszych wierszy wyjścia z testera z powyższym wywołaniem:
(Jeśli chcesz nieco pomóc programowi, możesz zmienić
P="".join(P)
naP="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):Zwracana wartość to ciąg
'print(1)'
.Wreszcie, dla zabawy, oto co się stanie, jeśli alfabet jest
string.printable
, tjWklej link do wszystkich prawidłowych programów w języku Python 3 o wielkości 0-2 znaków
źródło