Problem E
Turing Machine Cube Recognizer

Photo by Rocky Acosta

For this problem, write an algorithm that uses just the basics of a Turing machine to recognize when its input is a string of the symbol ‘a’ whose length is a cube. For example, it should accept ‘a’ and ‘aaaaaaaa’, while rejecting ‘aaa’ and ‘aaaaa’.

Use only the TuringMachineTape and TuringMachineUtility classes provided as included code. You may write functions, but you may not use the following typical programming features:

• Do not use any arithmetic operations (e.g. +, ++, -, --, *, etc.) bitwise operations (e.g. |, &, etc.), bit shifting operations (e.g. >>, <<), or inequality operations (e.g. <, >).

• Do not allocate any memory dynamically (except what is necessary to create TuringMachineTape objects).

• Do not use recursion (you may write and use functions, however).

You will observe that the TuringMachineTape class uses dynamic memory allocation and arithmetic operators in its implementation; you just can’t use these programming language features in your code.

The only types you will need to use are char, int and boolean. You can call the special method TuringMachineTape.accept() to accept, and use TuringMachineTape.reject() to reject.

Observe that the TuringMachineTape class has a constructor that can read its input from standard input. This will let you read a whole line of input without using arrays, strings or arithmetic. Since we can’t use strings or arrays, you will want to initially read the input using this constructor.

Have a look at the TuringMachineUtility class for a description of how you might write subroutines that make some things easier when working with tapes. You may write any code you want (including extra methods) within these guidelines.

Input

Input contains one line containing between $0$ and $25\, 000$ copies of the letter ‘a’.

Output

Output accept if the string has cubic length; reject otherwise.

a

accept

aa

reject

aaaaaaaaaaaaaaaaaaaaaaaaaaa

accept