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

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

<p>If the programming language has two kinds of matched parentheses (e.g., <code>()</code> and <code>[]</code>), then the problem is NP-hard, as <a href="https://cs.stackexchange.com/q/96221/755">shown here</a>, as we can restrict to programs that contain only those symbols.  Most languages have at least two kinds of parentheses symbols (e.g., <code>()</code> or <code>[]</code> or <code>{}</code>).</p>

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

CC BY-SA 4.0
2018-08-17T01:20:54.260Z
@NealYoung, you're right; corrected.
D.W.
CC BY-SA 4.0
2018-08-17T03:27:52.130Z
(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.
Neal Young
CC BY-SA 4.0
2018-08-17T03:54:59.157Z
@NealYoung, that sounds interesting.  I'd be interested to see how to construct such a program.
D.W.
CC BY-SA 4.0
2018-08-17T14:52:10.187Z
E.g. make a single-line program that checks all possible assignments and returns 0 iff there is a satisfying assignment.
Neal Young
CC BY-SA 4.0
2018-08-16T23:02:11.787Z
2018-08-17T01:20:47.523Z
2018-08-17T01:20:47.523Z
D.W.
<p>At first not all the permutations will lead to a valid program. 
secondly, the answer depend on how the code is formatted.</p>

<p>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:</p>

<pre><code>(define (factorial x)
   (if (= x 0)
       1
       (else 
         (* x (factorial (- x 1)))
    ))
</code></pre>

<p>and consider the following permutation of its lines:</p>

<pre><code>(define (factorial x)
   (* x (factorial (- x 1)))
    (if (= x 0)
       1
       (else              
    ))
</code></pre>

<p>it is clear that it will not terminate.</p>

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

CC BY-SA 4.0
2018-08-17T00:35:58.103Z
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.)
Neal Young
CC BY-SA 4.0
2018-08-17T07:11:06.097Z
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
CC BY-SA 4.0
2018-08-17T14:53:34.730Z
Sure but you then conclude "it cannot be possible" (by any means, presumably), which does not follow from your argument.
Neal Young
CC BY-SA 4.0
2018-08-13T18:37:16.633Z
2018-08-13T18:37:16.633Z
RTK
<p>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$.</p>

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

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

CC BY-SA 4.0
2018-08-14T08:17:46.707Z
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$?
Christian Komusiewicz
CC BY-SA 4.0
2018-08-14T18:16:03.100Z
@CKomus yes that's promised by the OP
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-15T12:42:40.770Z
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.
Andrej Bauer
CC BY-SA 4.0
2018-08-15T19:47:55.057Z
I would say semidecidable. “Computable” is too vague and if anything it means decidable (to me at least).
Andrej Bauer
CC BY-SA 4.0
2018-08-15T20:03:43.053Z
@AndrejBauer fair enough, it's a partial recursive function
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-17T15:09:22.767Z
That's exactly why I asked whether the output is given as a promise. If yes, then it does not matter whether some permutations run forever. There is one that outputs 1,2,6,24, by definition it does not run forever and since we run the algorithms in parallel, we do not care about those permutations that run forever.
Christian Komusiewicz
CC BY-SA 4.0
2018-08-17T16:03:02.660Z
@CKomus right, we're just discussing which words are appropriate for that case
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-29T06:20:42.333Z
Can the second and first answers be merged by an author ? Because the NP hard reduction is a valid answer .
Joshua Herman
CC BY-SA 4.0
2018-08-29T06:48:53.963Z
@JoshuaHerman Not exactly merged (as there would be no way to divvy up the points). But it's okay to have several upvoted answers.
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-13T18:23:00.470Z
2018-08-15T20:03:26.190Z
2018-08-15T20:03:26.190Z
Bjørn Kjos-Hanssen
<p>Lets say I have a computer program below.</p>

<pre><code>(define (factorial x)
   (if (= x 0)
       1
       (else (* x (factorial (- x 1)))))
</code></pre>

<p>I then take each line of the program and create a random permutation.</p>

<pre><code>       1
   (if (= x 0)
       (else (* x (factorial (- x 1)))))
(define (factorial x)
</code></pre>

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

<p>Your task is to sort the permutations of the program until it gives you the result.</p>

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

<p>What is the runtime to solving this problem?</p>

CC BY-SA 4.0
2018-08-13T16:24:51.783Z
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.
Konstantinos Koiliaris
CC BY-SA 4.0
2018-08-13T17:23:36.377Z
@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.
Joshua Herman
CC BY-SA 4.0
2018-08-13T17:26:42.837Z
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?
Konstantinos Koiliaris
CC BY-SA 4.0
2018-08-17T00:32:49.510Z
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.
Neal Young
<cc.complexity-theory><reference-request><pl.programming-languages><sorting>
Sorting a programs instructions until it works
Joshua Herman
# Sorting a programs instructions until it works

(Asked by: username_0 on 2018-08-13)

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?

**Tags:** cc.complexity-theory, reference-request, pl.programming-languages, sorting

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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?  
> **username_2**: 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.  

---

## 3 answers

### Answer by username_5 on 2018-08-13. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_6**: 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$?  
> **username_5**: @CKomus yes that's promised by the OP  
> **username_7**: 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.  
> **username_7**: I would say semidecidable. “Computable” is too vague and if anything it means decidable (to me at least).  
> **username_5**: @AndrejBauer fair enough, it's a partial recursive function  
> **username_6**: That's exactly why I asked whether the output is given as a promise. If yes, then it does not matter whether some permutations run forever. There is one that outputs 1,2,6,24, by definition it does not run forever and since we run the algorithms in parallel, we do not care about those permutations that run forever.  
> **username_5**: @CKomus right, we're just discussing which words are appropriate for that case  
> **username_0**: Can the second and first answers be merged by an author ? Because the NP hard reduction is a valid answer .  
> **username_5**: @JoshuaHerman Not exactly merged (as there would be no way to divvy up the points). But it's okay to have several upvoted answers.  

---

### Answer by username_3 on 2018-08-16. Score: 3

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](https://cs.stackexchange.com/q/96221/755), 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.)

> **Comments:**
> **username_3**: @NealYoung, you're right; corrected.  
> **username_2**: (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.  
> **username_3**: @NealYoung, that sounds interesting.  I'd be interested to see how to construct such a program.  
> **username_2**: E.g. make a single-line program that checks all possible assignments and returns 0 iff there is a satisfying assignment.  

---

### Answer by username_4 on 2018-08-13. Score: 1

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.

> **Comments:**
> **username_2**: 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.)  
> **username_4**: 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.  
> **username_2**: Sure but you then conclude "it cannot be possible" (by any means, presumably), which does not follow from your argument.  

---

