Wednesday, December 31, 2014

WritingWords

Problem:

TopCoder Problem Statement - WritingWords
Single Round Match 618 Round 1 - Division II, Level One

Overview:

Count how many key presses are needed to type out a word on a cell phone.

Java Source:
01: public class WritingWords {
02: 
03:     public int write(String word) {
04: 
05:         int count = 0;
06: 
07:         for (int i = 0; i < word.length(); i++) {
08:             count += word.charAt(i) - 'A' + 1;
09:         }
10: 
11:         return count;
12:     }
13: }
Notes:

This is about as easy as it gets. It took longer to read the problem description than to actually code it up. Nevertheless, there's still a few things worth noting.

Remember that we can use String.charAt(i) to get the character at a given position in the String. Also chars in java are treated as 16-bit integers, so we can do normal integer arithmetic on them. The letters 'a' - 'z' are guaranteed to be consecutive, as are 'A' - 'Z'. So an expression like 'c' - 'a' will yield a value of 2. In this problem, the actual ascii values of the characters does not matter (A = 65 by the way).

To get the number of key presses for each letter we just subtract 'A' from that letter. But since, 'A' - 'A' would be 0, we need to add 1 to each value.

The variable count is initialized to 0, and then is incremented by the value of each new letter. The operator += is just a sort cut for writing "count = count + ..."

Tuesday, December 30, 2014

Egalitarianism3Easy

Problem:

TopCoder Problem Statement - Egalitarianism3Easy
Single Round Match 630 Round 1 - Division II, Level Two

Overview:

Find the largest set of cities where the distance between any pair of cities is equal to the distance between any other pair.

Java Source:
001: public class Egalitarianism3Easy {
002: 
003:     /*
004:     * There's a maximum of 10 cities, and a maximum distance of 1,000.  So,
005:     * no city can be more than 10,000 away from another.
006:     */
007:     private static final int INF_DISTANCE = (10 * 1000) + 1;
008: 
009:     public int maxCities(int n, int[] a, int[] b, int[] len) {
010: 
011:         // A matrix to hold the distances between any 2 cities.
012:         int[][] distances = new int[n][n];
013: 
014:   /*
015:    * Initialize distances.  Distance from any city to itself is 0.
016:   * Set distance to all other cities to infinity.
017:   */
018:         for (int i = 0; i < distances.length; i++) {
019:             for (int j = 0; j < distances[0].length; j++) {
020:                 distances[i][j] = (i == j) ? 0 : INF_DISTANCE;
021:             }
022:         }
023: 
024:         // Set distances from the input parameters
025:         for (int i = 0; i < a.length; i++) {
026: 
027:             // Roads are bi-directional, so set both ways.
028:             distances[a[i] - 1][b[i] - 1] = len[i];
029:             distances[b[i] - 1][a[i] - 1] = len[i];
030:         }
031: 
032:         // Floyd-Warshall's algorithm
033:         for (int k = 0; k < n; k++) {
034:             for (int i = 0; i < n; i++) {
035:                 for (int j = 0; j < n; j++) {
036:                     distances[i][j] = Math.min(distances[i][j],
037:                             distances[i][k] + distances[k][j]);
038:                 }
039:             }
040:         }
041: 
042:         // distances is now populated with the distance between any 2 cities.
043: 
044:         /*
045:         * The maximum number of cities in a set where the distances between
046:         * them all are equal.  This is the value we'll return.
047:         */
048:         int max = 0;
049: 
050:         /*
051:         * This will generate a bit pattern representing every possible subset
052:         * of cities.
053:         */
054:         for (int citySetMask = 0; citySetMask < (1 << n); citySetMask++) {
055: 
056:             int citySetDistance = -1;
057:             boolean allDistancesEqual = true;
058:             int cityCount = 0;
059: 
060:             int city1 = 0;
061:             while ((city1 < n) & allDistancesEqual) {
062: 
063:                 // Make sure city1 is in the set.
064:                 if ((citySetMask & (1 << city1)) != 0) {
065: 
066:                     cityCount++;
067: 
068:                     int city2 = 0;
069:                     while ((city2 < n) & allDistancesEqual) {
070: 
071:                         // Make sure city2 is in the set (and != city1)
072:                         if ((city1 != city2) &&
073:                                 ((citySetMask & (1 << city2)) != 0)) {
074: 
075:                             // Set the distances if this is the first pair.
076:                             if (citySetDistance == -1) {
077:                                 citySetDistance = distances[city1][city2];
078:                             }
079: 
080:                             if (distances[city1][city2] != citySetDistance) {
081:                                 allDistancesEqual = false;
082:                             }
083: 
084:                         }
085: 
086:                         city2++;
087:                     }
088:                 }
089: 
090:                 city1++;
091:             }
092: 
093:             if (allDistancesEqual) {
094:                 max = Math.max(max, cityCount);
095:             }
096: 
097:         }
098: 
099:         return max;
100:     }
101: }
Notes:

There's a lot going on in this problem. It's tough for division 2 level 2. The solution uses the Floyd-Warshall algorithm to determine the shortest distance between all pairs of cities. If you're unfamiliar with the algorighm, check out this video tutorial. Floyd-Warshall Tutorial Take the time to work through the example until you understand what's going on.

One thing to be careful of when using this algorithm: you can't set unknown distances to Integer.MAX_VALUE. The reason is that we need to add two distances together, and this will cause an overflow. To avoid this, I created INF_DISTANCE which is 1 greater than any possible distance given the constraints of the problem.

When the section labeled Floyd-Warshall's algorithm complets, the distances[][] will contain a table that maps the distance from any city to any other city. Then we just need to find the sets of cities that match the criteria, and determine the largest.

The number of possible subsets of all cities is reasonably small. Just 2^10 = 1024. So it's very possible to generate all combinations and test each one. To generate all possible subsets, I used a trick using a bit mask. It's the first time a solution on this site has used it, so I'll go into some detail as to how it works.

Imagine each set of cities is represented as a binary string. So "0000000111" would represent a set that included cities 0, 1, and 2. "1000000000" is a set that includes only city 9, and "1111111111" contains all cities. By simply counting from 0 to 2^n (Where n is the number of cities/bits) we'll get every possible combination of bits.
Note that care must be taken because the cities start at 1 and not 0. So city 9 is actually represented by the 10th bit from the right. city 0 is in the first bit on the right.

Now, to tell if a given city is in the current set, we'll use an expression such as (citySetMask & (1 << city1) where citySetMask is the current binary pattern, and city1 is the city that we're checking. The << operator taks the value of 1 (...001) and shifts it's bits to the left by the value of city1. Let's say our citySetMask is "0001010111" and city1 is 4. The << operator will take 1 (0000000001) and shift if over 4 places (0000010000). We then use the bit-wise and operator & to test the two values. In this case, the city is in the set.

The remainder of the logic if pretty straight forward. We initialize citySetDistance to -1. Then when the first other city is found, we'll set that to the distance between those first two cities. allDistancesEqual is set to false if we ever find a pair of cities whose distances is not what was previously set in citySetDistance. When allDistancesEqual becomes false, both the inner and outer while loops terminate, and we give up on the current set. If all cities in the set do have equal distances, then we set max to the larger of max or cityCount.

Again, this is pretty tough for a division 2 level 2 problem. Compared to the early single round matches, like the 100 series, this would be a division 1 level 2 or division 2 level 3 problem at least, but that appears to be the way things are going with these newer problem sets.

Monday, December 29, 2014

DoubleLetter

Problem:

TopCoder Problem Statement - DoubleLetter
Single Round Match 630 Round 1 - Division II, Level One

Overview:

Remove double letters from the left side of a String until no more double letters exist.

