Brainf**k

17Nov13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

Brainf**k

Brainf**k is an esoteric programming language. It consists of the following eight commands:

>
Increments the data pointer
<
Decrements the data pointer
+
Increments the byte at the data pointer
Decrements the byte at the data pointer
.
Output the byte at the data pointer
Get one byte of input and store it in the byte at the data pointer
[
If the byte at the data pointer is zero, jump forward to the matching ] command
]
If the byte at the data pointer is nonzero, jump backward to the matching [ command

Any other symbols or characters are treated as comments.

The following Brainf**k program prints “Hello World!”:

+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
- - - - - - .           print 'l'
- - - - - - - - .       print 'd'
> + .                   print '!'
> .                     print '\n'

Just as in a previous puzzle, write an interpreter for the Brainf**k programming language

Solution (Brainf**k.py):

# Solution for problem "Brainf**k" (17th November 2013) of http://ContestCoding.WordPress.com/

from __future__ import print_function

def increment_data_pointer(): # >
  global data_pointer, data
  data_pointer += 1
  if data_pointer >= len( data ):
    data = data + [ 0 ]

def decrement_data_pointer(): # <
  global data_pointer, data
  data_pointer -= 1
  if data_pointer < 0:
    data_pointer = 0
    data = [ 0 ] + data

def increment_value_at_data_pointer(): data[ data_pointer ] += 1 # +

def decrement_value_at_data_pointer(): data[ data_pointer ] -= 1 # -

def get_value_at_data_pointer__character(): print( chr( data[ data_pointer ] ), end = "" ) # .

def set_value_at_data_pointer__character(): # ,
  global input_buffer
  while input_buffer is None:
    input_buffer = raw_input()
    if len( input_buffer ) < 1:
      input_buffer = None
  data[ data_pointer ] = ord( input_buffer[ 0 ] )
  input_buffer = input_buffer[ 1 : ]
  if len( input_buffer ) < 1:
    input_buffer = None

instruction_function_map = { '>':increment_data_pointer,
                             '<':decrement_data_pointer,
                             '+':increment_value_at_data_pointer,
                             '-':decrement_value_at_data_pointer,
                             '.':get_value_at_data_pointer__character,
                             ',':set_value_at_data_pointer__character }

data = [ 0 ]
data_pointer = 0

input_buffer = None

instructions = []
instruction_pointer = 0

fname = raw_input( "Please enter the file name of the Brainfuck program to execute: " )
f = open( fname, 'r' )
jump_stack = []
for line in f:
  for character in line:
    if character in ( '>', '<', '+', '-', '.', ',', '[', ']' ):
      instructions.append( character )
      if character == '[':
        jump_stack.append( len( instructions ) - 1 )
      elif character == ']':
        if len( jump_stack ) == 0:
          quit( "Error: unmatched jump if non-zero/']' instruction." )
        index = jump_stack.pop()
        instructions[ index ] = ( '[', len( instructions ) - 1 )
        instructions[ -1 ] = ( ']', index )
if len( jump_stack ) != 0:
  quit( "Error: unmatched jump if zero/'[' instruction." )

while instruction_pointer < len( instructions ):
  instruction = instructions[ instruction_pointer ]
  if isinstance( instruction, str ):
    instruction_function_map[ instruction ]()
  elif instruction[ 0 ] == '[':
    if data[ data_pointer ] == 0:
      instruction_pointer = instruction[ 1 ]
  else:
    if data[ data_pointer ] != 0:
      instruction_pointer = instruction[ 1 ]
  instruction_pointer += 1
Advertisements


No Responses Yet to “Brainf**k”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: