Friday, August 29, 2014

StripePainter

Problem:

TopCoder Problem Statement - StripePainter

Overview:

Calculate the minimum number of brush strokes needed to create a given pattern.

Java Source:
01: public class StripePainter {
02: 
03:     private static final char BLANK_COLOR = 'A' - 1;
04:     private static final int MAX_COLORS = 27;  // A-Z plus one for blank
05: 
06:     /*
07:     * Holds all the combinations of starting position, string size, and color
08:     * that we've encountered before.  If they come up again, we can return
09:     * the stored value and avoid re-calculating.
10:     */
11:     int[][][] alreadySeen;
12: 
13:     public int minStrokes(String stripes) {
14: 
15:         int length = stripes.length();
16: 
17:         /*
18:         * Initialize the alreadySeen array.  The Java spec guarantees all
19:         * values will be set to zero.  No need to do it explicitly.
20:         */
21:         alreadySeen = new int[length][length + 1][MAX_COLORS];
22: 
23:         /*
24:         * Calculate calculateMinStrokes on the entire stripes String, starting
25:         * with a blank canvas.
26:         */
27:         return calculateMinStrokes(stripes, 0, length, BLANK_COLOR);
28:     }
29: 
30:     private int calculateMinStrokes(String stripes, int start, int size,
31:                                     char color) {
32: 
33:         // Breaks the recursive calls.
34:         if (size == 0) return 0;
35: 
36:         /*
37:         * If the left-most color matches the given color, then just move
38:         * on to the next stripe.
39:         */
40:         if (stripes.charAt(start) == color) {
41:             return calculateMinStrokes(stripes, start + 1, size - 1, color);
42:         }
43: 
44:         /*
45:         * If we've already calculated this combination of starting position,
46:         * string length, and colore; then just return that value.
47:         */
48:         if (alreadySeen[start][size][color - BLANK_COLOR] > 0) {
49:             return alreadySeen[start][size][color - BLANK_COLOR];
50:         }
51: 
52:         int min = Integer.MAX_VALUE;
53: 
54:         /*
55:         * Calculates the minimum number of strokes for all possible
56:         * combinations of sub-strings to the right of the current position.
57:         * In the first pass, the first call to calculateMinStrokes will be
58:         * empty, and the entire remainder of the string will be used in the
59:         * second call to calculateMinStrokes.  In each subsequent pass, a
60:         * character is added to the first call, and removed from the second
61:         * call.
62:         */
63:         for (int i = 1; i <= size; i++) {
64:             min = Math.min(min, 1 +
65:                     calculateMinStrokes(stripes, start + 1, i - 1, stripes.charAt(start)) +
66:                     calculateMinStrokes(stripes, start + i, size - i, color));
67:         }
68: 
69:         // Store the calculate value to avoid having to calculate it again.
70:         alreadySeen[start][size][color - BLANK_COLOR] = min;
71: 
72:         return min;
73: 
74:     }
75: }
Notes:

For any given pattern X (where X represents any number of stripes) a new pattern xX (where x is one additional stripe to the left side of X) can be created with just 1 more stroke than the number of strokes neeeded to create X. We'll use this as an upper-bound. So if the pattern X takes 10 strokes, then xX will take at most 11 - possibly less.

