Minify Brainfuck

Question

Your challenge is to minify Brainfuck code, according to these rules:

• Remove anything that is not one of +-><[].,.
• For any group of consecutive + or - characters, if the amount of +s and -s is the same, remove them.
• Do the same as above, but with > and <.
• Remove sequences of the +->< characters if they do nothing. For example, you should remove +>-<->+<. (This may be the trickiest and hardest one to implement.) Make sure you don't get any false positives, like +>-<+>-<, which should not be removed.

---

Test cases:

Input

++++++[->++++++<]>.   prints a $
[-]<                  resets tape
>,[>,]<[.<]           reverses NUL terminated input string
++-->><<              does nothing

Output

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

Input

Should disappear: ++>>+<+++<->-->-<<->-<
Should disappear: +++>-<--->+<
Should stay: +++>-<+>---<

Output

+++>-<+>---<

---

You may accept input and output however you would like - stdin/stdout, a function, etc., but input may not be hardcoded.

This is code-golf, so the shortest code in character count will win.

Answer 1

Brainfuck, 579 bytes

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

With formatting and some comments:

,
[
  <<+>> >>+<<
  [
    [<+> >+<-]
    ++++++[>-------<-]
    >-
    [
      not plus
      -
      [
        not comma
        -
        [
          not minus
          -
          [
            not period
            --------------
            [
              not less than
              --
              [
                not greater than
                <+++++[>------<-]>+
                [
                  not open bracket
                  --
                  [
                    not close bracket
                    <<[-]>>-
                  ]
                ]
                <
              ]
              >
              [
                greater than
                >>-<<
                <<<[-]<[<]<<<[<]
                >>>>>>>>[<]
                <-[+>]
                +[->+]
                >>>>+>[<-]
                <[>+<-<]
                >
              ]
              <
            ]
            >
            [
              less than
              <<<[-]-[<]
              >>>> >>>>>>>[<]
              <<<<<<[<]
              <-[+>]
              +[-<+]
              <<<+<[>-<<<]
              >[-<+<]
            ]
          ]
          <
        ]
        >
        [
          minus
          +>[-<]
          <[<<]
          <[-]>>
        ]
      ]
      <
    ]
    +>
    [
      plus
      -[<-]
      <[>+>+<<-<]
      <[-]>+>
    ]
    <<
    [
      comma or period or bracket
      >-
    ]
    >[,>]
    <
  ]
  comma or period or bracket or eof
  <+<
  [
    start and end same cell
    >
  ]
  >
  [
    >>>
    [
      <<<<[-<]<<<
    ]
    >>>+>>>>
    [
      start right of end
      <<<<->>>>
      [>>>[-<]>>>>]
    ]
  ]
  >
  [
    <<<
    [
      <+[-->>]
    ]
    >[-[.[-]]]
    >[<]
    >
    [
      <<++++++[>+++++++<-]>+>>
      [<<.>>-]
      <<++>-[<.>-]
      +++[<+++++>-]
      +<<<<< <+>
      [
        <<
        [
          go left
          >->>>>>.
          [[-]<<<<]
          <<<+>>>
        ]
        >
        [
          toggle left right
          ->->>>>[-]
        ]
      ]
      <
      [
        toggle right left
        ->+[>>>>>]>>[<]
        <<<<<<<<
        [
          [-]<
        ]
        >
        [
          go right
          ++.[-]
          >>>>>>>
        ]
        <
      ]
    ]
    >>
  ]
  <[>>>>>>>]
  +[-<<<<<[-]<<]
  ,
]

This uses the same approach as Keith Randall's solution, minifying all contiguous sequences of +-<> optimally by simulation. For example, +++>-<+>---< becomes ++++>----< and >+<+<<+>+<->>>> becomes +<+>>+>.

