# Is there a general strategy for decoding Brainfuck mutations?

There are many Brainfuck variations used in puzzles in geocaching, for example Ook! They are usually not so hard to decode because they are 'standards' - therefore the substitution is googlable, there are often online converter.

But what is general strategy to dealing with such puzzles, if the only thing I know it's based on Brainfuck substitution? Or at least, I suppose it's a substitution?

I've found that one:

Buuga Uuga Uga Buga Búga Ùga Buuga Uuga Uga Ûga Úga Ùga Buuga Uuga Bùga Búga Bùga Bùga Bùga Ûga

I know (suppose) that the output is the code for a cipher lock. Judging for the number of the tokens, each Brainfuck token is likeyly to be substituted with separate uga token. Because brainfuck-encoded texts has very many repeating + on begin, and in that uga text there are little repetitions, I suppose that some uga symbols represent multiple +.

For example, encoding 1234 gives the output:

+++++ ++[-> +++++ ++<]> .+.+. +.<

so any simple substitution would give visible repetitions. However, some symbol can encode "+++", for example, or can be a "special word", that encoded together with second one gives 2 up to 9 "+".

Are there any algorithms that would help to beat that beast, or the only way is to brute-force all possible substitutions? Taking into account, that the substitutions can be quite sophisticated, is it solvable at all?

• There are nine different words in the given text, so it can't be a cipher, as there are only 8 brainfuck symbols. I also don't see the repetition typical of brainfuck programs, so it almost certainly something odd. This could be quite difficult without knowing the rules. – Kendall Frey Jul 18 '14 at 13:36
• It also isn't possible to come up with a general method, because doing so would require solving the halting problem. – user20 Jul 18 '14 at 15:09
• Could you maybe write a program to try different substitutions and see if the resulting brain fuck program compiles? – Ankit Soni Jul 19 '14 at 9:34
• Writing checking problem is a viable solution, yes, but only if I can find out what substitution should I test for. – Danubian Sailor Jul 19 '14 at 20:56
• only thing you can guarantee is that opening and closing brackets [ ] must nest properly, and first reachable < or > must be a > – ratchet freak Jul 20 '14 at 0:08

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)
• [ and ] 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.)
• + and - are the most likely - possibly the only - terms that will appear multiple times in a row
• . and , can be expected to appear the least in code
• > and < can be expected to appear near [, ] with very high consistency.

The most important thing we can determine about this output is that [ and ] 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 . and , (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.

• I don't know brainfuck, but I'd think that another condition would be that reading from left to right, you can never have encountered more ] than [ – Ben Aaronson Apr 15 '15 at 16:28
• Definitely a good start for one-to-one mappings of symbols. It gets more complicated for symbol groups (i.e. let Buuga = ++[). – Ian MacDonald Apr 15 '15 at 16:29
• @BenAaronson Oooh, that's a good one, actually. I'm going to edit that in. Thank you! – user20 Apr 15 '15 at 16:30
• The halting problem is solved, according to Computerphile. – garr890354839 Nov 2 '16 at 2:21
• @GarrisonPendergrass That's... definitely not true. The halting problem isn't a "problem," and can't be "solved"; it's a statement that certain program operations are undecidable. – user20 Nov 2 '16 at 3:02