import std.stdio, std.algorithm, std.conv, std.range, std.typecons,
       std.string, std.array;

struct UTM {
    enum : char {right, left, stay}

    private TapeHead head;
    private const TuringMachine tm;

    static struct TuringMachine {
        char[] symbols;
        char blank;
        char initialState;
        char[] haltStates, runningStates;
        char[][string] rules;
        char[] input;
    }

    static struct TapeHead {
        const char[] symbols;
        const char blank;
        char[] tape;
        size_t index;

        this(in ref TuringMachine t) {
            this.symbols = t.symbols;
            this.blank = t.blank;
            this.tape = t.input.dup;
            if (tape.empty)
                tape = [blank];
            this.index = 0;
        }

        auto read() const pure nothrow {
            return this.tape[this.index];
        }

        void write(in char symbol) {
            .write(this);
            this.tape[this.index] = symbol;
        }

        void right() pure nothrow {
            this.index++;
            if (index == tape.length)
                tape ~= blank;
        }

        void left() pure nothrow {
            if (this.index == 0)
                this.tape = this.blank ~ this.tape;
            else
                this.index--;
        }

        void stay() const pure nothrow {
            // Do nothing.
        }

        void move(in char dir) {
            switch (dir) {
                case UTM.left:  left();  break;
                case UTM.right: right(); break;
                case UTM.stay:  stay();  break;
                default: assert(0);
            }
        }

        string toString() const {
            return text(tape) ~ '\n'
                   ~ format("%" ~ text(index + 1) ~ "s", "^")
                   ~ '\n';
        }
    }

    this(const ref TuringMachine tm_) {
        this.tm = tm_;
        this.head = TapeHead(this.tm);

        char state = this.tm.initialState;
        while (true) {
            if (tm.haltStates.canFind(state))
                break;
            if (!tm.runningStates.canFind(state))
                throw new Exception("Unknown state.");
            auto symbol = this.head.read();
            auto rule = this.tm.rules["" ~ state ~ symbol];
            this.head.write(rule[0]);
            this.head.move(rule[1]);
            state = rule[2];
        }
    }
}

void main() {
    writeln("Incrementer:");
    immutable UTM.TuringMachine tm1 = {
        symbols: ['0', '1'],
        blank: '0',
        initialState: 'A',
        haltStates: ['H'],
        runningStates: ['A'],
        rules: ["A1": ['1', UTM.right, 'A'],
                "A0": ['1', UTM.left,  'H']],
        input: ['1', '1', '1']
    };
    UTM(tm1);

    writeln("\nBusy beaver machine:");
    immutable UTM.TuringMachine tm2 = {
        symbols: ['0', '1'],
        blank: '0',
        initialState: 'A',
        haltStates: ['H'],
        runningStates: ['A', 'B', 'C'],
        rules: ["A0": ['1', UTM.right, 'B'],
                "A1": ['1', UTM.left,  'C'],
                "B0": ['1', UTM.left,  'A'],
                "B1": ['1', UTM.right, 'B'],
                "C0": ['1', UTM.left,  'B'],
                "C1": ['1', UTM.stay,  'H']]
    };
    UTM(tm2);
}