Napisz Solver złożoności Kołmogorowa

16

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.

Hobby Calvina
źródło
7
Mój mózg boli.
Alex A.
1
Czy potrafisz złagodzić wymóg, że język docelowy i język, w którym jest napisany meta-solver, muszą być takie same?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
I czy nie byłoby możliwe napisanie programu, który konwertuje dane wyjściowe na literalną reprezentację języka przez ciąg?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ Nie, chodzi o to, aby zrobić to w tym samym języku. Tak, ale nie zawsze byłby to najkrótszy program.
Calvin's Hobbies
@ Calvin'sHobbies: W końcu więc tylko wyzwanie dla golfa polega na tym, aby dowiedzieć się, który język może łatwo napisać kod do urządzeń wywołujących (lub zaimplementować kompilator, jeśli go nie ma), aby skompilować sam język?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳

Odpowiedzi:

11

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

Sp3000
źródło