Hide

Problem F
Turing Machine Cube Recognizer

The score given to accepted submissions to this problem will be multiplied by 100
/problems/tmcubes/file/statement/en/img-0001.jpg
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’ (since $1 = 1^3$ and $8 = 2^3$), while rejecting ‘aaa’ and ‘aaaaa’ (since $3$ and $5$ are not cubes).

Use only the TuringMachineTape and TuringMachineUtility classes provided as included code. Your program may use additional functions, but it may not use the following typical programming features:

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

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

  • It may not use a iterator-based loops, range-based iteration, or similar constructs. For example, ‘range(...)’ and ‘enumerate(...)’ in Python3 are not allowed.

  • It may not use recursion (it can use non-recursive functions you write, however).

The TuringMachineTape class uses dynamic memory allocation and arithmetic operators in its implementation; your program just can’t use these programming language features.

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

The TuringMachineTape class has a constructor that can read its input from standard input. This will let your program read a whole line of input without using arrays, strings, or arithmetic. Since your program may not use strings or arrays, it should 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 additional code you want (including extra methods) within these guidelines.

Your program may use more than one tape. However, it may not dynamically allocate tapes. Put another way, the number of tapes your program uses does not depend on the input – it is always the same for every run.

Hints

There are many approaches to solving this problem, with some that are easier to implement than others (as usual). Given the limitations of this problem, here are some suggestions to think about:

  • A simple approach is to try to construct a tape that has a length that is a cube, and compare it (symbol by symbol) to the input.

    • If the length of the constructed tape matches the length of the input tape, then the input length is a cube.

    • If the constructed tape is shorter than the input tape, then construct the next larger cube and try again.

    • If the constructed tape is longer than the input tape, and all smaller cubes have been tried, then the input tape’s length must not be a cube.

  • While you cannot use a traditional loop counter (e.g. an integer) for this problem (because you may not use the integer increment operation), you could construct a loop that uses a tape as a (unary) loop counter. Think about the length of the tape as representing a number – the number of iterations of the loop. For example, if a tape has length $k$, then a while loop could iterate over each symbol (from the beginning to the first blank symbol) to perform $k$ loop iterations.

  • Using multiple tapes will likely simplify your program. You could use multiple tapes to represent multiple loop counters.

For an extra challenge, try implementing your solution using only one tape!

Input

Input contains one line containing $0 \le n \le 100\, 000$ copies of the letter ‘a’.

Output

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

Scoring

Your program will be tested on a set of test groups, each of which is worth a number of points. Each test group contains several test cases, and to receive the points for a test group your program must solve all of the test cases in that group. The score of your program is the sum of the points received on all of the test groups.

Group

Points

Constraints

1

40

$0 \le n \le 10$.

2

30

$11 \le n \le 100$.

3

10

$101 \le n \le 1\, 000$.

4

10

$1\, 001 \le n \le 10\, 000$.

5

10

$10\, 001 \le n \le 100\, 000$.

Sample Input 1 Sample Output 1
a
accept
Sample Input 2 Sample Output 2
aa
reject
Sample Input 3 Sample Output 3
aaaaaaaaaaaaaaaaaaaaaaaaaaa
accept

Please log in to submit a solution to this problem

Log in