Submission 616d4783...

ChallengeBrainFuck interpreter
Submitter0xd0b40847c318da4...
Submitted at2018-42-30
Gas used5579974
/**
 * 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 len = program.length;
        uint ipp;
        uint opp;
        uint dp;
        uint ip;
        uint[] memory jumpStack;
        uint[] memory jump;
        bytes memory mem = new bytes(1024);
        bytes memory output = new bytes(1024);

        if (len == 0) {
            return;
        }

        for(dp = len - 1; dp < len; dp--) {
            if (program[dp] == ']') {
                break;
            }
        }

        dp++;
        if (dp > 0) {
            jump = new uint[](dp);
            jumpStack = new uint[](dp/2);
        }

        for(ip = 0; ip < dp; ip++) {
            if(program[ip] == '[') {
                ipp++;
                jumpStack[ipp] = ip;
            } else if(program[ip] == ']') {
                opp = jumpStack[ipp];
                jump[opp] = ip;
                jump[ip] = opp;
                ipp--;
            }
        }

        opp = ipp = dp = 0;
        for(ip = 0; ip < len; ip++) {
            byte instruction = program[ip];
            if(instruction == '+') {
                mem[dp] = byte(uint(mem[dp]) + 1);
            } else if(instruction == '-') {
                mem[dp] = byte(uint(mem[dp]) - 1);
            } else if(instruction == '>') {
                dp++;
            } else if(instruction == '<') {
                dp--;
            } else if(instruction == '.') {
                output[opp++] = mem[dp];
            } else if(instruction == ',') {
                mem[dp] = input[ipp++];
            } else if(instruction == '[') {
                if(mem[dp] == 0) {
                    ip = jump[ip];
                }
            } else if(instruction == ']') {
                if(mem[dp] != 0) {
                    ip = jump[ip];
                }
            }
        }

        if (opp == 1024) {
            return output;
        }

        bytes memory ret = new bytes(opp);
        for(ip = 0; ip < opp; ip++) {
            ret[ip] = output[ip];
        }
        return ret;
    }
}
/*
        for (dp = len - 1; dp < len; dp--) {
            if(program[dp] == ']') {
                break;
            }
        }
        uint[] memory jump;
        if(dp > 0 && dp < len) {
            jump = new uint[](dp+1);
        }
        for(ip = 0; ip < dp; ip++) {
            if(program[ip] == '[') {
                for(;dp > ip; dp--) {
                    if(program[dp] == ']') {
                        jump[dp] = ip;
                        jump[ip] = dp;
                        break;
                    }
                }
            }
        }
*/