Monday, September 29, 2014

Sets

Problem:

TopCoder Problem Statement - Sets

Overview:

Perform some basic Set operations and return the results.

Java Source:
01: import java.util.Arrays;
02: import java.util.HashSet;
03: import java.util.Set;
04: 
05: public class Sets {
06:  
07:  public int[] operate(int[] A, int[] B, String operation) {
08: 
09:         Set setA = new HashSet<>();
10:         Set setB = new HashSet<>();
11:         Set setC = new HashSet<>();
12: 
13:         for (int x : A)  {
14:             setA.add(x);
15:         }
16: 
17:         for (int x : B)  {
18:             setB.add(x);
19:         }
20: 
21:         if ("INTERSECTION".equals(operation)) {
22:             setC.addAll(setA);
23:             setC.retainAll(setB);
24: 
25:         } else if ("UNION".equals(operation))  {
26:             setC.addAll(setA);
27:             setC.addAll(setB);
28: 
29:         } else if ("SYMMETRIC DIFFERENCE".equals(operation))  {
30: 
31:             // setC contains the Union
32:             setC.addAll(setA);
33:             setC.addAll(setB);
34: 
35:             // SetD contains the Intersection
36:             Set setD = new HashSet<>();
37:             setD.addAll(setA);
38:             setD.retainAll(setB);
39: 
40:             // Remove the intersection from the union to get the symmetric diff.
41:             setC.removeAll(setD);
42:         }
43: 
44:         // Create the return array, sort it, and return it.
45:         int[] r = new int[setC.size()];
46: 
47:         int i = 0;
48:         for (Integer x : setC)  {
49:             r[i++] = x;
50:         }
51: 
52:         Arrays.sort(r);
53: 
54:         return r;
55:  }
56: }
Notes:

Another fairly easy Division 2 - Level 2 problem - if you use the language features to do all the work.

We'll use Java's HashSet to perform all of the operations. Lines 9 through 19 create the HashSets and load values into them. setC will hold our results. Then we'll use a combination of addAll(), retainAll(), and removeAll() depending on the type of operations. If you're not familiar with these operations, I encourage you to read up on them.

If the operation is INTERSECTION, then all all the elements from setA into our result setC. Then use retainAll() to keep only those elements that are also in setB.

UNION is the easiest. We just use addAll() to add the contents of setA and setB to setC. It doesn't matter if there are duplicates, Sets guarantee that no duplicates are stored.

For SYMMETRIC DIFFERENCE, we first populate setC as the union of setA and setB. The we create a new setD to hold the intersection of setA and setB. Finally, that intersection is removed from the union.

Lines 45 through 54 create the return array, populate it with the contents from setC, sort it, and return.

StreetParking

Problem:

TopCoder Problem Statement - StreetParking

Overview:

Determine the number of parking spaces available on a street given a set of rules.

Java Source:
01: public class StreetParking {
02:  
03:  public int freeParks(String street) {
04: 
05:         int numSpots = 0;
06: 
07:         for (int p = 0; p < street.length(); p++)  {
08:             if (isGoodParkingSpot(p, street))  {
09:                 numSpots++;
10:             }
11:         }
12: 
13:         return numSpots;
14:  }
15: 
16:     private static boolean isGoodParkingSpot(int p, String s)  {
17: 
18:         // Is it directly in front of a private driveway.
19:         if (s.charAt(p) == 'D') return false;
20: 
21:         // Is it directly in front of a bus stop.
22:         if (s.charAt(p) == 'B') return false;
23: 
24:         // Is it 5 meters in front of a bus stop.
25:         if (((p + 1)  < s.length()) && (s.charAt(p + 1) == 'B')) return false;
26: 
27:         // Is it 10 meters in front of a bus stop.
28:         if (((p + 2) < s.length()) && (s.charAt(p + 2) == 'B')) return false;
29: 
30:         // Is it directly in front of a side-street.
31:         if (s.charAt(p) == 'S') return false;
32: 
33:         // Is it 5 meters before a side street.
34:         if (((p + 1)  < s.length()) && (s.charAt(p + 1) == 'S')) return false;
35: 
36:         // Is it 5 meters after a side street.
37:         if ((p > 0) && (s.charAt(p - 1)) == 'S') return false;
38: 
39:         return true;
40:     }
41: }
Notes:

To solve this, simply step through each position of the street String, and increment a count for each position that is valid.

The method isGoodParkingSpot() inspects the given String position to see if it matches all the criteria. As soon as a rule violation is found, it returns false. If all the conditions are satisfied, then it returns true.

The only thing you need to be careful of is not going beyond the boundaries of the string. When looking at positions 5 or 10 meters ahead, check to make sure that there are 1 or 2 more positions. Similarly, when checking 5 meters behind, make sure that this is not the first position.

Sunday, September 28, 2014

Gems

Problem:

TopCoder Problem Statement - Gems

Overview:

Compute the number of possible moves for the given state of a game.

