/*
  Interpreter of the Turing Machine.
  An initial CURRENT_STATE of the Turing Machine is coded by "start",
  final CURRENT_STATE - by "stop".
  The shift of the head to the right is designated through "right",
  to the left - through "left" .
*/

class delete {

    public static int ltape=10;  /* Length of a tape  */
    public static int nunits=0; 
    public static int head;
    public static String state;

    /* Indexes in array of the instructions,   */
    public static final int CURRENT_STATE  = 0;
    public static final int CURRENT_SYMBOL = 1;
    public static final int NEXT_SYMBOL    = 2;
    public static final int NEXT_STATE     = 3;
    public static final int MOVE           = 4;

    public static String[] tape =
        { ".", " ", " ", " ", "1", "1", " ", "1", ".", " " };

    public static final String[][] instruction = {
        { "start", ".",  ".",  "b",    "right"},
        { "b",     "1",  "1",  "b",    "right"},
        { "b",     " ",  " ",  "c",    "right"},
        { "b",     ".",  ".",  "stop", "right"},
        { "c",     " ",  " ",  "c",    "right"},
        { "c",     "1",  " ",  "d",    "left" },
        { "c",     ".",  " ",  "g",    "left" },
        { "d",     " ",  " ",  "d",    "left" },
        { "d",     "1",  "1",  "f",    "right"},
        { "d",     ".",  ".",  "f",    "right"},
        { "f",     " ",  "1",  "c",    "right"},
        { "g",     " ",  " ",  "g",    "left" },
        { "g",     "1",  "1",  "h",    "right"},
        { "g",     ".",  ".",  "h",    "right"},
        { "h",     " ",  ".",  "stop", "left" }
    };

    public static void main (String args[]) {
        head = 0;
    //    for (int i = 0; i < ltape; i++)      /* filling of blank  */
    //        tape[i] = " ";
    //    for (int i = head; i < head+nunits; i++)
    //        tape[i] = "1";
        long start = System.currentTimeMillis();

        test();

        long end = System.currentTimeMillis();
        System.out.println("Total time = "+ (end-start)*0.001);
        System.out.println("Final Tape : " );
        for (int i = 0; i < ltape; i++)
            System.out.print(tape[i]) ;
    }


    public static void test() {
        state = "start";
        while (state != "stop") {
            for (int i=0; i<instruction.length; i++) {
                if (state == instruction[i][CURRENT_STATE]
                && tape[head] == instruction[i][CURRENT_SYMBOL]) {
                    state=instruction[i][NEXT_STATE];
                    tape[head]=instruction[i][NEXT_SYMBOL];
                    if(instruction[i][MOVE]=="right") head++;
                    if(instruction[i][MOVE]=="left" ) head--;
                }
            }
        }
    }
}