# Sorting a programs instructions until it works

Lets say I have a computer program below.

(define (factorial x)
(if (= x 0)
1
(else (* x (factorial (- x 1)))))


I then take each line of the program and create a random permutation.

       1
(if (= x 0)
(else (* x (factorial (- x 1)))))
(define (factorial x)


Now I give you a set of valid values that the program must return. 1,2,6,24

Your task is to sort the permutations of the program until it gives you the result.

Is this a new problem? I haven't found anything remotely like the problem I proposed above.

What is the runtime to solving this problem?

• In almost all cases where your program is more than 5-6 lines, there will only be a handful permutations that compile and return values? As you increase the complexity of the program, the permutations will decrease dramatically too. Commented Aug 13, 2018 at 16:24
• @KonstantinosKoiliaris Yea so worst case runtime would be O(N!) * O(C) where N is the amount of lines and C is the run time of the program. Commented Aug 13, 2018 at 17:23
• Brute force, you’d have to try all O(N!) permutations, but the run time of the program is not guaranteed to terminate for any random permutation (halting problem). So, wouldn’t that make the problem undecidable? Commented Aug 13, 2018 at 17:26
• This is surely undecidable in most programming languages -- as you can modify any given program P so that the only permutation that is syntactically correct is equivalent to P, and so solving the problem for the modified program could tell you whether running P ever returns, say, 0. Which is undecidable. Commented Aug 17, 2018 at 0:32

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$.

(Of course, that does not guarantee that you found the correct permutation for input 5.)

Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start with a line number which makes this solvable in polynomial time.

• It seems your solution assumes that it is provided as a promise that one of the permutations outputs $1, 2, 6, 24$ on inputs $1, 2, 3, 4$? Commented Aug 14, 2018 at 8:17
• Why is it decidable? It seems to me that it is only semi-decidable, as some of the permutations may run forever and we won't be able to tell. Commented Aug 15, 2018 at 12:42
• I would say semidecidable. “Computable” is too vague and if anything it means decidable (to me at least). Commented Aug 15, 2018 at 19:47
• @AndrejBauer fair enough, it's a partial recursive function Commented Aug 15, 2018 at 20:03
• @CKomus right, we're just discussing which words are appropriate for that case Commented Aug 17, 2018 at 16:03

Others have pointed out this is semidecidable. In most programming languages, the problem is NP-hard. In particular, the following problem is NP-hard:

Input: a set of lines of code
Question: does there exist a permutation, so that this yields a syntactically valid program?

If the programming language has two kinds of matched parentheses (e.g., () and []), then the problem is NP-hard, as shown here, as we can restrict to programs that contain only those symbols. Most languages have at least two kinds of parentheses symbols (e.g., () or [] or {}).

(Even in a language as simple as Scheme, it might still be possible to encode two independent types of parenthesis symbols: e.g., let (# and t) be the first pair of symbols, and (if #t and   1) be the other pair of symbols.)

• @NealYoung, you're right; corrected.
– D.W.
Commented Aug 17, 2018 at 1:20
• (Deleting my other comment given the updated post.) Here's another way to show it is NP hard: given a SAT formula, produce a program P that has no syntactically correct permutation (other than the identity) and that outputs "True" if and only if the formula is satisfiable. Commented Aug 17, 2018 at 3:27
• @NealYoung, that sounds interesting. I'd be interested to see how to construct such a program.
– D.W.
Commented Aug 17, 2018 at 3:54
• E.g. make a single-line program that checks all possible assignments and returns 0 iff there is a satisfying assignment. Commented Aug 17, 2018 at 14:52

At first not all the permutations will lead to a valid program. secondly, the answer depend on how the code is formatted.

next, there could be permutations that produce a program that do not terminate making it impossible to know if the output correspond to the valid values you gave. for instance suppose you have formatted your previous program as follow:

(define (factorial x)
(if (= x 0)
1
(else
(* x (factorial (- x 1)))
))


and consider the following permutation of its lines:

(define (factorial x)
(* x (factorial (- x 1)))
(if (= x 0)
1
(else
))


it is clear that it will not terminate.

As a result it cannot be possible to give the run time needed to solve it in the general case.

• I agree with your conclusion but not your reasoning. (It's true that the obvious approach -- executing each permutation -- doesn't work for the reason you point out, but that does not imply that no approach works. For that you need a more careful argument.) Commented Aug 17, 2018 at 0:35
• The difficulty is that if we want to know that a permuted program produces the right output, then we shall execute it and compare its output with the correct one. However this latter is not guaranteed to terminate.
– RTK
Commented Aug 17, 2018 at 7:11
• Sure but you then conclude "it cannot be possible" (by any means, presumably), which does not follow from your argument. Commented Aug 17, 2018 at 14:53