Java Source:
01: public class DoubleLetter {
02: 
03:     public String ableToSolve(String S) {
04: 
05:         // A StringBuilder will be much more efficient for deleting characters.
06:         StringBuilder sb = new StringBuilder(S);
07: 
08:         boolean changed = true;
09: 
10:         while (changed) {
11:             changed = false;
12: 
13:             for (int i = 0; i < sb.length() - 1; i++) {
14:                 if (sb.charAt(i) == sb.charAt(i + 1)) {
15:                     sb.deleteCharAt(i);
16:                     sb.deleteCharAt(i);
17:                     changed = true;
18: 
19:                     // Start over from the left of the string.
20:                     break;
21:                 }
22:             }
23:         }
24: 
25:         return (sb.length() == 0) ? "Possible" : "Impossible";
26:     }
27: }
Notes:

First, I create a StringBuilder object out of the given String. This will make deleting characters from the string more efficient. Every time a String is modified in Java, a new object is created. On the other hand, StringBuilder is mutable.

I used the boolean variable changed to note when any characters have been deleted. If we pass through the entire string with no changes, then we're done. Note that I call sb.deleteCharAt(i) twice. The first deletes the first characters, and causes all subsequent characters to shift one place to the left. The second call deletes the second of the double characters.

Upon exiting the while loop, simply check the size of the remaining string, and return Possible or Impossible accordingly.

Sunday, December 28, 2014

SMBus

Problem:

TopCoder Problem Statement - SMBus
Single Round Match 162 Round 1 - Division II, Level Three

Overview:

Simulate a simple network. Determine how long it will take to process a series of messages.

Java Source:
001: import java.util.HashSet;
002: import java.util.Set;
003: 
004: public class SMBus {
005: 
006:     /*
007:     * Represents a device that wishes to transmit a message.  Contains
008:     * the message it wants to send, and how long it takes to send each
009:     * byte.
010:     */
011:     class Master {
012: 
013:         final String message;
014:         final int time;
015: 
016:         Master(String message, int time) {
017:             this.message = message;
018:             this.time = time;
019:         }
020:     }
021: 
022:     /*
023:     * Represents the SMBus.  Master objects may call setChar() and setTime()
024:     * to put the next character in their message, and the time required to
025:     * transmit onto the bus.  SMBus will keep track of the lowest value
026:     * character, and the greatest time.
027:     */
028:     class Bus {
029: 
030:         /*
031:         * Bigger than any legal character.  Expected to be over written when
032:         * the first character is set.
033:         */
034:         private final char MAX_CHAR = '9' + 1;
035: 
036:         StringBuilder message = new StringBuilder();
037:         int charIdx = 0;
038:         int time = 0;
039: 
040:         Bus() {
041:             reset();
042:         }
043: 
044:         void reset() {
045:             message = new StringBuilder();
046:             message.append(MAX_CHAR);
047:             time = 0;
048:             charIdx = 0;
049:         }
050: 
051:         // Creates a place holder for the next character.
052:         void nextChar() {
053:             message.append(MAX_CHAR);
054:             charIdx++;
055:         }
056: 
057: 
058:         // Keeps the lesser of the current character, and the parameter c.
059:         void setChar(char c) {
060:             if (c < message.charAt(charIdx)) {
061:                 message.setCharAt(charIdx, c);
062:             }
063:         }
064: 
065:         // Keeps the greater of the current time, and the parameter t.
066:         void setTime(int t) {
067:             time = Math.max(time, t);
068:         }
069: 
070:         int getTime() {
071:             return time;
072:         }
073: 
074:         void clearTime() {
075:             time = 0;
076:         }
077: 
078:         /*
079:         * Returns the current value in the message.  Removes the last
080:         * character, since that will be a place holder.
081:         */
082:         String getMessage() {
083:             return message.substring(0, message.length() - 1);
084:         }
085: 
086:     }
087: 
088:     // The method called by TopCoder.
089:     public int transmitTime(String[] messages, int[] times) {
090: 
091:         int time = 0;
092: 
093:         Bus bus = new Bus();
094: 
095:         // Holds all the masters that have not finished sending their message.
096:         Set incomplete = new HashSet<>();
097: 
098:         // Populate incomplete using the given parameters.
099:         for (int i = 0; i < messages.length; i++) {
100:             incomplete.add(new Master(messages[i], times[i]));
101:         }
102: 
103:         while (!incomplete.isEmpty()) {
104: 
105:             bus.reset();
106: 
107:             boolean messageComplete = false;
108: 
109:             // Loop until some master is able to complete their message.
110:             while (!messageComplete) {
111: 
112:                 String currentMessage = bus.getMessage();
113: 
114:                 /*
115:                 * If a message has been completed, we'll store a reference
116:                 * to it here.
117:                 */
118:                 Master completed = null;
119: 
120:                 // Look for a completed message.
121:                 for (Master m : incomplete) {
122:                     if (m.message.equals(currentMessage)) {
123:                         completed = m;
124:                         break;
125:                     }
126:                 }
127: 
128:                 /*
129:                 * If we've found a completed message, remove its master
130:                 * from the incomplete list.  Set messageComplete to true
131:                 * so we can prepare for a new message to start.
132:                 */
133:                 if (completed != null) {
134:                     incomplete.remove(completed);
135:                     messageComplete = true;
136: 
137:                 } else {
138: 
139:                     /*
140:                     * Otherwise.  Put the least character, and the greatest
141:                     * time onto the bus.
142:                     */
143:                     for (Master m : incomplete) {
144: 
145:                         /*
146:                         * Only consider masters whose message still matches
147:                         * the current pattern.
148:                         */
149:                         if (m.message.startsWith(currentMessage)) {
150:                             bus.setChar(m.message.charAt(bus.charIdx));
151:                             bus.setTime(m.time);
152:                         }
153:                     }
154: 
155:                     time += bus.getTime();
156: 
157:                     // Prepare for the next character.
158:                     bus.clearTime();
159:                     bus.nextChar();
160:                 }
161:             }
162:         }
163:         return time;
164:     }
165: }
Notes:

To solve this, I've created a class to represent the Master devices and another class to simulate the network. The transmitTime() method then coordinates these objects and keeps track of how much time is needed to complete all the messages.

The Master class simply represents a device that wishes to send a message. It's initialized with the message, and the time it requires to place each byte on the bus.

The Bus class represents the I2C System Management Bus. The idea is that after the bus is initialized or reset, Master objects can call setChar() and setTime() to drop their request onto the bus. The bus will keep track of the smallest character, and the greatest time. It also remembers all the characters in the current message.

When the transmitTime() method is called, it will create Master objects for each of the parameters. It adds all of these Master objects to the incomplete Set. It will then loop until the incomplete Set is empty - all Master devices have completed sending their messages.

For each message, we check to see if the current message on the bus matches the complete message for any Master. In this case, that Master is done, and is removed from the incomplete Set. Otherwise, each Master in the incomplete Set places it's character and time on the bus, so long as it's message continues to match the bus's message. time is incremented, and the bus is set up to receive the next character.

After all Master objects have been removed from the incomplete Set, time will hold our finishing time.

PaperFold

Problem:

TopCoder Problem Statement - PaperFold
Single Round Match 162 Round 1 - Division I, Level One
Single Round Match 162 Round 1 - Division II, Level Two

Overview:

Calculate the minimum number of folds needed to fit a sheet of paper into a box.

Java Source:
01: public class PaperFold {
02:  
03:  public int numFolds(int[] paper, int[] box) {
04:   
05:   int paperMax = Math.max(paper[0], paper[1]);
06:   int paperMin = Math.min(paper[0], paper[1]);
07:   int boxMax = Math.max(box[0], box[1]);
08:   int boxMin = Math.min(box[0], box[1]);
09: 
10:   int f1 = countFolds(paperMax, boxMax) + countFolds(paperMin, boxMin);
11:   int f2 = countFolds(paperMax, boxMin) + countFolds(paperMin, boxMax);
12: 
13:   int folds = Math.min(f1, f2);
14: 
15:   return (folds <= 8) ? folds : -1;
16:  }
17: 
18:  private static int countFolds(int a, int b)  {
19: 
20:   int folds = 0;
21: 
22:   while (a > b)  {
23:    folds++;
24:    b *= 2;
25:   }
26: 
27:   return folds;
28:  }
29: }
Notes:

We need to consider two possibilities. First, that we can fold the paper length-wise and width-wise until it fits in box, and second, that we must first rotate the paper, and then fold it down to fit into the box. We'll try both ways, and go with the one that takes fewer folds.

On line 10, f1 is assigned the number of folds required if the maximum dimension of the paper is aligned with the maximum dimension of the box. On the next line, f2 is assigned the number of folds if this were rotated 90°.

The countFolds() method simply counts how many times the box's dimension needs to be doubled before it can fit the paper. I choose to double the size of the box rather than halving the size of the paper to avoid having to convert to doubles in order to deal with fractions.

Saturday, December 27, 2014

LCMRange

Problem:

TopCoder Problem Statement - LCMRange
Single Round Match 162 Round 1 - Division II, Level One

Overview:

Find the Least Common Multiple of a range of numbers.

Java Source:
01: public class LCMRange {
02:  
03:  public int lcm(int first, int last) {
04: 
05:   /*
06:   * The Least Common Multiple must be a multiple of last, so we'll
07:   * start there and increment by last to get the next value.
08:   */
09:   int lcm = last;
10: 
11:   boolean found = false;
12: 
13:   // Continue until we find the LCM
14:   while (!found)  {
15: 
16:    int i = first;
17: 
18:    /*
19:    * Check each number between first and last (inclusive) to ensure
20:    * that lcm is a multiple.
21:    */
22:    while (i <= last)  {
23: 
24:     // If it doesn't divide evenly, skip this number.
25:     if ((lcm % i) != 0)  {
26:      break;
27:     }
28: 
29:     i ++;
30:    }
31: 
32:    /*
33:    * If we've tested all the numbers, then we've successfully found
34:    * a Least Common Multiple
35:    */
36:    if (i > last)  {
37:     found = true;
38: 
39:    } else  {
40: 
41:     /*
42:     * Otherwise try the next number.  We know it must be a
43:     * multiple of first, so we can increment by that amount.
44:     */
45:     lcm += last;
46:    }
47:   }
48: 
49:   return lcm;
50:  }
51: }
Notes:

The constraints of this problem make it small enough that a brute-force method works well. We could just start at 1 and check to see if it is a Least Common Multiple (LCM) of each number in the range. If not, just increment by 1 and try again. A simple optimization is to note that our answer must be a multiple of last. So we can start our search there, and increment by the value of last to get the next number to test.

The % operator is used to determine if one number divides another evenly. if ((a % b) == 0) then b evenly divides a. Or, a is a multiple of b.

Note the break; statement in the inner-most while loop. This lets us quit on a potential LCM as soon as we find a number that it is not a multiple of. When the break is encountered, i will be <= last, and the if statement below will use this to determine if a LCM has been found or not.

Friday, December 26, 2014

FryingHamburgers

Problem:

TopCoder Problem Statement - FryingHamburgers
Single Round Match 159 Round 1 - Division I, Level One

Overview:

Optimize the time it takes to cook a number of hamburgers given the number of burgers, and the size of a grill.

Java Source:
01: public class FryingHamburgers {
02: 
03:  private static final int MINS_PER_SIDE = 5;
04:  private static final int MINS_PER_BURGER = 2 * MINS_PER_SIDE;
05: 
06:  public int howLong(int panSize, int hamburgers) {
07: 
08:   // If there are no hamburgers, it takes no time.
09:   if (hamburgers == 0)  return 0;
10: 
11:   // All the hamburgers can fit on one pan.
12:   if (hamburgers <= panSize)  return MINS_PER_BURGER;
13: 
14:   // The hamburgers divide evenly by panSize
15:   if ((hamburgers % panSize) == 0)  {
16:    return (hamburgers / panSize) * MINS_PER_BURGER;
17:   }
18: 
19:   /*
20:   * If the remainder is <= panSize, we can use the trick described in
21:   * the tests to save the cooking time of one side.
22:   */
23:   if ((hamburgers % panSize) <= (panSize / 2))  {
24:    return ((hamburgers / panSize + 1) * MINS_PER_BURGER)
25:      - MINS_PER_SIDE;
26:   }
27: 
28:   // Worst case, we just cook one side, then the other.
29:   return (hamburgers / panSize + 1) * MINS_PER_BURGER;
30: 
31:  }
32: }
Notes:

This is the sort of nasty little problem that you might encounter during a programming interview. I've seen it asked with 3 burgers and a grill that holds two. That's easy enough to explain. Coding it up for the general case is quite a bit trickier. It's also very likely that you'll pass the given examples, and then fail during the challenge phase, since it's so easy to make a mistake in the logic that goes undetected.

There are essentially five cases to think about:

  1. hamburgers == 0. This is trivial, if there are no burgers, it takes no time
  2. hamburgers <= panSize. Again, pretty trivial. We can put all burgers on the pan at once. Flip them after 5 minutes, and they'll be done in 10. There's no way to shorten this.
  3. (hamburgers % panSize) == 0. The number of burgers divides evenly by the panSize. Similar to the above case, but we repeat the process until all hamburgers are gone.
  4. Here's out special case. If the remainder of the burgers when divided by the pan size is <= half the pans size: (hamburgers % panSize) <= (panSize / 2), then we can use a trick. We flip over half the burgers, set the other half of the burgers aside, and fill the pan with a new set of burgers. This can save us the time it takes to cook one side of a burgers.
  5. Failing the above cases, we fall back to the number of burgers divided by the size of the pan times how long it takes to cook a burger.

IsHomomorphism

Problem:

TopCoder Problem Statement - IsHomomorphism
Single Round Match 161 Round 1 - Division I, Level One

Overview:

Test if two functions, given as tables, provide the same results for a set of values.

Java Source:
01: import java.util.ArrayList;
02: import java.util.List;
03: 
04: public class IsHomomorphism {
05:  
06:  public String[] numBad(String[] source, String[] target, int[] mapping) {
07: 
08:   List results = new ArrayList<>();
09: 
10:   for (int a = 0; a < source.length; a++)  {
11:    for (int b = 0; b < source.length; b++)  {
12: 
13:     /*
14:     * Testing:
15:     * mappings(a@b) = mappings(a)~mappings(b)
16:     * for all values of a and b.
17:     */
18: 
19:     /*
20:     * For the '@' operator, the first value given is the index into
21:     * the source array, and the second value gives the character
22:     * we're interested in.
23:     */
24:     int leftSide = mapping[source[a].charAt(b) - '0'];
25: 
26:     // Same for the '~' operator, except use the target array
27:     int rightSide = target[mapping[a]].charAt(mapping[b]) - '0';
28: 
29:     // If the sides are not equal, add the pair to the results list.
30:     if (leftSide != rightSide) {
31:      results.add("(" + a + "," + b + ")");
32:     }
33:    }
34:   }
35: 
36:   // Convert the List to an array and return it.
37:   String[] ret = new String[results.size()];
38:   for (int i = 0; i < ret.length; i++)  {
39:    ret[i] = results.get(i);
40:   }
41: 
42:   return ret;
43:  }
44: }
Notes:

The source and target tables map two inputs to a result. The result of a@b is source[a].charAt(b). Likewise, the result of a~b is target[a].charAt(b). Since the value in the table is a char, we need to subtract '0' to get it's int value.

We need to determine is if:

mapping(a@b) = mapping(a)~mapping(b)