Try it online. (If a simulated cell's absolute value gets close to 256, there will be overflow issues.)

The overall structure is

while not EOF:
  while not EOF and next char not in ",.[]":
    process char
  print minified sequence (followed by the char in ",.[]" if applicable)

The tape is divided into 7-cell nodes; at the beginning of the inner loop, the memory layout is

0 s 0 c 0 a b

where s is a boolean flag for start cell, c is the current character, a is the negative part of the simulated cell value (plus one), and b is the positive part of the simulated cell value.

When the minified sequence is being printed, the memory layout is

d n e 0 0 a b

where d is a boolean flag for direction, a and b are as before (but become one/zero when printed), and n and e are only nonzero for the end node; n is related to how many times the node has been seen, and e is the value of the char that halted the inner loop (plus one).

Originally I considered keeping track of more information per node: leftmost and rightmost node as boolean flags, and node's position in relation to the start and end nodes. But we can avoid that by looking at neighboring cells when needed, and by doing left and right scans in order to find the start node.

When printing the minified sequence and deciding how to move the simulated pointer, we can take a general approach: start by moving away from the end node (in an arbitrary direction if start and end nodes are the same), turn around at leftmost and rightmost nodes, and stop based on the number of times the end node has been seen: 3 times if the start and end nodes are the same, otherwise 2.

Answer 2

REBEL - 104

_/^_$/$</([^][<>.,+-]|\+-|-\+|<>|><)//((?<X>(<|>))+[+-]+(?!\2)(?<-X><|>)+(?(X)(?!)))([+-]+)/$3$1/.+/$>$&

Usage:

Input: Reads one line from stdin.

Output: Prints one line to stdout.

Anomalies*:

• Entering _ causes another line to be read and used, rather than outputting nothing.
• The second test outputs ++++>----< instead of +++>-<+>---<. But that's OK, right? ;)
• >-<+ etc. are replaced with +>-< etc.

Spoiler:

Implementing anomaly #3 makes things quite trivial.

_{* It's not a bug, it's a feature!}

Answer 3

Python, 404 chars

This code does a perfect optimization of all subsequences of +-<>. A bit more than you asked for, but there you go.

M=lambda n:'+'*n+'-'*-n                                                           
def S(b):                                                                         
 s=p=0;t=[0];G,L='><'                                                             
 for c in b:                                                                      
  if'+'==c:t[p]+=1                                                                
  if'-'==c:t[p]-=1                                                                
  if G==c:p+=1;t+=[0]                                                             
  if L==c:s+=1;t=[0]+t                                                            
 if p<s:k=len(t)-1;t,p,s,G,L=t[::-1],k-p,k-s,L,G                                  
 r=[i for i,n in enumerate(t)if n]+[s,p];a,b=min(r),max(r);return(s-a)*L+''.join(M(n)+G for n in t[a:b])+M(t[b])+(b-p)*L                                           
s=b=''                                                                            
for c in raw_input():                                                             
 if c in'[].,':s+=S(b)+c;b=''                                                     
 else:b+=c                                                                        
print s+S(b) 

It works by simulating the +-<> operations on the tape t. s is the starting position on the tape and p is the current position. After simulation, it figures out the extent [a,b] that needs to be operated on and does all the +/- in one optimal pass.

Answer 4

CoffeeScript - 403 397

i=prompt().replace /[^\]\[,.+-><]/g,''
x=(c)->
 t={};p=n=0
 for d in c
  t[p]?=0;switch d
   when'+'then n=1;t[p]++;when'-'then n=1;t[p]--;when'<'then p--;when'>'then p++
 (n=0if v!=0)for k,v of t;n
s=e=0;((e++;(i=(i.substr 0,s)+i.substr e;e=s=0)if x (i.substr s,e-s).split "")while(i[e]||0)!in['[',']',0];e=++s)while s<=i.length
r=/(\+-|-\+|<>|><|^[<>]$)/g
i=i.replace r,'' while r.test i
alert i

Demo (please forgive the use of bit.ly here, the whole URL would break the markdown)

Uncompressed version (w/ debug code):

console.clear()
input = """Should disappear: ++>>+<+++<->-->-<<->-<
Should disappear: +++>-<--->+<
Should stay: +++>-<+>---<"""

input = input.replace /[^\]\[,.+-><]/g, ''
console.log input

execute = (code) ->
  stack = {}
  item = 0
  console.log code
  nop = false
  for char in code
    switch char
      when '+' then nop = true; stack[item]?=0;stack[item]++
      when '-' then nop = true; stack[item]?=0;stack[item]--
      when '<' then item--
      when '>' then item++
  console.debug stack
  (nop = false if v != 0) for k,v of stack
  nop
start = 0
end = 0

while start <= input.length
 while input.charAt(end) not in [ '[', ']', '' ]
  end++
  if execute (input.substring start, end).split("")
    input = (input.substring 0, start) + input.substring end
    end = start = 0
    console.log input
 end = ++start
input = input.replace /(\+-|-\+|<>|><|^(<|>)$)/g, '' while /(\+-|-\+|<>|><)/.test input
console.log 'Result: ' + input