TopCoder problem "TwistyPassages" used in SRM 378 (Division I Level Three)



Problem Statement

    

You find yourself in a maze of twisty little passages, all alike. Each passage connects two rooms, and can be traveled in either direction. The rooms are all circular and look exactly the same, and the entrances to the passages are evenly spaced around the room, making it impossible to know anything except the number of passages connected to the room. Rooms with the same number of connecting passages are said to have the same type. The passages are so twisty that by the time you reach the other end of one, you have no idea where you are or which direction you are facing.

You have a map of the maze, but you have no idea where you are. "No problem," you think, "I'll walk around the maze and deduce where I started." Suppose that you follow some path, and note the type of each room you pass through and your decisions about which passages you selected (relative to the passage you entered by). You can then trace the same route on your map for every possible starting room and orientation of that room, and see if the room types match up. You hope that by choosing the right path, you can eliminate all but one possible starting room.

After thinking about the problem some more, you realize that some sets of rooms cannot be told apart. That is, if you started in one of them, this method would never be able to tell you which one regardless of the path you chose.

You will be given a String[] maze, describing the maze. Element i of maze is a space-separated list of numbers, which are the numbers of the rooms connected to room i by passages. The numbers are listed in the order that they appear going clockwise around the room from an arbitrary starting point. Return a int[] containing the same number of elements as maze, where element i of this list is the number of other rooms that cannot be told apart from room i.

 

Definition

    
Class:TwistyPassages
Method:similarRooms
Parameters:String[]
Returns:int[]
Method signature:int[] similarRooms(String[] maze)
(be sure your method is public)
    
 

Constraints

-maze will contain exactly N elements, where N is between 1 and 50, inclusive.
-Each element of maze will contain between 0 and 50 characters, inclusive.
-Each element of maze will be a space-separated list of integers, with no leading, trailing, or double spaces.
-Each integer in maze will be between 0 and N - 1, inclusive, with no extra leading zeroes.
-For all i between 0 and N - 1 inclusive, element i of maze will not contain i.
-For all i and j between 0 and N - 1 inclusive, element i of maze will contain at most one j.
-For all i and j between 0 and N - 1 inclusive, element i of maze will contain j if and only if element j of maze contains i.
 

Examples

0)
    
{"1 2 3", "0", "0", "0"}
Returns: {0, 2, 2, 2 }
A central room with three passages leading to three dead ends. The dead ends can not be told apart.
1)
    
{"1 2 3", "0", "0", "0 4", "3"}
Returns: {0, 0, 0, 0, 0 }
Now we add a passage to one of the dead ends. When in room 0, going down each passage will show which one is room 3 (it is the only one with 2 passages), which gives the orientation of room 0. If you started in some other room, proceed to room 0, determine its orientation, and then you will know where you started.
2)
    
{"1 2 3", "0", "0", "0 4", "3",
 "6 7 8", "5", "5", "5 9", "8"}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
Two disconnected copies of the previous example. It is impossible to tell corresponding rooms apart.
3)
    
{"1 2 3 4",  "0", "0 5",  "0", "6 0",  "2", "4",
"8 10 9 11", "7", "7 12", "7", "13 7", "9", "11"}
Returns: {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }
The two components are similar, but the order of passages around the central chamber is different and so they can be told apart.
4)
    
{"1 2", "2 0", "0 1", "4 6", "5 3", "6 4", "3 5"}
Returns: {6, 6, 6, 6, 6, 6, 6 }
A triangle and a square. Since you cannot tell when you get back to your initial room, there is no way to tell which component you are in.
5)
    
{"1 2 3", "4 5 0", "6 7 0", "8 9 0", "10 11 1", "12 13 1", 
 "14 15 2", "16 17 2", "18 19 3", "20 21 3", "22 23 4", 
 "24 25 4", "26 27 5", "28 29 5", "30 31 6", "32 33 6", 
 "34 35 7", "36 37 7", "38 39 8", "40 41 8", "42 43 9", 
 "44 45 9", "10", "10", "11", "11", "12", "12", "13", "13",
 "14", "14", "15", "15", "16", "16", "17", "17", "18", "18",
 "19", "19", "20", "20", "21", "21"}
Returns: 
{0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8282

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10798&pm=8282

Writer:

bmerry

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Graph Theory