JOIN
Get Time

   Problem Statement  

 Problem Statement for MapGuessing

Problem Statement

    

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.



 

Definition

    
Class:MapGuessing
Method:countPatterns
Parameters:String, String[]
Returns:long
Method signature:long countPatterns(String goal, String[] code)
(be sure your method is public)
    
 

Notes

-Note that we are only counting the possible initial contents of the tape. Even if multiple starting positions work for a given tape, we only count it once.
-For some test cases the return value may be zero (0).
-The constraints imply that code will contain at most 555 characters.
-The automaton used in the problem is not an actual Turing machine. The actual Turing machines are more complex, with a potentially infinite tape and a more powerful "programming language". Of course, this has no relevance regarding the problem you have to solve.
 

Constraints

-goal will contain between 1 and 36 characters, inclusive.
-Each character in goal will be either '0' or '1'.
-code will contain between 1 and 15 elements, inclusive.
-Each element of code will contain between 1 and 37 characters, inclusive.
-Each character in each element of code will be one of '0', '1', '<', and '>'.
 

Examples

0)
    
"000"
{"0"}
Returns: 4

There are 4 possible contents of the initial tape: "000", "001", "010", and "100".

1)
    
"001"
{"0>1"}
Returns: 5

There are 5 possible contents of the initial tape: "000", "001", "010", "011", and "101".

Note that for the initial tape "101" we have to choose the leftmost cell as the starting one.

We will then reach the goal after the first command is executed.

2)
    
"000"
{"1>1>1"}
Returns: 1

The goal can also be reached before any commands are executed.

3)
    
"11001"
{">><<<<><<"}
Returns: 0

There is no possible contents of the initial tape. (We do reach the goal if the initial tape is equal to the goal tape, but as the head leaves the word, this does not count.)

4)
    
"1000101011"
{"1<<0>>0>1"}
Returns: 22
5)
    
"00000010000000000000000000000000"
{"><>>0<0<>>1>0><>", "<<0>>0<>><0>0>>><><", ">>>0<>", ">0><>>>>0<<><>>0>>>0<0>>0>"}
Returns: 13601

Don't forget to concatenate code.

6)
    
"11100011010111111010100100110001101"
{"11111111111111111111"
,"1<><><><><><><><><>1"
,"1<>000>000><0<><0<>1"
,"1<0<><>0><0<00>00<>1"
,"1<>00<>000><0<0<0<>1"
,"1<><>0>0><0<0<><0<>1"
,"1<000<>0><0<0<><0<>1"
,"1<><><><><><><><><>1"
,"1<>000><000<>000><>1"
,"1<>0><><0<><>0><><>1"
,"1<>000><000<>000><>1"
,"1<><>0><><0<><>0><>1"
,"1<>000><000<>000><>1"
,"1<><><><><><><><><>1"
,"11111111111111111111"}
Returns: 90

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 555 Round 1 - Division I, Level Three