import java.io.*;

/* A simple Turing machine simulator

Run from the command line with one argument, as: java tm <filename>
where <filename> is the name of a file containing a quintuple listing 
representing a Turing machine.
Once loaded, the machine can be run on successive tapes.
The tape may be entered at the command line or input from a file.
For the former, just enter the tape at the "Enter tape" prompt; 
for the latter enter "@<filename>". 
NOTE: In the quintuple listings, the blank symbol is represented by '-'; 
hence this cannot be used as a separate tape symbol.
Quintuples may contain a 'wildcard' character '*'; thus the quintuple
2 * 2 * 1
means that any input symbol is allowed; the output symbolo will be the same.
The execution mode can be changed at any time when the execution is halted; 
entering a carriage-return only will keep the execution mode unchanged.

Antony Galton, 2005 */

public class tm
{
    static Quintuple[] quins; // the quintuple listing
    static Tape tape; // the tape, with the current head position marked
    static int qCount;  // counts the number of quintuples in the listing
    static int state; // the current state of the Turing machine
    static int mode; // the execution mode ('s','c','q','a','n' or 'h')
    static int leftmost; // leftmost tape square visited
    static int rightmost; // rightmost tape square visited
    static int netmove; // the net displacement from starting position

    public static void main(String[] args)
    {
	String quinfile = args[0];
	readFromFile(quinfile);
	String tapeinput = "";
	while (tapeinput.length()==0 || tapeinput.charAt(0)!='q')
	    {
		BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
		System.out.println();
		System.out.print("Enter tape (q to quit): ");		
		try
		    {
			tapeinput = console.readLine();
		    }
		catch (IOException e){}
		if (tapeinput.length()>0 && tapeinput.charAt(0)=='@')
		    {
			String tapefile = tapeinput.substring(1,tapeinput.length());
			try
			    {
				BufferedReader in = new BufferedReader(new FileReader(tapefile));
				tapeinput = in.readLine();
				System.out.println(tapeinput);
				in.close();
			    }
			catch(IOException e){System.out.println("File not found");}
		    }
		if (tapeinput.length()==0 || tapeinput.charAt(0)!='q')
		    {		
			tape = Tape.parseTape(tapeinput);
			runTM(); // this is where the action happens!
		    }
	    }
    }
    
    public static void readFromFile(String filename)
    {
	try{
	    BufferedReader in = new BufferedReader(new FileReader(filename));
	    String line;
	    // Find out number of quintuples (=qCount).
	    qCount = 0;
	    boolean counting = true;
	    while ((line = in.readLine())!=null && counting)
		{
		    Reader inline = new StringReader(line);
		    if (inline.read()=='0') counting=false;
		    if (counting) qCount++;
		}
	    System.out.println(qCount+" quintuples:");
	    in.close();
	    // Set up array for quintuples, read them in, and display them.
	    quins = new Quintuple[qCount];
	    BufferedReader in2 = new BufferedReader(new FileReader(filename));
	    int qNumber = 0;
	    while ((line = in2.readLine())!=null && qNumber<qCount)
		{      
		    quins[qNumber] = Quintuple.parseQuintuple(line);
		    quins[qNumber].writeQuintuple();
		    qNumber++;
		}
	    in2.close();
	}
	catch (IOException e){
	    System.out.println("There's a problem!");
	}

    }

    public static void runTM() // executes the machine on the input tape
    {
	System.out.println();
	displayModeMenu();
	System.out.println();
	System.out.print("Enter required execution mode (default=s): ");
	mode = getMode('s');
	state = 1;
	leftmost = 0;
	rightmost = 0;
	netmove = 0;
	displayConfiguration(); // always display initial configuration
	int stepCount = 0; // counts execution steps
	while (mode!='a' && oneStep()) stepCount++; // this is the action!
	if (mode=='a')
	    System.out.println("Execution aborted after "+stepCount+" steps.");
	else 
	    {
		System.out.println(stepCount+" steps executed");
		int v = rightmost-leftmost+1;
		System.out.println(v+" squares visited");
		System.out.println("Net displacement "+netmove);
	    }
    }

    public static int getMode(int oldMode) // enables change of execution mode
    {
	BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
	String chooseMode = null;
	int m = 'h'; 
	while (m == 'h')
	    {
		try {chooseMode = console.readLine();}
		catch (IOException e){};
		if (chooseMode.length()>0)
		    {
			m=chooseMode.charAt(0);
			if (m=='h') displayModeMenu();
			else if (m!='n' && m!='q' && m!='a' && m!='c') m='s';
		    }
		else m=oldMode; // if just enter key pressed, don't change mode
	    }
	return m;
    }

