Invader Squid Girl is a big fan of the Advanced Turing Game.
This is a game in which the player programs a simple Turing machine (defined below).
The goal of this game is to turn the starting tape into a pre-determined goal tape.
The picture above explains how the Turing machines in our problem operate.
On the top you can see the goal tape: a finite sequence of cells, each containing a zero (0) or a one (1).
The player starts with a tape of the same length as the goal tape.
The player's tape is initially filled with some zeros and ones.
The Turing machine has a "head": a reading and writing device.
At each moment, the head points at one of the cells of the tape.
In order to change it to the goal tape, the player picks a starting cell for the head and writes a program for the Turing machine.
In this problem, the program is simply a sequence of commands, executed one after another.
There are just four commands:
- '0' : Write 0 into the cell where the head points. (The old content of the cell is lost.)
- '1' : Write 1 into the cell where the head points. (The old content of the cell is lost.)
- '<' : Move the head one cell to the left.
- '>' : Move the head one cell to the right.
It is not allowed for the head to leave the tape (i.e., move left from the leftmost cell or right from the rightmost one).
Should that happen, the player loses -- even if the goal has been reached before the head left the tape.
In other words, a level of the Advanced Turing Game is considered solved if the head never leaves the tape, and at any point during the execution of the program (including the beginning and the end) the content of the tape exactly matches the goal tape.
Squid Girl recently solved a level of the Advanced Turing Game.
However, she forgot the initial contents of the tape, and her choice of the starting cell.
All she remembers is the program she wrote, and the content of the goal tape.
Help her by counting the number of possible initial contents of the tape.
You are given a String goal that describes the goal tape, and a String[] code.
Concatenate all elements of code to get Squid Girl's program.
Return a long containing the number of possible initial contents of the tape.
|