Java Source:
001: public class Gems {
002: 
003:     private static final int MIN_GROUP_SIZE = 3;
004: 
005:     private int board_height;
006:     private int board_width;
007: 
008:     public int numMoves(String[] b) {
009: 
010:         board_height = b.length;
011:         board_width = b[0].length();
012: 
013:         /*
014:         * Copy the String[] into a char[][].  This makes it much easier to
015:         * work with, for example, when swapping positions.
016:         */
017:         char[][] board = new char[board_height][board_width];
018: 
019:         for (int y = 0; y < board_height; y++) {
020:             for (int x = 0; x < board_width; x++) {
021:                 board[y][x] = b[y].charAt(x);
022:             }
023:         }
024: 
025:         int numMoves = 0;
026: 
027:         for (int y = 0; y < board_height; y++) {
028:             for (int x = 0; x < board_width; x++) {
029: 
030:                 // If not at right edge, swap right.
031:                 if (x < board_width - 1) {
032:                     swapGems(board, x, y, x + 1, y);
033: 
034:                     if ((getGroupSize(board, x + 1, y) >= MIN_GROUP_SIZE) ||
035:                             (getGroupSize(board, x,y) >= MIN_GROUP_SIZE))  {
036:                         numMoves++;
037: //                        System.out.println("Y: " + y + " X:" + x +
038: //                              " --> Y1:" + y + " X1:" + (x+1));
039: 
040:                     }
041: 
042:                     swapGems(board, x + 1, y, x, y);
043:                 }
044: 
045:                 // If not at bottom edge, swap down.
046:                 if (y < board_height - 1) {
047:                     swapGems(board, x, y, x, y + 1);
048: 
049:                     if ((getGroupSize(board, x, y + 1) >= MIN_GROUP_SIZE) ||
050:                             (getGroupSize(board,x,y) >= MIN_GROUP_SIZE))  {
051:                         numMoves++;
052: //                        System.out.println("Y: " + y + " X:" + x +
053: //                          " --> Y1:" + (y+1) + " X1:" + x);
054: 
055:                     }
056: 
057:                     swapGems(board, x, y + 1, x, y);
058:                 }
059:             }
060:         }
061: 
062:         return numMoves;
063:     }
064: 
065:     /*
066:     * Swaps the values at the two positions given.
067:     */
068:     private static void swapGems(char[][] board, int x, int y,
069:                                  int x1, int y1) {
070: 
071:         char t = board[y][x];
072:         board[y][x] = board[y1][x1];
073:         board[y1][x1] = t;
074: 
075:     }
076: 
077:     /*
078:     * Returns the larger of the horizontal or vertical group size
079:     * that the given position belongs to.
080:     */
081:     private int getGroupSize(char[][] board, int x, int y) {
082: 
083:         int groupSizeVer = 1;  // Size of Vertical group
084:         int groupSizeHor = 1;  // Size of Horizontal group
085: 
086:         int x1;
087:         int y1;
088: 
089:         char target = board[y][x];
090: 
091:         // Check Up
092:         x1 = x;
093:         y1 = y - 1;
094:         while ((y1 >= 0) && (board[y1][x1] == target)) {
095:             y1--;
096:             groupSizeVer++;
097:         }
098: 
099:         // Check Down
100:         x1 = x;
101:         y1 = y + 1;
102: 
103:         while ((y1 < board_height) && (board[y1][x1] == target)) {
104:             y1++;
105:             groupSizeVer++;
106:         }
107: 
108:         // Check Left
109:         x1 = x - 1;
110:         y1 = y;
111:         while ((x1 >= 0) && (board[y1][x1] == target)) {
112:             x1--;
113:             groupSizeHor++;
114:         }
115: 
116:         // Check Right
117:         x1 = x + 1;
118:         y1 = y;
119:         while ((x1 < board_width) && board[y1][x1] == target) {
120:             x1++;
121:             groupSizeHor++;
122:         }
123: 
124:         return Math.max(groupSizeVer, groupSizeHor);
125: 
126:     }
127: }
Notes:

The problem can be solved using a brute force algorithm. Loop through each row and column of the board, swap the gem with it's neighbor to the right and below, and see if it results in a group of 3 or more in a row being created. We only swap to the right and down in order to avoid double-counting moves.

First, I suggest copying the String[] into a 2-dimensional character array. This makes opearations like swapping characters much easier. I hate mixing array indexes with .charAt(). It's easy enough to convert to the far more useful char[][], and since memory is much of a concern here, there's no reason not to. This is handled on lines 17-23.

Next, we entered a nested loop that iterates over each row, and then each column within the row. So long as we're not at the right-edge, swap the current position with the one to it's right. Then, getGroupSize() is called to see if a large enough group was created. getGroupSize() may need to be called for both the current position, and the swap position. We then swap the gems back to their original posistion, and check to see if a downward swap works, again checking to ensure that we're not already on the bottom row, and taking care to swap the gems back when we're done. The number of swaps that result in a large enough group is tallied, and returned at the end.

The swapGems() method does exactly what you'd expect - it swaps the values at the two given locations.

getGroupSize() returns the size of the largest group, wether it be horizontal or vertical, at the current position. It works by just moving from the start position up, then down, counting each position until it no longer matches the value at the original position, or reaches an edge. The same is done horizontally, and the larger value is returned.

