TopCoder problem "AlphaDice" used in SRM 167 (Division I Level Three)



Problem Statement

    A six-sided die has each of its sides labeled with a distinct letter. We repeatedly roll it and record the result. We can only see three sides, so each roll is recorded as a String of 3 letters, denoting the labels on the visible sides in the order top,front,right.
 
        ______   
       / A   /| 
      /_____/ | 
      |     |C|  
      | B   | /   
      |_____|/     
For the above roll, we should record "ABC"

We want to check the data for consistency -- we know that the data recording process is error-prone. Create a class AlphaDice that contains a method badData that is given a String[] roll giving the recorded data, and that returns the (0-based) index of the first entry in roll that, when combined with its predecessors, is inconsistent.

If all the roll data are consistent with some distinct labeling of the die, return -1.

 

Definition

    
Class:AlphaDice
Method:badData
Parameters:String[]
Returns:int
Method signature:int badData(String[] roll)
(be sure your method is public)
    
 

Constraints

-roll will contain between 1 and 50 elements inclusive
-each element of roll will have length 3 and will contain only 'A'-'Z'
 

Examples

0)
    
{"ABC","ZCB"}
Returns: -1
This is the example above where there is a Z on the bottom. On the second roll the die was oriented so the Z was on the top, the C at the front, and the B on our right. These data are consistent with a distinctly labeled die.
1)
    
{"ABC","DEF","BCA","GHI","ABC"}
Returns: 3
The first 3 were consistent with a die with 6 distinct labels, but the "GHI" must be bad data since we could not possibly observe more than 6 different labels.
2)
    
{"ABA","CDE","CDE","CDE","CDE"}
Returns: 0
The first observation shows two sides labeled with 'A'
3)
    
{"ABC","DEF","BCF"}
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4640&pm=1761

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Geometry