9
\$\begingroup\$

Given a BF program consisting of only the characters +-[]<>., with the property that there's an equal number of < and > between every matching pair of [].

You have to find the shortest program that can be achieved with the optimal memory layout (by rearranging the cells on the tape).

If there are multiple such programs, output any of them.

For such a program, it's possible to tell exactly where (on which memory cell) the memory pointer is for each instruction executed. The memory can be rearranged such that the program is shorter, without changing the program execution.

Example input/output

Input : Output
,>>, : ,>,
,<++[->>+<<] : ,>++[->+<]
+<><>+ : ++

Background

Note that the challenge is well-defined (see the "formal description" section below) even without this section.

Background on the language:

Brainfuck operates on an array of memory cells, each initially set to zero. [...]. There is a pointer, initially pointing to the first memory cell. The commands are:

Command Description
> Move the pointer to the right
< Move the pointer to the left
+ Increment the memory cell at the pointer
- Decrement the memory cell at the pointer
. Output the character signified by the cell at the pointer
, Input a character and store it in the cell at the pointer
[ Jump past the matching ] if the cell at the pointer is 0
] Jump back to the matching [ if the cell at the pointer is nonzero

(Source: brainfuck - Esolang)

For the purpose of this challenge, assume that the tape is unbounded on both ends.

Therefore, for all programs that are valid input for this challenge,

  • the memory cell that the pointer is on is completely determined by the instruction that is going to be executed, and
  • there's only a finite number of accessed memory cells.

(Note that the program might not terminate.)

Now assume that the memory layout is rearranged so that whatever a cell x is used (by a command not in <>) in the original program, the cell f(x) is used in the new program. Then the new program might be shorter than the original program.

Your task is to find the shortest program that can be obtained by rearranging the memory layout, without changing the execution or order of the other commands.

For example, assume that the cells are numbered -1, 0, 1, 2,..., the starting position is 0, and > and < increases/decreases the position of the memory pointer respectively.

Consider the program ,>>,. It executes , on cell 0, then move to cell 2, then executes , again.

If the cells 2 and 1 are swapped, then the new program should execute , on cell 0, then move to cell 1, then execute , again, which can be achieved by ,>,. This is the shortest possibility.

Note that you can swap cell 2 and -1, so the resulting program is ,<,, which is just as short.

However, the new memory layout must not rearrange two different cells to the same cell, so it's invalid to read to cell 0 both times (program ,,).


FAQ

I'm not sure what questions people may have, in any case refer to the formal description.

  • The amount and order of the non-<> in the input and output must be the same.
  • If two (non-<>) commands in the original program access the same cell, the two corresponding commands must access the same cell in the shortened program. (i.e., if a and b accesses the same cell in program 1, and their corresponding character in program 2 are a' and b', then a' and b' must access the same cell)
  • Assume that all branches are reachable (that memory is corrupted or something). (you can't assume that there's no unreachable code, however)

Formal definition

Define the set S to be the set of strings that consists of only the characters in .,<>+-[], the [] forms matching pairs, and between every pairs of matching [] there's an equal number of < and >.

Let s be a string. Then define value(s) :: String -> Integer = (number of > in s) - (number of < in s).

Consider a string A in S, where the number of characters in A and not in <> is n.

Consider an injective function f :: Integer -> Integer. There exists exactly one shortest string A' such that:

  • There are exactly n characters in A' not in <>, and the corresponding characters in A and A' have the same value.
  • For each corresponding character a in A and a' in A', let p be the string formed by concatenating in order all the characters before the character a in A, and define p' similarly, then f(value(p)) == value(p').

Given the string A, you have to find the shortest string A', for all possible functions f.

\$\endgroup\$
23
  • 3
    \$\begingroup\$ I feel like a description of BF and "Then, we can tell exactly where the memory pointer is for each instruction executed" would be much more useful than the provided "Formal definition", which I think is about as clear as mud after the definition of S. \$\endgroup\$ – Jonathan Allan Feb 6 at 15:49
  • 1
    \$\begingroup\$ I cannot decipher the challenge, but maybe someone more familiar can help you communicate it more clearly? Anyone? \$\endgroup\$ – Jonathan Allan Feb 6 at 16:06
  • 1
    \$\begingroup\$ @JonathanAllan What. The formal description is formal, isn't it? \$\endgroup\$ – user202729 Feb 6 at 16:07
  • 3
    \$\begingroup\$ "The formal description is formal, isn't it?" - Quite possibly, but I, unfortunately, do not comprehend it; so I believe there will be others that also do not. \$\endgroup\$ – Jonathan Allan Feb 6 at 16:11
  • 1
    \$\begingroup\$ I think it's clearer now. (It might be clearer to describe the use of f here but it makes sense once one understands the formal language). \$\endgroup\$ – Jonathan Allan Feb 6 at 16:41
1
\$\begingroup\$

JavaScript (Node.js), 239 bytes

s=>(x=[],i=n=s.length,s.map(t=>t<'<'|t>'>'?x.push([i,t]):i+=t<'>'?1:-1),f=(r,i=0)=>{2*n in r?(i=n,y='',x.map(([j,t])=>y+=((j=r[j]-i)<0?'<':'>').repeat(j>0?j:-j,i+=j)+t),s[y.length]&&(s=y)):i>2*n||f(r,i+1,r.includes(i)||f([...r,i]))},f``,s)

Try it online!

Badly golfed

s=>(
    x=[],
    i=n=s.length,
    s.map(t=>t<'<'|t>'>'?x.push([i,t]):i+=t<'>'?1:-1), // pack each []+-,. into (pos,instr)
    f=(r,i=0)=>{
        2*n in r?(
            i=n,y='',
            x.map(([j,t])=>y+=((j=r[j]-i)<0?'<':'>').repeat(j>0?j:-j,i+=j)+t), // generate instr
            s[y.length]&&(s=y)
        ):
        i>2*n||f(r,i+1,r.includes(i)||f([...r,i]))     // r be all rearrangements of [0,2n]
    },f``,s
)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.