The Kolmogorov complexity of a string S is the length of the shortest program P, written in some programming language L, whose output is exactly S.
(Yes, the real definition is more formal but this will suffice for the challenge.)
Your task in this challenge is to write the shortest possible "Kolmogorov complexity solver", that is, a program written in L itself that takes in a string S and returns the shortest P written in L that outputs S.
The naive approach to this is to iterate over all length 1 programs, then all length 2 programs, then all length 3 programs, and so on, running each of them and measuring the output until a program that outputs S is found. The issue with this approach is that some of these programs may never stop running, which means that the solver itself may never stop. And due to the halting problem there is no surefire way to avoid the programs that don't stop.
A simple, though imperfect solution is to put a time limit on the execution time of each of the potential P's. Programs that don't happen to halt in time may be passed over, but the solver will definitely stop (assuming that a program in L can indeed output S within the time limit).
Write your solver as a program or function that takes in three things:
- The string S.
- A positive integer T that is the time limit in seconds or some smaller time span (e.g. milliseconds).
- A string A of the alphabet of characters to use for potential P's.
And outputs the shortest P that only contains characters in A, runs in less than T time units, and outputs S.
This is the general pseudocode:
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
- You may assume that there will always be a P made from the characters in A that runs in time T that outputs S.
- You may assume that the execution of the potential P's will not have side effects that prevent the solver from running or working correctly (like messing with the solver's allocated memory).
- You may not assume that the potential P's are error free. Be sure to include
catchblocks or whatever applicable around the execution call.
- If there are multiple shortest P's, then any will suffice. "Shortness" is measured in characters not bytes.
- The output of potential P's is what's printed to stdout (or your language's usual output area). The empty string is a potential P.
- Ideally your solver will allow A to contain any characters. A must at least to be able to contain printable ASCII characters plus tabs and newlines.
- Input may come from file/stdin/command line/function args. Output goes to stdout or similar, or can be returned as a string if you wrote a function.
The submission with the fewest bytes wins. Tiebreaker goes to earliest posted submission.