which can be coded as:

mapping[source[a].charAt(b) - '0'] == target[mapping[a]].charAt(mapping[b]) - '0'

Now, just test that for all values of a and b. For any combination that fails the test, we'll add it to a List. Once complete, we convert the List to an array, and return it.

Since we loop through a in the outer loop, and then b in the inner loop, entries will be added to the results List in exactly the order we need. There is no need to sort them to match the expected output.

Iditarod

Problem:

TopCoder Problem Statement - Iditarod
Single Round Match 160 Round 1 - Division I, Level One

Overview:

Determine the average number of minutes contestants needed to complete a multi-day race.

Java Source:
01: public class Iditarod {
02:  
03:  public int avgMinutes(String[] times) {
04: 
05:   int totalMinutes = 0;
06: 
07:   // Add up the total minutes for each finishing time.
08:   for (String t : times)  {
09:    totalMinutes += calcMinutes(t);
10:   }
11: 
12:   // Get the average.
13:   double avg = (double) totalMinutes / (double) times.length;
14: 
15:   // Round off by adding .5 and truncating.
16:   avg += 0.5;
17:   return (int) avg;
18:  }
19: 
20:  private static int calcMinutes(String s)  {
21: 
22:   // Format is: hh:mm xM, DAY n
23: 
24:   int hours = Integer.parseInt(s.substring(0,2));
25:   int minutes = Integer.parseInt(s.substring(3,5));
26:   boolean isPM = (s.charAt(6) == 'P');
27: 
28:   // Handles both 1 and 2 digit day lengths.
29:   int day = Integer.parseInt(s.substring(14, s.length()));
30: 
31:   // Handle 12 PM and 12 AM hours
32:   if (hours == 12)  {
33:    if (isPM)  {
34:     hours = 0;
35:    } else {
36:     hours = 24;
37:     day -= 1;
38:    }
39:   }
40: 
41:   if (isPM) hours += 12;
42: 
43:   // Subtract off the start time.
44:   hours -= 8;
45: 
46:   // Minutes per day, times number of days (don't count day 1)
47:   int totalMinutes = (24*60) * (day - 1);
48: 
49:   totalMinutes += (60 * hours);
50: 
51:   totalMinutes += minutes;
52: 
53:   return totalMinutes;
54:  }
55: 
56: }
Notes:

Not much difficulty here. avgMinutes() loops through all the finishing times and keeps a running total of the number of minutes for all the competitors to finish. Then it just divides the today by the number of times - casting to double to avoid losing decimal places. To round off, just add 0.5 and truncate - a trick everyone should know. There's no danger of overflow here, so just stick with the simplest thing that works.

Calculating the number of minutes for a given time is also pretty simple. We just need to take care dealing with the 12:00 PM and 12:00 AM hours. Here, if it's 12 PM, I set the hours to 0. If it's 12 AM, I set hours to 24, and subtract a day. Then for any PM times, I add 12 hours. It may take a minute to think it through, but it's not tough. Remember to subtract off the 8:00 AM starting time. Then it's just a matter of adding up the number of minutes in a day, an hour, and the minutes portion.

TennisRallies

Problem:

TopCoder Problem Statement - TennisRallies
Single Round Match 161 Round 1 - Division I, Level Two
Single Round Match 161 Round 1 - Division II, Level Three

Overview:

Calculate the number tennis shot patterns possible given a set of forbidden sequences.

Java Source:
001: public class TennisRallies {
002: 
003: 
004:     private int numPossible;
005: 
006:     public int howMany(int numLength, String[] forbidden, int allowed) {
007: 
008:         /*
009:         * Used to see if we're better off calling isValid() more often to keep
010:         * the size of the recursion tree smaller, or hold off using it until
011:         * after all possible combinations have been generated.
012:         */
013:         boolean usedDelayedValidate = true;
014: 
015:         numPossible = 0;
016: 
017:         long start = System.currentTimeMillis();
018: 
019:         if (usedDelayedValidate)  {
020:             addShotsDelayedValidate("", numLength, forbidden, allowed);
021:         } else {
022:             addShotsEarlyValidate("", numLength, forbidden, allowed);
023:         }
024:         long end = System.currentTimeMillis();
025: 
026:         System.out.println("Time: " + (end - start) + "ms");
027: 
028:         return numPossible;
029:     }
030: 
031:     // Use recursion to create and validate all possible shot patterns.
032:     private void addShotsEarlyValidate(String base, int size,
033:                                        String[] forbidden, int allowed) {
034: 
035:         if (base.length() == size) {
036:             numPossible++;
037: 
038:         } else {
039:             if (isValid(base + "c", forbidden, allowed)) {
040:                 addShotsEarlyValidate(base + "c", size, forbidden, allowed);
041:             }
042: 
043:             if (isValid(base + "d", forbidden, allowed))
044:                 addShotsEarlyValidate(base + "d", size, forbidden, allowed);
045:         }
046:     }
047: 
048:     private void addShotsDelayedValidate(String base, int size,
049:                                          String[] forbidden, int allowed) {
050: 
051:         if (base.length() == size) {
052:             if (isValid(base, forbidden, allowed))  {
053:                 numPossible++;
054:             }
055:         } else  {
056:             addShotsDelayedValidate(base + "c", size, forbidden, allowed);
057:             addShotsDelayedValidate(base + "d", size, forbidden, allowed);
058:         }
059:     }
060: 
061:     /*
062:     * Counts the number of times a pattern given in forbidden appears in
063:     * s.  Stops when that count reaches allowed.
064:     */
065:     private boolean isValid(String s, String[] forbidden, int allowed) {
066: 
067:         int numFails = 0;
068: 
069:         for (String f : forbidden) {
070:             numFails += countMatches(s, f, (allowed - numFails));
071:             if (numFails >= allowed) return false;
072:         }
073: 
074:         return true;
075: 
076:     }
077: 
078:     /*
079:     * Counts the number of times pat appears in str.  Stops when/if
080:     * maxMatches is reached.
081:     */
082:     private int countMatches(String str, String pat, int maxMatches) {
083: 
084:         int strIdx = 0;
085:         int patIdx = 0;
086:         int startOfMatch = 0;
087:         int numMatches = 0;
088: 
089:         if (str.length() < pat.length()) {
090:             return 0;
091:         }
092: 
093:         // Walk through str one char at a time until we reach the end.
094:         while (strIdx < str.length()) {
095: 
096:             // Advance until a char in str matches the first char in pat.
097:             while ((strIdx < str.length() &&
098:                     (str.charAt(strIdx) != pat.charAt(patIdx)))) {
099:                 strIdx++;
100:             }
101: 
102:             if (strIdx == str.length()) return numMatches;
103: 
104:             // Note the beginning of a potential match.
105:             startOfMatch = strIdx;
106: 
107:             // Advance through both strings so long as the chars match
108:             while ((strIdx < str.length()) &&
109:                     (patIdx < pat.length()) &&
110:                     str.charAt(strIdx) == pat.charAt(patIdx)) {
111:                 strIdx++;
112:                 patIdx++;
113:             }
114: 
115:             // If we've reached the end of pat, then a match has been found.
116:             if (patIdx == pat.length()) {
117:                 numMatches++;
118:                 if (numMatches == maxMatches) {
119:                     return numMatches;
120:                 }
121: 
122:                 // Begin again at the next character.
123:                 strIdx = startOfMatch + 1;
124:                 patIdx = 0;
125: 
126:    /*
127:    * If we didn't reach the end of the string, then the characters
128:    * must have differed.  Start again at the character following
129:    * startOfMatch.
130:    */
131:             } else if (strIdx < str.length()) {
132:                 strIdx = startOfMatch + 1;
133:                 patIdx = 0;
134:             }
135: 
136:         }
137: 
138:         return numMatches;
139:     }
140: 
141: }
Notes:

The solution uses recursion to generate all valid combinations of cross-court "c", and down-the-line "d" shots. The howMany() method simply resets the counter variable numPossible, and the launches the recursive method addShots(). When addShots() completes, we'll have our answer in numPossible.

It's important to note the constraints given by the problem. numLength can be at most 18. Since we have only two characters (c and d), there can be at most 2^18 = 262,144 possible sequences. This is entirely possible to solve using a brute-force algorithm. If there were one or two more shot types, say a passing shot and/or a lob, then we'd be looking at 3^18 = 387,420,489 and 4^18 = ~69 billion which would make brute-force less feasible.

I've left in two variations of the addShots() method: addShotsEarlyValidate() and addShotsDelayedValidate(). In addShotsEarlyValidate(), we check each String as it is being built to ensure it will be valid before making the recursive call. The idea is to limit the size of the recursive tree. However, this results in many more calls to isValid(). Alternatively, addShotsDelayedValidate() allows all possible patterns to continue, and only calls isValid() once the desired length has been reached. This results in a larger recursive tree, but limits the number of calls to isValid(). I ran both against the provided test cases, and addShotsDelayedValidate() ran in roughly half as much time.

The isValid() method simply calls countMatches() on each string in the forbidden array. It exits as soon as the value of allowed is reached.

The real work is performed in countMatches(). countMatches() works left to right through the str String. At each character, it checks to see if pat can be found anywhere to the right of the current index. It too keeps track of the number of matches it has found and exits early once maxMatches is reached.

Wednesday, December 24, 2014

StringTrain

Problem:

TopCoder Problem Statement - StringTrain

Overview:

Concatenate a series of Strings together by matching prefixes and suffixes.

Java Source:
001: import java.util.HashSet;
002: import java.util.Set;
003: 
004: public class StringTrain {
005: 
006:     // The method called by TopCoder
007:     public String buildTrain(String[] cars) {
008: 
009:         String train = cars[0];
010: 
011:         // Process each car in turn.
012:         for (int i = 1; i < cars.length; i++) {
013:             train = processCar(train, cars[i]);
014:         }
015: 
016:         // Get the train length before removing characters.
017:         int trainLength1 = train.length();
018: 
019:         train = removeAllButLastChar(train);
020: 
021:         return trainLength1 + " " + train;
022:     }
023: 
024:     private static String processCar(String train, String car) {
025: 
026:         int trainIdx = 0;
027:         int carIdx = 0;
028: 
029:         while (trainIdx < train.length()) {
030: 
031:             /*
032:             * Move forward through the characters in train until one that
033:             * matches the first character of car is found.
034:             */
035:             while ((trainIdx < train.length()) &&
036:                     (car.charAt(carIdx) != train.charAt(trainIdx))) {
037:                 trainIdx++;
038:             }
039: 
040:             // If we reach the end of train, return train.
041:             if (trainIdx == train.length()) {
042:                 return train;
043:             }
044: 
045:             // Mark the start of this possible suffix.
046:             int startOfSuffix = trainIdx;
047: 
048:             /*
049:             * While the characters match, and we haven't reached the
050:             * end of either string, move to the next character of each string.
051:             */
052:             while ((trainIdx < train.length()) &&
053:                     (carIdx < car.length()) &&
054:                     (car.charAt(carIdx) == train.charAt(trainIdx))) {
055:                 trainIdx++;
056:                 carIdx++;
057:             }
058: 
059:             // If we've reached the end of the train.
060:             if (trainIdx == train.length()) {
061: 
062:                 /*
063:                 * If startOfSuffix == 0, then the entire train String
064:                 * is being used.  If carIdx == car.length, then the entire
065:                 * car String is used.  In either case, it's not a proper
066:                 * pre/suf-fix.
067:                 */
068:                 if ((startOfSuffix != 0) && (carIdx < car.length())) {
069: 
070:                     /*
071:                     * Create the return string by starting with train as the
072:                     * base and adding the remaining characters from car.
073:                     */
074:                     StringBuilder sb = new StringBuilder();
075:                     sb.append(train);
076:                     for (int i = carIdx; i < car.length(); i++) {
077:                         sb.append(car.charAt(i));
078:                     }
079:                     return sb.toString();
080:                 }
081:             }
082: 
083:             // Move train index forward, and reset the car index.  Try again.
084:             trainIdx = startOfSuffix + 1;
085:             carIdx = 0;
086: 
087:         }
088: 
089:         return train;
090:     }
091: 
092:     private static String removeAllButLastChar(String s) {
093: 
094:         // This set contains all characters that have been seen.
095:         Set usedChars = new HashSet<>();
096: 
097:         StringBuilder sb = new StringBuilder(s.length());
098: 
099:         /*
100:         * Work backward from the end of the String to the front.
101:         * Add characters to the output only if they are not in the usedChars
102:         * set.  When a new character is encountered, add it to the front
103:         * of the output, and add the character to usedChars so it is not
104:         * added again.
105:         */
106:         for (int i = s.length() - 1; i >= 0; i--) {
107:             if (!usedChars.contains(s.charAt(i))) {
108:                 usedChars.add(s.charAt(i));
109:                 sb.insert(0, s.charAt(i));
110:             }
111:         }
112: 
113:         return sb.toString();
114: 
115:     }
116: 
117: }
Notes:

The main method buildTrain() simply sets the initial value of the train and then loops through each of the remaining cars, calling processCar() on them. All of the hard work is done inside processCar(). After all the cars have been processed, we note the length of the train, and then call removeAllButLastChar() before returning the results.

processCar() works by moving through the train string from beginning to end. The variable trainIdx is the current character in the train string that we're examining. carIdx is an index into the car String, and startOfSuffix will hold the position of the beginning of a possible prefix/suffix match. This is in case the match ultimately fails so we can pick up from the next character.

First, processCar() skips over characters in train until it finds one that matches the first character of car. If there are no matches before reaching the end of train, then just return train. Assuming that the first character of car appears in train, we mark that location as the beginning of a possible suffix. Then we walk through both strings one character at a time until we either reach the end of one of the Strings, or until the characters no longer match.

If we reach the end of the train string, then we have a possible prefix/suffix match. Check to make sure that our match does not include the entire train or car String, as this would not be a "proper" prefix or suffix. If that test passes, then we construct the result string by appending the remaining characters from car onto the end of train.

If the characters cease to match up, or if we reach the end of the car string, then we reset carIdx back to the beginning of the car String and set the trainIdx to the character following where we began the previous prefix/suffix match attempt. We then continue trying to find a match from that point.

With the hard part done, we now turn to removeAllButLastChar(). First we create a Set of characters to hold all of the characters we've seen so far. Then there's a StringBuilder to build up our result. Next, we'll work backward through the string. For each chacter, if it exists in the usedChars Set, then skip it. If it's not in that set, add it, and then add that character to the front of our StringBuilder.

Quilting

Problem:

TopCoder Problem Statement - Quilting

Overview:

Determine the color of the last patch when constructing a quilt.