    public static void displayModeMenu()
    {
	System.out.println("s  Step (one step displayed at a time)");
	System.out.println("c  Change (only state-changes displayed)");
	System.out.println("q  Quick (all steps displayed without stopping)");
	System.out.println("n  No display (only halting step displayed)");
	System.out.println("a  Abort (terminate execution immediately)");
	System.out.println("h  Help (display this menu and await further input)");
    }

    public static void displayConfiguration()
    {
	System.out.println();
	tape.writeTape();
	for (int j=0;j<tape.left.length();j++)
	    System.out.print(' ');
	System.out.println(state);
	if (mode=='s' || mode=='c') mode=getMode(mode);
    }

    public static boolean oneStep()  // true if computation step executed
    {
	Quintuple q = new Quintuple();
	// run through quintuple listing looking for match
	int i=0;
	while (i<qCount 
	       && !(quins[i].oldstate==state && 
		    (quins[i].readsym==tape.head || quins[i].readsym=='*')))
	    i++;
	if (i<qCount) // matching quintuple found
	    {
		q = quins[i]; // set q to the matching quintuple	
		if (q.readsym=='*') q.writesym=tape.head;
		state = q.newstate;
		Tape newtape = new Tape();
		if (q.move == -1) //move left
		    {
			newtape.right = q.writesym + tape.right;
			if (tape.left.length()==0)
			    {
				newtape.head = ' ';
				newtape.left = "";
			    }
			else
			    {
				newtape.left = tape.left.substring(1,tape.left.length());
				newtape.head = tape.left.charAt(0);
			    }
			if (leftmost==netmove) leftmost--;
			netmove--;
		    }
		else if (q.move == 1) //move right
		    {
			if (tape.left.length()==0 && q.writesym==' ')
			    newtape.left = "";
			else newtape.left = q.writesym + tape.left;
			if (tape.right.length()==0)
			    {
				newtape.head = ' ';
				newtape.right = "";
			    }
			else 
			    {
				newtape.head = tape.right.charAt(0);
				newtape.right=tape.right.substring(1,tape.right.length());
			    }
			if (rightmost==netmove) rightmost++;
			netmove++;
		    }
		else if (q.move == 0) // stay put
		    {
			newtape.left = tape.left;
			newtape.head = q.writesym;
			newtape.right = tape.right;
		    }
		tape = newtape;
		if (mode=='s' || mode=='q' || (mode=='c' && state!=q.oldstate) ||state==0)
		    displayConfiguration();			
		return true;
	    }
	else // no matching quintuple found, so execution halts
	    {
		if (state==0) System.out.println("Success!");
		else System.out.println("No matching quintuple found for ("+state+","+tape.head+").");
		return false;
	    }
    }
    
}

class Quintuple{
    int oldstate;
    int newstate;
    char readsym;
    char writesym;
    int move;

    public static Quintuple parseQuintuple(String s)
	// Extracts quintuple components from a string such as "14 a 15 b -1"
    {
	Quintuple q = new Quintuple();
	int blank = s.indexOf(' ');
	q.oldstate = Integer.parseInt(s.substring(0,blank));
	if (s.charAt(blank+1) == '-') q.readsym = ' ';
	else q.readsym = s.charAt(blank+1);
	String rest = s.substring(blank+3,s.length());
	blank = rest.indexOf(' ');
	q.newstate = Integer.parseInt(rest.substring(0,blank));
	if (rest.charAt(blank+1) == '-') q.writesym = ' ';
	else q.writesym = rest.charAt(blank+1);
	String tail = rest.substring(blank+3,rest.length());
	q.move = Integer.parseInt(tail);
	return q;
    }

    public void writeQuintuple()
    {
	System.out.print(this.oldstate+" ");
	if (this.readsym==' ') System.out.print("- ");
	else System.out.print(this.readsym+" ");
	System.out.print(this.newstate+" ");
	if (this.writesym==' ') System.out.print("- ");
	else System.out.print(this.writesym+" ");
	System.out.println(this.move);
    }

}

class Tape{
    String left;
    String right;
    char head;

    public static Tape parseTape(String s)
	// Extracts tape components from a string such as "1101011"
	// This is an input string, with the head presumed to be scanning
	// the first character.
    {
	Tape t = new Tape();
	t.left = "";
	if (s.length()==0) 
	    {
		t.head=' ';
		t.right="";
	    }
	else 
	    {
		String s2 = "";
		for (int i=0;i<s.length();i++)
		    {
			// Replace '-' in s by ' '
			if (s.charAt(i)=='-') s2=s2+' ';
			else s2=s2+s.charAt(i);
		    }
		t.head = s2.charAt(0);
		t.right = s2.substring(1,s2.length());
	    }
	return t;
    }

    public void writeTape()
    {
	for (int i=this.left.length()-1;i>=0;i--)
	    System.out.print(this.left.charAt(i));
	System.out.print(this.head);
	System.out.println(this.right);
	for (int i=0;i<this.left.length();i++)
	    System.out.print(' ');
	System.out.println('^');
    }
}