Submission d3aed5db...

Challenge	BrainFuck interpreter
Submitter	0xff3c2241cd767b7...
Submitted at	2018-04-26
Gas used	2742615

/**
 * 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:    2685670
    /**
     * @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 >= 0x3c){
          if (instruction > 0x5a){
            // [ or ]
            if (instruction == "["){
              if (data[d]==0){
                i=jumpmap[i];
              }
            } else if (instruction == "]"){
              if (data[d]!=0){
                i=jumpmap[i];
              }
            } else {
              program[i] = 0x00;
            }
          } else {
            if (instruction==">"){
              d+=jumpmap[i];
              i+=jumpmap[i];
              i-=1;
            } else if (instruction =="<"){
              d-=1;
            } else {
              program[i] = 0x00;
            }
          }
        } else {
          if (instruction > 0x2c){
            // - or .
            if (instruction=="-"){
              data[d]-=1;
            } else if (instruction=="."){
              // output
              output[output_pointer] = data[d];
              output_pointer+=1;
            } else {
              program[i] = 0x00;
            }
          }else {
            if (instruction=="+"){
              data[d]+=1;
            } else if (instruction==","){
              // input
              data[d] = uint8(input[input_pointer]);
              input_pointer+=1;
            } else {
              program[i] = 0x00;
            }
          }
        }

        i+=1;
      }

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