The strategy then is to skip the left-most stripe and solve for everything to the right of it. Then determine if the left-most stripe can be added with 0 or 1 additional strokes. For example: GR takes 2 stroke, but R GR also only needs 2 because the left-most and right-most stripes are the same color (You'd paint R first, and then put a G in the middle of it). If the ends weren't the same color, as in B GR, then a third stripe would be needed.

The loop at lines 63-67 divides the substring to the right of the current position into 2 segments. It then tries every possible combination of these segment's lengths. So, if the part to the right was 4 characters long, the first segment would be called with lengths 0, 1, 2, 3, and 4 - while the second segement would have lenghts of 4, 3, 2, 1, and 0. This ensures that each way of dividing up the part to the right is tried.

The solution also uses the notion of memoization. This has been discussed in earlier posts (see HillHike). The idea is that once a particular pattern has been calculated, we'll store it so it never needs to be calculated again. Line 70 stores each combination of start position, string length, and color that gets calculated. Then at line 48, we check to see if the combination has been calculated before. For some tests, it's not possible to finished within the time limit without this technique.

Wednesday, August 27, 2014

HourGlass

Problem:

TopCoder Problem Statement - HourGlass

Overview:

Determine the time intervals that can be measured using two hourglasses.

Java Source:
001: import java.util.Collections;
002: import java.util.PriorityQueue;
003: 
004: /*
005: * An immutable class to represent an hour class.
006: */
007: class GlassTimer {
008: 
009:     private final int topBulb;
010:     private final int bottomBulb;
011: 
012:     GlassTimer(int top, int bottom) {
013:         this.topBulb = top;
014:         this.bottomBulb = bottom;
015:     }
016: 
017:     // Returns a new copy of this oject
018:     GlassTimer copy() {
019:         return new GlassTimer(this.topBulb, this.bottomBulb);
020:     }
021: 
022:     // Returns a new inverted copy of the timer.
023:     public GlassTimer flip() {
024:         return new GlassTimer(this.bottomBulb, this.topBulb);
025:     }
026: 
027:     // Returns how much sand is in the topBulb.
028:     public int getTimeRemaining() {
029:         return this.topBulb;
030:     }
031: 
032:     /*
033:     * Runs i amount of time out of the top bulb, and adds it to the bottom.
034:     * If i > topBulb, we'll stop when the top runs out.
035:     */
036:     public GlassTimer runFor(int i) {
037: 
038:         if (i > topBulb) {
039:             i = topBulb;
040:         }
041: 
042:         return new GlassTimer(topBulb - i, bottomBulb + i);
043:     }
044: }
045: 
046: public class HourGlass {
047: 
048:     // The number of items we'll return in the result.
049:     public static final int NUM_TIMES_TO_RETURN = 10;
050: 
051:     /*
052:     * A PriorityQueue to store the times we've calculated so far.  By passing
053:     * Collections.reverseOrder, the PriorityQueue will always have the largest
054:     * element in the first position.
055:     */
056:     PriorityQueue maxPQ =
057:             new PriorityQueue(NUM_TIMES_TO_RETURN,
058:                     Collections.reverseOrder());
059: 
060:     // The method called by the TopCoder tests.
061:     public int[] measurable(int glass1, int glass2) {
062: 
063:         flipHourGlasses(new GlassTimer(glass1, 0), new GlassTimer(glass2, 0), 0);
064: 
065:         /*
066:         * Upon returning from flipHourGlasses, maxPQ will contain the
067:         * NUM_TIMES_TO_RETURN smallest times. Create a new array to hold the
068:         * return array, and fill it in starting from the back, by pulling the
069:         * next largest item off the PriorityQueue
070:         */
071:         int[] returnArray = new int[NUM_TIMES_TO_RETURN];
072: 
073:         int i = NUM_TIMES_TO_RETURN - 1;
074:         while (i >= 0) {
075:             returnArray[i--] = maxPQ.poll();
076:         }
077: 
078:         return returnArray;
079: 
080:     }
081: 
082:     /*
083:     * Each time this method is called, one or both hour glasses will have just
084:     * emptied.  At that point, there are four things we can do:
085:     * 1. Nothing - let the seocnd glass run out.
086:     * 2. Flip Glass 1
087:     * 3. Flip Glass 2
088:     * 4. Flip Both glasses.
089:     * This method makes recursive calls trying each of these possiblities.
090:     * With each call, the amount of time until the next hour glass runs out
091:     * is calculated and added to elapsedTime
092:     */
093:     private void flipHourGlasses(GlassTimer g1, GlassTimer g2, int elapsedTime) {
094: 
095:         /*
096:         * If we've already stored our 10 numbers, and now the elapsedTime is
097:         * more than the largest time we've seen, just return.
098:         * maxPQ.peek() will give us the largest time stored in maxPQ.
099:         */
100:         if ((maxPQ.size() == NUM_TIMES_TO_RETURN) &&
101:                 (elapsedTime >= maxPQ.peek())) {
102:             return;
103:         }
104: 
105:         /*
106:         * If maxPQ doesn't already contain the current elapsed time, And
107:         * Either maxPQ hasn've filled up yet or our current time is smaller
108:         * than the largest in maxPQ, store our current time.
109:         */
110:         if ((elapsedTime > 0) &&
111:                 (!maxPQ.contains(elapsedTime)) &&
112:                 ((maxPQ.size() < NUM_TIMES_TO_RETURN) ||
113:                         (elapsedTime < maxPQ.peek()))) {
114: 
115:             // If maxPQ is full, remove that largest to avoid holding > 10.
116:             if (maxPQ.size() == NUM_TIMES_TO_RETURN) {
117:                 maxPQ.remove();
118:             }
119: 
120:             /*
121:             * Store the current time.  PriorityQueues use Poll() and Offer() in
122:             * place of Pop() and Push()
123:             */
124:             maxPQ.offer(elapsedTime);
125:         }
126: 
127:         GlassTimer g1a;
128:         GlassTimer g2a;
129:         int runTime;
130: 
131:         // Flip neither
132:         g1a = g1.copy();
133:         g2a = g2.copy();
134:         runTime = getNextPause(g1a, g2a);
135: 
136:         /*
137:         * Do not make calls where the runTime is not advanced.  This will
138:         * result in infinite loops.
139:         */
140:         if (runTime != 0) {
141:             flipHourGlasses(g1a.runFor(runTime), g2a.runFor(runTime),
142:                     elapsedTime + runTime);
143:         }
144: 
145:         // Flip glass 1
146:         g1a = g1.flip();
147:         g2a = g2.copy();
148:         runTime = getNextPause(g1a, g2a);
149: 
150:         if (runTime != 0) {
151:             flipHourGlasses(g1a.runFor(runTime), g2a.runFor(runTime),
152:                     elapsedTime + runTime);
153:         }
154: 
155:         // Flip glass 2
156:         g1a = g1.copy();
157:         g2a = g2.flip();
158:         runTime = getNextPause(g1a, g2a);
159: 
160:         if (runTime != 0) {
161:             flipHourGlasses(g1a.runFor(runTime), g2a.runFor(runTime),
162:                     elapsedTime + runTime);
163:         }
164: 
165:         // Flip both
166:         g1a = g1.flip();
167:         g2a = g2.flip();
168:         runTime = getNextPause(g1a, g2a);
169: 
170:         if (runTime != 0) {
171:             flipHourGlasses(g1a.runFor(runTime), g2a.runFor(runTime),
172:                     elapsedTime + runTime);
173:         }
174: 
175:     }
176: 
177:     /*
178:     * Determines when the next timer will run out.  In general, this will be
179:     * the smaller time remaining, but we want to avoid returning 0 if possible.
180:     */
181:     private static int getNextPause(GlassTimer a, GlassTimer b) {
182: 
183:         int a1 = a.getTimeRemaining();
184:         int b1 = b.getTimeRemaining();
185: 
186:         if ((a1 == 0) && (b1 == 0)) {
187:             return 0;
188:         }
189: 
190:         if (a1 == 0) {
191:             return b1;
192:         }
193: 
194:         if (b1 == 0) {
195:             return a1;
196:         }
197: 
198:         return Math.min(a1, b1);
199:         
200:     }
201: }
Notes:

The first thing to note is that we can only take an action when one (or both) of the hourglasses has emptied. These types of problems do not allow for the possibility of stopping a hourglass at the 1/2 way point, or any other intermediate position. I'll call the time at which an hourglass empties a "Pause". At these moments, one of four actions can occur.:

  1. Nothing. We don't flip either hourglass. Instead, just continue until the second one runs out too.
  2. Flip Hourglass #1
  3. Flip Hourglass #2
  4. Flip Both #1 and #2

Whenever a Pause is reached, we'll recursively call flipHourGlass() for each of these four possibilities. In each case, the time to the next Pause is calculated and added to the total elapsed time. Lines 131 - 173.

The next Pause is calculated by the getNextPause() method which examines the amount of time remaining in each hourglass. The Pause will occur when the smaller of the two runs out - unless the smaller is already at zero. Care needs to be taken here to ensure that we don't enter an infinite loop by choosing to pause at the same state over and over again.

The times that can be calculated are stored in a max PriorityQueue. Normally this structure ensure that the smallest element is always the next to be popped off. But, by passing Collections.reverseOrdeer() to the constructor, Lines 56-58, we end up with the largest element at the top. So long as the PriorityQueue maxPQ has fewer than 10 elements, we'll add the elapsedTime at every Pause. Once it holds 10 elements, then we'll compare the current elapsed time to maxPQ's largest element, and if the current time is smaller, then we'll replace the largest with the current time. In this way, we are assured that the smallest 10 numbers are stored.

Also, the PriorityQueue provides a convienient way of breaking the recursive calls to flipHourGlass(). Once the elapsedTime is greater than the largest element stored in maxPQ, there is no sense in continuing. We can return at that point. Line 101.

Finally, I've created a class to represent the hourglasses - GlassTimer. This object is immutable. Once created, it's properties cannot be changed. Calls to update the ojbect, like flip() and runFor() return new instances of GlassTimer. This is very useful, and protects against your local variables from being modified - especially when using recursion.

Putting it all together, the program enters by calling measurable() at line 61. flipHourGlasses is called with two new GlassTimers, both filled at the top, and an initial elapsedTime of 0. Once that returns, we'll have a priority quest holding the 10 smallest times. We pop (poll) the largest number off one at a time, and use it to fill in the return array working from back to front.

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

Salary

Problem:
TopCoder Problem Statement - Salary
Overview:

Determine an employee's compensation for the day. Rates vary for evening and night shifts.

Java Source:
01: public class Salary {
02: 
03:     private static String DAY_START = "06:00:00";
04:     private static String DAY_END = "17:59:59";
05: 
06:     /*
07:     * Converts the current time to the number of seconds since midnight
08:     */
09:     private static long convertTimeToSeconds(String time)  {
10: 
11:         String[] timeArray = time.split(":");
12:         int hours = Integer.parseInt(timeArray[0]);
13:         int minutes = Integer.parseInt(timeArray[1]);
14:         int seconds = Integer.parseInt(timeArray[2]);
15: 
16:         return (hours * 3600) + (minutes * 60) + seconds;
17:     }
18: 
19:     public int howMuch(String[] arrival, String[] departure, int wage) {
20: 
21:         /*
22:         * The number of seconds worked, modified for evening and night time.
23:         * To avoid using decimals (float or long), we'll count each day
24:         * shift second as 2, and each evening/night shift second as 3.
25:         * Then, at the very end, divide the total by 2.
26:         */
27:         long effectiveSecondsWorked = 0;
28: 
29:         // Markers for the start and end of the day shifts.
30:         long dayStart = convertTimeToSeconds(DAY_START);
31:         long dayEnd = convertTimeToSeconds(DAY_END);
32: 
33: 
34:         for (int i = 0; i < arrival.length; i++) {
35: 
36:             long shiftStart = convertTimeToSeconds(arrival[i]);
37:             long shiftEnd = convertTimeToSeconds(departure[i]);
38: 
39:             // Loop through each secod of the shift.
40:             for (long j = shiftStart; j < shiftEnd; j++)  {
41: 
42:                 /*
43:                 * If the current second is part of the day shift, increment the
44:                 * count by 2.
45:                 */
46:                 if ((j >= dayStart) && (j <= dayEnd))  {
47:                     effectiveSecondsWorked += 2;
48: 
49:                 /*
50:                 * If it's part of an evening or night shift, increment the count
51:                 * by 3.
52:                 */
53:                 } else  {
54:                     effectiveSecondsWorked += 3;
55:                 }
56:             }
57:         }
58: 
59:         /*
60:         * Multiply the wage by the number of hours worked.  Note that there are
61:         * 60 * 60 = 3600 seconds in an hour, but since we doubled that when
62:         * counting the seconds, we need to divide by 2 * 3600 = 7200
63:         */
64:         return (int) ((effectiveSecondsWorked * wage) / 7200);
65:     }
66: }
Notes:

The first thing to note is that you want to avoid using decimals. If you introduce doubles, you'll waste a ton of time tracking down off-by-one errors. To get around this, we simply double each second as we count it: A day shift second counts as 2; and an evening or night shift second will count as 3. Then, when the result is calculated, the number of seconds in an hour is also doubled to compensate.

The approach taken is to examine each second of the shift, and determine if it falls during the day shift hours or evening/night. The method convertTimeToSeconds() will give the number of seconds since the start of the day. We use that to set two markers; the start of the day shift and the end of the day shift. Then we loop through each of the shifts, and each second of each shift and compare that seconds agains the markers. The counter effectiveSecondsWorked is the incremented by either 2 or 3.

Once the effective total number of seconds is know, we multiple that by the wage, and divide by ther number of seconds in an hour times 2.

An alternative approach would be to determine the number of seconds in a shift by subtracting the start time from the end time. If a shift spans a night/day or day/evening boundary, then it would need to be broken into two (or more) segments. I had a solution using this approach about 99% done, but found a few tests that were off by 1 or 2. Frustrated, I re-wrote the solution using the current approach.

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

GuessTheNumber

Problem:
TopCoder Problem Statement - GuessTheNumber
Overview:

Determine the number of guesses it will take to arrive at the answer in the I'm Thinking of a Number game.

Java Source:
01: import java.lang.Integer;
02: 
03: public class GuessTheNumber {
04:  
05:  public int noGuesses(int upper, int answer) {
06: 
07:         int lower = 1;
08:         int numGuesses = 0;
09:         int guess = 0;
10: 
11:         while (guess != answer) {
12: 
13:             numGuesses++;
14: 
15:             // guess = (upper + lower) / 2;  // Don't do This!!!
16:             guess = ((upper - lower) / 2) + lower;
17:             // System.out.println(guess);
18: 
19:             if (guess < answer) {
20:                 lower = guess + 1;
21: 
22:             } else if (guess > answer) {
23:                 upper = guess - 1;
24:             }
25: 
26:         }
27: 
28:         return numGuesses;
29:  }
30: 
31:     public static void main(String[] args) {
32:         int upper = Integer.MAX_VALUE - 1;
33:         int answer = Integer.MAX_VALUE - 2;
34: 
35:         System.out.println(new GuessTheNumber().noGuesses(upper, answer));
36:     }
37: }
Notes:

One of the first programs you'll write (after hello world! of course) is the number guessing game. We enter a while loop until the guess matches the answer. After each guess, we evaluate if that guess was too high, too low or correct. If the guess is incorrect, we can eliminate anything to the wrong side of our guess. The guess should be as close to the middle as possible, so that we can narrow our search down quickly. The code for this is pretty simple, and should be familiar to anyone that has written any code. The only real difference here is that the computer is playing against itself, and we're just couting the number of guesses.

One bit of advice though. On line 16, the next guess is calculated. This should be the mid-point of upper and lower. Avoid calculating this as shown on line 15. It won't matter for this problem, since upper won't be any higher than 1000; but if upper could be very large (close to Integer.MAX_VALUE) then upper + lower could cause an overflow. The safer way is shown on line 16. This is a bug that famously laid unnoticed for decades in many sorting and search algorightms. See Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken if you're intereseted.

Try swapping the comments on lines 15 16, and 17; then running the main method to see the results.

Sunday, August 17, 2014

Inventory

Problem:

TopCoder Problem Statement - Inventory

Overview:

Determine the number of items a business can expect to sell per month based on past averages.

Java Source:
01: public class Inventory {
02: 
03:     private static final double DAYS_IN_MONTH = 30.0;
04: 
05:     /*
06:     Calculates the average sales for the month. For months that sold out in
07:     less than 30 days, assume the same rate for the remainder of the month.
08:      */
09:     private static double calcAverage(int sales, int days) {
10:         return ((double) sales) / ((double) days / DAYS_IN_MONTH);
11:     }
12: 
13:     public int monthlyOrder(int[] sales, int[] daysAvailable) {
14: 
15:         /*
16:         Keep a running total of the sum of monthly sales,
17:         and the number of months.  We'll divides these to get the average.
18:          */
19:         double sumOfMonthlySales = 0.0;
20:         int numMonths = 0;
21: 
22:         for (int i = 0; i < sales.length; i++) {
23: 
24:             // If items were available for 0 days, do not count the month.
25:             if (daysAvailable[i] == 0) { continue; }
26: 
27:             // Add current months sales to the running total.
28:             sumOfMonthlySales += calcAverage(sales[i], daysAvailable[i]);
29:             numMonths++;
30:         }
31: 
32:         double average = sumOfMonthlySales / (double) numMonths;
33: 
34:         /*
35:         Adjusts for the imprecision of Doubles.  See the Notes in the problem
36:          statement.
37:          */
38:         average -= Double.parseDouble("1e-9");
39: 
40:         // Round up using the ceiling method.
41:         return (int) Math.ceil(average);
42:     }
43: }
Notes:

Our task is to determine the expected number of sales per month given past peformance. There are some months where the items was not in stock at all. We do not count these months in our calculations. In other months, the item may have sold out before the end of the month. In this case, we need to project out what the sales would have been had enough inventory been available.

The solution works by counting up the actual or projected sales of each month. Then it determines the average by dividing that sum by the number of months where the item was available.

numMonths is a counter that keeps track of the number of months where the item is available. If the item was not available at all during that month, line 33 will skip to the next month, and numMonths will not be incremented.

The calcAverage() method calculates the actual or projected number of sales for any month. By dividing the number of days the item was available by the number of days in a month, we get the fraction of the month that the item was availble. If it was available for all 30 days, this fraction will be 1. Then the number of sales is divided by this fraction to get the projected sales for the entire month. So, if the item was available for 1/2 the month, this equation would return twice the number of sales.

Lines 40-49 calculate the average and return it. Note that there is a "fudge factor" that is referenced in the problem statement. Without this correction on line 46, some tests will not pass.

Saturday, August 16, 2014

PickTeam

Problem:

TopCoder Problem Statement - PickTeam

Overview:

Choose the most effective team based on how well individuals work together.

Java Source:
001: /*
002:  * TopCoder Single Round Match: 153
003:  * Division: 2
004:  * Level: 3
005:  * Points: 1000
006:  * Problem Statement: http://community.topcoder.com/stat?c=problem_statement&pm=1773
007:  */
008: 
009: import java.util.*;
010: 
011: public class PickTeam {
012: 
013:     /*
014:      * This method converts the String[] people in a List of Perosn objects
015:      */
016:     private static List getAllPeople(String[] people) {
017: 
018:         List l = new ArrayList<>();
019: 
020:         for (int i = 0; i < people.length; i++) {
021:             Person p = new Person(i, people[i].split(" "));
022:             l.add(p);
023:         }
024: 
025:         return l;
026: 
027:     }
028: 
029:     /*
030:      * Returns a set of all possible teams given the list of people and the
031:      * desired team size.
032:      */
033:     private static Set getAllTeams(List allPeople,
034:                                          int size) {
035: 
036:         // This is the set we'll return.
037:         Set teams = new HashSet<>();
038: 
039:         /*
040:          * Check that we have people to work with, and that the desired team
041:          * size is not more than the number of people available.
042:          */
043:         if ((allPeople == null) || (allPeople.size() == 0) ||
044:                 (size > allPeople.size())) {
045:             return teams;
046:         }
047: 
048:         /*
049:          * If the desired team size is 1.  Then everyone get their own team.
050:          */
051:         if (size == 1) {
052:             for (Person p : allPeople) {
053:                 Team t = new Team();
054:                 t.addTeamMember(p);
055:                 teams.add(t);
056:             }
057:             return teams;
058:         }
059: 
060:         // Copies the list of allPeople
061:         List currentPeople = new ArrayList<>();
062:         currentPeople.addAll(allPeople);
063: 
064:         /*
065:          * For each person, we'll call getAllTeams() will all of the remaining
066:          * people
067:          */
068:         for (int i=0; i allPeople = getAllPeople(people);
069: 
070:         // Get a set of all possible teams
071:         Set allTeams = getAllTeams(allPeople, teamSize);
072: 
073:         int maxScore = Integer.MIN_VALUE;
074:         Team bestTeam = null;
075: 
076:         // Find the team with the greatest score.
077:         for (Team team : allTeams) {
078:             int score = team.getScore();
079:             if (score > maxScore) {
080:                 maxScore = score;
081:                 bestTeam = team;
082:             }
083:         }
084: 
085:         return bestTeam.getNames();
086:     }
087: }
088: 
089: /*
090:  * The Team class holds a set of Person which represents the people on the
091:  * team.  Also provide methods for calculating the score, and displaying
092:  * the team members in the format expected by the tests.
093:  */
094: class Team {
095: 
096:     Set teamMembers = new HashSet<>();
097: 
098:     // Calculates the score for the team.
099:     public int getScore() {
100: 
101:         int score = 0;
102: 
103:         for (Person p : teamMembers) {
104:             for (Person p1 : teamMembers) {
105:                 score += p.getCompatibility(p1);
106:             }
107:         }
108: 
109:         return score;
110:     }
111: 
112:     // Returns the team member's names as a sorted array.
113:     public String[] getNames() {
114: 
115:         String[] names = new String[teamMembers.size()];
116: 
117:         int i = 0;
118:         for (Person p : teamMembers) {
119:             names[i++] = p.name;
120:         }
121: 
122:         Arrays.sort(names);
123:         return names;
124:     }
125: 
126:     public void addTeamMember(Person p) {
127:         teamMembers.add(p);
128:     }
129: 
130: }
131: 
132: class Person {
133: 
134:     final int id;
135:     final String name;
136:     final Map compatibilityMap = new HashMap();
137: 
138:     Person(int id, String[] data) {
139: 
140:         this.id = id;
141:         name = data[0];
142: 
143:         for (int i = 1; i < data.length; i++) {
144:             compatibilityMap.put((i - 1), Integer.parseInt(data[i]));
145:         }
146:     }
147: 
148:     // Returns an int representing how compatible this person is with the other.
149:     public int getCompatibility(Person p) {
150:         return compatibilityMap.get(p.id);
151:     }
152: 
153: }
Notes:

The problem asks us to create the best possible team by selecting from a pool of individuals. Each individual has a set of scores which represent how compatible they are with each other individual. The team's score is determinined by summing the compatibility ratings for each person on the team with every other team member. The team with the highest score should be selected.

The solution use two inner classes to help represent the data: Person and Team. Person stores the person's name, an ID (which comes in handy since people may have the same name), and a Map that maps another Person's ID to their compatibility score.

Team holds a set of Person objects, and has methods for adding new team mebers, generating the required return value for the winning team, and calculating the score.

The hardest part of this problem, is coming up with the set of all possible teams - this is handled by the getAllTeams() method. The method works by iterating through the list of all people. For each person, getAllTeams() is called with a list of all people that come after the current person, and a team size that's decremented by one. For each of the teams returned, the current person is added to the team, and that team is added to the set that gets returned. The recursion continues until the size of the desired team is 1, in which case each person in the list of allPeople is effectively their own team.

The number of teams is small enough that this brute force approach is possible. Although, the code, as given may fail one of the test for taking more that 2 seconds. It ran in 0.6 seconds on my machine, so I'm not too concerned. I've written essentially the same algorithm in C, and it passed easily.

Once a Set of all possible teams is obtained, it's a simple matter of calculating the score for each team, and keeping track of which team has the highest.

Thursday, August 14, 2014

MostProfitable

Problem:

TopCoder Problem Statement - MostProfitable

Overview:

Determine the most profitable item sold based on cost, price, and the number of sales.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 153
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1774
08:  */
09: 
10: public class MostProfitable {
11: 
12:     public String bestItem(int[] costs, int[] prices, int[] sales,
13:                            String[] items) {
14: 
15:         int maxProfitIdx = -1;
16:         int maxProfitAmt = Integer.MIN_VALUE;
17: 
18:         /*
19:          * For each item, calculate the profit.  If it's greater than any
20:          * we've seen so far, store that amount and its index.
21:          * The profit is calculated as the (price - cost) times the number of
22:          * sales.
23:          */
24:         for (int i = 0; i < costs.length; i++) {
25:             int profit = (prices[i] - costs[i]) * sales[i];
26:             if (profit > maxProfitAmt) {
27:                 maxProfitIdx = i;
28:                 maxProfitAmt = profit;
29:             }
30:         }
31: 
32:         /*
33:          * If the profit on our most profitable item is greater than 0,
34:          * return it's name.  If there are no profitable items,
35:          * return an empty string.
36:          */
37:         if (maxProfitAmt > 0) {
38:             return items[maxProfitIdx];
39:         } else {
40:             return "";
41:         }
42:     }
43: }
Notes:

There's just two steps to solving this problem. First, we need to loop through each item and calculate it's profit. This is given by the equation on line 25: profit = (prices[i] - costs[i]) * sales[i];

Then, for each profit, we need to determine if it's greater than any previously seen value; and if so, we store both the index of that item as well as the profit. This is done on lines 26-29. By requiring the new profit to be greater than maxProfitAmt (as opposed to greater than or equal to), we ensure that in cases of a tie, the first value remains.

Sunday, August 10, 2014

ProblemWriting

Problem:

TopCoder Problem Statement - ProblemWriting

Overview:

Determine if the given input String matches a Backus-Naur form.

Java Source:
001: /*
002: TopCoder
003: Single Round Match: 152
004: Division: 2
005: Level: 3
006: Points: 1000
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1763
008:  */
009: 
010: public class ProblemWriting {
011: 
012:     private static final String ERROR_LENGTH = "dotForm must contain between " +
013:             "1 and 25 characters, inclusive.";
014: 
015:     // Replace the 'X' with the position where it failed.
016:     private static final String ERROR_FORM = "dotForm is not in dot notation," +
017:             " check character X.";
018: 
019:     public String myCheckData(String dotForm) {
020: 
021:         // First check that we meet the length requirements.
022:         if ((dotForm == null) || (dotForm.length() < 1) ||
023:                 (dotForm.length() > 25)) {
024:             return ERROR_LENGTH;
025:         }
026: 
027:         StateMachine m = new StateMachine();
028: 
029:         /*
030:          * Use the state machine to process each character of the input.
031:          * After each transition, check that we are in a valid state.
032:          */
033:         for (int i = 0; i < dotForm.length(); i++) {
034:             m.transition(dotForm.charAt(i));
035: 
036:             if (!m.isValidState()) {
037:                 return ERROR_FORM.replace("X", "" + i);
038:             }
039:         }
040: 
041:         // When done, make sure we're in a valid end state.
042:         if (m.isEndState()) {
043:             return "";
044:         }
045: 
046:         // Otherwise, return an error - we're expecting more characters.
047:         return ERROR_FORM.replace("X", "" + dotForm.length());
048: 
049:     }
050: 
051:     /*
052:      * StateMachine will help us keep track of the valid next characters
053:      * given our current state.
054:      */
055:     private class StateMachine {
056: 
057:         private final int STATE_START = 0;
058:         private final int STATE_NUMBER = 1;
059:         private final int STATE_DOT1 = 2;
060:         private final int STATE_OPERATOR = 3;
061:         private final int STATE_DOT2 = 4;
062:         private final int STATE_ERROR = -1;
063: 
064:         private int state = STATE_START;
065: 
066:         public boolean isValidState() {
067: 
068:             return (state != STATE_ERROR);
069:         }
070: 
071:         public boolean isEndState() {
072: 
073:             return (state == STATE_NUMBER);
074:         }
075: 
076:         /*
077:          * Using the char c, and our current state, determine the next state.
078:          * There is no return from STATE_ERROR.
079:          */
080:         public void transition(char c) {
081: 
082:             if (state == STATE_START) {
083:                 if (isNumber(c)) {
084:                     state = STATE_NUMBER;
085:                 } else {
086:                     state = STATE_ERROR;
087:                 }
088: 
089:             } else if (state == STATE_NUMBER) {
090:                 if (isDot(c)) {
091:                     state = STATE_DOT1;
092:                 } else if (isOperator(c)) {
093:                     state = STATE_OPERATOR;
094:                 } else {
095:                     state = STATE_ERROR;
096:                 }
097: 
098:             } else if (state == STATE_DOT1) {
099:                 if (isDot(c)) {
100:                     state = STATE_DOT1;
101:                 } else if (isOperator(c)) {
102:                     state = STATE_OPERATOR;
103:                 } else {
104:                     state = STATE_ERROR;
105:                 }
106: 
107:             } else if (state == STATE_OPERATOR) {
108:                 if (isDot(c)) {
109:                     state = STATE_DOT2;
110:                 } else if (isNumber(c)) {
111:                     state = STATE_NUMBER;
112:                 } else {
113:                     state = STATE_ERROR;
114:                 }
115: 
116:             } else if (state == STATE_DOT2) {
117:                 if (isDot(c)) {
118:                     state = STATE_DOT2;
119:                 } else if (isNumber(c)) {
120:                     state = STATE_NUMBER;
121:                 } else {
122:                     state = STATE_ERROR;
123:                 }
124:             }
125:         }
126: 
127:         private boolean isNumber(char c) {
128: 
129:             return ((c >= '0') && (c <= '9'));
130:         }
131: 
132:         private boolean isOperator(char c) {
133: 
134:             return ((c == '+') || (c == '-') || (c == '*') || (c == '/'));
135:         }
136: 
137:         // Didn't need a method for this, but it's better to be consistent.
138:         private boolean isDot(char c) {
139: 
140:             return (c == '.');
141:         }
142: 
143:     }
144: 
145: }
Notes:

There are a lot of difficult ways to solve this problem (recursion, regular expressions, etc.), but the easiest approach is to use a state machine to track our progress through the input String. First, ensure that the input meets the length requirements. Then, for each character of the input we'll call transition() on our state machine. If the state ever becomes invalid, return the appropriate string with the current position. When done, make sure we've finished at a valid end state.

The following diagram shows the various states and legal transitions.

# represents any digit. + is any operation (+, -, *, /). . represents a Dot, and the star designates a valid end state.

Any transition that is not explicitly shown in the diagram results in moving to the error state, from which there is no return.

The code for the state machine is very simple. We being in the start state, and then for each call to transition(); the current state and given character are used to determine the new state.

Saturday, August 9, 2014

LeaguePicks

Problem:

TopCoder Problem Statement - LeaguePicks

Overview:

Determine which picks you'll get in a fantasy league draft.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 152
04: Division: 2 / 1
05: Level: 2 / 1
06: Points: 500 / 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1716
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.List;
12: 
13: public class LeaguePicks {
14: 
15:     public int[] returnPicks(int position, int friends, int picks) {
16: 
17:         // Uses a re-sizeable list instead of calculating the size of the int[]
18:         List pickList = new ArrayList<>();
19: 
20:         // Your first pick is just your position.
21:         int nextPick = position;
22: 
23:         /*
24:          Keeps track of whether we are working from the beginning of the list
25:          toward the end.  Or if we've reached the end,
26:          and are working back toward the front.
27:          */
28:         boolean startToEnd = true;
29: 
30:         // Continue until we've run out of picks.
31:         while (nextPick <= picks) {
32: 
33:             pickList.add(nextPick);
34: 
35:             if (startToEnd) {
36:                 nextPick += (2 * (friends - position) + 1);
37:             } else {
38:                 nextPick += (2 * position) - 1;
39:             }
40: 
41:             startToEnd = !startToEnd; // Switch direction.
42:         }
43: 
44:         // Convert the ArrayList into an int[] and return it.
45:         int[] returnList = new int[pickList.size()];
46: 
47:         for (int i = 0; i < pickList.size(); i++) {
48:             returnList[i] = pickList.get(i);
49:         }
50: 
51:         return returnList;
52:     }
53: }
Notes:

It pays to come up with the equations on lines 36 and 38 prior to starting any coding. Initially, next pick is set to your position, and startToEnd is set to true - indicating that we're working from the start of the list toward the end. There are (friends - position) people in the line after you; and each of them will get 2 picks - one on the way down and a second on the way back up. So, your second pick will come (2 * (friends - position) + 1) picks later. startToEnd is flipped to indicate that we're now working from the end back to the start.

There are position -1 people in the line ahead of you; and they'll each get 2 picks before it's your turn again. So, your next pick will come (2 * position) - 1 picks later. Again, startToEnd is flipped to indicate that we're now headed to the end of the line. This process continues until the value in picks has been reached.

As each value of nextPick is calculated, it gets added to the pickList array. This relieves us of having to determine the length of the returned int[] until the end. Lines 45-51 create the return array, copy the contents of the pickList to the array, and then return it.

Friday, August 8, 2014

FixedPointTheorem

Problem:

TopCoder Problem Statement - FixedPointTheorem

Overview:

Determine the high and low values of a function when called thousands of time, where the output of one iteration is the input of the next.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 152
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1765
08: */
09:
10: public class FixedPointTheorem {
11:
12:     // Number of iterations before we being keeping track of high and low.
13:     private static final int SETTLE_CYCLES = 200_000;
14:
15:     // Number of iterations where we do track high and low.
16:     private static final int RANGE_CYCLES = 1000;
17:
18:     // This is the function that we'll be iterating through
19:     private static double fnct(double R, double X) {
20:
21:         return R * X * (1 - X);
22:     }
23:
24:     public double cycleRange(double R) {
25:
26:         double X = 0.25;
27:
28:         // Run through 200,000 iterations to stabilize the function.
29:         for (int i = 1; i < SETTLE_CYCLES; i++) {
30:             X = fnct(R, X);
31:         }
32:
33:         // Grab the first number and set it to both the high and low.
34:         X = fnct(R, X);
35:
36:         double hi = X;
37:         double lo = X;
38:
39:         // Start at 2 since we already grabbed the first one.
40:         for (int i = 2; i < RANGE_CYCLES; i++) {
41:             X = fnct(R, X);
42:             hi = Math.max(hi, X);
43:             lo = Math.min(lo, X);
44:         }
45:
46:         return (hi - lo);
47:     }
48: }
Notes:

Be careful that you call the function exactly 200,000 times when stabilizing it, and exactly 1,000 times when determining the high and low values. An off-by-one error will affect the results of some tests.

Also, be sure that you set the initial range values correctly. After stabilizing, the first call to the function will give you both the max and min values. Then, continue through the remaining 999 calls updating the max and min as appropriate.

Finally, make sure that your function is correct. It doesn't explicitly state it in the problem statement, but the function you want to use is the one given in the sample: F(X) = R * X * (1 -X)

Monday, August 4, 2014

MergeSort

Problem:

TopCoder Problem Statement - MergeSort

Overview:

Implement Merge Sort, and count the number of comparisons needed to sort an array.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2 / 1
05: Level: 3 / 2
06: Points: 1000 / 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1705
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.List;
12: 
13: public class MergeSort {
14: 
15:     private int numCompares = 0;
16: 
17:     public int howManyComparisons(int[] numbers) {
18: 
19:         // Convert the int[] into a List
20:         List list = new ArrayList(numbers.length);
21: 
22:         for (int i : numbers) {
23:             list.add(i);
24:         }
25: 
26:         mergeSort(list);
27: 
28:         return numCompares;
29:     }
30: 
31:     private List mergeSort(List a) {
32: 
33:         if (a.size() <= 1) { return a; }
34: 
35:         List sb = mergeSort(a.subList(0, a.size() / 2));
36:         List sc = mergeSort(a.subList((a.size() / 2), a.size()));
37: 
38:         return merge(sb, sc);
39:     }
40: 
41:     private List merge(List b, List c) {
42: 
43:         /*
44:          * It's important that new Lists are created here to hold copies of b
45:          * and c. Otherwise, we run the risk of a concurrent modification
46:          * exception when we start removing elements
47:          */
48:         List b1 = new ArrayList<>();
49:         List c1 = new ArrayList<>();
50: 
51:         b1.addAll(b);
52:         c1.addAll(c);
53: 
54:         // We know the final size of the List, might as well provide it.
55:         List a = new ArrayList(b.size() + c.size());
56: 
57:         while (!b1.isEmpty() && !c1.isEmpty()) {
58: 
59:             int x = b1.get(0);
60:             int y = c1.get(0);
61: 
62:             numCompares++;
63:             if (x < y) {
64:                 a.add(b1.remove(0));
65:             } else if (x > y) {
66:                 a.add(c1.remove(0));
67:             } else {
68:                 a.add(b1.remove(0));
69:                 a.add(c1.remove(0));
70:             }
71: 
72:         }
73: 
74:         if (!b1.isEmpty()) { a.addAll(b1); }
75: 
76:         if (!c1.isEmpty()) { a.addAll(c1); }
77: 
78:         return a;
79:     }
80: }
Notes:

Merge sort is a classic algorithm that you should know how to implement. The problem statement outlines exactly what you need to do - making this relatively easy. There is only a few obstacles beyond just doing what the problem asks for.

First, we'll need to convert the int[] into a List. That's done on lines 20-24. Pretty basic stuff.

Then, we'll need to split the array correctly inside mergeSort(). The problem statement describes what to do if the size of the array is odd or oven. We don't need to care about that. The / operation rounds down, so we can just take the list from 0 to (size / 2) and from (size / 2) to size. Lines 35 and 36. Note that the first argument to subList is inclusive, and the second is exclusive. The the first subList will get position 0, but stops just before (size / 2). The second subList starts at (size / 2) and stops at the end.

The biggest potential roadback probably lies at line 69. If you do not make copies of the Lists passed into merge, then you're likely to get a ConcurrentModificationException. This can be frustrating if you don't understand what's going on. When subList is called on lines 35 and 36, you don't get a new List, rather it returns a view into the original list. So both sb and sc are backed by List a. If you modify the elememts in one list - say by removing an element, and then access the other view; an exception will be thrown. The solution is just to copy the given Lists into two new Lists. Then you're free to modify them as you wish.

Birthday

Problem:

TopCoder Problem Statement - Birthday

Overview:

Given a set of dates, determine the next date to occur after a given date.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2
05: Level: 2
06: Points: 500
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1739
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.Arrays;
12: import java.util.Collections;
13: import java.util.List;
14: 
15: public class Birthday {
16: 
17:     public String getNext(String date, String[] birthdays) {
18: 
19:         List reminders = new ArrayList<>();
20:         for (String s : birthdays) {
21:             reminders.add(new Reminder(s));
22:         }
23:         Collections.sort(reminders);
24: 
25:         Reminder now = new Reminder(date);
26: 
27:         for (Reminder next : reminders) {
28:             if (next.compareTo(now) >= 0) {
29:                 return next.toString();
30:             }
31:         }
32: 
33:         return reminders.get(0).toString();
34:     }
35: 
36:     public class Reminder implements Comparable {
37: 
38:         final int month;
39:         final int day;
40:         final String monthStr;
41:         final String dayStr;
42: 
43:         public Reminder(String s) {
44: 
45:             String s1[] = s.split("( )|(/)");
46:             month = Integer.parseInt(s1[0]);
47:             day = Integer.parseInt(s1[1]);
48:             monthStr = s1[0];
49:             dayStr = s1[1];
50:         }
51: 
52:         public int compareTo(Object o) {
53: 
54:             Reminder other = (Reminder) o;
55:             if (month < other.month) { return -1; }
56:             if (month > other.month) { return 1; }
57:             if (day < other.day) { return -1; }
58:             if (day > other.day) { return 1; }
59:             return 0;
60:         }
61: 
62:         public String toString() {
63: 
64:             return monthStr + "/" + dayStr;
65: 
66:         }
67:     }
68: 
69:     public String getNextImproved(String date, String[] birthdays) {
70: 
71:         Arrays.sort(birthdays);
72: 
73:         for (String next : birthdays) {
74:             if (next.compareTo(date) >= 0) {
75:                 return next.split(" ")[0];
76:             }
77:         }
78: 
79:         return birthdays[0].split(" ")[0];
80:     }
81:     
82: }
Notes:

This solution illustrates 2 important concepts. First is Java's Comparable interface:

The solution creates an inner class named Reminder that implements Comparable. This allows us to easily sort and compare dates. The Reminder class takes a String for it's constructor and parses out the month and day. Next, it provides compareTo() which uses the month and day to determine if another Reminder comes before, after, or is equal to the current object. Finally, Reminder provides a toString() method to give the date in the format required.

Using the Remidner class, the for loop at line 20 converts all the Strings into Reminders. Then we sort them on line 23. The remaining lines get the new date and use compareTo() to find the first date that comes after the given date. If there are no such dates, then we return the first date of the new year.

Now, for the second important lesson - don't rush to start coding! In this case, birthdays could have been sorted just the way they were, as Strings. Given their format of MM/DD, birthdays would be sorted in exactly the same way. If the format was DD/MM - then this would not be the case. But here, the Reminder class was completely unnecessary. I've included the method getNextImproved() at the bottom which is obviously much better.

PrefixCode

Problem:

TopCoder Problem Statement - PrefixCode

Overview:

Determine if a given array of Strings constitutes a prefix code.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1700
08:  */
09: 
10: public class PrefixCode {
11: 
12:     public String isOne(String[] words) {
13: 
14:         for (int i = 0; i < words.length - 1; i++) {
15:             for (int j = i + 1; j < words.length; j++) {
16: 
17:                 if (words[i].startsWith(words[j])) {
18:                     return ("No, " + j);
19:                 } else if (words[j].startsWith(words[i])) {
20:                     return ("No, " + i);
21:                 }
22:             }
23:         }
24:         return "Yes";
25:     }
26: }
Notes:

The problem statement is a little confusing. If you just read the first and third paragraphs it makes more sense. The second paragraph adds nothing and just diverts your attention away from what you need to do. All that you need to do here is determine if any string in the given array of strings is a prefix of any other string. If a prefix is present, return the least prefix index.

The solution uses two for loops with one nested inside the other. Note that the outer for loop goes from i = 0 to i < length - 1; while the inner loop goes from j= i + 1 to j < length. The outer loop marches along from left to right, while the inner loop bounces from the current outer position to the end - with it's space getting shorter and shorter as i increases. This pattern gets used over and over again. The nice thing about this setup is that j is always > i - there is no overlap.

Then, for each value of i and j, we check to see if j is a prefix of i. Or, failing that, if i is a prefix of j. As soon as a prefix if found, we will have the lowest index, so we can stop immediately and return it.

If we exit the for loops without having returned, then there are no prefixes - this is a valid prefix code, so return "Yes"

InterestingDigits

Problem:

TopCoder Problem Statement - InterestingDigits

Overview:

Determine the "interesting" digits for a given base.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 150
04: Division: 2 / 1
05: Level: 2 / 1
06: Points: 500 / 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1523
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.List;
12: 
13: public class InterestingDigits {
14: 
15:     /*
16:      * Loops through all 3 or fewer digit multiples of digitBase testing each
17:      * to see if the sum of all digits divides evenly by digitBase
18:      */
19:     private static boolean isInteresting(int digitBase, int base) {
20: 
21:         // The largest 3-digit number in the given base
22:         int max = base * base * base;
23: 
24:         // Loop through all multiples of digit
25:         for (int digitMultiple = digitBase; digitMultiple < max;
26:              digitMultiple += digitBase) {
27: 
28:             if (!(sumOfDigitsDividesEvenly(digitMultiple, digitBase, base))) {
29:                 return false;
30:             }
31:         }
32: 
33:         return true;
34:     }
35: 
36:     /*
37:      * Sums all the digits in multiple and tests to see if it divides evenly
38:      * by digit.  If the result is multi-digit, then sumOfDigitsDividesEvenly()
39:      * is call recursively on the result.
40:      */
41:     private static boolean sumOfDigitsDividesEvenly(int multiple, int digit,
42:                                                     int base) {
43: 
44:         int sum = 0;
45: 
46:         while (multiple > base) {
47: 
48:             int x = 1;
49: 
50:             while ((x * base) < multiple) {
51:                 x *= base;
52:             }
53:             int div = (multiple / x);  // div now contains left-most digit.
54: 
55:             sum += div;
56:             multiple = multiple - (x * div);
57:         }
58: 
59:         sum += multiple;
60: 
61:         /*
62:          * If the result is larger than base, then recursively call
63:          * sumOfDigitsDevidesEvenly() on the result.
64:          */
65:         if (sum > base) {
66:             return sumOfDigitsDividesEvenly(sum, digit, base);
67:         }
68: 
69:         return ((sum % digit) == 0);
70:     }
71: 
72:     /*
73:      * Loops through all digits in the given base.  If the digit is
74:      * interesting for that base, then add it to a List.
75:      * When done, convert the List to an array and return it.
76:      */
77:     public int[] digits(int base) {
78: 
79:         List interestingDigits = new ArrayList<>();
80: 
81:         for (int digit = 2; digit < base; digit++) {
82:             if (isInteresting(digit, base)) {
83:                 interestingDigits.add(digit);
84:             }
85:         }
86: 
87:         // Convert the List to an int[]
88:         int[] retArray = new int[interestingDigits.size()];
89:         int x = 0;
90:         for (int i : interestingDigits) {
91:             retArray[x++] = i;
92:         }
93: 
94:         return retArray;
95:     }
96: }
Notes:

To determine if a digit is interesting, we need to check all of it's 1, 2, and 3 digit multiples. For each multiple, we add up the digits. If this sum is more than one digit, then add up the sum of those digits. When the sum is just 1 digit, it should be divided evenly by our original digit. For example, the digit 9 is interesting in base 10. If we take any multiple, say 9 X 123 = 1107. And 1 + 1 + 0 + 7 = 9 - which is evenly divisible by 9.

The problem gets a little tricky because we must handle various bases. Continuing the example above, 9 is not interesting in base 16. 9 * A = 5A. 5 + A = F which is not evenly divisible by 9. Luckily , there isn't much that needs to change to support working in different bases.

Our main method, digits(), simply iterates through each digit in the current base and tests to see if it is interesting. If so, the digit is added to a List. When done, the List is converted to any int[] and returned. Here, a different base will just alter the number that the loop counts up to. For base 8, we'll stop at 7. For base 16, we'll go up to 15. etc.

isInteresting() iterates through all 1, 2, and 3 digit multiples of the given number, and determines if the sum of those digits is evenly divisible by the original digit. Line 22 calculates the largest possible 3 digit number for the given base. And the increment portion of the for loop goes up by digitBase - that way we only look at multiples.

Finally, sumOfDigitsDividesEvenly() does the real work of determining, well, if the sum of the digits in multiple is evenly divisible by the given digit. The method is recursive, so the check at line 46 breaks the recursion when we get down to a single digit. Inside the while loop, we get the left-most digit, add it to sum, subtract it off of multiple, and repeat. Line 59 adds the final, right-most, digit to sum. Then on line 65, it checks to see if our sum has more than one digit. If so, then sumOfDigitsDividesEvenly() is called recursively using the sum as it's input. If the sum is just one digit (i.e. < base) the we return true if sum is evenly divisible by digit.

There's actually a much simpler way of determining if a number is "interesting". See the solution given in the TopCoder Match Editorials

Sunday, August 3, 2014

Pricing

Problem:

TopCoder Problem Statement - Pricing

Overview:

Determine pricing categories in order to maximize sales revenue.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 149
04: Division: 2
05: Level: 3
06: Points: 1000
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1600
08:  */
09:
10: import java.util.Arrays;
11: import java.util.HashSet;
12: import java.util.Set;
13:
14: public class Pricing {
15:
16:     /*
17:      * Given an array consisting of the prices that people are willing to
18:      * pay, and four pricing categories given in increasing price order,
19:      * this will return the expected sales total.
20:      * The price of a cat4 ticket > cat 3 > cat 2 > cat1.
21:      */
22:     private static int calcSales(int[] prices, int cat1, int cat2,
23:                                  int cat3, int cat4) {
24:
25:         int sum = 0;
26:
27:         for (int willingToPay : prices)  {
28:
29:             if (willingToPay >= cat4)  {  // Big spenders
30:                 sum += cat4;
31:             } else if (willingToPay >= cat3)  {
32:                 sum += cat3;
33:             } else if (willingToPay >= cat2)  {
34:                 sum += cat2;
35:             } else if (willingToPay >= cat1)  {
36:                 sum += cat1;
37:             } else {
38:                 // do nothing - even cat1 is too expensive.
39:             }
40:         }
41:
42:         return sum;
43:     }
44:
45:     /*
46:      * Returns the number of unique values in the int[]
47:      */
48:     private static int numUniqueValues(int[] prices) {
49:
50:         Set s = new HashSet<>();
51:
52:         for (int i : prices) {
53:             s.add(i);
54:         }
55:
56:         return s.size();
57:     }
58:
59:     public int maxSales(int[] price) {
60:
61:         /*
62:          * If there are 4 or less unique prices, then we can just assign each
63:          * customer their maximum price.  Add them up, and return the sum.
64:          */
65:         if (numUniqueValues(price) <= 4) {
66:             int sum = 0;
67:             for (int aPrice : price) {
68:                 sum += aPrice;
69:             }
70:             return sum;
71:         }
72:
73:         // Sort the array of prices.
74:         Arrays.sort(price);
75:
76:         int maxSales = 0;
77:
78:         for (int i = 0; i < price.length - 3; i++) {
79:
80:             for (int j = i + 1; j < price.length - 2; j++) {
81:
82:                 for (int k = j + 1; k < price.length - 1; k++) {
83:
84:                     for (int m = k + 1; m < price.length; m++) {
85:
86:                         int thisSales = calcSales(price, price[i], price[j],
87:                                 price[k], price[m]);
88:
89:                         maxSales = Math.max(thisSales, maxSales);
90:                     }
91:                 }
92:             }
93:         }
94:
95:         return maxSales;
96:     }
97: }
Notes:

The constraints limit the input to a maximum of 50 elements, and there are at most 4 pricing categories. This domain is small enough to allow for a brute force approach. The strategy used here is to take each possible combination of 4 prices, and see which one yields the greatest income. Note that the price categories should come from the array of prices that customers are willing to pay. Any price that is slightly below what a customer is willing to pay can bumped up to the price the customer will pay without losing the sale.

The if statement on line 65 checks the number of unique prices in the input. If there are 4 or less, then we simply assign a price category to each of those values, and we're done. If there are more than 4 unique prices, then we'll have some customers that either refuse to pay even the minimum amount, or end up paying less than they are willing to. The number of unique prices is determined by numUniqueValues() - which just adds all values to a Set, and returns the size of the Set. Since Sets do not allow duplicate values, this works out nicely.

After determining that there are more than 4 unique prices, the next step is to sort the prices. This is important because we'll be passing these prices into calcSales() which expects the price categories to be in ascending order.

Next, a series of nested for loops, beginning on line 78, try every possible combination of prices. Note that the for loops do not overlap m > k > j > i. This saves a lot of duplicate work, and ensures that the price categories are given to calcSales in the proper order.

calcSales() loops through all the prices that the customers are willing to pay and determines the most expensive category that they're willing to pay for. Here, it's important that the categories are in order, with cat4 the most expensive and cat1 the least. For each, sum is incremented by the value of that category.

Finally, the expected sales amount for the current set of categories is compared to the maximum amount seen thus far (line 89), and if it's greater, then max is updated.

This is a surprisingly easy for a 1000 point Division 2 question. Once you realize that the four categories must come from the array of prices given, and that a brute-force solution will suffice, the code practically writes itself.

WordParts

Problem:

TopCoder Problem Statement - WordParts

Overview:

Determine the fewest number of word parts (either prefixes or suffixes) from a given string that are needed to create another string.

Java Source:
001: /*
002: TopCoder
003: Single Round Match: 156
004: Division: 2
005: Level: 3
006: Points: 1000
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1361
008:  */
009: 
010: import java.util.HashMap;
011: import java.util.Map;
012: 
013: public class WordParts {
014: 
015:     /*
016:      * Holds all the word parts that we've processed so far,
017:      * along with the minimum number of word parts needed to create them.
018:      */
019:     Map wordParts;
020: 
021:     /*
022:      * Returns a map containing all possible substrings that either start at
023:      * the beginning of the String s, or end at the end of s.  For example,
024:      * if the input string is "java", the map would contain:
025:      * j, ja, jav, java, a, va, ava
026:      * The value for each of these keys represents the number of parts
027:      * required to make the string.  Inititally these are all 1.  A string
028:      * like "ajava" would have a value of 2: a=1 + java=1
029:      */
030:     private static Map getWordParts(String s) {
031: 
032:         Map m = new HashMap<>();
033: 
034:         for (int i = 1; i <= s.length() - 1; i++) {
035:             m.put(s.substring(0, i), 1);  // Starts from beginning
036:             m.put(s.substring(i), 1);     // Starts from the end
037:         }
038: 
039:         // Don't forget to include the entire string.
040:         m.put(s, 1);
041: 
042:         return m;
043:     }
044: 
045:     /*
046:      * The main method
047:      */
048:     public int partCount(String original, String compound) {
049: 
050:         // Check for the empty string case.
051:         if ((compound == null) || (compound.length() < 1)) {
052:             return 0;
053:         }
054: 
055:         // Create a map of all possible prefixes and suffixes.
056:         wordParts = getWordParts(original);
057: 
058:         return fewestParts(compound);
059: 
060:     }
061: 
062:     /*
063:      * fewestParts recursively calls itslef to determine the minimum number
064:      * of parts to create each substring of s.
065:      * If no valid substring can be formed, it returns null
066:      */
067:     private int fewestParts(String s) {
068: 
069:         // Break the recursion when string length becomes 0.
070:         if ((s == null) || (s.length() == 0)) {
071:             return -1;
072:         }
073: 
074:         // If our map contains this key, just return the value.
075:         if (wordParts.containsKey(s)) {
076:             return wordParts.get(s);
077:         }
078: 
079:         int fewest = -1;
080: 
081:         for (int i = 1; i <= s.length(); i++) {
082: 
083:             String prefix = s.substring(0,i);  // Gets the first i characters.
084:             String suffix = s.substring(i);  // Characters after the first i.
085: 
086:             if (!wordParts.containsKey(prefix)) {
087:                 continue;
088:             }
089: 
090:             /*
091:              * Recursively call fewestParts the determine the fewest number
092:              * of parts that are needed to create the suffix.  If the suffix
093:              * can be created (does not return -1), then add the number of
094:              * parts to create the prefix.  If this sum is less than any that
095:              * we've seen to this point, store it in fewest.
096:              */
097:            int f = fewestParts(suffix);
098: 
099:             if (f > 0) {
100: 
101:                 f += wordParts.get(prefix);
102: 
103:                 if ((fewest == -1) || (f < fewest)) {
104:                     fewest = f;
105:                 }
106:             }
107:         }
108: 
109:         /*
110:          * We now know the fewest number of parts needed to create the
111:          * current string, so store it in the map.
112:          */
113:         if (fewest != -1)  {
114:             wordParts.put(s, fewest);
115:         }
116: 
117:         return fewest;
118:     }
119: }
Notes:

The solution uses a technique known as dynamic programming. It works by starting at the end of the compound string and works backward one character at a time. At each character it determines and stores the smallest number of word parts that are needed to create that substring. Once it has reached the beginning of the compound string, we'll have our answer.

First, we check for a null or empty input string on line 51. It's easiest to just get this case out of the way up front.

Next, we build a map named wordParts that contains all possible substrings of original that either start at the beginning of the string (prefixes), or end at the end of string (suffixes). Each of these strings can be created with one word part, so we'll mark them with a value of 1. As an example, if our origninal word was "coder", then the wordParts map would contain: c, co, cod, code, coder, r, er, der, oder. When we encounter any of these substrings, they can be counted as 1 word part.

With the map in place, we call fewestParts() on line 58, and return the result - We're Done.

All that's left is to implement fewestParts().

fewestParts() works by calculating the fewest number of word parts needed to create the string s for each possible prefix/suffix combination. If the input is "cocoder", then it will divide it up as c/ocoder, co/coder, coc/oder, coco/der, cocod/er, cocode/r, and cocoder. For each case, if the prefix is not in the wordParts map, then we skip it. Otherwise, recursively call fewestParts() on the suffix, and add this to the value of the prefix. If that value is the smallest we've seen so far, then it is stored in the wordParts map. Combining this example, with the one from above - we see that co/coder is the best we can do since "co" has a value of 1, and "coder" also has a value of 1. Therefore, "cocoder" can be formed with 2 word parts. Note that "co" + "cod" + "er" also works (along with some others), but this gives us a value of 3, so we don't want to store that.

fewestParts() is recursive, so we need to ensure that the recusion breaks at some point. This occurs on line 72 if the string becomes empty, or line 77 if the string already exists in the wordParts map. In this case, we've already deteremined the fewest number of word parts needed to create the string we're currently examining, so we can just return that.

A good thing to know is that the prefixes and suffixes can be generated easily using java's String.substring() method. substring(0,i) will return a prefix consisting of the first i characters. substring(i) will return a suffix beginning after the ith character and continuing to the end.

Normally you don't need dynamic programming techniques in division 2, that's typically saved for divison 1. I also found the problem statement difficult to understand and had to read it several times to get what needed to be done. The examples were also of limited help. I'd call this one of the toughest division 2 problems I've seen.

BombSweeper

Problem:

TopCoder Problem Statement - BombSweeper

Overview:

Predict the likelihood that you'll win a mine sweeper like game.

Java Source:
001: /*
002: TopCoder
003: Single Round Match: 156
004: Division: 2 / 1
005: Level: 2 / 1
006: Points: 600 / 300
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1778
008:  */
009: 
010: public class BombSweeper {
011: 
012:     /*
013:      * Converts the array of Strings into a 2-Dimensional array of
014:      * characters.  This will simplify working with the board.
015:      */
016:     private static char[][] generateBoard(String[] strs) {
017: 
018:         char[][] charArray = new char[strs.length][strs[0].length()];
019: 
020:         for (int row = 0; row < strs.length; row++) {
021:             for (int col = 0; col < strs[0].length(); col++) {
022:                 charArray[row][col] = strs[row].charAt(col);
023:             }
024:         }
025: 
026:         return charArray;
027:     }
028: 
029:     /*
030:      * Checks each of the 8 surrounding squares looking for bombs.  If a bomb
031:      * is found, returns true - otherwise returns false
032:      */
033:     private static boolean hasBombNeighbor(char[][] field, int row, int col) {
034: 
035:         // Check row above
036:         if (row > 0) {
037: 
038:             // Above and to the left
039:             if (col > 0) {
040:                 if (field[row - 1][col - 1] == 'B') { return true; }
041:             }
042: 
043:             // Directly above
044:             if (field[row - 1][col] == 'B') { return true; }
045: 
046:             // Above and to the right
047:             if (col < field[0].length - 1) {
048:                 if (field[row - 1][col + 1] == 'B') { return true; }
049:             }
050:         }
051: 
052:         // Same row - To the left
053:         if (col > 0) {
054:             if (field[row][col - 1] == 'B') { return true; }
055:         }
056: 
057:         // Same row - To the right
058:         if (col < field[0].length - 1) {
059:             if (field[row][col + 1] == 'B') { return true; }
060:         }
061: 
062:         // Check row below
063:         if (row < field.length - 1) {
064: 
065:             // Below and to the left
066:             if (col > 0) {
067:                 if (field[row + 1][col - 1] == 'B') { return true; }
068:             }
069: 
070:             // Directly below
071:             if (field[row + 1][col] == 'B') { return true; }
072: 
073:             // Below and to the right
074:             if (col < field[0].length - 1) {
075:                 if (field[row + 1][col + 1] == 'B') { return true; }
076:             }
077:         }
078: 
079:         return false;
080:     }
081: 
082:     public double winPercentage(String[] board) {
083: 
084:         int numBombs = 0;
085:         int numWins = 0;
086: 
087:         char[][] mineField = generateBoard(board);
088: 
089:         /*
090:          * Loop through each position of the board.  For each position,
091:          * determine if it is a bomb, or has any neighbors that are bombs.
092:          */
093:         for (int row = 0; row < mineField.length; row++) {
094:             for (int col = 0; col < mineField[0].length; col++) {
095:                 if (mineField[row][col] == 'B') {
096:                     numBombs++;
097:                 } else if (hasBombNeighbor(mineField, row, col)) {
098:                     // doNothing
099:                 } else {
100:                     numWins++;
101:                 }
102:             }
103:         }
104: 
105:         // This equation is given in the problem statement.
106:         return ((double) numWins / (double) (numWins + numBombs)) * 100.0;
107:     }
108: }
Notes:

The equation for determining the likelihood of winning is given in the problem statement as (wins / (wins + losses)) where wins are the number of squares that are not bombs and do not have any neighbors that are bombs; and losses are squares that are bombs. Be sure to multiply by 100 to get this number as a percentage.

Quite often, I find it easier to work with a 2-Dimensional array of characters rather than the given String array. The method generateBoard() performs this simple conversion. With the 2-Dimensional char array, we can refer to each square using just its indices, and not have to mix an index with a String.charAt(). It's a personal preference, but I think board[row][col] is cleaner than board[row].charAt(col)

With the mineField created, lines 94-104 loop through each row and column testing to see if that position is a bomb, or if any of it's neighbors are bombs. If the position is a bomb, numBombs is incremented. If it's not a bomb, but a neighbor is, then nothing happens. And if it's not a bomb, and none of it's neighbors are either, then numWins is incremented.

hasBombNeighbor() determines if a given position has a bomb in any of the 8 positions surrounding it. Just be careful here to avoid checking a neighbor that falls outside the bounds of the board.

Once numBombs, and numWins are known, we can plug those into the given equation and return the result.

DiskSpace

Problem:

TopCoder Problem Statement - DiskSpace

Overview:

Determine the smallest number of hard drives needed to store all your stuff.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 156
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1777
08:  */
09:
10: import java.util.Arrays;
11:
12: public class DiskSpace {
13:
14:     public int minDrives(int[] used, int[] total) {
15:
16:         int capacityNeeded = 0;
17:
18:         // Calculate the total amount of space needed.
19:         for (int u : used) {
20:             capacityNeeded += u;
21:         }
22:
23:         /*
24:          * Sort the drive capacitites.
25:          * Then we'll start filling from the largest disc working back to the
26:          * smallest.
27:          */
28:         Arrays.sort(total);
29:
30:         // Start with the largest drive.
31:         int i = total.length - 1;
32:
33:         // The number of drives needed.
34:         int count = 0;
35:
36:         while (capacityNeeded > 0) {
37:             count++;
38:
39:             // Subtract the current drive's capacity from the amount needed.
40:             capacityNeeded -= total[i--];
41:         }
42:
43:         return count;
44:     }
45: }
Notes:

This solution is a simple example of using a greedy algorithm. We'll fill up the largest drives first, and use up smaller and smaller drives as necessary.

The first step is to determine the toal amount of space that your data requires. This is calculated by the for loop starting on line 19, and is stored in the variable capacityNeeded.

Next, the drives are sorted by their capacity using Arrays.sort(). This will arrange the array with the smallest element first.

Finally, we begin filling the drives, beginning with the largest one at the end of the total[] array and working backward to the smaller drives. For each drive, we subtract their volume from capctiyNeeded, until capacityNeeded is no longer greater than zero.

We don't need to worry about not having enough space, because the problem statement guarantees that the capacity of the drives will be large enough.

Also, it's good to remember that Java provides the methods Arrays.sort() and Collections().sort for sorting.