All in all, this was pretty easy for a Division 2 - 1000 point problem.

Friday, September 26, 2014

BaseMystery

Problem:

TopCoder Problem Statement - BaseMystery

Overview:

Determine which bases a given equation is valid in.

Java Source:
01: import java.util.ArrayList;
02: import java.util.List;
03: 
04: public class BaseMystery {
05: 
06:     private static final int MAX_BASE = 20;
07: 
08:     public int[] getBase(String equation) {
09: 
10:         // Saves all of the validBases as they're discovered.
11:         List validBases = new ArrayList<>();
12: 
13:         // Try each base from 2 to MAX_BASE
14:         for (int base = 2; base <= MAX_BASE; base++) {
15:             if (isLegal(base, equation)) {
16:                 validBases.add(base);
17:             }
18:         }
19: 
20:         // Convert the List to the expected return type int[]
21:         int[] ret = new int[validBases.size()];
22:         int index = 0;
23: 
24:         for (int i : validBases) {
25:             ret[index++] = i;
26:         }
27: 
28:         return ret;
29:     }
30: 
31:     private boolean isLegal(int base, String equation) {
32: 
33:         // Splits the equation up into it's three parts.
34:         String[] s = equation.split("[+=]");
35: 
36:         int addend1;
37:         int addend2;
38:         int sum;
39: 
40:         // Let the Integer class do all the hard work for you!
41:         try {
42:             addend1 = Integer.parseInt(s[0], base);
43:             addend2 = Integer.parseInt(s[1], base);
44:             sum = Integer.parseInt(s[2], base);
45: 
46:         } catch (NumberFormatException e) {
47: 
48:             /*
49:             * An exception is thrown if the number format is invalid for the
50:             * given base.  i.e. a 2 in base-2 or a G in base-16
51:             */
52:             return false;
53:         }
54: 
55:         return (addend1 + addend2) == sum;
56:     }
57: }
Notes:

This is a very easy Divison 2 - 500 point problem, if you let the language do all of the hard work. All you need to do is loop through the possible bases, from 2 up to the limit of 20, and check to see if the equation is valid. To be valid, it must not contain any invalid digits for the given base, and the equation must be true.

isLegal() begins by splitting the equation up into its two addends and it's sum. This is done easily with the split method on line 34. The parameter "[+=]" causes it to split on both the + and = character, thus dividing the equation into three pieces.

Knowing that the Integer class provides a parseInt() method that can interpret different bases makes the rest of the problem a piece of cake. Just allow it to do its thing, and catch any NumberFormatExceptions that it might throw.

Finally, just check to see that that equation evaluates to true.

Thursday, September 25, 2014

Tire Rotation

Problem:

TopCoder Problem Statement - TireRotation

Overview:

Given an initial state, determine the number of tire rotations needed to reach the current state.

Java Source:
01: public class TireRotation {
02:
03:  public int getCycle(String initial, String current) {
04:
05:         // Start at phase 1 and the initial pattern.
06:         int phase = 1;
07:         String s = initial;
08:
09:         /*
10:         * Loop until we either match the current pattern, or have cycled
11:         * through all 4 phases.
12:         */
13:         while ((phase < 5) && (!s.equals(current))) {
14:             s = rotateTires(s);
15:             phase++;
16:         }
17:
18:         /*
19:         * If phase is > 4, then the pattern was invalid, return -1.
20:         * Otherwise return phase.
21:         */
22:         return (phase > 4) ? -1 : phase;
23:     }
24:
25:     /*
26:     * Returns a String representing the new tire pattern after performing
27:     * a rotation.
28:     * The tire in:
29:     * position 1, c[0] receives the tire from position 4, charAt(3)
30:     * position 2, c[1] receives the tire from position 3, charAt(2)
31:     * position 3, c[2] receives the tire from position 1, charAt(0)
32:     * position 4, c[3] receives the tire from position 2, charAt(1)
33:     */
34:     private static String rotateTires(String s)  {
35:
36:         char[] c = new char[4];
37:
38:         c[0] = s.charAt(3);
39:         c[1] = s.charAt(2);
40:         c[2] = s.charAt(0);
41:         c[3] = s.charAt(1);
42:
43:         return new String(c);
44:     }
45: }
Notes:

There's just two things to take care of to solve this problem, both of which are very easy. First, write a method that performs the tire rotation and returns the results. And second, loop through the rotations until a match is found, or we've exhausted all possible configurations.

The while loop on line 13 calls rotateTires() and checkes the result. The loop terminates when a match is found, or if phase becomes greater than 4 - meaning that there is no possible solution.

The rotateTires() method takes a String and returns a new String representing the tire pattern after a rotation. It simply creates an array to store the new values, and maps the old positions into their proper new place. Just make sure you map in the right direction and offset everything by 1.

Monday, September 8, 2014

GoodSubset

Problem:

TopCoder Problem Statement - GoodSubset

Overview:

Determine all combinations of an array that when multiplied together equal a given value.

