7
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ It also isn't possible to come up with a general method, because doing so would require solving the halting problem. $\endgroup$
    – user20
    Jul 18, 2014 at 15:09
  • $\begingroup$ Writing checking problem is a viable solution, yes, but only if I can find out what substitution should I test for. $\endgroup$
    – user66
    Jul 19, 2014 at 20:56
  • 1
    $\begingroup$ only thing you can guarantee is that opening and closing brackets [ ] must nest properly, and first reachable < or > must be a > $\endgroup$ Jul 20, 2014 at 0:08
  • $\begingroup$ @ratchetfreak your hint is something with which one can start finding substitutions even on paper $\endgroup$
    – user66
    Jul 20, 2014 at 21:17
  • $\begingroup$ There are just so many substitution possibilities, right? One might encode .+ in a single token, for example. $\endgroup$
    – justhalf
    Jul 21, 2014 at 1:35

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Definitely a good start for one-to-one mappings of symbols. It gets more complicated for symbol groups (i.e. let Buuga = ++[). $\endgroup$ Apr 15, 2015 at 16:29
  • 1
    $\begingroup$ @BenAaronson Oooh, that's a good one, actually. I'm going to edit that in. Thank you! $\endgroup$
    – user20
    Apr 15, 2015 at 16:30
  • $\begingroup$ The halting problem is solved, according to Computerphile. $\endgroup$ Nov 2, 2016 at 2:21
  • $\begingroup$ @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. $\endgroup$
    – user20
    Nov 2, 2016 at 3:02
  • $\begingroup$ Then why is it even a "problem"? $\endgroup$ Nov 2, 2016 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.