TopCoder problem "QuipuReader" used in SRM 155 (Division I Level Two)



Problem Statement

    

The Incas used a sophisticated system of record keeping consisting of bundles of knotted cords. Such a bundle of cords is called a quipu. Each individual cord represents a single number. Surprisingly, the Incas used a base-10 positional system, just like we do today. Each digit of a number is represented by a cluster of adjacent knots, with spaces between neighboring clusters. The digit is determined by the number of knots in the cluster. For example, the number 243 could be represented by a cord with knots tied in the following pattern 

     -XX-XXXX-XXX-
where each uppercase 'X' represents a knot and each '-' represents an unknotted segment of cord (all quotes for clarity only).

A sequence of numbers is represented by a sequence of cords. For example, the numbers 725, 234, and 558 could be represented by the cords 

     -XXXXXXX--XX-----XXXXX---
     ---XX----XXX-----XXXX----
     -XXXXX---XXXXX--XXXXXXXX-
Notice how consecutive dashes are used to align clusters of knots on different cords. Clusters representing digits in the same position are required to overlap completely. Clusters representing digits in different positions never overlap. All quipus obey these rules. For example, the following configurations would all be illegal: 
     -XXXXX---
     ----XXX--    [The 3 and 5 must overlap completely or not at all.]

     -XXXXXXXXX-
     --XX------- 
     -------XX--  [Both 2s overlap with the 9, but not each other.]

     -XXXXXXXX-
     --XX----X-   [The 2 and 1 cannot both overlap with the 8.]

Unlike many ancient civilizations, the Incas were aware of the concept of zero, and used it in their quipus. A zero is represented by a cluster containing no knots. For example, the numbers 105 and 340 could be represented by the cords 

     --X--------XXXXX-
     -XXX--XXXX-------
Assume that the numbers being represented do not all contain zeros in the same position. For example, any input that you could conceivably interpret as representing the numbers 105 and 802, you should interpret as 15 and 82 instead.

Write a method to translate a sequence of quipu cords (of type String[]) into a sequence of integers (of type int[]), where the integer in position i corresponds to the cord in position i.

 

Definition

    
Class:QuipuReader
Method:readKnots
Parameters:String[]
Returns:int[]
Method signature:int[] readKnots(String[] knots)
(be sure your method is public)
    
 

Constraints

-knots contains between 1 and 10 elements, inclusive.
-Each element of knots contains the same number of characters, between 1 and 50, inclusive.
-Each element of knots contains only the characters 'X' and '-'. Note that 'X' is uppercase.
-At least one element of knots contains at least one 'X'.
-No element of knots contains 10 consecutive 'X's.
-If two (non-empty) clusters of knots A and B overlap at all, then they must overlap completely. More formally, let A0 be the position of the first 'X' in cluster A, and let A1 be the position of the last 'X' in cluster A. Let B0 and B1 be defined similarly for cluster B. Assume, without loss of generality, that A0 <= B0. Then either B1 <= A1 (they overlap completely) or A1 < B0 (they do not overlap at all).
-All clusters of knots that overlap with some particular cluster also overlap with each other. More formally, if two (non-empty) clusters of knots A and B both overlap with a third (non-empty) cluster C, then A and B also overlap with other.
-Each element of knots will represent a number between 0 and 1000000, inclusive.
 

Examples

0)
    
{ "-XXXXXXX--XX-----XXXXX---",
  "---XX----XXX-----XXXX----",
  "-XXXXX---XXXXX--XXXXXXXX-" }
Returns: { 725,  234,  558 }
One of the examples above. Notice that adjacent digit positions are usually separated by one or more columns of dashes. In this example, the first and second positions are separated by one column of dashes, and the second and third positions are separated by two columns of dashes.
1)
    
{ "XX---XXXX",
  "XXX-----X" }
Returns: { 24,  31 }
Notice that leading and trailing dashes are not required.
2)
    
{ "-XXX---XX----X",
  "--X----X-XXXXX",
  "-XX--XXXX---XX" }
Returns: { 321,  115,  242 }
Notice that adjacent digit positions are not always separated by columns of dashes. In this example, the first and second positions are separated by a column of dashes, but the second and third positions are not.
3)
    
{ "-------X--------",
  "--XXX----XXXX---",
  "--------------XX" }
Returns: { 100,  3040,  2 }
Notice that leading zeros are permitted. For example, 100 is really 0100 and 2 is really 0002.
4)
    
{ "--XXX-XXXXXXXX----------XXXXXXXXX--XXXXXXXX-",
  "--XX----XXXX-----XXXXXX---XXX------XXXXXXXX-",
  "--------------------X----XXXXXXXX--XXXXXXXX-",
  "--XX-------X------XXXX----XXX-------XXXXXX--",
  "--XXX---XXXXX-------X------XX--------X------",
  "-XXXX--XXXXXXX-----------XXXXXXX----XXXXX---",
  "-----------X---XXXXXXXX----XX--------XXX----",
  "-----------X---XXXXXXXX----X----------------",
  "---X--XXXXXXXX--XXXXXXX---XXX---------------",
  "--XX---XXXXXXX--XXXXXXX----XX-------XXXXX---" }
Returns: { 38098,  24638,  188,  21436,  35121,  47075,  1823,  1810,  18730,  27725 }
5)
    
{"X","-"}
Returns: { 1,  0 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4580&pm=1694

Writer:

vorthys

Testers:

lbackstrom , brett1479

Problem categories:

String Parsing