Java Source:
001: import java.util.ArrayList;
002: import java.util.Collection;
003: import java.util.List;
004: 
005: public class GoodSubset {
006: 
007:     /*
008:     * Stores a list of Integers along with their product.  Avoids having
009:     * to muliply the Integers together multiple times to get their product.
010:     * This class was added after the solution was working in an attempt to
011:     * improve performace.  A lot of time was being spent re-calculating
012:     * the products of these lists.
013:     * Note: I don't think it helped much...
014:     */
015:     class ListAndProduct {
016:         List ints;
017:         int product;
018: 
019:         ListAndProduct(List ints, int product)  {
020:             this.ints = ints;
021:             this.product = product;
022:         }
023:     }
024: 
025:     // Reset count each time it reaches this value.
026:     public static final int MOD_VALUE = 1_000_000_007;
027: 
028: 
029:     /*
030:     * The method called by the tests.  Obtains a Collection of ListAndProduct
031:     * objects, and then counts the number of items whose product equals
032:     * goodValue.
033:     */
034:     public int numberOfSubsets(int goodValue, int[] d) {
035: 
036:         if (d.length == 0) return 0;
037: 
038:         Collection possibleGoodSubsets =
039:                 getPossibleGoodSubsets(goodValue, d, 0);
040: 
041:         int count = 0;
042: 
043:         for (ListAndProduct lap : possibleGoodSubsets) {
044: 
045:             if (goodValue == lap.product) {
046:                 count++;
047:                 if (count == MOD_VALUE) count = 0;
048:             }
049: 
050:         }
051: 
052:         return count;
053: 
054:     }
055: 
056:     /*
057:     * Returns a Collection of ListAndProduct objects.  The product of of
058:     * each item will be a factor of goodValue.
059:     */
060:     private Collection getPossibleGoodSubsets(
061:             int goodValue, int[] d, int index) {
062: 
063:         Collection possibleGoodSubSets;
064: 
065:         /*
066:         * If this is the last element in d[] the create the return list,
067:         * otherwise, obtain it by recursively calling getPossibleSubsets using
068:         * the next index.
069:         */
070:         if (index == (d.length - 1)) {
071:             possibleGoodSubSets = new ArrayList<>();
072: 
073:         } else {
074:             possibleGoodSubSets = getPossibleGoodSubsets(
075:                     goodValue, d, index + 1);
076:         }
077: 
078:         // Only interested in numbers that are factors of goodValue.
079:         if (goodValue % d[index] == 0) {
080: 
081:             /*
082:             * Contains new items to be added to possibleGoodSubSets.  Don't
083:             * want to modify that list until the for loop is done though.
084:             */
085:             List toAdd = new ArrayList<>();
086: 
087:             for (ListAndProduct lap : possibleGoodSubSets) {
088: 
089:                 /*
090:                 * For each of the items currently in the possibleGoodSubSets
091:                 * Collection, does multiplying that product by d[index] also
092:                 * result in a factor of goodValue?  If so, note it so it gets
093:                 * added to the Collection.
094:                 */
095:                 long product = (long) d[index] * (long) lap.product;
096: 
097:                 if ((goodValue % product) == 0) {
098: 
099:                     /*
100:                     * Create and store a new ListAndProduct object using the
101:                     * previous list of integers, and the current index.  Store
102:                     * the list along with its product.
103:                     */
104:                     List newInts = new ArrayList<>();
105:                     for (int i : lap.ints) {
106:                         newInts.add(i);
107:                     }
108:                     newInts.add(d[index]);
109:                     toAdd.add(new ListAndProduct(newInts, (int) product));
110:                 }
111: 
112:             }
113: 
114:             /*
115:             * possibleGoodSubSets could not be modified within the above for
116:             * loop.  So now, we can add all the items from toAdd into it.
117:             */
118:             for (ListAndProduct lap : toAdd) {
119:                 possibleGoodSubSets.add(lap);
120:             }
121: 
122:             // The current index is a factor of goodValue, so add that in too.
123:             List l = new ArrayList<>();
124:             l.add(d[index]);
125:             possibleGoodSubSets.add(new ListAndProduct(l, d[index]));
126:         }
127: 
128:         return possibleGoodSubSets;
129: 
130:     }
131: }
Notes:

First, a disclaimer. The given code works, but fails one of the timing tests. The constraints are that the solution must complete in under 2 seconds. The code above passes all the tests except test #32. It give the correct answer, but takes about 25 seconds to complete. I've tried a few techniques to bring this time down without success. If you've got any ideas, I'd like to hear them.

The solution uses a technique know as dynamic programming. Here, we'll solve for the last element in the array; and then using what we've computed, work backward toward the beginning of the array. I'll explain how it works, by walking through an example.

For test3, the input array is { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } and goodValue = 12.

The idea is to start at the right side of the array, and only consider elements or products that are factors of goodValue. Items matching our criteria are stored in a Collection of Lists of Integers called possibleGoodSubsets. So starting at 12: 12 is a factor of 12, so add it to possibleGoodSubsets. 11, 10, 9, 8, and 7 are not factors of 12, so we skip past those.