Java Source:
001: import java.util.ArrayList;
002: import java.util.List;
003: 
004: public class Quilting {
005: 
006:     private static final int NO_COLOR = -1;
007: 
008:     // X and Y steps when moving up, left, down, and right
009:     private static final int[] spiralX = {0, -1, 0, 1};
010:     private static final int[] spiralY = {-1, 0, 1, 0};
011: 
012:     // Ensures that we move up after the first patch.
013:     private int direction = 3;
014: 
015:     // Each int is an index into colorList.
016:     private int[][] quilt;
017: 
018:     /*
019:     * Keeps track of how often a color was used.  The index matches
020:     * the index in colorList, and the value is the count.
021:     */
022:     private int[] colorUsageQuilt;
023: 
024:     /*
025:     * Method called by TopCoder
026:     */
027:     public String lastPatch(int length, int width, String[] colorList) {
028: 
029:         // Initialize the quilt.  All colors set to NO_COLOR
030:         quilt = new int[width][length];
031:         for (int x = 0; x < width; x++)  {
032:             for (int y = 0; y < length; y++)  {
033:                 quilt[x][y] = NO_COLOR;
034:             }
035:         }
036: 
037:         colorUsageQuilt = new int[colorList.length];
038: 
039:         // Starting point, location of first patch.
040:         int x = width / 2;
041:         int y = length / 2;
042: 
043:         int lineLength = 0;
044: 
045:         // Change directions when lineLength reaches this.
046:         int lineLengthMax = 1;
047: 
048:         // Loop through all patches
049:         for (int i = 0; i < (width * length); i++)  {
050: 
051:             int color = getPatchColor(x, y);
052:             quilt[x][y] = color;
053:             colorUsageQuilt[color]++;
054: 
055:             lineLength++;
056: 
057:             if (lineLength == lineLengthMax)  {
058:                 lineLength = 1;
059:                 direction = (direction + 1) % 4;
060: 
061:                 // Line length increases when starting up or down.
062:                 if ((direction % 2) == 0)  {
063:                     lineLengthMax++;
064:                 }
065:             }
066: 
067:             // Move to next patch position.
068:             x += spiralX[direction];
069:             y += spiralY[direction];
070:         }
071: 
072:         // Back up one to the last patch
073:         x -= spiralX[direction];
074:         y -= spiralY[direction];
075: 
076:         return colorList[quilt[x][y]];
077:     }
078: 
079:     private int getPatchColor(int x, int y)  {
080: 
081:         // Calculate least used neighboring color.
082:         List leastNeighborColors = getLeastNeighborColors(x, y);
083:         if (leastNeighborColors.size() == 1)  {
084:             return leastNeighborColors.get(0);
085:         }
086: 
087:         // Of the least used neighboring colors, calculate least used overall.
088:         List leastOverallColors =
089:                 getLeastOverallColors(leastNeighborColors);
090:         if (leastOverallColors.size() == 1)  {
091:             return leastOverallColors.get(0);
092:         }
093: 
094:         // If still tied, return minimum value in list
095:         int min = Integer.MAX_VALUE;
096:         for (int i : leastOverallColors)  {
097:             min = Math.min(min, i);
098:         }
099:         return min;
100:     }
101: 
102:     private List getLeastNeighborColors(int x, int y) {
103: 
104:         int[] colorCount = new int[colorUsageQuilt.length];
105: 
106:         // Loop through the 9x9 grid surrounding x,y and count the colors.
107:         for (int x1 = x-1; x1 <= x+1; x1++)  {
108:             for (int y1 = y-1; y1 <= y+1; y1++)  {
109: 
110:                 // Ensure we're not out of bounds, and that a color is set.
111:                 if ((x1 >= 0) && (x1 < quilt.length) &&
112:                         (y1 >= 0) && (y1 < quilt[0].length) &&
113:                         (quilt[x1][y1] != NO_COLOR))  {
114: 
115:                     // Increment the count for the color at this position.
116:                     colorCount[quilt[x1][y1]]++;
117:                 }
118: 
119:             }
120:         }
121: 
122:         // Determine the smallest count.
123:         int leastCount = Integer.MAX_VALUE;
124: 
125:         for (int i = 0; i < colorCount.length; i++)  {
126:             leastCount = Math.min(leastCount, colorCount[i]);
127:         }
128: 
129:         // Add all colors that have the smallest count.
130:         List leastUsedColors = new ArrayList<>();
131: 
132:         for (int i = 0; i < colorCount.length; i++)  {
133:             if (colorCount[i] == leastCount)  {
134:                 leastUsedColors.add(i);
135:             }
136:         }
137: 
138:         return leastUsedColors;
139:     }
140: 
141:     private List getLeastOverallColors(List colors)  {
142: 
143:         // Determine the smallest count among all colors.
144:         int leastCount = Integer.MAX_VALUE;
145: 
146:         for (int color : colors)  {
147:             leastCount = Math.min(leastCount, colorUsageQuilt[color]);
148:         }
149: 
150:         // Add all colors that have that smallest count.
151:         List leastUsedColors = new ArrayList<>();
152: 
153:         for (int color : colors)  {
154:             if (colorUsageQuilt[color] == leastCount)  {
155:                 leastUsedColors.add(color);
156:             }
157:         }
158: 
159:         return leastUsedColors;
160:     }
161: 
162: }
Notes:

The quilt is represented as a 2 dimensional array of ints, where the value of each location is an index into the colorList array. We start by initializing each location in the quilt to -1 to indicate that the color has not yet been choosen.

The next step is to determine where the first patch will be located. Here it might help to draw some examples out on paper. You'll find that the origin works out to x = width / 2 and y = length / 2. Remember, the / operator removes any decimal portion of the division, effectively rounding down.

To determine the color of the first patch, we simply implement the 3 rules that were given. This is found in getPatchColor(). getLeastNeighbor() looks at the 9 positions surrounding the current location, and counts the number of times each color appears. Here we have to be careful not to look outside the bounds of the arrays, and to ignore any place where the color has not been set. Once we've counted how many times each color appears, we find the smallest number, and finally return a list that contains all colors whose count is equal to that smallest number.

If the list size is 1, we're done. If there are ties, we move on to rule 2. The array colorUsageQuilt keeps track of how many times each color is used in the entire quilt. We use this and similar logic as before to return the colors that came out of rule 1 which now match the minimum count. If there are still ties, we just return the color with the smallest index.

That takes care of determining the color for a patch. The next step is to devise a method to move from one patch to the next following the outward spiraling pattern. Here the arrays spiralX and spiralY come into play and the related variables diretion, lineLength, and lineLengthMax. direction provides an index into spiralX and spiralY to get the change in x and y to move to the next location. We also keep track of the current line length, and the maximum length for the current line. This tells us when to change direction.

Initially the direction is to the right, and the lineLengthMax is 1. Then we set the color of the first patch, and lineLength becomes 1. This matches lineLengthMax, so we increment direction (mod 4) which corresponds to up, and reset lineLength. Whenever the direction changes to up or down, we increment lineLengthMax. This setup gives us a nice counter-clockwise outward spiral movement.

Finally, we just need to loop through the number of patches, setting the color at each, and then moving on to the next patch. After all the patches have been set, we need to back up one place since we'll have moved on to the next location. Then just return the color there. Remember, the value at that location is an index into colorList.

Monday, December 22, 2014

CheatCode

Problem:

TopCoder Problem Statement - CheatCode

Overview:

Determine if a series of key presses matches a cheat code. The key presses may contain repeating characters that are not present in the code.

