Submission 2ca7bb4d...

ChallengeBrainFuck interpreter
Submitter0xff3c2241cd767b7...
Submitted at2018-34-25
Gas used3083515
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract BrainFuck {
    // This implementation:    2944896
    /**
     * @dev Executes a BrainFuck program, as described at https://en.wikipedia.org/wiki/Brainfuck.
     *
     * Memory cells, input, and output values are all expected to be 8 bit
     * integers. Incrementing past 255 should overflow to 0, and decrementing
     * below 0 should overflow to 255.
     *
     * Programs and input streams may be of any length. The memory tape starts
     * at cell 0, and will never be moved below 0 or above 1023. No program will
     * output more than 1024 values.
     *
     * @param program The BrainFuck program.
     * @param input The program's input stream.
     * @return The program's output stream. Should be exactly the length of the
     *          number of outputs produced by the program.
     */
    function execute(bytes program, bytes input) public pure returns(bytes) {
      uint i = 0;
      uint d = 0;
      uint8[1024] memory data;
      uint8[1024] memory output;
      uint output_pointer = 0;
      uint input_pointer = 0;

      uint[] memory jumpmap = new uint[](program.length);
      uint[] memory jumpmaptmp = new uint[](program.length/2);
      // Fill in the jumpmap
      uint depth;
      for (uint j=0; j<program.length; j++){
        if (program[j]=="["){
          depth +=1;
          jumpmaptmp[depth] = j;
        } else if (program[j] == "]"){
          jumpmap[j] = jumpmaptmp[depth];
          jumpmap[jumpmaptmp[depth]] = j;
          depth -=1;
        } else if (program[j] == ">"){
          i = 1;
          while (program[j+i] == ">"){
            i+=1;
          }
          jumpmap[j] = i;
          j+=i;
        }
      }
      i=0;
      while (i < program.length){
        byte instruction = program[i];
        // Valid instructions are 0x3c 0x3e 0x2e 0x2c 0x2b 0x2d 0x5b 0x5d
        if (instruction & 0x0f < 0x0b){
          // Then it's a noop instruction. This doesn't catch all of them, but catches more
          // than half of them, and there seems to be a lot of them.
        } else if (instruction=="+"){
          data[d]+=1;
        } else if (instruction=="-"){
          data[d]-=1;
        }
        else if (instruction==">"){
          d+=jumpmap[i];
          i+=jumpmap[i];
          i-=1;
        } else if (instruction=="<"){
          d-=1;
        } else if (instruction=="."){
          // output
          output[output_pointer] = data[d];
          output_pointer+=1;
        } else if (instruction == "["){
          if (data[d]==0){
            i=jumpmap[i];
          }
        } else if (instruction == "]"){
          if (data[d]!=0){
            i=jumpmap[i];
          }
        } else if (instruction==","){
          // input
          data[d] = uint8(input[input_pointer]);
          input_pointer+=1;
        }
        i+=1;
      }

      bytes memory ret = new bytes(output_pointer);
      for (i=0; i< output_pointer; i++){
        ret[i] = byte(output[i]);
      }
      return ret;
    }
}