Submission 2af336b3...

ChallengeBrainFuck interpreter
Submitter0x53b21be84eece2e...
Submitted at2018-21-25
Gas used2384333
/**
 * 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 {
    /**
     * @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.
     */
    
    // 2297819
    // 2217770
    function execute(bytes program, bytes input) public pure returns(bytes) {
        // [62 60 43 45 46 44 91 93]
        //  >  <  +  -  .  ,  [  ]

        uint prog_len = program.length;
        uint8[] memory tape = new uint8[](1024);
        uint8[] memory output = new uint8[](1024);
        uint[] memory brace = new uint[](prog_len);
        uint pointer = 0;
        uint outpointer = 0;
        uint inpointer = 0;
        uint i = 0;
        // uint max_i = 0;
        uint match_lbrace = 0;
        // uint8 val;

        for (i = 0; i < prog_len; i++) {
            uint8 char;
            // assembly {
            //     char := div(mload(add(program, add(0x20, i))), 0x100000000000000000000000000000000000000000000000000000000000000)
            // }
            char = uint8(program[i]);
            if (char == 91) { // [
                brace[i] = match_lbrace;
                match_lbrace = i;
            }
            else if (char == 93) { // ]
                brace[i] = match_lbrace;
                match_lbrace = brace[match_lbrace];
            }
        }

        for (i = 0; i < prog_len; i++) {
            char = uint8(program[i]);

            if (char < 50) {
                if (char == 43) { // +
                    tape[pointer]++;
                }
                else if (char == 45) { // -
                    tape[pointer]--;
                    // val--;
                    // tape[pointer] = val;
                    // tape[pointer] = val == 0 ? 255 : val - 1;
                }
                else if (char == 44) { // ,
                    tape[pointer] = uint8(input[inpointer++]);
                }
                else if (char == 46) { // .
                    output[outpointer++] = tape[pointer];
                }
            } else {
                if (char == 62) { // >
                    pointer++;
                }
                else if (char == 60) { // <
                    pointer--;
                }
                // else if (char == 91) { noop } // [
                else if (char == 93) { // ]
                    if (tape[pointer] != 0) {
                        i = brace[i];
                    }
                }
            }
        }

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


    }
}