ManyPaths | Topcoder Archive

Problem Statement

You are playing a board game that called "Journey to the Sacred Island". The object of the game is to land on the Sacred Island once play has ended. You begin at the location START and are given a movelist. A movelist is any string of 'A's, 'B's, and 'C's(quotes for clarity). Each turn you must move according to the movelist. Once all of the moves are done, if you are at location SACRED you win. For example:
map = {"START A GREEN","START B SACRED","START C BLUE","GREEN B SACRED"}

START----A----> GREEN
 |   \            /
 C    B          B
 |     \        /
 v     _\|    |/_
BLUE     SACRED

From START you can choose path 'A' and go to GREEN, path 'B' and go to SACRED or path 'C' and go to BLUE. From GREEN you can choose path 'B' and go to SACRED. If given the movelist "AB", or "B" you would win since they would lead you to SACRED. Given a movelist like "C" or "A" you would lose since you would end on BLUE and GREEN respectively.

If you attempt to walk down a path that doesn't exist you lose the game. For example, in the previous diagram, if you took path 'A' from location GREEN you would lose since no path named 'A' leaves location GREEN. This means that movelists such as "ABB", "AAA" and "BB" in the above diagram would lose.

To make the game exciting, a particular location can have more than one path leaving it with the same name. For example:
map = {"START A ONE","START A TWO","START B THREE","ONE C SACRED","TWO B SACRED"}

START ----A----> ONE -----C----> SACRED
      |\                           ^
      | \                          |
      B  A                         |
      |   \                        |  
      V   _\|                      |
   THREE   TWO--------B------------|

At location START, if you were moving down path 'A', you would have a choice between locations ONE and TWO. Given a movelist like "AC", if you go from START to ONE you will win by taking path 'C' to SACRED. If you initially choose to go to TWO, you will lose since there is no path from TWO named 'C'. A movelist is called WINNABLE if someone could win with it, assuming they made the correct path choices. In the above example "AC" and "AB" are both winnable, whereas all other paths are not. Given a map of the board you will determine how many WINNABLE movelists there are that have length equal to some specified value.

Create a class ManyPaths that contains the method numWin, which takes a String[] map, and an int len, and returns an int representing the number of WINNABLE movelists for map of length len.

Definition

Class:: ManyPaths
Method:: numWin
Parameters:: String[], int
Returns:: int
Method signature:: int numWin(String[] map, int len)
(be sure your method is public)

Notes

Pathes are one way
Cycles can exist in the map
There can be pathes from one location back to itself
SACRED need not appear in map

Constraints

map will contain between 1 and 50 elements inclusive
Each element of map has length between 5 and 50 inclusive
Each element of map is of the format <FROM> <PATH> <TO> where :<FROM> - Where the path begins, a string consisting of capital letters 'A'-'Z'<PATH> - The path name, 'A', 'B' or 'C'<TO> - Where the path leads to, a string consisting of letters 'A'-'Z'
Each element of map will contain NO leading or trailing whitespace
map will contain no duplicate elements
START will appear as the FROM location in at least 1 element of map
len will be between 1 and 10 inclusive

Examples

```
{"START A ONE","START A TWO","START B THREE","ONE C SACRED","TWO B SACRED"}
```
```
2
```
```
Returns: 2
```
This is the map mentioned above. There are two WINNABLE paths of length 2, namely "AB" and "AC". All of the other possible paths of length 2 ("AA","BA","BB","BC","CA","CB","CC") lose.
```
{"START A START","START B START","START C SACRED"}
```
```
2
```
```
Returns: 2
```
|-A,B-> START--C-->SACRED | / | / | / | / |/ As seen above, START leads to back to itself on A or B and to SACRED on C. The WINNABLE paths of length 2 are "AC", and "BC".

{"START A START","START B START","START C SACRED"}

Returns: 16

Same as example 2 except the length is now 5.

```
{"START A ONE","START B TWO","ONE B THREE","TWO A THREE"}
```
```
2
```
```
Returns: 0
```
This map has no location named SACRED so there are no WINNABLE paths.

{"START A ONE","START B TWO","ONE B THREE","TWO A THREE","THREE C SACRED","THREE A SACRED"}

Returns: 4

{"START A START","START A A","START A B","START A SACRED","A A START","A A A","A A B","A A SACRED","B A START","B A A","B A B","B A SACRED","SACRED A START","SACRED A A","SACRED A B","SACRED A SACRED","START B START","START B A","START B B","START B SACRED","A B START","A B A","A B B","A B SACRED","B B START","B B A","B B B","B B SACRED","SACRED B START","SACRED B A","SACRED B B","SACRED B SACRED","START C START","START C A","START C B","START C SACRED","A C START","A C A","A C B","A C SACRED","B C START","B C A","B C B","B C SACRED","SACRED C START","SACRED C A","SACRED C B","SACRED C SACRED"}

Returns: 81

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.