## Monday, June 30, 2014

### PeopleCircle

Problem:
Overview:

Determine the starting arrangement of a number of males and females sitting around a circle, given the number of females, and the value of i, where the ith person is removed each round.

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 147
04: Division: 2
05: Level: 2
06: Points: 600
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1225
08:  */
09:
10: public class PeopleCircle {
11:
12:     private char[] circle;
13:
14:     private int numAdded = 0;
15:
16:     public String order(int numMales, int numFemales, int K) {
17:
18:         // Creates a new array large enough to hold all males and females.
19:         circle = new char[numMales + numFemales];
20:
21:         /*
22:           Initialize the circle to have numMales. This is the problem's
23:           ending condition.  We'll work backwards from here.
24:          */
25:         for (int i = 0; i < numMales; i++) {
26:             circle[i] = 'M';
27:         }
28:
29:         /*
30:        Set the initial positions to be just after the number of males.  When
31:         problem description has finished, the circle will have all males,
32:         the last female will have just been removed.
33:         */
34:         int position = numMales;
36:
37:         // Check for the case where there were no females to start with.
38:         if (numFemales == 0) {
39:             return new String(circle);
40:         }
41:
42:         /*
43:         Count back and insert females until all have been added.
44:          */
45:         while (numAdded < numFemales) {
46:             insertFemale(position);
48:             position = position - K + 1;
49:
50:             // Loop around to the back of the array
51:             while (position < 0) {
52:                 position += numMales + numAdded;
53:             }
54:         }
55:
56:         /*
57:         Construct the return string by taking the elements to the right
58:         of the current positions, and then adding the elements from the
59:         beginning of the circle up to the current position.
60:          */
61:         String s1 = new String(circle).substring(position);
62:         String s2 = new String(circle).substring(0, position);
63:         return s1 + s2;
64:     }
65:
66:     /*
67:     Inserts a female ('F') at the given positions.
68:     Shifts everything to the right of pos one spot further to the right
69:     creating a space to insert the new character.
70:      */
71:     private void insertFemale(int pos) {
72:
73:         /*
74:         Works backward from the end of the array shifting everything
75:         over to the right.
76:          */
77:         for (int i = circle.length - 1; i > pos; i--) {
78:             circle[i] = circle[i - 1];
79:         }
80:
81:         circle[pos] = 'F';
82:     }
83: }```
Notes:

This problem requires you to start from the end state and work backwards to reconstruct what the beginning must have looked like. We know from the problem that it started as some point and removed the Kth person. This repeated numFemale times until all the females are gone. So the first hint is that on every move a female is removed, the number of males remains constant.

Lines 19 through 27 create an array large enough to hold all participants, and then inserts the number of males starting at the head of the array.

Now, we reverse the process. Instead of counting ahead and removing a female, we count back and insert a female. Line 48 handles counting back, and the insertFemale() method takes care of inserting the 'F' at the given position and shifting everything beyond that point one spot to the right.

We must be careful because the size of the circle array is not the number of people currently in the circle at that point. Lines 51-53 detect when we've gone in front of the beginning of the array, and set us back to the end based on the number of people.

Finally, we won't necessary end up at the start of the array. So, to construct the return string, we need to concatenate everything to the right of our current position, with everything from the beginning of the the array up to our current position.

 |--A--- ----------B----------| ^

For some clarity, if our final position is at the ^, then the return string would be B + A.

### HillHike

Problem:
Overview:

Determine the number of possible paths over a hill. At each step, you may go up, down, or stay level. You must reach the maximum height and a number of landmarks in between.

Java Source:
```    1  : /*
2  : TopCoder
3  : Single Round Match: 145
4  : Division: 1
5  : Level: 3
6  : Points: 1000
7  : Description: http://community.topcoder.com/stat?c=problem_statement&pm=1158
8  :  */
9  :
10 : public class HillHike {
11 :
12 :     private int maxDistance;
13 :
14 :     private int maxHeight;
15 :
16 :     private int[] landmarks;
17 :
18 :     private PathCache pathCache;
19 :
20 :     public long numPaths(int distance, int maxHeight, int[] landmarks) {
21 :
22 :         this.maxDistance = distance;
23 :         this.maxHeight = maxHeight;
24 :         this.landmarks = landmarks;
25 :
26 :         // Initialize a new PathCache to store values once they've been seen.
27 :         pathCache = new PathCache(distance, maxHeight, landmarks.length);
28 :
29 :         /*
30 :         The first move must be to distance=1, height=1 so we might as well
31 :         start from there.
32 :          */
33 :         return getPaths(0, 0, 0, false);
34 :     }
35 :
36 :     /*
37 :     Calculates the number of paths starting from a point at distance,height.
38 :     The number of paths also depends on how many landMarks haave been seen
39 :     and whether or not the maximum height has been reached yet.
40 :      */
41 :     private long getPaths(int distance, int height, int landMarksSeen,
42 :                           boolean maxHeightReached) {
43 :
44 :         // Check for going beyond height or distance
45 :         if (distance > maxDistance) { return 0; }
46 :         if ((height > maxHeight) || (height < 0)) { return 0; }
47 :
48 :         // Can't climb faster or descend faster than 1:1
49 :         if (height > distance) { return 0; }
50 :
51 :         // Won't be able to get down in time
52 :         if (height > (maxDistance - distance)) { return 0; }
53 :
54 :         // Can only have a height of 0 at the start and finish
55 :         if ((height == 0) && (distance != 0) && (distance != maxDistance)) {
56 :             return 0;
57 :         }
58 :
59 :         /*
60 :         If we've seen these values before, we'll use that instead of
61 :         recalculating.
62 :          */
63 :         long numPaths = pathCache.getPath(distance, height, landMarksSeen,
64 :                 maxHeightReached);
65 :
66 :         if (numPaths >= 0) { return numPaths; }
67 :
68 :         /*
69 :         If we've reached maxDistance, and we've:
70 :             Seen the maximum height
71 :             Seen all of the landmarks
72 :             and are now back down to height == 0
73 :         Then we have a valid path, return 1
74 :         Otherwise return 0
75 :          */
76 :         if (distance == maxDistance) {
77 :             return (maxHeightReached && (height == 0) &&
78 :                     (landMarksSeen == landmarks.length)) ? 1 : 0;
79 :         }
80 :
81 :         // True if we've seen maxHeight in the past, or are at it now.
82 :         boolean seenMaxHeight = maxHeightReached || (height == maxHeight);
83 :
84 :         int newLandMarksSeen = landMarksSeen;
85 :
86 :         /*
87 :         If we haven't seen all the landmarks yet, and the current height
88 :         equals the height of the next landMark, then increment the number
89 :         of landMarks seen.
90 :          */
91 :         if (landMarksSeen < landmarks.length) {
92 :             if (landmarks[landMarksSeen] == height) {
93 :                 newLandMarksSeen++;
94 :             }
95 :         }
96 :
97 :         // Check how many paths if we go up from here.
98 :         numPaths = getPaths(distance + 1, height + 1, newLandMarksSeen,
99 :                 seenMaxHeight);
100:
101:         // Add how many paths if we stay level from here.
102:         numPaths += getPaths(distance + 1, height, newLandMarksSeen,
103:                 seenMaxHeight);
104:
105:         // Add how many paths if we descend from here.
106:         numPaths += getPaths(distance + 1, height - 1, newLandMarksSeen,
107:                 seenMaxHeight);
108:
109:         // Store this value so we don't have to recalculate it.
110:         pathCache.storePath(distance, height, landMarksSeen,
111:                 seenMaxHeight, numPaths);
112:
113:         return numPaths;
114:     }
115:
116:     /*
117:       Stores the paths that have already been calculated,
118:       so that we don't have to calculate them again.
119:     */
120:     class PathCache {
121:
122:         /*
123:         The number of paths from a given point to the finish is determined by
124:          the distance to the point, it's height, how many landMarks have been
125:           seen up to that point, and if the highest elevations has been
126:           reached yet.  This multi-dimensions array stores the number of
127:           paths given each of these combinations.
128:          */
129:         private final long[][][][] pathsFound;
130:
131:         PathCache(int maxDistance, int maxHeight, int numLandMarks) {
132:
133:             pathsFound = new long[maxDistance + 1][maxHeight + 1]
134:                     [numLandMarks + 1];
135:
136:             // Initialize all values in pathsFound to -1
137:             for (int i = 0; i <= maxDistance; i++) {
138:                 for (int j = 0; j <= maxHeight; j++) {
139:                     for (int k = 0; k <= numLandMarks; k++) {
140:                         for (int m = 0; m < 2; m++) {
141:                             pathsFound[i][j][k][m] = -1;
142:                         }
143:                     }
144:                 }
145:             }
146:         }
147:
148:         /*
149:         Stores the number of paths for the given parameters.
150:          */
151:         void storePath(int distance, int height, int landMarksSeen,
152:                        boolean maxHeightReached, long numPaths) {
153:
154:             pathsFound[distance][height][landMarksSeen]
155:                     [maxHeightReached ? 1 : 0] = numPaths;
156:         }
157:
158:         /*
159:        Returns the number of paths given the input conditions, or
160:        -1 if they haven't been calculated yet.
161:         */
162:         long getPath(int distance, int height, int landMarksSeen,
163:                      boolean maxHeightReached) {
164:
165:             return pathsFound[distance][height][landMarksSeen]
166:                     [maxHeightReached ? 1 : 0];
167:         }
168:     }
169: }
```
Notes:

There are two important concepts on display here. The first is determining the number of paths to the finish given a set of parameters. The second is storing those values so that they do not need to be recalculated over and over. You can get by on small input sets without storing the calculated values, but you will fail at least one of the tests due to the 2 second time limit.

The general approach goes like this: The number of paths to the finish equals the number of successful paths if the next point is a climb, plus the number of paths if the next point is the same height, plus the number of paths if the next point is a descent. We'll recursively call getPaths() on each of these three points and add them together. At each point, if our current height equals the maximum height, then we'll set maxHeightReached to true. Also, if our current height equals the height of the next landmark, then we'll check that off and begin looking for the next landmark. When we reach the finish (distance == maxDistance), then we'll check to see if all the conditions have been met.

First, look at the getPaths() method beginning on line 41. Lines 45-57 perform some rudimentary checks to see if it's even possible to reach the finish given the input. If we're already past the maximum distance, gone over the maximum height, too high given the forward distance, cannot possibly get back down to a height of zero in the remaining distance, of if our height is zero and we're not at either the start or finish; then the are no possible paths - return 0.

Once we've passed all of these checks, lines 63-66 determine if we've already calculated the number of paths given these inputs. If we have, then just return that number and we skip the trouble of recalculating. It's important that we check the out of bounds conditions in the previous paragraph first, as this will prevent ArrayIndexOutOfBoundsExceptions. This can happen if for example, we check for a height above the maximum height.

On line 66, we'll get back a -1 if the path from here has not you been calculated.

Lines 76-80 check to see if we've reach the end and have met all the conditions. We've reached the maximum height at least once. We've passed through all the landmarks, and we've reached distance == maxDistance at height == 0. If all these are true, then return 1 - otherwise, return 0. If we haven't reached maxDistance yet, then we'll continue on and calculate the number of paths from here.

On Line 82, we set seenMaxHeight to be true if we've been at maxHeight previously, or are at it now.

Lines 91-95 check the height of the next expected landMark. If we're at the height of that next land mark, then we increment newLandMarksSeen. That way we'll begin looking for the next land mark height - or if newLandMarksSeen equals the number of land marks, then we know we've seen all of them.

Lines 98-110 recursively call getPaths() using the next distance, and points that are higher then, equal to, and lower than the current point. The sum of all these paths becomes the number of paths from the current point to the finish. We'll store that value at line 110 so that it does not need to be calculated again.

With this setup, we can call getPaths() from the first point 0,0 and it will calculate all possible paths from the start to the finish that meet the constraints of the problem.

The inner class PathCache at line 120 stores the number of paths given the inputs. This technique is know as memoization and it comes in very handy in this case. By storing values that we've seen before, we can eliminate the need to calculate the same subtrees over and over again.

On line 129, a 4 dimensional array is created. This allows any possible combination of distance, height, number of land marks seen, and max height seen to be mapped to a long - which is the number of paths from that point. Initially these are all set to -1, so a value of 0 or more denotes a number that has already been calculated.

The distance and height dimensions are 1 unit larger than the need to be, bu t this prevents having to do some -1 calculations in other places. The size of the numLandMarks dimension must be one larger than the number of landmarks to protect against the case where the number of landmarks is zero. We always want at least one unit here. The final dimension maps to the boolean maxHeightReached. Here true gets location 1 and false is location 0.

If you're unconvinced about the need to store the previously calculated paths, please try this: Run test 4 from the topcoder arena with the code as is. For me, it took about 7ms to complete. Now comment out lines 66 and replace it with "return -1". This essentially forces every path to be calculated as if it weren't cached. My time is now... we'll it's been running for more than 10 minutes, so I'll let you know when it completes.

## Sunday, June 29, 2014

### Bonuses

Problem:
Overview:

Determine the amount of bonuses to award to each employee.

Java Source:
```    01: /*
02: TopCoder
03: Single Round Match: 145
04: Division: 1
05: Level: 1
06: Points: 250 Points
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1677&rd=4530
08:  */
09:
10: public class Bonuses {
11:
12:     public int[] getDivision(int[] points) {
13:
14:         // An array to store the bonus amounts.  This is the return value.
15:         int[] bonuses = new int[points.length];
16:
17:         // Used to keep track of employees that received the "extra" bonus.
18:         boolean[] extraBonus = new boolean[points.length];
19:
20:         // Calculate the total points that have been awarded.
21:         int totalPoints = 0;
22:         for (int point : points) {
23:             totalPoints += point;
24:         }
25:
26:         /*
27:         Assign each employee their bonus percentage based on their points
28:         and the total points.  Fractions will be rounded down.  Keeps
29:         track of the percentage remaining.
30:          */
31:         int bonusPctRemaining = 100;
32:         for (int i = 0; i < points.length; i++) {
33:             bonuses[i] = (points[i] * 100) / totalPoints;
34:             bonusPctRemaining -= bonuses[i];
35:         }
36:
37:         /*
38:         If there is any bonus percentage remaining, we'll assign 1% to each
39:         of the top scoring employees until it is used up.
40:          */
41:         while (bonusPctRemaining > 0) {
42:
43:             int maxPoints = -1;
44:             int employee = -1;
45:
46:             /*
47:             Find the employee with the highest points value that has
48:             not yet been awarded the extraBonus.
49:             Ties go to the employee positioned earlier in the points array.
50:              */
51:             for (int i = 0; i < points.length; i++) {
52:                 if ((!extraBonus[i]) && (points[i] > maxPoints)) {
53:                     employee = i;
54:                     maxPoints = points[i];
55:                 }
56:             }
57:
58:             /*
59:             We've found the next top employee, so set extraBonus to true,
60:             so they are not considered next time; add 1% to their bonus,
61:             and remove 1% from the amount remaining.
62:              */
63:             extraBonus[employee] = true;
64:             bonuses[employee] += 1;
65:             bonusPctRemaining -= 1;
66:         }
67:
68:         return bonuses;
69:     }
70: }
```
Notes:

Lines 21-24 simply counts up the total number of points that were assigned across all employees.

Line 33 then calculates the percentage for each employee. The "/" operator truncates any fractions. As each bonus is assigned, we subtract that amount from the bonus percentage remaining.

While there is any bonus percentage remaining, we'll assign 1% to the top scoring employee that has not already received this extra bonus.

This is implemented by creating an array of booleans (Line 15) that keeps track of each employee that has received this extra bonus. The loop at line 51 looks for the employee with the greatest score that has not been awarded the bonus. Ties will go to the employee appearing earlier in the points array, since line 52 requires that the current employee's points be greater than what has already been seen.

A more efficient way to do this might be to sort the employees by score, and award the extra bonus starting at the beginning of the list until the bonus runs out. However, we'd need to copy the points array to the new sorted array, and maintain a mapping between the tow. Furthermore, we'd need to use a stable sorting algorithm, that is, one that does not switch the positions of two employees if their score is the same. I'm not sure if the standard java sorting algorithms guarantee this or not - so we'd be looking at implementing our own sorting algorithm, which is not hard, but not necessary for this problem.

Update: Java's Collections.sort() is guaranteed to be stable.

### RectangularGrid

Problem:
Overview:

Count the number of non-square rectangles that are contained in a rectangular grid.

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 146
04: Division: 2
05: Level: 2
06: Points: 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1589
08:  */
09:
10: public class RectangularGrid {
11:
12:     /*
13:     Determines the number of s-sized Squares that can be found in a rectangle
14:      of dimensions width x height.
15:      */
16:     private static long findSquaresInRectangle(int s, int width, int height) {
17:
18:         long count = 0;
19:
20:         for (int x = 0; (x + s) <= width; x++) {
21:             for (int y = 0; (y + s) <= height; y++) {
22:                 count++;
23:             }
24:         }
25:
26:         return count;
27:     }
28:
29:     public long countRectangles(int width, int height) {
30:
31:         long widthL = (long) width;
32:         long heightL = (long) height;
33:
34:         /*
35:         The total number of rectangles, including squares,
36:         that can be found in a rectangular grid is given by the formula:
37:         (width^2 + width) * (length^2 + length) / 4
38:         See: http://www.gottfriedville.net/mathprob/comb-subrect.html
39:          */
40:         long totalWithSquares =
41:                 (((widthL * widthL) + widthL) *
42:                         ((heightL * heightL) + heightL)) / 4;
43:
44:         // Now, We subtract off the number of squares.
45:         long totalWithoutSquares = totalWithSquares;
46:
47:         /*
48:         Loop from size 1x1 up to the smaller of the two dimensions:
49:         height x height OR width x width.
50:         So, we'll subtract off squares of size 1x1, 2x2, 3x3, ...
51:          */
52:         for (int i = 1; i <= Math.min(width, height); i++) {
53:             totalWithoutSquares -=
54:                     findSquaresInRectangle(i, width, height);
55:         }
56:
58:     }
59: }
```
Notes:

This problem is solved in two steps. First, I calculate the total number of rectangles, including squares, that can be found in the rectangular grid. Then, I subtract off the number of squares.

The formula for the number of rectangles in the grid is given in the comment on line 37, and is calculated on lines 40-42. Be careful here as this number can exceed the maximum value that can be stored in an int. Lines 31 and 32 convert width and height to longs so these new variables can be used in the calculation - avoiding a lot of ugly casting.

The second step is to subtract off the number of squares. For this, we consider squares of size 1 x 1 up to N x N where N is the minimum of height and width. Lines 52-55.

The method findSquaresInRectangle() calculates the number of squares that can be found in a rectangular grid. There may be a formula for this, but it's pretty straight forward to figure it out.

Imagine a square of size s x s positioned in the top left corner of the rectangle. We then slide it right one space, and then again, until the right edge of the square falls outside the bounds of the rectangle. Line 20. Then move it down one row and repeat. Keep going until moving it down causes the bottom edge of the square to go outside the rectangle. Line 21.

## Thursday, June 26, 2014

### ExerciseMachine

Problem:
Overview:

Count the number of times a second aligns with a whole number percentage of the total workout time.

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 145
04: Division: 2
05: Level: 2
06: Points: 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1675
08:  */
09:
10: public class ExerciseMachine {
11:
12:     public static final int SECS_PER_MINUTE = 60;
13:     public static final int SECS_PER_HOUR = SECS_PER_MINUTE * 60;
14:
15:     public int getPercentages(String time) {
16:
17:         // Split the time on the ':' character, and get it's components.
18:         String[] timeArr = time.split(":");
19:         int hours = Integer.parseInt(timeArr);
20:         int minutes = Integer.parseInt(timeArr);
21:         int secs = Integer.parseInt(timeArr);
22:
23:         // Calculate the total number of seconds in the workout.
24:         int totalSeconds = (hours * SECS_PER_HOUR) +
25:                 (minutes * SECS_PER_MINUTE) + secs;
26:
27:         int counter = 0;
28:
29:         // For each second, determine if the counter will be displayed.
30:         for (int i = 1; i < totalSeconds; i++) {
31:             if (((i * 100) % totalSeconds) == 0) {
32:                 counter++;
33:             }
34:         }
35:
36:         return counter;
37:     }
38: }
```
Notes:

Lines 18-21 break apart the "time" String into it components. Line 15 then performs simple multiplication and addition to determine the total number of seconds in the workout.

With that, lines 30-34 count through each second and determine if falls on a whole number percentage of the total workout time.

### YahtzeeScore

Problem:
Overview:

Given a dice roll, determine which set of die values adds up to the greatest score.

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 146
04: Division: 2
05: Level: 1
06: Points: 250 Points
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1692
08:  */
09:
10: import java.util.*;
11:
12: public class YahtzeeScore {
13:
14:     public int maxPoints(int[] toss) {
15:
16:         // Holds die points, and the sum of those points.
17:         Map score = new HashMap();
18:
19:         // Loop through each toss.
20:         for (int i = 0; i < toss.length; i++) {
21:             int d = toss[i];
22:
23:             Integer s = score.get(d);
24:
25:             // Add or update total for that value.
26:             if (s == null) {
27:                 score.put(d, d);
28:             } else {
29:                 score.put(d, score.get(d) + d);
30:             }
31:         }
32:
33:         // Find the largest score.
34:         int maxScore = 0;
35:         for (Integer s : score.values()) {
36:             if (s > maxScore) {
37:                 maxScore = s;
38:             }
39:         }
40:
41:         return maxScore;
42:     }
43: }
```
Notes:

This solution utilizes a HashMap to store each die value along with the total off all dice of that value. So, if roll is 1,3,3,1,5 then the map will look like this:

 1 : 2 3 : 6 5 : 5

It then loops through all the values in the map (line 35) and returns the largest score.

### ImageDithering

Problem:
Overview:

Count the number of times any letter in "dithered" appear in "screen".

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 145
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1728
08:  */
09:
10: import java.util.HashSet;
11: import java.util.Set;
12:
13: public class ImageDithering {
14:
15:     public int count(String dithered, String[] screen) {
16:
17:         int count = 0;
18:
19:         char[] dColors = dithered.toCharArray();
20:         Set dSet = new HashSet<>();
21:
22:         for (char dColor : dColors) {
24:         }
25:
26:         for (String row : screen) {
27:             for (int i = 0; i < row.length(); i++) {
28:                 if (dSet.contains(row.charAt(i))) {
29:                     count++;
30:                 }
31:             }
32:         }
33:
34:         return count;
35:     }
36: }
```
Notes:

In lines 14-18, I create a Hash set to hold all of the characters in "dithered".

Then in lines 24-30, I loop through the rows and then columns in screen, checking to see if each character is in that set. If it is, increment count.

## Tuesday, June 24, 2014

### Lottery

Problem:
SRM 144 DIV 1 - 550 Points
Overview:
Calculate the number of possible outcomes for a number of lottery games. Each game is defined by the amount of possible numbers to choose from, the amount of numbers that must be chooses, whether those numbers must be unique, and whether those numbers must be in non-descending order.
Java Source:
```    001: /*
002: TopCoder
003: Single Round Match: 144
004: Division: 1
005: Level: 2
006: Points: 550
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1659
008:  */
009:
010: import java.util.ArrayList;
011: import java.util.Collections;
012: import java.util.List;
013:
014: public class Lottery {
015:
016:     /*
017:     Reads each String from rules, creates a new LotteryGame out of it,
018:     sorts the games, and returns the sorted list of names.
019:      */
020:     public String[] sortByOdds(String[] rules) {
021:
022:         List games = new ArrayList<>();
023:
024:         /*
025:         Read each of the input Strings, create a LotteryGame object out of
026:         them, and add them to the games array.
027:          */
028:         for (String s : rules) {
030:         }
031:
032:         Collections.sort(games);
033:
034:         /*
035:         Create the return array, copy the now sorted games into it, and return.
036:          */
037:         String[] names = new String[games.size()];
038:
039:         int i = 0;
040:         for (LotteryGame g : games) {
041:             names[i++] = g.getName();
042:         }
043:
044:         return names;
045:     }
046:
047:     /*
048:     Parses the input String and returns a new LotteryGame object.
049:      */
050:     private LotteryGame CreateGame(String s) {
051:
052:         // Split the string on the space char.
053:         String[] nameAndOptions = s.split(":");
054:
055:         String name = nameAndOptions;
056:
057:         String[] options = nameAndOptions.split(" ");
058:
059:         int choices = Integer.valueOf(options);
060:         int blanks = Integer.valueOf(options);
061:
062:         boolean sorted = "T".equals(options);
063:         boolean unique = "T".equals(options);
064:
065:         return new LotteryGame(name, choices, blanks, sorted, unique);
066:     }
067:
068:     /*
069:     An inner class that represents each type of game.
070:     It encapsulates the details of calculating the number of possible
071:     combinations, and implements Comparable to make the sorting easy.
072:      */
073:     class LotteryGame implements Comparable {
074:
075:         final String name;
076:
077:         final long combinations;
078:
079:         /*
080:         Calculates the number of combinations (permutations?) upon object
081:         creation.
082:          */
083:         LotteryGame(String name, int choices, int blanks, boolean sorted,
084:                     boolean unique) {
085:
086:             this.name = name;
087:
088:             /*
089:            There are four different ways to compute the number of
090:            combinations base on the values of unique and sorted.  The first
091:            three you should recognize from discrete math classes.  The last
092:            case (!unique && sorted) I don't fully understand.
093:             */
094:             if (unique && sorted) {
095:                 combinations = choose(choices, blanks);
096:             } else if (unique) {
097:                 combinations = choose(choices, blanks) * factorial(blanks);
098:             } else if (!sorted) {
099:                 combinations = power(choices, blanks);
100:             } else {
101:                 combinations = choose(choices + blanks - 1, blanks);
102:             }
103:         }
104:
105:         /*
106:         Implements (m choose n) = m! / ((m-n)! * n!)
107:          */
108:         long choose(int choices, int blanks) {
109:             return factorial(choices, blanks) / factorial(blanks);
110:         }
111:
112:         public long factorial(int n) {
113:             return factorial(n, n);
114:         }
115:
116:         /*
117:         Doing large factorials runs the risk of overflows.  This allows us to
118:          calculate, for example, 100! / 98! without having to multiply it all
119:           out.
120:          */
121:         long factorial(int n, int stopAfter) {
122:
123:             long result = (long) n;
124:
125:             for (long i = (n - 1); i > (n - stopAfter); i--) {
126:                 result *= i;
127:             }
128:
129:             return result;
130:         }
131:
132:         /*
133:         Does the same thing as Math.pow() but this uses longs instead of
134:         doubles.
135:          */
136:         long power(int base, int exp) {
137:
138:             if (exp == 0) { return 1L; }
139:
140:             // I don't ever expect this, but just in case.
141:             if (exp < 0) {
142:                 throw new IllegalArgumentException("" + exp);
143:             }
144:
145:             long result = base;
146:
147:             for (int i = 1; i < exp; i++) {
148:                 result *= (long) base;
149:             }
150:
151:             return result;
152:         }
153:
154:         long getCombinations() {
155:             return this.combinations;
156:         }
157:
158:         String getName() {
159:             return this.name;
160:         }
161:
162:         /*
163:         Sort based on the number of possible combinations.  The more possible
164:          combinations, the harder the game is to win.
165:          If two games have the same number of combinations,
166:          then sort based on their name.
167:          */
168:         public int compareTo(LotteryGame other) {
169:
170:             if (this.combinations < other.getCombinations()) {
171:                 return -1;
172:             } else if (this.combinations > other.getCombinations()) {
173:                 return 1;
174:             } else {
175:                 return this.name.compareTo(other.getName());
176:             }
177:         }
178:     }
179: }
```
Notes:
There's basically three parts to this problem:
1. Parsing each String into a lottery game.
2. Determining how many possible combinations* each game has.
3. Sorting and returning the results.
*I'll use "combinations" through the code and comments, even though "permutations" may be more appropriate in some cases.
By far the toughest part is determining the number of possible combinations there are given the various options. So, I put it off as long as I could.
The CreateGame() method on line 50 takes care of reading each String and creating a LotteryGame object out of it. There is nothing difficult here. One split of the String on the ':' character separates the name of the game from it's options. A second split, on the options half using the space character breaks out all the options. With that, I had everything I needed.
I chose to make the LotteryGame implement the Comparable interface so that I could use Collections.sort() (line 32) to put all the games in order. compareTo() (line 168) handles all the details of the sorting.
Now, there was nothing left to do but calculate the number of combinations.
The first three cases were pretty easy:
Let m = the number of numbers to choose from - choices, and n = the number of numbers that must be chosen - blanks.
• If the numbers are unique and sorted, then the possible combinations = m choose n.
• If the numbers do not need to be sorted, then we can multiple the (m choose n) by n!
• And easiest of all - if they are not unique, and not required to be sorted, then it's just m^n.
If any of these are difficult, then I recommend checking out the Probability and Combinatorics series on the Kahn Academy site.
I didn't get how to calculate the number of combinations for a sorted but not unique game (line 101) until I checked out the TopCoder forums. I still don't think I could explain it. choose(choices+ blanks - 1, blanks) works, so I'll leave it at that.
As a final note, lines 108-152 implement the choose, factorial, and power functions. Power is available in the Math package, but it takes and return doubles. Rather than deal with converting longs to doubles and back, it seemed easier to re-write it.
I don't know if choose and factorial are in any standard libraries. Also, I needed to customize the factorial function so in cases where large factorials were being divided by other large factorials (i.e. 100! / 98!), I could simplify that to just 100 * 99. Computing 100! would probably cause an overflow.
Thank you for taking the time to read this solution. I welcome any feedback you may have.
For this, and other TopCoder solutions, please visit www.topcodingsolutions.net.

### BridgeCrossing

Problem:
Overview:

Solve the problem where a number of people have to cross a rickety bridge in as little time as possible.

The following rules apply:

• At most, two people may be on the bridge at any given time.
• There is a single flashlight which must accompany any group crossing the bridge.
• Each person will have an amount of time that it takes them to cross the bridge. (i.e. person 1 = 1 minute, person 2 = 5 minutes, etc.)
• Any group (2 people) crossing together will take as much time as the slowest person in the group.
Java Source:
```001: /*
002: TopCoder
003: Single Round Match: 146
004: Division: 2
005: Level: 3
006: Points: 1000
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1599
008:  */
009:
010: import java.util.HashSet;
011: import java.util.Set;
012:
013: public class BridgeCrossing {
014:
015:     /*
016:     Use two hash sets to hold the people that are on
017:     the starting side (side1) and the finish (side2)
018:      */
019:     private final Set side1 = new HashSet();
020:
021:     private final Set side2 = new HashSet();
022:
023:     /*
024:     Move people from the "fromSide" set to the "toSide" set.
025:     numToSend - indicates the number of people moving across together.  It
026:     must be either 1 or 2.
027:     fastest - indicates whether we want the fastest people (true), or the
028:     slowest (false) to go across.
029:     Returns the amount of time it will take to move the people across.
030:      */
031:     private static int sendOver(int numToSend, boolean fastest,
032:                                 Set fromSide, Set toSide) {
033:
034:         int eTime = 0;
035:         int currentMax;
036:
037:         // Loop either 1 or 2 times, depending on the number being asked to
038:         // send.
039:         for (int n = 0; n < numToSend; n++) {
040:
041:             if (fastest) {
042:                 currentMax = Integer.MAX_VALUE;
043:             } else {
044:                 currentMax = 0;
045:             }
046:
047:             /*
048:             If we're looking for the fastest person (fastest = true),
049:             then look for values that are below currentMax.
050:             If we're looking for the slowest person (fastest = false),
051:             then look for values that are above currentMax.
052:              */
053:             for (int i : fromSide) {
054:                 if ((fastest && (i < currentMax)) ||
055:                         (!fastest && (i > currentMax))) {
056:                     currentMax = i;
057:                 }
058:             }
059:
060:             /*
061:             We've found either the fastest or slowest.  Remove them from the
062:             from side and add them to the to side.
063:             Set eTime to either eTime (if this is the first time through the
064:             loop) or the greater of eTime and currentMax if we've been
065:             through the loop before.  The effect is that eTime will contain the
066:             slower person's time.
067:              */
068:             fromSide.remove(currentMax);
070:             eTime = Math.max(eTime, currentMax);
071:         }
072:
073:         // Return the slower person's time.  (Just the time if numToSend = 1)
074:         return eTime;
075:     }
076:
077:     public int minTime(int[] times) {
078:
079:         int eTime = 0;  // Holds the elapsed time.  The return value.
080:
081:         // Put all the people onto the starting side
082:         for (int i = 0; i < times.length; i++) {
084:         }
085:
086:         /*
087:         Send the two fastest from side1 to side2.
088:         Check to make sure there are more than 1 people on side 1.
089:         If there is only one person on side1, then just send that one.
090:         */
091:         eTime += sendOver((side1.size() >= 2) ? 2 : 1, true, side1, side2);
092:
093:         // When side1 no longer has any people, we're done.
094:         while (side1.size() != 0) {
095:
096:             // Send the fastest person back from side2 to side1
097:             eTime += sendOver(1, true, side2, side1);
098:
099:             /*
100:             Send the two slowest people from side1 to side2.
101:             There must be at least two people, since we weren't done,
102:             and above we've just sent one more back.
103:              */
104:             eTime += sendOver(2, false, side1, side2);
105:
106:             // Check again to see if we're done.
107:             if (side1.size() == 0) {
108:                 return eTime;
109:             }
110:
111:             // Send the fastest person back from side2 to side1
112:             eTime += sendOver(1, true, side2, side1);
113:
114:             // Send the two fastest from side1 to side2.
115:             eTime += sendOver(2, true, side1, side2);
116:         }
117:
118:         return eTime;
119:     }
120: }
```
Notes:

In order to minimize the time it takes for everyone to cross, we'll want to use the following strategy:

• Group the slowest people together. If the slowest two people take 5 and 10 minutes respectively, then the trip will take 10 minutes, but there is no faster way to get the slowest person across. By sending the second slowest with the slowest, the second slowest person gets across "for free".
• Utilize the fastest person in situations where we're just bringing the flashlight back and forth.

The algorithm looks like this:

Repeat until side 1 is empty:

1. Send the two fastest people (person 1 and person 2) from side 1 to side 2.
2. Send the fastest (person 1) from side 2 back to side 1.
3. Send the two slowest people from side 1 to side 2.
4. Send the fastest person on side 2 (person 2) from side 2 back to side 1.

Once you have the algorithm, the main method is pretty straight forward. I created a method sendOver() to abstract the details of moving people from one side to another.

The sendOver() method takes as parameters the number of people to send (1 or 2), whether we want to send the fastest or slowest people (fastest = true|false), the source side, and the destination side.

Lines 41-45 and 53-58 are a little tricky. Basically, if we're sending the fastest people over, then I'll set currentMax to a high number, and then update it whenever I find something smaller. If I'm looking for slow people, then I set it to a low number, and update it whenever I find something larger. I could have picked a better name than currentMax, since often it will actually be a minimum.

Line 115 might also be confusing. We'll reach this line either once or twice depending on the value of numToSend. The first time, eTime will equal 0, so it will get set to currentMax, the time it took for the first person to cross the bridge. The second time, it will either keep it's value, or get set to the new person's time, depending on who is slower.

## Monday, June 23, 2014

### CCipher

Problem:
Overview:

A simple Caesar cipher.  Take the String given by 'cipherText' and shift each character over by the amount in 'shift'.

Java Source:
```01: /*
02: TopCoder
03: Single Round Match: 147
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1667
08:  */
09:
10: public class CCipher {
11:
12:     public String decode(String cipherText, int shift) {
13:
14:         char[] chArray = cipherText.toCharArray();
15:
16:         for (int i = 0; i < chArray.length; i++) {
17:
18:             int c = chArray[i] - shift;
19:
20:             // If before 'A' - wrap around to the end.
21:             if (c < 'A') {
22:                 c += 26;
23:             }
24:
25:             chArray[i] = (char) c;
26:         }
27:
28:         return new String(chArray);
29:     }
30: }```
Notes:

When working with the individual characters in a String, it’s usually easier to convert them to a character array (line 14).

You can use the + and - operators on characters.

Lines 21-23 handle the case where we wrap around the end of the alphabet.

## Saturday, June 21, 2014

### VendingMachine

Problem:
Overview:

Simulate a vending machine.

Java Source:
```001: /*
002: TopCoder
003: Single Round Match: 145
004: Division: 2
005: Level: 3
006: Points: 1100
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1130
008:  */
009:
010: public class VendingMachine {
011:
012:     // Number of minutes before the machine rotates to the most expensive
013:     // column.
014:     private static final int TIME_TO_RESET = 5;
015:
016:     // The number of moves that the machine has made
017:     private int moves = 0;
018:
019:     // The column currently facing forward.
020:     private int currentCol = 0;
021:
022:     private int numColumns;
023:
024:     private int numShelves;
025:
026:     // The vending machine is modeled as 2 dimensional array [shelves][columns]
027:     private int[][] machine;
028:
029:     private int timeOfLastPurchase = 0;
030:
031:     /*
032:     Simulate to use of the vending machines motor.
033:     Prices is an array of Strings, each String is a space separate list of
034:     integers.  Each array item represents a shelf, while each item in the
035:     String represents the price of an item at that column.purchases are in
036:     the format of shelf,column:time
037:      */
038:     public int motorUse(String[] prices, String[] purchases) {
039:
040:         // Determine the number of shelves and columns.
041:         numShelves = prices.length;
042:         numColumns = prices.split(" ").length;
043:
044:         machine = new int[numShelves][numColumns];
045:
046:         // Initialize the machine
047:         for (int shelf = 0; shelf < numShelves; shelf++) {
048:
049:             // split the String by spaces into an array of prices.
050:             String[] itemArray = prices[shelf].split(" ");
051:             for (int column = 0; column < numColumns; column++) {
052:                 machine[shelf][column] = Integer.parseInt(itemArray[column]);
053:             }
054:         }
055:
057:         rotateToMostExpensive();
058:
059:         /*
060:         We'll throw an exception if the user attempts to buy an item that has
062:         Catch the exception, and return -1.
063:          */
064:         try {
065:
066:             // Process each of the purchases.
067:             for (String p : purchases) {
068:                 processPurchase(p);
069:             }
070:
072:             rotateToMostExpensive();
073:         } catch (IllegalStateException e) {
074:             return -1;
075:         }
076:
077:         return moves;
078:     }
079:
080:     /*
081:     Calculates the most expensive column in the vending machine, and then
082:     rotates to that column.
083:      */
084:     private void rotateToMostExpensive() {
085:         int col = getMostExpensiveCol();
086:         rotateTo(col);
087:     }
088:
089:     /*
090:     Calculates the most expensive column in the vending machine.
091:      */
092:     private int getMostExpensiveCol() {
093:
094:         // The value of the most expensive column we've seen so far.
095:         int mostExpensiveColVal = 0;
096:
097:         // The index of the most expensive column seen so far.
098:         int mostExpensiveColNum = 0;
099:
100:         for (int column = 0; column < numColumns; column++) {
101:
102:             int valOfColumn = 0;
103:             for (int shelf = 0; shelf < numShelves; shelf++) {
104:                 valOfColumn += machine[shelf][column];
105:             }
106:             if (valOfColumn > mostExpensiveColVal) {
107:                 mostExpensiveColNum = column;
108:                 mostExpensiveColVal = valOfColumn;
109:             }
110:         }
111:
112:         return mostExpensiveColNum;
113:     }
114:
115:     /*
116:     Rotates the vending machine to the given column.
117:     Increments the number of motor moves required to get there.
118:     The move may be either clock-wise or counter-clockwise.
119:      */
120:     private void rotateTo(int dest) {
121:
122:         /*
123:         Determine how many moves it will take if we rotate left,
124:         then how many moves it will take to rotate right.
125:          */
126:         int rotL = Math.abs(dest - currentCol);
127:         int rotR = numColumns - rotL;
128:
129:         // Increase the number of moves the motor makes by the smaller of the
130:         // two.
131:         moves += (rotL < rotR) ? rotL : rotR;
132:
133:         // Set the current column to the destination.
134:         currentCol = dest;
135:     }
136:
137:     private void processPurchase(String purchase) {
138:
139:         /*
140:         Parse the purchase string by breaking it into its shelf, column,
141:         and time components.
142:          */
143:         String[] purchaseArr = purchase.split("(,)|(:)");  // A handy regex.
144:         int shelf = Integer.parseInt(purchaseArr);
145:         int column = Integer.parseInt(purchaseArr);
146:         int time = Integer.parseInt(purchaseArr);
147:
148:         // If more than 5 minutes have elapses, rotate to the most expensive
149:         // column first.
150:         if ((time - timeOfLastPurchase) >= TIME_TO_RESET) {
151:             rotateToMostExpensive();
152:         }
153:
154:         // Rotate to the purchase column.
155:         rotateTo(column);
156:
157:         // Probably not the right type of exception to throw, but it'll work.
158:         if (machine[shelf][column] == 0) {
159:             throw new IllegalStateException("Item Already Purchased! Shelf="
160:                     + shelf + " Column=" + column);
161:         }
162:
163:         // Mark the slot as gone.
164:         machine[shelf][column] = 0;
165:
166:         // Update the time of last purchase.
167:         timeOfLastPurchase = time;
168:     }
169: }
```
Notes:

For an 1100 point problem, this one was actually pretty straight forward. It does not require the use of any complicated algorithms or data structures. There's really only two places where you might get tripped up.

The first is the rotateTo() method on line 120. Be careful and make sure that your are always rotating the shortest distance, whether that be to the right, or to the left. One lines 126 and 127, I calculate both rotL and rotR (rotL = rotate Left, rotR = rotate Right). rotL is the absolute value of the difference between the destination column and the current column.

We then use the value of rotL to calculate rotR. The two must add up to the total number of columns in the machine, so rotR = numColumns - rotL.

Looking back, I guess right and left don't really matter. Think of it as rotate one direction, and rotate the opposite direction.

Getting this part right is half the battle. It's worth it to write some unit tests and write it out on paper to ensure that it's giving you the correct values.

The second part that may prove difficult is in parsing the purchases String. Here knowing how to use regular expressions can be very handy. The purchase Sting has the format "<shelf>,<column>:<time>". Line 143 splits the String on either a ',' or a ':' character.

### Time

Problem:
Overview:

Given the number of seconds since midnight, return a formatted String giving the number of hours, minutes, and seconds that have elapsed.

Java Source:
```01: public class Time {
02:
03:     public static final int SECONDS_PER_MINUTE = 60;
04:     public static final int SECONDS_PER_HOUR = SECONDS_PER_MINUTE * 60;
05:
06:     public String whatTime(int seconds) {
07:
08:         /*
09:         Get the whole number of hours that fits into seconds.
10:         Store that as h and then subtract the hours portion
11:          off of seconds.
12:          */
13:         int h = seconds / SECONDS_PER_HOUR;
14:         seconds -= (h * SECONDS_PER_HOUR);
15:
16:         // Repeat to get the number of minutes.
17:         int m = seconds / SECONDS_PER_MINUTE;
18:         seconds -= (m * SECONDS_PER_MINUTE);
19:
20:         // What's left over is the number of seconds.
21:         int s = seconds;
22:
23:         // Create the return String in the appropriate format.
24:         return new String(h + ":" + m + ":" + s);
25:     }
26: }```
Notes:

Remember that when dividing ints in Java, the / operator returns the whole number of times that the denominator fits into the numerator. So 10 / 3 = 3.

On line 13, we use this to get the number of hours in the input parameter. The result is multiplied by the number of seconds in an hour, and then subtracted from seconds (line 14).

At that point, the number of seconds left must be less than 1 hour. On line 17 and 17, we repeat the process to get the minute portion. Whatever is left over is the number of seconds.

### BinaryCode

Problem:
Overview:

You are asked to decode a string. The original String is in binary format. The encoded string is formed by adding both neighboring digits to the current digit.

Java Source:
```01: public class BinaryCode {
02:
03:     /*
04:     Decodes the string. The string is encoded by adding it's two neighbors to
05:     it's values. So: 1001001 becomes 1111111
06:     In some cases the message may decode to two different values depending on
07:     if pos1 = 0 or 1.
08:     In other cases a value of 0 or 1 may lead to a message that cannot be
09:     decoded.
10:     i.e. would require a a digit other than 0 or 1 to make the sums add up.
11:      */
12:     private static String decode(char[] message, char pos1) {
13:
14:         /*
15:         Create a return array that is 1 element larger than the message. This
16:         extra space will make it easier to compute the last element, and will
17:         ultimately get chopped off before returning anyway.
18:          */
19:         char[] ret = new char[message.length + 1];
20:
21:         // Set the first position to either a 0 or 1 depending on the parameter.
22:         ret = pos1;
23:
24:         // Loop through the return array starting at position 1.
25:         for (int i = 1; i < ret.length; i++) {
26:             Integer a = Integer.parseInt("" + message[i - 1]);
27:             Integer b = Integer.parseInt("" + ret[i - 1]);
28:
29:             // This protects from going in front of the beginning of the array.
30:             Integer c = (i == 1) ? 0 : Integer.parseInt("" + ret[i - 2]);
31:
32:             /*
33:             The current value in the return array will equal:
34:             (one position back in the message) - (one position back in the
35:             return array) - (2 positions back in the return array)
36:             Write this out on papers until you're convinced that it works.
37:              */
38:             int val = a - b - c;
39:
40:             /*
41:             If we arrive at a non-binary digit, then the encoding was
42:             impossible given the value of pos1.
43:               */
44:             if ((val > 1) || (val < 0)) {
45:                 return "NONE";
46:             }
47:
48:             // Convert the number to a character.
49:             ret[i] = (char) (val + '0');
50:         }
51:
52:         // Convert the array to a String, and chop off the last place.
53:         return new String(ret).substring(0, ret.length - 1);
54:     }
55:
56:     public String[] decode(String message) {
57:
58:         // Create an array of Strings to return.
59:         String[] ret = new String;
60:
61:         /*
62:         Populate the return array with the results of decoding.
63:         First when we assume that the first digit was a 0.
64:         Then when we assume the first digit was a 1.
65:          */
66:         ret = decode(message.toCharArray(), '0');
67:         ret = decode(message.toCharArray(), '1');
68:
69:         return ret;
70:     }
71: }```
Notes:

The toughest part of this problem is determining how to calculate the value at the current location of the return String - Line 38. I suggest you write this out on paper to see how it works. For example:

 message: 1 2 3 2 return: 0 1 1 ?

The value of the ? will be one space back in the message array (3) - one space back in the return array (1) - two spaces back in the return array (1). 3 - 1 - 1 = 1. These values are calculated on lines 50, 51, and 54.

If you insert 1 for the ?, you'll see that the encoding/decoding of the message is correct up to that point.

The next position in the return array must be 0, since the 2 is already the total the 1 (at the ? location) and 1 (one space before the ?).

Thank you for taking the time to read this solution. I welcome any feedback you may have.