Java Source:
001: import java.util.ArrayList;
002: import java.util.List;
003: 
004: public class CheatCode {
005: 
006:     /*
007:     * This class simply binds a char and an int together.
008:     */
009:     private class CharAndCount {
010: 
011:         final char c;
012:         final int count;
013: 
014:         CharAndCount(char c, int count) {
015:             this.c = c;
016:             this.count = count;
017:         }
018:     }
019: 
020:     public int[] matches(String keyPresses, String[] codes) {
021: 
022:         // Encode the String to make it easier to analyse.
023:         List keyPressCode = createCode(keyPresses);
024: 
025:         // Holds all of the codes that match keyPresses
026:         List matches = new ArrayList<>();
027: 
028:         /*
029:         * Loop through each code.  If keyPresses matches the code, then
030:         * add code to the list of matches.
031:         */
032:         for (int i = 0; i < codes.length; i++) {
033:             if (matchesCheat(keyPressCode, createCode(codes[i]))) {
034:                 matches.add(i);
035:             }
036:         }
037: 
038:         // Convert the List into an array and return it.
039:         int[] result = new int[matches.size()];
040:         for (int i = 0; i < result.length; i++) {
041:             result[i] = matches.get(i);
042:         }
043:         return result;
044: 
045:     }
046: 
047:     /*
048:     * Takes an encoded string that represents the keyPresses, and one
049:     * that represents the code.  See the createCode method.
050:     * code matches if it's character sequence is contained in presses,
051:     * and each character's count is less than or equal to the count in
052:     * presses.
053:     */
054:     private boolean matchesCheat(List presses,
055:                                  List code) {
056: 
057:         int pStartIdx = 0;
058:         int codeIdx = 0;
059: 
060:         /*
061:         * Start at position 0 in presses and check until the current position
062:         * plus the length of the code would put us beyond the length of
063:         * presses.
064:         */
065:         while (pStartIdx <= (presses.size() - code.size())) {
066: 
067:             int pCurrentIdx = pStartIdx;
068: 
069:             /*
070:             * While presses and code agree, increment indexes for each
071:             */
072:             while ((pCurrentIdx < presses.size()) &&
073:                     (codeIdx < code.size()) &&
074:                     (presses.get(pCurrentIdx).c == code.get(codeIdx).c) &&
075:                     (presses.get(pCurrentIdx).count >=
076:                             code.get(codeIdx).count)) {
077:                 pCurrentIdx++;
078:                 codeIdx++;
079:             }
080: 
081:             // If we matched the entire code, return true.
082:             if (codeIdx == code.size()) return true;
083: 
084:             /*
085:             * Otherwise, return to the beginning of the code, and start with
086:             * the next position in presses.
087:             */
088:             codeIdx = 0;
089:             pStartIdx++;
090:         }
091: 
092:         return false;
093:     }
094: 
095:     /*
096:     * Encodes a String by replacing each repeating character with a
097:     * CharAndCount object that holds the character and the number of
098:     * times it repeats.  For example:
099:     * AAABBC becomes {{3,A}, {2,B}, {1,C}}
100:     */
101:     private List createCode(String s) {
102: 
103:         List result = new ArrayList<>();
104: 
105:         if ((s == null) || (s.length() == 0)) return result;
106: 
107:         int count = 0;
108:         char c = s.charAt(0);
109: 
110:         for (int i = 0; i < s.length(); i++) {
111: 
112:             // If character is the same, just increase the count.
113:             if (c == s.charAt(i)) {
114:                 count++;
115:             } else {
116: 
117:                 // Set up the next repeating sequence.
118:                 result.add(new CharAndCount(c, count));
119:                 count = 1;
120:                 c = s.charAt(i);
121:             }
122:         }
123:         result.add(new CharAndCount(c, count));
124: 
125:         return result;
126:     }
127: }
Notes:

In my first attempt at this problem, I built a regular expression out of each of the codes and then simply checked to see if the key presses were matched by that regular expression. I inserted a '+' after each character of the code, meaning that it matches on 1 or more characters from key presses. So, if the code was "ABC", the regular expression became "A+B+C+" which would match "AAAAAAAAABCCC". This worked great, except that there are some test cases that timed out. For example, checking to see if "A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+A+" matches "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" is extermely slow. Regular expression matching in Java can run in O(n^2) time, making this approach unfeasible. For a good explanation of Regular Expression running time, see Regular Expression Matching Can Be Simple And Fast

This solution encodes the key presses and all of the codes by replacing repeating characters (or even a single character) with a character and it's count. The key press sequence "AAAAAAAAAA" is encoded as {A,10}. The character and it's cound are bound together using a CharAndCount class.

Once the Stirngs are encoded, it becomes much easier to see if there is a match. We'll use two indexes into the key press list: pStartIdx, and pCurrentIdx. pStartIdx begins at the first character of the key press string and slowly makes its way toward the end. For each position of pStartIdx, pCurrentIdx searches the remainder of the key press string, beginning at pStartIdx and going to the end attempting to match the given code. If no match is found, then pStartIdx is incremented and the process repeats.

In order for the code the match, there must be a sequence of characters in presses that matches the sequence given by code. Also, the count in presses must be greater than, or equal to, the count in code for each corresponding character.

ContestScore

Problem:

TopCoder Problem Statement - ContestScore

Overview:

Rank contestants based on scores given by a panel of judges.

Java Source:
001: import java.util.ArrayList;
002: import java.util.Collections;
003: import java.util.Comparator;
004: import java.util.List;
005: 
006: public class ContestScore {
007: 
008:     /*
009:     * A class to hold the data related to a single contestant.
010:     */
011:     private class Contestant {
012: 
013:         final String name;
014:         final int[] scores;
015:         final int[] ranks;
016: 
017:         Contestant(String data) {
018: 
019:             // Get the contestant's name
020:             String[] elements = data.split(" ");
021:             this.name = elements[0];
022: 
023:             // Copy the remainder of data into scores.
024:             scores = new int[elements.length - 1];
025: 
026:             for (int i = 1; i < elements.length; i++) {
027: 
028:     /*
029:     * For now, we'll remove the decimal place from the score.
030:     * This won't change the rankings at all.  We'll put the
031:     * decimal back in when displaying the results.
032:     */
033:                 int score = Integer.parseInt(elements[i].replace(".", ""));
034:                 scores[i - 1] = score;
035:             }
036: 
037:             // Ranks is empty for now.
038:             this.ranks = new int[scores.length];
039: 
040:         }
041: 
042:         // Returns the sum of all elements in rank
043:         int getTotalRank() {
044:             int totalRank = 0;
045:             for (int i = 0; i < ranks.length; i++) {
046:                 totalRank += ranks[i];
047:             }
048:             return totalRank;
049:         }
050: 
051:         // Returns the sum of all elements in score
052:         int getTotalScore() {
053:             int totalScore = 0;
054:             for (int i = 0; i < scores.length; i++) {
055:                 totalScore += scores[i];
056:             }
057:             return totalScore;
058:         }
059: 
060:         public String toString() {
061: 
062:             int totalRank = getTotalRank();
063:             int totalScore = getTotalScore();
064: 
065:    /*
066:    * score1 is the integer portion of the score.
067:    * score2 will be the decimal portion.
068:    */
069:             int score1 = totalScore / 10;
070:             int score2 = totalScore % 10;
071: 
072:             StringBuilder sb = new StringBuilder();
073:             sb.append(name);
074:             sb.append(" ");
075:             sb.append(totalRank);
076:             sb.append(" ");
077:             sb.append(score1);
078:             sb.append(".");
079:             sb.append(score2);
080:             return sb.toString();
081:         }
082:     }
083: 
084:     /*
085:     * Compares contestants based on the given judge.
086:     */
087:     private class ContestantComparatorByJudge implements
088:             Comparator {
089: 
090:         private final int judge;
091: 
092:         ContestantComparatorByJudge(int judge) {
093:             this.judge = judge;
094:         }
095: 
096:         @Override
097:         public int compare(Contestant o1, Contestant o2) {
098: 
099:             // Sort scores highest to lowest.
100:             return -1 * Integer.compare(o1.scores[judge], o2.scores[judge]);
101:         }
102:     }
103: 
104:     /*
105:     * Compares contestants based on their ranks.  All the ranks should be
106:     * computed prior to calling.
107:     */
108:     private class ContestantComparatorOverall implements
109:             Comparator {
110: 
111:         @Override
112:         public int compare(Contestant o1, Contestant o2) {
113: 
114:             // Compare rank first
115:             if (o1.getTotalRank() != o2.getTotalRank()) {
116:                 return Integer.compare(o1.getTotalRank(), o2.getTotalRank());
117:             }
118: 
119:             // If there's a tie, compare by score, highest to lowest.
120:             if (o1.getTotalScore() != o2.getTotalScore()) {
121: 
122:                 // Multiply by -1, since we want the higher score first.
123:                 return -1 * Integer.compare(o1.getTotalScore(),
124:                         o2.getTotalScore());
125:             }
126: 
127:             // If still tied, compare by name.
128:             return o1.name.compareTo(o2.name);
129: 
130:         }
131:     }
132: 
133: 
134:     public String[] sortResults(String[] data) {
135: 
136:         if (data == null) {
137:             return null;
138:         }
139: 
140:         if (data.length == 0) {
141:             return new String[0];
142:         }
143: 
144:         List contestants = new ArrayList<>();
145: 
146:         for (int i = 0; i < data.length; i++) {
147:             contestants.add(new Contestant(data[i]));
148:         }
149: 
150:         int numJudges = data[0].split(" ").length - 1;
151: 
152:         for (int i = 0; i < numJudges; i++) {
153: 
154:             // Create a new comparator to examine current judge's scores.
155:             ContestantComparatorByJudge judgeComparator =
156:                     new ContestantComparatorByJudge(i);
157: 
158:             // Sort the contestants using the new comparator.
159:             Collections.sort(contestants, judgeComparator);
160: 
161:    /*
162:    * Assign ranks to each contestant.  Need to keep track of previous
163:    * rank and score in the event that there are ties.
164:    */
165:             int rank = 0;
166:             int lastScore = -1;
167:             int lastRank = 1;
168: 
169:             for (Contestant c : contestants) {
170:                 rank++;
171:                 if (c.scores[i] == lastScore) {
172:                     c.ranks[i] = lastRank;
173:                 } else {
174:                     c.ranks[i] = rank;
175:                     lastScore = c.scores[i];
176:                     lastRank = rank;
177:                 }
178:             }
179:         }
180: 
181:   /*
182:   * Once all the ranks are assigned.  Sort the contestants using
183:   * the ContestantComparatorOverall comparator.
184:   */
185:         ContestantComparatorOverall overallComparator =
186:                 new ContestantComparatorOverall();
187: 
188:         Collections.sort(contestants, overallComparator);
189: 
190:         // Build the result String[]
191:         String[] results = new String[data.length];
192: 
193:         int i = 0;
194:         for (Contestant c : contestants) {
195:             results[i++] = c.toString();
196:         }
197: 
198:         return results;
199: 
200:     }
201: }
Notes:

To solve this, we first need to assign ranks based on each judge's score, and then sort the contestants based on their rankings. To make things easy, a Contestant class is used to store all the data related to a single contestant, and two Comparator classes help out with the sorting.

The constructor for the Contestant class handles reading in a string and parsing out the name and the scores. The name is the first element, and the remainder of the String is chopped up into ints and copied to the scores array. Note that at this point I strip out the decimal place. I'll add that back in when displaying the results. But for now, it'll be easier to effectively just multiply all scores by 10. Finally, the constructor initializes an array to hold the rankings, but this cannot be filled in yet.

The sortResults() method begins by first checking to ensure that the data parameter is not empty, and then creates a List to store the Contestants. Then, for each judge, we'll create a new ContestantComparatorByJudge comparator to help sort the contestants by the current judge. The ContestantComparatorByJudge class takes a int in it's constructor, and uses that to compare the scores in the Contestan's score array. Note that the compare() method multiplies the result of Integer.compare() by -1 because we want the contestants in order from highest to lowest. Once the contestants are sorted by a given judge's score, we can assign a rank to each contestant for that judge. Here, we need to be careful in case there is a tie in the score.

Once all the ranks are assigned, a different comparator, ContestantComparatorOverall, is used to sort the contestants one last time. ContestantComparatorOverall first compares by the sum of all ranks (lowest to highest), then if there is a tie, by total score (highest to lowest). If there is still a tie, it compares their names.

After the contestans are sorted in their final order, just loop through them, using their toString() method to build the String[] result.

All in all, this was not too hard for a 1000 point problem. Just a few key points:

  1. If possible, convert decimals to integers to keep things easy.
  2. Use Collections.sort to do all the sorting. Just implement the custom comparators.
  3. Be careful with how you handle ties.

If you can handle that, there's really not much to this problem.

Thursday, December 18, 2014

Archimedes

Problem:

TopCoder Problem Statement - Archimedes

Overview:

Approximate the value of Π using the circumference of polygons inscribed in a circle.

Java Source:
01: public class Archimedes {
02:
03:     public double approximatePi(int numSides) {
04:
05:         double innerAngle = 360 / (double) numSides;
06:         double outerAngle = (180 - innerAngle) / 2;
07:
08:         // Don't forget to convert to Radians 
09:         double lengthOfSide = Math.cos(Math.toRadians(outerAngle));
10:  
11:         return numSides * lengthOfSide;
12:
13:     }
14: }
Notes:

To solve this, we need to determine the length of each side of the inscribed polygon.

To construct the inscribed polygon, start by imagining spokes coming from the center of the circle out to the edge. The number of spokes equals the number of sides in the polygon. The polygon will be drawn by connecting the points where the spokes intersect the circle.

Next, the angle between the spokes is simply 360° divided by the number of spokes (sides). I've called this innerAngle.

outerAngle is the angle formed between a spoke and a side of the inscribed polygon. Since two adjacent spokes and the connecting edge between them constitute a triangle, the sum of their interior angles is 180° Therefore, outerAngle is 180° - innerAngle divided by 2.

Now, the length of the side of the polygon is just the cosine of the outerAngle. Note that Math.cos() expects a value in radians, so remember to call Math.toRadians() first since we've been working in degrees.

Finally, just return numSides * lengthOfSide.

Be careful to cast to a double where necessary in order to avoid losing precision. You will not get the correct answer if the cast is left out of the calculation for the innerAngle.

If you need to brush up on your trigonometry, there are plenty of sites to help out. I recommend checking out the Kahn Academy

As a final note, the TopCoder editorials given an even shorter answer:

  • return numSides * Math.sin(Math.PI / numSides);
I'm not sure how I feel about using Math.PI when we're trying to approximate Π but I supposed that's being picky. Besides, I'm sure the toRadians() method uses Π anyway.

Tuesday, December 16, 2014

CardCount

Problem:

TopCoder Problem Statement - CardCount

Overview:

Determine the cards that will end up in each players hand after a deck has been delt.

Java Source:
01: public class CardCount {
02: 
03:     public String[] dealHands(int numPlayers, String deck) {
04: 
05:         int numCardsPerPlayer = deck.length() / numPlayers;
06: 
07:         String[] hands = new String[numPlayers];
08: 
09:         // Loop through the players one at a time.
10:         for (int i = 0; i < numPlayers; i++) {
11: 
12:             StringBuilder hand = new StringBuilder(numCardsPerPlayer);
13: 
14:             /*
15:             * Start with the card at position i, then skip numPlayers cards
16:             * until the hand is full.
17:             */
18:             for (int j = i; hand.length() < numCardsPerPlayer; j += numPlayers) {
19:                 hand.append(deck.charAt(j));
20:             }
21: 
22:             hands[i] = hand.toString();
23:         }
24: 
25:         return hands;
26:     }
27: }
Notes:

Rather than deal the first card to player one, then the next card to player two, and so on; this solution determines all of the cards that will end up in a player's hand before moving on to the next player.

It's simple enough to determine how many cards each player will get, just divide the length of the deck by the number of players. The division operator rounds down, which ensures that all players get the same number of cards without needing more cards than there are in the deck.

The outer-most for loop loops through each of the players. For each player, their first card will be in position i. Then we just add each card that is numPlayers further down in the deck until the player has the correct number of cards. Each card is added to a StringBuffer, which gets converted into a String and added to the appropriate place in the hands[] array.