6 is a factor of 12, so add that. However 6 * 12 = 72 which is not a factor, so we don't add 6,12 to the List.

5 is not a factor, so skip it. 4 is a factor, so we'll add it just like 6 was.

3 is a factor of 12. Also 4 is already in our list, and 3 * 4 = 12 is a factor, so we'll add not only 3; but also 3,4

The table below shows how possibleGoodSubsets grows as we work backward through the array.

Value possibleGoodSubsets
12 {{12}}
11 {{12}}
10 {{12}}
9 {{12}}
8 {{12}}
7 {{12}}
6 {{12}, {6}}
5 {{12}, {6}}
4 {{12}, {6}, {4}}
3 {{12}, {6}, {4}, {3,4}, {3}}
2 {{12}, {6}, {4}, {3,4}, {3}, {6,2}, {3,2}, {2}}
1 {{12}, {6}, {4}, {3,4}, {3}, {6,2}, {3,2}, {2}, {12,1}, {6,1}, {4,1}, {3,4,1}, {3,1}, {6,2,1}, {3,2,1}, {2,1}, {1}}

The collection given at Value 1 is what will be returned to the numOfSubsets() method. It then looks for elements whose product equals goodValue. In this case {{12}, {3,4}, {6,2}, {12,1}, {3,4,1}, {6,2,1}}

This works great so long as not too many elements of the input array are factors of goodValue. In test32 all 100 of the items in the input array are factors, and many of those number, when multiplied together produce factors. So the size of possibleGoodSubsets really explodes in that case.

One thing I noticed when profiling the code was this it was spending most of its time computing the products. To alieviate this, I introduced the class ListAndProduct so that I could store a List of Integers and it's product together, and thus avoid having to calculate the product of that list over and over again. Unfortunately, the effectiveness of that chage was minimal.

I think this is a good algorithm, and does a good job of illustrating techniques of dynamic programming. So, I'm not really interested in re-writing it. But, if you have ideas that can help get this under the 2 second limit for the worst case scenarios, I'd like to hear it.

Saturday, September 6, 2014

PotentialGeometricSequence

Problem:

TopCoder Problem Statement - PotentialGeometricSequence

Overview:

Calculate the number of sub-sequences of an array that may generate a geometric sequence.

Java Source:
01: public class PotentialGeometricSequence {
02: 
03:     public int numberOfSubsequences(int[] d)  {
04: 
05:         int count = 0;
06: 
07:         /*
08:         * j bounces back and forth between i and d.length as i
09:         * moves from 0 to d.length.
10:         * This gives us every possible contiguous subsequence.
11:         */
12:         for (int i = 0; i < d.length; i++)  {
13:             for (int j = i; j < d.length; j++)  {
14:                 if (checkSequence(i, j, d))  {
15:                     count++;
16:                 }
17:             }
18:         }
19: 
20:         return count;
21:     }
22: 
23:     /*
24:     * Checks to see if the values in d[] decrease by the same amount
25:     * for each step from j down to i.  If so, return true; otherwise false.
26:     * For example, if the values in d[] are {3,4,5} it will return true
27:     * because we decrease by 1 to go from 5 to 4, and then by 1 again to
28:     * go from 4 to 3.
29:     */
30:     private static boolean checkSequence(int i, int j, int[] d)  {
31: 
32:         /*
33:         * If there are 0 or 1 steps between i and j, then it must be true
34:         */
35:         if ((j - i) <= 1) return true;
36: 
37:         /*
38:         * Get the difference between the two right-most values.  Each step
39:         * from here on must differ by this same amount.
40:         */
41:         int diff = d[i + 1] - d[i];
42: 
43:         /*
44:         * Work right to left from j down to i.  Ensure that each step
45:         * differs by diff
46:         */
47:         for (int x = i; x < j; x++)  {
48:             if ((d[x] + diff) != (d[x+1]))  {
49:                 return false;
50:             }
51:         }
52: 
53:         return true;
54:     }
55: 
56: }
Notes:

Possibly the most confusing problem statement I've come across so far on TopCoder. The solution above passes all of the system tests, but I still have no idea what the problem is asking for.

My advice is to ignore almost everything in the problem statement and notes. The mention of possible geometric sequences, trailing zeros in the binary representation of the number, answers being positive or negative, etc. are all irrelevant. There is no need to examine the binary representation of any numbers, or calculate geometric sequences. Here, in one sentence, is what you need to do:

For each possible sub-sequence in d[], determine if the values are evenly spaced. That's it!

Any sub-sequence of size 1 or 2 will be evenly spaced by definition, and therefore included in the count. For larger sub-sequences, calculate the step size by subtraction: d[x+1] - d[x]. Now, test to see if each d[i] + step = d[i + 1] for all values of i between x and j.

The following tables illustrates the 37 possible sub-sequences expected by Example #4

Input array. Given as parameter d[]
Index in d[] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Value of d[x] 1 3 5 5 5 5 64 4 23 2 3 4 5 4 3


