TopCoder problem "Hexagons" used in TCI '02 Semifinals 3 (Division I Level Two)



Problem Statement

    

You are given a puzzle with 7 pieces, each one of them a perfect hexagon. On each side of each hexagon there is a number, 1-6, and each hexagon has exactly one of each number.

You are supposed to assemble the pieces such that there is a center piece with the 6 other pieces surrounding it, and everywhere that two pieces touch, their touching sides must have the same number.

So for example, the following configuration is a solution to the puzzle, given the 7 pieces

  ___     ___     ___     ___     ___     ___     ___
 / 5 \   / 1 \   / 4 \   / 4 \   / 1 \   / 5 \   / 1 \
/2   4\ /6   3\ /3   1\ /2   5\ /6   5\ /4   3\ /6   2\
\3   6/ \2   5/ \5   2/ \6   1/ \4   2/ \2   6/ \5   3/
 \_1_/   \_4_/   \_6_/   \_3_/   \_3_/   \_1_/   \_4_/

       ___
      / 5 \
  ___/2   4\___
 / 5 \3   6/ 1 \
/4   3\_1_/6   3\
\2   6/ 1 \2   5/
 \_1_/6   2\_4_/
 / 1 \5   3/ 4 \
/6   5\_4_/3   1\
\4   2/ 4 \5   2/
 \_3_/2   5\_6_/
     \6   1/
      \_3_/

In this configuaration, the last piece is in the middle and the first through sixth pieces are placed in clockwise order from the top.

Note that even though in this case no rotation of the pieces was necessary, pieces may be rotated. So the middle piece could have been presented as

  ___
 / 6 \
/5   1\
\4   2/
 \_3_/

and the above configuration would still be legal. All that was necessary was to rotate the middle piece 1/6th of a turn counter-clockwise.

Given a String[] representing the 7 pieces, figure out all of the legal configurations and return a int[], sorted in ascending order, of the distinct indices (1-indexed) which appeared as the middle piece in one or more of these legal configurations.

Each element of the input will be 6 characters in length and will contain each of the characters '1' to '6', inclusive, exactly once. This is the order of the numbers on the piece, in clockwise order (as mentioned above, the starting point doesn't matter). You cannot flip the order, so 123456 cannot be considered as 654321 (it can, however, be considered as 234561, 345612, etc.)

 

Definition

    
Class:Hexagons
Method:centers
Parameters:String[]
Returns:int[]
Method signature:int[] centers(String[] pieces)
(be sure your method is public)
    
 

Constraints

-pieces has exactly 7 elements
-each element of pieces has length 6
-each element of pieces contains each of the characters '1' to '6', inclusive, exactly once.
 

Examples

0)
    
{"546132","135426","412653","451362","152346","536124","123456"}

Returns: { 7 }
This is the above example, where the last (7th) piece is the only legal center.
1)
    
{"123654","123654","513624","654123","625314","541236","324615"}
Returns: { 1,  2,  4,  6 }
Notice that pieces 1, 2, 4 and 6 are in fact all the same piece. The puzzle has a solution with this piece at its center, for example the following configuration of pieces (1-indexed):
  7   2
6   1   3
  5   4
2)
    
{"512634","152364","243516","612345","152643","342165","321456"}
Returns: { }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4372&pm=964

Writer:

chogyonim

Testers:

alexcchan , lbackstrom

Problem categories:

Brute Force, Recursion, Search