Just because UofT now teaches Java in the first year, it doesn't mean you can forget about Turing. Alan Turing pretty much defined computers by defining a computing device that has come to bear his name. Your task is to write a (simplified) Turing machine simulator.
A Turing machine is a state machine that reads and writes symbols on an external memory called a tape, using a device called a head. In this question, those symbols will be a subset of the decimal digits 0 through 9, with digit 9 representing a blank.
The tape is initialized to some non-empty string of digits, interpreted as the input to the machine.
There are s+2 states in the machine. The s active states are numbered 0 through s-1. State -1 is the accepting state; state -2 is the rejecting state.
The ``program'' of the machine is stored in a table of triples indexed by an active state number and a symbol. If the triple stored for state q and symbol d is (d',m,q'), then whenever the machine is in state q and sees symbol d under its head, then the head overwrites d with d', moves its head m positions right (m is either 1 or -1; -1 means move left one symbol), and enters state q'.
The machine starts in state 0 with its head positioned over the leftmost symbol of the tape. It then repeatedly takes steps according to the above rule. If the machine ever enters state -1, it accepts the input and stops. If it ever enters state -2, it rejects the input and stops. If it ever tries to move to the left of where its head started, it rejects the input and stops. If it ever tries to move to the right of the digit string currently on the tape, it interprets the new (blank) cell as being filled with symbol 9, and continues.
Input: The machine and its input are described using numbers and digit strings, separated by whitespace (spaces, tabs, and newlines). The first item is a digit symbol d; the machine uses symbols 0 through d, and 9. The second item is s, is the number of active states.
The next items encode the state transition table. Triples are provided for all possible state transitions, and are presented in order: all triples indexed by state 0 come first, then all those indexed by state 1, up until all those indexed by s; within each such ``row'', the triples are ordered with the triple indexed by symbol 0 first, up until the triple indexed by symbol d, and finally the triple indexed by 9 (the ``blank''). Each triple is a digit symbol d', and then a move number -1 or 1, and finally a state number q'. The input will always be valid.
Finally, a decimal string of up to 100 digits is given, and it is interpreted as the string of initial values of the tape cells.
The Turing machine programs presented will never use more than 1000 tape cells, and will always eventually stop by either accepting or rejecting.
Output: Given a machine description and an input, simulate the machine until it stops. If it has accepted, print the string accept followed by a single space, followed by the contents of the tape and a single newline. If it has rejected, print the string reject followed by a single space, followed by the contents of the tape and a single newline. By ``the contents of the tape'', we mean the contents of any squares that had a specified value (including 9) at input time, or over which the machine's read/write head passed during execution.
Description of sample machine: The machine in the samples below treats its input as a binary number n. If and n is divisible by 4, then the machine leaves a binary representation of n/4 on the tape (with some trailing 9's representing blanks), and accepts. Otherwise, the machine rejects.
Sample input:
1 4 0 1 0 1 1 0 9 -1 1 9 -1 2 9 -1 3 9 -1 -2 9 -1 -1 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 010100Corresponding output:
accept 0101999Sample input (same machine, different input):
1 4 0 1 0 1 1 0 9 -1 1 9 -1 2 9 -1 3 9 -1 -2 9 -1 -1 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 9 -1 -2 110101Corresponding output:
reject 1101999