Subsequences that meet the problem's criteria
count Start Index End Index Length
1001
2111
3221
4331
5441
6551
7661
8771
9881
10991
1110101
1211111
1312121
1413131
1514141
16012
17122
18232
19342
20452
21562
22672
23782
24892
259102
2610112
2711122
2812132
2913142
30023
31243
32353
339113
3410123
3512143
36254
379124

In the bottom table, we see each possible sub-sequence of lenght 1 or 2. Also included are all subsequences where the step from one index to the next is equal. For example, for count #37 d[9] = 2 and d[10] = 3. A step size of 1. d[11] and d[12] continue this pattern, but d[13] breaks it. Therefore we include the subsequence from d[9] to d[12].

RunningAroundPark

Problem:

TopCoder Problem Statement - RunningAroundPark

Overview:

Count the minimum number of laps a runner could have made around a loop based on the trees they remember seeing.

Java Source:
01: public class RunningAroundPark {
02:  
03:  public int numberOfLap(int N, int[] d) {
04: 
05:         int previousTree = N;
06:         int numLaps = 0;
07: 
08:         for (int i = 0; i < d.length; i++)  {
09: 
10:             // When we see a smaller (or equal) numbered tree, increment numLaps
11:             if (d[i] <= previousTree)  {
12:                 numLaps++;
13:             }
14: 
15:             previousTree = d[i];
16:         }
17: 
18:         return numLaps;
19:     }
20: }
Notes:

We need to count the number of inversions in the input array. That is, each time we encounter a number that is smaller than (or equal to) the previous number, increase the number of laps.

Start by setting previousTree to be the largest numbered tree in the park, the parameter N. Then loop through each of the elements in d[]. If the current element is less than or equal to previousTree, increment the number of laps. At each step, update previousTree to the new current value.

Thursday, September 4, 2014

LongWordsDiv2

Problem:

TopCoder Problem Statement - LongWordsDiv2

Overview:

Determine if a string meets a given set of criteria.

Java Source:
01: public class LongWordsDiv2 {
02: 
03:     public String find(String word) {
04:         return (checkWord(word)) ? "Likes" : "Dislikes";
05:     }
06: 
07:     private boolean checkWord(String word) {
08: 
09:         for (int i = 0; i < word.length(); i++) {
10:             // Check for all upper case
11:             if ((word.charAt(i) < 'A') || (word.charAt(i) > 'Z')) {
12:                 return false;
13:             }
14:         }
15: 
16:         // Check for next character matches
17:         for (int i = 0; i < (word.length() - 1); i++) {
18:             if (word.charAt(i) == word.charAt(i + 1)) {
19:                 return false;
20:             }
21:         }
22: 
23:         /*
24:         * Check for pattern xyxy
25:         * */
26:         for (int i = 0; i < word.length() - 1; i++) {
27:             for (int j = i + 1; j < word.length(); j++) {
28:                 String regex = ".*" + word.charAt(i) + ".*" + word.charAt(j)
29:                         + ".*" + word.charAt(i) + ".*" + word.charAt(j) + ".*";
30:                 if (word.matches(regex)) {
31:                     return false;
32:                 }
33:             }
34:         }
35: 
36:         return true;
37:     }
38: }
Notes:

There are three conditions that we need to check:

  1. Each letter must be an uppercase, english letter.
  2. There are no consecutive letters
  3. There are no patters of the form xyxy - where are and why are any (not necessarily distinct) seqquences of characters

The first condition is actually unnecessary since the problem's constraints guarantee that each character will be an uppercase English letter. Nevertheless, I've choosen to include the check. Note that, technically, we can't use Character.isUpperCase() to test the character, since isUpperCase() will return true for some non-English characters. But, again, it's sort of a moot point.

For the second condition, we just loop through each character and look at the next character. Just be careful to stop the loop one character early, so that looking at the next position is not out of bounds.

The last condition is the trickiest, but it's not that hard if you allow regular expressions expressions to do all the work. We build the following regular expression .*x.*y.*x.*x.* and if our word matches that, return false. We do however need two nested for loops in order to check each letter with each possible following letter.

Wednesday, September 3, 2014

ProfitCalculator

Problem:

TopCoder Problem Statement - ProfitCalculator

Overview:

Calculate the profit margin given an array of items.

Java Source:
01: public class ProfitCalculator {
02: 
03:     public int percent(String[] items) {
04: 
05:         // Holds running totals of the customer and stores costs.
06:         float totalCustCost = 0f;
07:         float totalStoreCost = 0f;
08: 
09:         for (String s : items) {
10: 
11:             // Splits the item into customer and store components
12:             String[] costs = s.split(" ");
13: 
14:             totalCustCost += Float.parseFloat(costs[0]);
15:             totalStoreCost += Float.parseFloat(costs[1]);
16:         }
17: 
18:         float margin = ((totalCustCost - totalStoreCost) / totalCustCost) * 100;
19: 
20:         return (int) margin;
21:     }
22: }
Notes:

