BF memory layout optimizer

Question

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.

Answer 1

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
)