Brainfuck in Ruby

Brainfuck in Ruby

Brainfuck could be described as a Turing tarpit - it can be formally proven that it is equal in power to most other programming languages, but it is tremendously difficult to actually do anything useful in it.

Nevertheless, it is a nice coding challenge; I wrote a intepreter for it in Ruby, and improved the standard by doing some optimizations not necessarily required by a simple one.

module Brainfck ## # Evaluates the given Brainf*ck program with the given input, and returns the output. Improved from the CodeWars version published earlier. # def self.evaluate(prog, input) #1st optimization - remove all non-significant characters from program command_array = prog.chars.select {|cmd| cmd =~ /[\[\]\<\>\+\-\,\.]/} #Convert the input to a stack form input_stack = input.chars.reverse #2nd optimization; look through the code, and save the precise locations of brackets, so that we don't have to search the main command array back and forth for them bracket_positions = [] command_array.map!.with_index do |cmd, i| if (cmd == "]" || cmd == "[") then bracket_positions << "#{cmd}#{i}" #Save the location of this bracket in the main command array to the quick-search array "#{cmd}#{bracket_positions.length-1}" #Put in a version which contains the precise location of this bracket in the quick-search array else cmd #Not a bracket, as is end end #### command_pointer = 0 #Points to where we are in the command array data_pointer = 0 #Data pointer; points to memory locations output_buffer = "" #Buffer for output #The nature and size of the memory in Brainf*ck machines is not strictly defined. To make the implementation slightly easier and to support "negative" addresses, let's use a hash memory_hash = Hash.new(0) #Loop until we end up outside the array of commands while ((0...command_array.length).include?(command_pointer)) cmd = command_array[command_pointer] case cmd when /[\<\>]/ data_pointer += (cmd == ">" ? 1 : -1) #Adjust the pointer as given when /[\+\-]/ #Adjust the value at the pointer as given val = memory_hash[data_pointer] val += (cmd == "+" ? 1 : -1) #We set the size of a value as one byte; it is not strictly defined anywhere, but is a possible option if (val < 0) then memory_hash[data_pointer] = 255 else memory_hash[data_pointer] = val % 256 end when "." #Write the value at the current location to output output_buffer << memory_hash[data_pointer].chr when "," #Take a byte and put it in memory, if possible - if not, leave it be memory_hash[data_pointer] = input_stack.pop.ord unless input_stack.empty? when /[\[\]].+/ jump_forward = (cmd[0] == "[") #Are we jumping forward? #As defined for Brainf*ck: if we are jumping forward, the byte at the given location must be zero. And if we want to jump backwards, nonzero if (jump_forward && memory_hash[data_pointer] == 0) || ((!jump_forward) && memory_hash[data_pointer] != 0) then array_index = cmd[1..-1].to_i #Index where we want to start searching from; [1..-1] slices the command so that the index is left. subset_array = jump_forward ? bracket_positions[(array_index+1)..-1] : bracket_positions[0..(array_index-1)].reverse #Which direction we shall step towards? If forward, slice till the end; if backward, slice to the beginning and reverse #We shall find the nearest matching bracket. Do note that it is not necessarily the same as the NEAREST bracket. #Let's use a counter. If we start from an opening bracket, let it be 1, otherwise -1. We seek a 0 balance_counter = jump_forward ? 1 : -1 nearest_bracket = subset_array.find do |chr| #Find the first bracket leading to a balance (that is, equal amount of openings and closures) balance_counter += (chr[0] == "[") ? 1 : -1 #Adjust the counter as fit balance_counter == 0 #Interrupt the loop, if we've found the desired bracket end #Place the pointer just before the command we'd like to jump to command_pointer = nearest_bracket == nil ? -2 : nearest_bracket[1..-1].to_i end else #Unknown command, skip end #Increment the command pointer command_pointer += 1 end #Return the buffer return output_buffer end end