Not much to this problem. totalCustCost and totalStoreCost are created to keep a running total of the customer and stores costs. We loop through each of the items in the input array, and update the totals as each item is processed. At the end just use the formulat ((customer cost - store cost ) / customer cost) * 100 to get the final profit.

When processing each item, the String method split() is used to divide the customer and store portions. Then Float.parseFloat() is used to convert the string representation into a float.

The return value must be an int, so we must cast this since a float to an int could lose precision. However, fortunately, that's just what the problem statement calls for.

SuperRot

Problem:

TopCoder Problem Statement - SuperRot

Overview:

Extend the rot13 function to include lower case characters and numerals.

Java Source:
01: public class SuperRot {
02: 
03:  public String decoder(String message) {
04: 
05:         char[] retMessage = new char[message.length()];
06: 
07:         int x = 0;
08: 
09:         for (int c : message.toCharArray())  {
10: 
11:             if (Character.isUpperCase(c))  {
12:                 c = ((c - 'A' + 13) % 26) + 'A';
13: 
14:             } else if (Character.isLowerCase(c))  {
15:                 c = ((c - 'a' + 13) % 26) + 'a';
16: 
17:             } else if (Character.isDigit(c))  {
18:                 c = ((c - '0' + 5) % 10) + '0';
19: 
20:             }
21: 
22:             retMessage[x++] = (char) c;
23:         }
24: 
25:         return new String(retMessage);
26:  }
27: }
Notes:

The if statement on lines 9 through 20 determines the type of character (Upper Case, Lower Case, or Digit) and takes the appropriate action. There's basically four steps in doing the conversion:

  1. Subtract the base character ('A', 'a', or '0') from the current character.
  2. Add the rotation value (13 for characters, 5 for digits).
  3. Mod the number by the size of the current set (26 for characters, 10 for digits)
  4. Add the base character ('A', 'a', or '0') back on.

That's it. Just repeat for each character in the input String.

CatsOnTheLineDiv2

Problem:

TopCoder Problem Statement - CatsOnTheLineDiv2

Overview:

Try to spread a bunch of cats out along a line in the given amount of time such that no two cats occupy the same position.

Java Source:
001: import java.util.ArrayList;
002: import java.util.Collections;
003: import java.util.List;
004: 
005: public class CatsOnTheLineDiv2 {
006: 
007:     public static String PASS = "Possible";
008:     public static String FAIL = "Impossible";
009: 
010:     /*
011:     * This class ties together a position with the number of cats at that
012:     * position.  It also implements Comparable so we can sort them.  After
013:     * sorting, we can go through the positions from left to right.
014:     */
015:     class Position implements Comparable {
016:         int position;
017:         int numCats;
018: 
019:         Position(int position, int numCats) {
020:             this.position = position;
021:             this.numCats = numCats;
022:         }
023: 
024:         // Compare based on position.  There should be no duplicates.
025:         @Override
026:         public int compareTo(Position o) {
027:             if (this.position < o.position) return -1;
028:             if (this.position > o.position) return 1;
029:             return 0;
030:         }
031:     }
032: 
033:     public String getAnswer(int[] position, int[] count, int time) {
034: 
035:         List initialLine = new ArrayList<>();
036: 
037:         int numCats = 0;
038: 
039:         /*
040:         * For each element of the position and count arrays, create a new
041:         * Position object and adds it to initialLine.  Also counts the
042:         * total number of cats.
043:         */
044:         for (int i = 0; i < position.length; i++) {
045:             initialLine.add(new Position(position[i], count[i]));
046:             numCats += count[i];
047:         }
048: 
049:         Collections.sort(initialLine);
050: 
051:         // Calculate the size of the line after allowing that cats to move.
052:         int minPos = initialLine.get(0).position - time;
053:         int maxPos = initialLine.get(initialLine.size() - 1).position + time;
054:         int numPositions = maxPos - minPos + 1;
055: 
056:         // See if there are more cats than positions.  Maybe we can quit early.
057:         if (numCats > numPositions) return FAIL;
058: 
059:         /*
060:         * Holds the positions that have a cat after they've moved.  Note that
061:         * the array cannont have negative indexes, so we'll need to shift
062:         * the position over by minPos in order to map it.
063:         * Also, when done, each position can only have 1 cat (or zero), so we
064:         * can use an array of booleans instead of ints.
065:         */
066:         boolean[] newLine = new boolean[numPositions];
067: 
068:         /*
069:         * Loop through each Position (working left to right, since they were
070:         * sorted).  At each Position, loop through the number of cats.  For
071:         * each cat, try to find a final position for them.  If a position
072:         * cannot be found, then return FAIL.
073:         */
074:         for (Position p : initialLine) {
075:             for (int i = 0; i < p.numCats; i++) {
076: 
077:                 /*
078:                 * Note (p.position - minPos).  This shifts all the values over
079:                 * so they are zero-based.
080:                 */
081:                 if (!findPositionForCat(newLine, p.position - minPos, time))
082:                     return FAIL;
083:             }
084:         }
085: 
086:         // If we've found positions for all the cats, return PASS.
087:         return PASS;
088:     }
089: 
090:     /*
091:     * Attempts to find a position to place the cat.  Returns true if a position
092:     * can be found; otherwise false.
093:     * We'll move the cat to the furthest position left as possible given the
094:     * amount of time.  If that position is full (true), then keep looking to
095:     * the right.
096:     */
097:     private static boolean findPositionForCat(boolean[] line, int p, int time) {
098: 
099:         for (int i = (p - time); i <= (p + time); i++) {
100:             if (!line[i]) {
101:                 line[i] = true;  // Mark the position is occupied.
102:                 return true;
103:             }
104:         }
105: 
106:         return false;
107:     }
108: 
109: }
Notes:

