22
\$\begingroup\$

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 , so the shortest code in character count will win.

\$\endgroup\$
  • 4
    \$\begingroup\$ I know this is an old challenge, but the test cases are inadequate. ++>>++<<-- should output >>++<<, and that wasn't covered. Please add more test cases. \$\endgroup\$ – mbomb007 Feb 29 '16 at 22:20
  • \$\begingroup\$ @mbomb007 did you examine the last test case, +++>-<+>---<? It can be shortened to avoid unnecessary pointer movement, but the expected output leaves it unchanged. My understanding based on looking at both the question and the answers is that Doorknob is cool with the spec being taken loosely; we must eliminate any no-op contiguous +->< sequences as explicitly stated, and beyond that it is permissible to do extra minifying as in your example ++>>++<<--, and we can also make rearrangements as long as they don't change the functionality of the code, e.g. >+<+ into +>+<. \$\endgroup\$ – Mitch Schwartz Oct 26 '16 at 4:26
  • \$\begingroup\$ @MitchSchwartz "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." - this is kind of vague \$\endgroup\$ – mbomb007 Oct 26 '16 at 13:40
  • \$\begingroup\$ @mbomb007 And the second and third bullet points are redundant and unnecessary because they are included in the fourth bullet point. So what? It's a cool task. My comment was meant to be constructive and provide clarification, not to attack you. Please take it the way I intended, or tell me how I should have said it differently. Because you did not really address what I wrote; it just seems like you're trying to defend yourself without really being constructive. In what way do you find it vague? How would you rewrite it? Do you want to edit the question? Do you want to ask Doorknob? \$\endgroup\$ – Mitch Schwartz Oct 26 '16 at 14:07
  • 1
    \$\begingroup\$ Oh, so we only have to remove contiguous sequences? \$\endgroup\$ – mbomb007 Oct 26 '16 at 14:19
10
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ "it's not a bug its a feature" +1! \$\endgroup\$ – Rohan Jhunjhunwala Aug 1 '16 at 2:18
36
+500
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Source: brainfuck. Target: brainfuck. +1 \$\endgroup\$ – Erik the Outgolfer Oct 28 '16 at 8:36
  • 2
    \$\begingroup\$ This fulfills an indefinite bounty \$\endgroup\$ – Destructible Lemon Oct 28 '16 at 9:47
  • 1
    \$\begingroup\$ I'll let this attract some attention and award the bounty in a day or two \$\endgroup\$ – lirtosiast Oct 29 '16 at 23:04
  • 1
    \$\begingroup\$ @MitchSchwartz Did you happen to test your code against your code? You may actually shorten it! #meta \$\endgroup\$ – WallyWest Oct 30 '16 at 0:08
  • 1
    \$\begingroup\$ @WallyWest (That appears to save 7 bytes!) Nevermind, the code in the permalink has linebreaks. \$\endgroup\$ – Dennis Oct 30 '16 at 0:11
7
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ An alternative way of posting Coffeescript demos is to use JSFiddle. In the left margin there's a "Languages" config pane which lets you use CoffeeScript instead of JS. \$\endgroup\$ – Peter Taylor Dec 30 '13 at 14:04
  • \$\begingroup\$ @PeterTaylor Thanks, i knew about JSFiddle before, but not that it is able to use CoffeeScript \$\endgroup\$ – TimWolla Dec 30 '13 at 15:07
  • \$\begingroup\$ This fails on >+.-<, producing the empty string instead of leaving it unchanged. \$\endgroup\$ – Mitch Schwartz Nov 3 '16 at 15:46

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.