The encoding of BF code can be reversed, but it isn't a simple task.
The Halting Problem is the first to interfere. There's no way to computationally guarantee that you'll determine which answer is the correct one, because you have no way of determining whether the program you decode actually exits. Even so, perhaps someone evil has decided to make code that doesn't exit.
Still, these problems can be mitigated by effective selection of output. Any code of this type can be broken into its respective components. For BF, we have:
+ - add one to memory
- - subtract one from memory
> - increment pointer
< - decrement pointer
[ - open a loop
] - close a loop
, - await user input
. - output to screen
There are a few reasonable conclusions we can make:
] can never have appeared more times than
[ (otherwise the code would terminate with an error)
] must appear an equal number of times. (The reason I list this separately is that someone might stick a stack of
[ in front to throw you off, but that seems unlikely and evil.)
- are the most likely - possibly the only - terms that will appear multiple times in a row
, can be expected to appear the least in code
< can be expected to appear near
[, ] with very high consistency.
The most important thing we can determine about this output is that
] must appear an equal number of times. Otherwise, the code won't run. (Someone can be evil and stick arbitrary
[ in front of their code, but that is unlikely.)
Using this method, you'll have a better idea of where to start. Usually, once you've identified various pairs, you have no more than 8 or 16 programs you can manually check. Doing so isn't hard - 90% of the time it will be obvious that a program won't do anything just by looking at it.
Obviously, if someone knew you were using this method to approach the problem, I don't think they would leave it this open for you to attack. It's fully possible to design a problem that can't be approached in this way; that just means you'll have to check a ton more combinations.
There's another approach to solving these problems that doesn't involve any complex searching of spaces. It requires a pattern (i.e. alphanumeric) that you expect the output to match, and it requires a reasonable computation time from the BF program. With these two in hand:
- Find the various terms that could be brackets (
[, ]) (i.e. an equal number of them)
- Set up every permutation of interpreted BF
- Run them all.
- If the program hasn't finished after a few million cycles (or billion - cycles are cheap nowadays), kill it and call it a failure.
- If the program finishes, pattern-match the memory dump to the pattern you expected. If it matches, print it and move on. If it doesn't, fail it and move on.
Supposing that you find a unique pair for brackets (which is likely), and have a guess at
, (also likely), that gives $2*2*4!=96$ combinations to test, which really isn't all that bad. It shouldn't take more than a few seconds to a minute to run on a reasonably fast computer.