Thursday, January 8, 2015

QuipuReader

Problem:

TopCoder Problem Statement - QuipuReader
Single Round Match 155 Round 1 - Division I, Level Two

Overview:

Determine values represented by a series of ropes and knots.

Java Source:
01: public class QuipuReader {
02: 
03:  private int ropeLength = 0;
04: 
05:  // The method called by TopCoder.
06:  public int[] readKnots(String[] knots) {
07: 
08:   int[] values = new int[knots.length];
09: 
10:   ropeLength = knots[0].length();
11: 
12:   int clusterStart = findClusterStart(knots, 0);
13: 
14:   while (clusterStart < ropeLength)  {
15: 
16:    int clusterEnd = findClusterEnd(knots, clusterStart);
17: 
18:    /*
19:    * We've found the start and end indexes for the current cluster.
20:    * Now count the number of knots that fall in that range for
21:    * each rope.
22:    */
23:    for (int q = 0; q < knots.length; q++)  {
24:     values[q] *= 10;
25:     values[q] += doCount(knots[q], clusterStart, clusterEnd);
26:    }
27: 
28:    clusterStart = findClusterStart(knots, clusterEnd);
29:   }
30: 
31:   return values;
32:  }
33: 
34:  /*
35:  * Returns the index of the next cluster which starts at or beyond p.
36:  * This will be the location of the first 'X' found among all ropes.
37:  */
38:  private int findClusterStart(String[] knots, int p)  {
39: 
40:   if (p >= ropeLength)  return ropeLength;
41: 
42:   int minStart = ropeLength;
43: 
44:   for (int q = 0; q < knots.length; q++)  {
45:    int i = p;
46: 
47:    while ((i < ropeLength) && knots[q].charAt(i) != 'X')  {
48:     i++;
49:    }
50: 
51:    // Note the earliest start position found.
52:    minStart = Math.min(minStart, i);
53:   }
54: 
55:   return minStart;
56:  }
57: 
58:  /*
59:  * Returns the index where the cluster starting at p ends.
60:  * This will be the position after the last 'X' of the longest continuous
61:  * string of 'X's starting at p among all the ropes.
62:  */
63:  private int findClusterEnd(String[] knots, int p)  {
64: 
65:   int maxEnd = p;
66: 
67:   for (int q = 0; q < knots.length; q++)  {
68:    int i = p;
69:    while ((i < ropeLength) && (knots[q].charAt(i) == 'X'))  {
70:     i++;
71:    }
72: 
73:    // Note the greatest ending position found.
74:    maxEnd = Math.max(maxEnd, i);
75:   }
76: 
77:   return maxEnd;
78:  }
79: 
80:  /*
81:  * Counts the number of knots located between clusterStart and clusterEnd
82:  * on the given rope.
83:  */
84:  private int doCount(String rope, int start, int end)  {
85: 
86:   int n = 0;
87: 
88:   for (int p = start; p < end; p++)  {
89:    if (rope.charAt(p) == 'X')  {
90:     n++;
91:    }
92:   }
93: 
94:   return n;
95:  }
96: }
Notes:

The tricky part of this problem is determining where each cluster starts and ends. I've created the methods findClusterStart() and findClusterEnd() to take care of that. With those indexes known, we simply count the number of knots between those points. The knots are read from left to right, and for each cluster, the current value is multiplied by 10, and the number of knots in the current cluster is added.

findClusterStart() returns the index of the first 'X' found at or after p among any of the knots given in the input array. The return value will be at most ropeLength.

findClusterEnd() is very similar to findClusterStart(). Here we're looking for the greatest index. It starts at position p, and increments the index so long as the current character is an 'X'. This is done for each knot in the knots array, and the greatest index is returned.

doCount() just returns the number of 'X's found in a string between the start and end indexes.

No comments:

Post a Comment