Submission 8b539934...

ChallengeBrainFuck interpreter
Submitter0xabcdef0db461f2f...
Submitted at2018-05-28
Gas used10547613
/**
 * 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) {
        uint8[] memory ram = new uint8[](1024);
        uint[] memory reg = new uint[](4);
        brainfuck(program, input, ram, reg);
        bytes memory ret = new bytes(reg[3]);
        for (uint i = 0; i < reg[3]; i++) {
            ret[i] = byte(ram[1023-i]);
        }
        return ret;
    }

    function brainfuck(
        bytes program, bytes input,
        uint8[] memory ram, uint[] memory reg
    ) internal pure {
        uint stack;
        while (reg[1] < program.length) {
            if (program[reg[1]] < 0x2f) {
                if (program[reg[1]] == 0x2b) {
                    ram[reg[0]] += 1;
                } else if (program[reg[1]] == 0x2c) {
                    ram[reg[0]] = uint8(input[reg[2]]);
                    reg[2]++;
                } else if (program[reg[1]] == 0x2d) {
                    ram[reg[0]] -= 1;
                } else if (program[reg[1]] == 0x2e) {
                    ram[1023-reg[3]] = ram[reg[0]];
                    reg[3]++;
                }
            } else if (program[reg[1]] < 0x3f) {
                if (program[reg[1]] == 0x3c) {
                    reg[0] -= 1;
                } else if (program[reg[1]] == 0x3e) {
                    reg[0] += 1;
                }
            } else if (program[reg[1]] < 0x5e) {
                if (program[reg[1]] == 0x5b) {
                    reg[1]++;
                    stack = reg[1];
                    while (ram[reg[0]] > 0) {
                        reg[1] = stack;
                        brainfuck(program, input, ram, reg);
                    }
                } else if (program[reg[1]] == 0x5d) {
                    return;
                }
            }
            reg[1]++;
        }
    }
}