The strategy is to work from left to right and move each cat as far to the left as they can in the given amount of time. If that position is already taken, then try the next position to the right. If any cat cannot find a suitable position, then we declare the problem to be impossible.

For example, lets say we have 2 cats (labeled A and B) at position zero, and three cats (labeled C, D and E) at position one. time = 2.

E
B D
A C
-2 -1 0 1 2 3

First, process the cats at position 0. Cat B can move two spaces to the left (time is 2, and position -2 is empty). Next we try to move cat A two spaces to the left, but that's already occupied (by B), so A goes in the first available space to the right.

E
D
B A C
-2 -1 0 1 2 3

Now we're done with position 0, and move on to position 1. Cat E cannot move into position -1 because it's occupied by cat A, so E moves to position 0. Cat D stays where it is, and cat C moves one position to the right.

B A E D C
-2 -1 0 1 2 3

It's important to note that the initial positions and final positions are kept in two separate arrays (initialLine and newLine). That's how cat D could stay put even though cat C had not been moved yet. The initial array is represented as a List of Position objects, where Position objects hold the location and number of cats at that location. The final position is represented by the boolean array newLine - either a cat has been placed there already or not. All indexes of newLine are initially set to false and become true when a cat is placed there.

On lines 52-55 we calculate the size needed for the newLine array. The cats can potentially move time positions to the left of the minimum starting position, or to the right of the maximum starting position. Be careful when mapping these positions between initialLine and newLine. We need to shift the values over so that the left most possible position aligns with the 0 index of newLine.

Since it's easy enough to count the number of cats at the start, and we now know the number of possible locations; I choose to add a check to see if the number of cats exceeds the number of locations. It's good to quit early and save a lot of computation if we can.

Note that we could have choosen to move all the cats to the right. The sort order on line 49, along with the directions on the for loop at line 99 would need to be reversed; but that's all.

As a final comment, I'll add that this seemed tougher than the typical Division 2 - Level 2 problem. If you don't see the algorithm, you're not likely to get done in time. I'd be interested to see if anyone solved this by working one time interval at a time. That is, something like:

  while (time > 0)  {
      moveCats();
      if (isSatisfied()) return "Possible";
      time--;
  }
  return "Impossible";

I spent too much time on that line of thinking before stepping back and trying another approach.

TaroGrid

Problem:

TopCoder Problem Statement - TaroGrid

Overview:

Count the largest number of consecutive colors by column in a grid.

Java Source:
01: public class TaroGrid {
02:  
03:  public int getNumber(String[] grid) {
04: 
05:         // Get the dimensions of the grid
06:         int numRows = grid.length;
07:         int numCols = grid[0].length();
08: 
09:         // Set to a small number to start.
10:         int maxVal = Integer.MIN_VALUE;
11: 
12:         // Step through each column.
13:         for (int col=0; col < numCols; col++)  {
14: 
15:             int count = 0;
16: 
17:             // Take a peek at the first color in the column
18:             char currentColor = grid[0].charAt(col);
19: 
20:             for (int row = 0; row < numRows; row++)  {
21: 
22:                 if (grid[row].charAt(col) == currentColor)  {
23:                     count++;
24: 
25:                 } else  {
26: 
27:                     // Start a new color
28:                     currentColor = grid[row].charAt(col);
29:                     maxVal = Math.max(maxVal, count);
30:                     count = 1;
31:                 }
32:             }
33: 
34:             // Don't forget.  The longest streak could be the bottom one.
35:             maxVal = Math.max(maxVal, count);
36:         }
37: 
38:         return maxVal;
39:  }
40: }
Notes:

Somehow, this problem seems like it would be easier it we were counting the colors across rows instead of down columns. But, no matter, the problem is not difficult if you can keep your directions straight.

To help keep things clear, I set numRows and numColumns on rows 6 and 7. This makes it much easier than trying to keep track of them using grid.length and grid[0].length().

Next, we set maxVal to the smallest possible integer. Then, on lines 29 and 35 we'll potentially update that using Math.max(). This pattern comes up in almost every problem, and this is the cleanest way I've found to write it.

Then, there are two nested for loops. The outer loops across the columns, and the inner loops down the rows in each column. At the start of a new column, we set reset count, and set the current color to be the first color in the column. Then we go down the column, incrementing count each time the current position matches currentColor. When they no longer match, cut off the current streak by updating currentColor, resetting count, and updating the maxVal if this streak is longer than any we've seen thus far.

After we've looped through all columns, return the maximum value found.