La complexité de Kolmogorov d'une chaîne S est la longueur du programme le plus court P , écrit dans un langage de programmation L , dont la sortie est exactement S .
_{(Oui, la vraie définition est plus formelle mais cela suffira pour le défi.)}

Votre tâche dans ce défi est d'écrire le plus court possible « solveur de la complexité de Kolmogorov », qui est un programme écrit en L lui - même qui prend une chaîne S et retourne le plus court P écrit en L que les sorties S .

L'approche naïve consiste à parcourir tous les programmes de longueur 1, puis tous les programmes de longueur 2, puis tous les programmes de longueur 3, etc., en exécutant chacun d'eux et en mesurant la sortie jusqu'à ce qu'un programme qui génère S soit trouvé. Le problème avec cette approche est que certains de ces programmes peuvent ne jamais s'arrêter, ce qui signifie que le solveur lui-même peut ne jamais s'arrêter. Et en raison du problème d'arrêt, il n'y a aucun moyen infaillible d'éviter les programmes qui ne s'arrêtent pas.

Une solution simple, quoique imparfaite, consiste à limiter le temps d'exécution de chacun des P potentiels . Les programmes qui ne s'arrêtent pas dans le temps peuvent être ignorés, mais le solveur s'arrêtera définitivement (en supposant qu'un programme en L peut en effet produire S dans le délai).

Défi

Écrivez votre solveur sous forme de programme ou de fonction qui prend en compte trois choses:

• La chaîne S .
• Un entier positif T qui est la limite de temps en secondes ou un intervalle de temps plus court (par exemple millisecondes).
• Une chaîne A de l'alphabet de caractères à utiliser pour les P potentiels .

Et les sorties les plus brefs P qui ne contient que des caractères en A , fonctionne en moins de T unités de temps, et les sorties S .

Voici le pseudocode général:

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

Détails

• Vous pouvez supposer qu'il y aura toujours un P fabriqués à partir des caractères A qui fonctionne en temps T que les sorties S .
• Vous pouvez supposer que l'exécution des P potentiels n'aura pas d'effets secondaires qui empêcheront le solveur de fonctionner ou de fonctionner correctement (comme jouer avec la mémoire allouée du solveur).
• Vous ne pouvez pas supposer que les P potentiels sont exempts d'erreurs. Assurez-vous d'inclure try/ catchblocs ou tout ce qui s'applique autour de l'appel d'exécution.
• S'il y a plusieurs P les plus courts , alors tout suffira. La "brièveté" est mesurée en caractères et non en octets.
• La sortie des P potentiels est ce qui est imprimé sur stdout (ou la zone de sortie habituelle de votre langue). La chaîne vide est un potentiel P .
• Idéalement, votre solveur permettra à A de contenir n'importe quel caractère. Un must au moins pour pouvoir contenir des caractères ASCII imprimables ainsi que des tabulations et des retours à la ligne.
• L'entrée peut provenir des fichiers / stdin / ligne de commande / fonction args. La sortie va à stdout ou similaire, ou peut être retournée sous forme de chaîne si vous avez écrit une fonction.

Notation

La soumission avec le moins d'octets est gagnante. Tiebreaker passe à la première soumission publiée.

Python 3, 240 236 octets

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

Ne lancez pas cela. Sur mon ordinateur, au moins, j'ai trouvé le programme vraiment difficile à arrêter une fois qu'il a commencé à s'exécuter en raison des fenêtres contextuelles créées par processus.

timeoutles s n'ont été ajoutés qu'à subprocess.check_outputPython 3, c'est pourquoi nous utilisons cela plutôt que Python 2.

Voici une version alternative avec un time.sleepqui imprime également tous les programmes valides trouvés en cours de route, ainsi que leur sortie correspondante:

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

Le programme utilise le nom ade fichier pour chaque programme Pà tester, donc si vous l'exécutez, assurez-vous que vous n'avez pas déjà un fichier de ce nom. Remplacez-la ["py","-3","a"]par la commande appropriée pour votre configuration (par exemple, ["python","a"]ou ["python3","a"]).

N'hésitez pas à modifier la sleepdurée à vos risques et périls :). Appelez comme f("1\r\n",1,"1()print"), où Test le délai d'attente en secondes.

Premières lignes de sortie du testeur avec l'appel ci-dessus:

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

^{(Si vous voulez aider le programme un peu, vous pouvez passer P="".join(P)à P="print"+"".join(P))}

Étant donné que les programmes ci-dessus n'ont pas de sortie, voici le résultat pour f("1\r\n",1,["print","(",")","1"])(les jetons ne font pas partie du défi, mais je voulais montrer ce qui se passe):

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

La valeur de retour est la chaîne 'print(1)' .

Enfin, juste pour le plaisir, voici ce qui se passe si l'alphabet est string.printable, c'est à dire

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

Lien Pastebin de tous les programmes Python 3 0-2 caractères valides