Brainfuck code optimization in Python

Question

I wrote a program to automatically optimize my Brainfuck source files. It works well, but the optimizations are only trivial ones and probably there are still some other points to improve.

def main():
 print "Enter the path of a brainfuck source file you want to optimize"
 path = raw_input()
 if path in ('exit', 'quit', 'close'):
 exit()
 f = open(path, 'r')
 text = f.read()
 f.close()
 cmd = '' # removing comments and whitespaces
 for c in text:
 if c in ('+', '-', '<', '>', '.', ',', '[', ']'):
 cmd += c
 found = True
 while found:
 length = len(cmd)
 found = False
 for i in range(length-1):
 if cmd[i:i+2] in ('+-', '-+', '<>', '><'):
 cmd = cmd[0:i] + cmd[i+2:length] # removing useless instruction pairs
 found = True
 ending = ''
 for i in range(len(path)):
 if path[i] == '.':
 ending = path[i:len(path)]
 path = path[0:i]
 break
 path = path + '_opt' + ending
 f = open(path, 'w')
 f.write(cmd)
 f.close()
if __name__ == '__main__':
 while True:
 main()

EDIT:
I'm considering about removing whole brackets, if it is obvious that they are never called. This is the case, if an opening bracket is directly after a closing bracket (][), because the first loop only breaks if the current cell value is zero and that means, that either the pointer or the cell value has to change to make the second loop work. However, unlike the other optimizations, I can't just remove ][, it should remove everything between [and the matching ] (including [ and ]). Are there any other cases I could remove unnecessary brainfuck code?

Answer 1

I'd do a couple of things:

• Remove exit. It's not intended to be use in proper programs.
• Add more functions, it's hard to tell what your current code is doing, and so adding a new function would make your code more understandable, and functions with good names are easy to understand.
• Your code that uses the found flag is terribly inefficient, you want to check if the previous character combined with the current character are in the optimize list, as then you can remove the previous character, and otherwise add the new character.
• You should always use with when you are using an object. This is as even if you come across an error when using the file, it will safely close the file for you and will remove the need to call .close.
• Change the way that you find the first period in the path. You can use ''.find, to find the first occurrence of a character in a string, rather than looping through the string.

Adding all the above to your program can get you:

ALLOWED_CHARS = {'+', '-', '<', '>', '.', ',', '[', ']'}
USELESS = {'+-', '-+', '<>', '><'}
def new_file_location(path):
 dot = path.find('.')
 head, ending = path[:dot], path[dot:]
 return head + '_opt' + ending
def remove_useless(cmd):
 new_cmd = []
 for char in cmd:
 if new_cmd and (new_cmd[-1] + char) in USELESS:
 new_cmd.pop()
 else:
 new_cmd.append(char)
 return ''.join(new_cmd)
def main(cmds):
 return remove_useless(c for c in cmds if c in ALLOWED_CHARS)
if __name__ == '__main__':
 while True:
 path = raw_input("Enter the path of a brainfuck source file you want to optimize")
 if path in ('exit', 'quit', 'close'):
 break
 with open(path) as f:
 text = f.read()
 cmd = main(text)
 with open(new_file_location(path), 'w') as f:
 f.writ(cmd)

Finally I'd change the way that new_file_location works, in *nix you use .filename for secret folders, and so your program will do things such as change this, /home/peilonrayz/.python/brainfuck.py, to /home/peilonrayz/._optpython/brainfuck.py... Not really what you want.

• Aemyl: Thank you! But why are you using { and }to define ALLOWED_CHARS and USELESS? It looks like a dictionary without keys or like a list with dictionary brackets o.O or does it mean something else, like constant lists?
• Peilonrayz: @Aemyl it's a set which is like a dictionary, just without values
• Aemyl: After using this good mentions, I have two new small questions: First: shouldn't I rather use ( and ) to define ALLOWED_CHARS and USELESS? Because they actually don't need to be changed. Second: Does it make sense to save ('exit', 'quit', 'close') in an extra tuple called EXIT_COMMANDS or something like this? By the way, I guess the last codeline in your answer was intended to be f.write(cmd)
• Peilonrayz: @Aemyl For you first question chose which data-type is best for the job, if you want to force it to be immutable, use a frozen set, but if you don't need \$O(1)\$ lookup a tuple could be good. For your second yes you can do that. And yeah that was a typo
• Aemyl: based on your mention on the efficiency of the found-flag, I used it because if I iterate over a string like ++--, the program just recognizes one +- in the middle. The output +- still contains unnecessary command pairs

Answer 2

Some quick remarks:

You should be using the with..as construct when opening a file to ensure it is always closed, even if some intermediate code raises an exception:

with open(path) as f:
 text = f.read()
...
with open(path, 'w') as f:
 f.write(cmd)

I would save the comment commands in a set and outside of the loop. in is O(1) for sets and O(n) for tuples (even though n=4 here).

cmds = {'+-', '-+', '<>', '><'}
found = True
while found:
 length = len(cmd)
 found = False
 for i in range(length-1):
 if cmd[i:i+2] in cmds:
 cmd = cmd[0:i] + cmd[i+2:length] # removing useless instruction pairs
 found = True

I would do the same with the longer command tuple before that:

comment_codes = {'+', '-', '<', '>', '.', ',', '[', ']'}
for c in text:
 if c in comment_codes:
 cmd += c

You could also use a generator comprehension and str.join here:

comment_codes = {'+', '-', '<', '>', '.', ',', '[', ']'}
cmd = "".join(c for c in text if c in comment_codes)

Your building of the output filename can be simplified using split and could use str.format:

name, ext = path.split('.')
path = '{}_opt.{}'.format(name, ext)