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

alias Direction = ubyte;
alias Symbol = uint;
alias State = char;

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

    private TapeHead head;
    private const TuringMachine tm;

    static struct Rule {
        Symbol toWrite;
        Direction direction;
        State nextState;
    }

    static struct TuringMachine {
        Symbol[] symbols;
        Symbol blank;
        State initialState;
        State[] haltStates, runningStates;
        Rule[Symbol][State] rules;
        Symbol[] input;
    }

    static struct TapeHead {
        const Symbol[] symbols;
        const Symbol blank;
        Symbol[] 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;
        }

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

        void write(in Symbol 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 Direction 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 format("%(%)", this.tape) ~ '\n'
                  ~ format("%" ~ text(this.index + 1) ~ "s", "^")
                      ~ '\n';
        }
    }

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

        State 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.toWrite);
            this.head.move(rule.direction);
            state = rule.nextState;
        }
        .write(head);
    }
}

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

    writeln("\nBusy beaver machine:");
    tm = UTM.TuringMachine();
    tm.rules['A'][0] = UTM.Rule(1, UTM.right, 'B');
    tm.rules['A'][1] = UTM.Rule(1, UTM.left,  'C');
    tm.rules['B'][0] = UTM.Rule(1, UTM.left,  'A');
    tm.rules['B'][1] = UTM.Rule(1, UTM.right, 'B');
    tm.rules['C'][0] = UTM.Rule(1, UTM.left,  'B');
    tm.rules['C'][1] = UTM.Rule(1, UTM.stay,  'H');
    tm.symbols = [0, 1];
    tm.blank = 0;
    tm.initialState = 'A';
    tm.runningStates = ['A','B', 'C'];
    tm.haltStates = ['H'];
    UTM(tm);
}