Submission b7d0b207...

ChallengeBrainFuck interpreter
Submitter0xabcdef0db461f2f...
Submitted at2018-09-03
Gas used2194736
/**
 * 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.
     */
    function execute(bytes program, bytes input) public pure returns(bytes) {
        uint progLen = clean(program);
        uint8[] memory ram = new uint8[](1024);
        uint oIdx = brainfuck(program, input, progLen, ram);
        bytes memory ret = new bytes(oIdx-progLen);
        for (uint i = 0; i < ret.length; i++) {
            ret[i] = byte(ram[progLen+i]);
        }
        return ret;
    }

    function clean(bytes program) internal pure returns(uint) {
        uint i = 0;
        uint j = 0;
        byte token;
        while (i < program.length) {
            token = program[i];
            if (token < 0x2b
                    || token > 0x5d
                    || (token > 0x2e && token < 0x3c)
                    || (token > 0x3e && token < 0x5b)
                    || token == 0x3d
                    || token == 0x5c) {
            } else {
                program[j] = token;
                j++;
            }
            i++;
        }
        return j;
    }

    function brainfuck(
        bytes program, bytes input, uint progLen, uint8[] memory ram
    ) internal pure returns(uint) {
        uint ptr = 0;
        uint pIdx = 0;
        uint iIdx = 0;
        uint oIdx = progLen;
        byte token;
        uint[] memory stack = new uint[] (16);
        uint sIdx = 0;
        while (pIdx < progLen) {
            token = program[pIdx];
            if (token < 0x30) {
                if (token < 0x2d) {
                    if (token == 0x2b) {
                        ram[ptr] += 1;
                    } else {
                        ram[ptr] = uint8(input[iIdx]);
                        iIdx++;
                    }
                } else {
                    if (token == 0x2d) {
                        ram[ptr] -= 1;
                    } else {
                        ram[oIdx] = ram[ptr];
                        oIdx++;
                    }
                }
            } else {
                if (token < 0x40) {
                    if (token == 0x3c) {
                        ptr -= 1;
                    } else {
                        ptr += 1;
                    }
                } else {
                    if (token == 0x5b) {
                        if (ram[ptr] == 0) {
                            pIdx++;
                            while (program[pIdx] != 0x5d) {
                                pIdx++;
                            }
                        } else {
                            stack[sIdx] = pIdx;
                            sIdx++;
                        }
                    } else {
                        if (ram[ptr] == 0) {
                            sIdx--;
                        } else {
                            pIdx = stack[sIdx-1];
                        }
                    }
                }
            }
            pIdx++;
        }
        return oIdx;
    }
}