Intersect

Problem:

TopCoder Problem Statement - Intersect

Overview:

Give the area where a set of rectangles intersect.

Java Source:

01: public class Intersect {
02: 
03:     class Rectangle {
04: 
05:         final int left;  // X coordinate of left edge
06:         final int right;
07:         final int top;  // Y coordinate of top edge
08:         final int bottom;
09: 
10:         public Rectangle(int x1, int y1, int x2, int y2) {
11: 
12:             /*
13:             * We don't know if the first point is the top-left or bottom-right
14:             * corner.  But we can assign the left edge to the smaller of the
15:             * x values, and the right edge to the larger.  Same goes for top
16:             * and bottom
17:             */
18:             this.left = Math.min(x1, x2);
19:             this.right = Math.max(x1, x2);
20:             this.top = Math.max(y1, y2);
21:             this.bottom = Math.min(y1, y2);
22:         }
23: 
24:         /*
25:         * Returns a rectangle that is the intersection of this rectangle
26:         * and the paramter r.  Returns null if there is no intersection.
27:         */
28:         public Rectangle getIntersection(Rectangle r)  {
29: 
30:             /*
31:             * If the right edge of one rectangle is >= the left edge of the
32:             * other, then there is no intersection.  Return null.  Same goes
33:             * for the other three edges.
34:             */
35:             if (r.left >= right) return null;
36:             if (r.right <= left) return null;
37:             if (r.top <= bottom) return null;
38:             if (r.bottom >= top) return null;
39: 
40:             /*
41:             * The intersection is given by the:
42:             * right-most left edge
43:             * highest bottom edge
44:             * left-most right edge
45:             * lowest top edge
46:             */
47:             return new Rectangle(
48:                     Math.max(left, r.left),
49:                     Math.max(bottom, r.bottom),
50:                     Math.min(right, r.right),
51:                     Math.min(top, r.top));
52:         }
53: 
54:         public int getArea() {
55:             return ((right - left) * (top - bottom));
56:         }
57:     }
58: 
59:     public int area(int[] x, int[] y) {
60: 
61: 
62:         /*
63:         * Start with the largest possible rectangle.  Then for each rectangle
64:         * reduce it to the intersection.  If the intersection is ever null,
65:         * return 0.
66:         */
67:         Rectangle common = null;
68: 
69:         for (int i=0; i < x.length - 1; i += 2)  {
70:             Rectangle r = new Rectangle(x[i], y[i], x[i+1], y[i+1]);
71: 
72:             if (common == null)  {
73:                 common = r;
74:             } else  {
75:                 common = common.getIntersection(r);
76:                 if (common == null) return 0;
77:             }
78:         }
79: 
80:         return common.getArea();
81:     }
82: }

Notes:

First, a Rectangle class is created to handle much of the work. This class provides a constructor, to take the input in a convenient manner; a method to get the Area of the Rectangle, and a method to return a new Rectangle that is the intersection of the current rectangle and the rectangle given as a parameter.

Then, we'll use a rectangle named common to represent the intersection of all the rectangles given. Initially, this gets set to the fist rectangle processed. Then with each additional rectangle, common becomes the intersection of itself and the new rectangle.

After all the input has been processed, return the area of the Rectangle common.

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

Substitute

Problem:

TopCoder Problem Statement - Substitute

Overview:

Given a key, decode a String.

Java Source:

01: public class Substitute {
02: 
03:     public int getValue(String key, String code) {
04: 
05:         int result = 0;
06: 
07:         for (int i = 0; i < code.length(); i++) {
08: 
09:             int p = key.indexOf(code.charAt(i));
10: 
11:             if (p >= 0) {
12:                 result *= 10;
13:                 result += (p + 1) % 10;
14:             }
15: 
16:         }
17: 
18:         return result;
19: 
20:     }
21: }

Notes:

The solution begins by initializing an int (result) to zero. Each time we encounter a character that is in key, we'll multiply result by 10, and then add the new number. This is a pretty standard way of parsing characters into integers.

The for loop on line 7 iterates through each character in the code. Line 9 sets p to the index in key of the current character. If that character does not appear in the key, indexOf() will return -1, and we'll move on to the next character.

If indexOf() returns a non-negative index (the current character in code appears in the key), then we use that as the next digit. Note howerver, that the values are off by one, so we need to add one to the value returned by indexOf() and also do a mod 10. This maps index 0 to 1, index 1 to 2, ... and index 9 to 0 (10 mod 10).

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

ThePriceIsRight

Problem:

TopCoder Problem Statement - ThePriceIsRight

Overview:

Find the maximum length of an increasing sequence in a series of numbers. Also determine the number of sequences of that length.

Java Source:

01: public class ThePriceIsRight {
02: 
03:     public int[] howManyReveals(int[] prices) {
04: 
05:         // Holds the longes sequence that ends at this prices.
06:         int[] maxLength = new int[prices.length];
07: 
08:         // Holds the nubmer of ways to reach that max length
09:         int[] waysToReachMaxLength = new int[prices.length];
10: 
11:         // out[0] = maxLength, out[1] = number of ways to do it.
12:         int[] out = new int[2];
13: 
14:         for (int i = 0; i < prices.length; i++) {
15: 
16:             int longest = 0;
17: 
18:             /*
19:             * Look for the longest sequence to the left that ends on a price
20:             * that is less than the current price.
21:             */
22:             for (int j = 0; j < i; j++) {
23:                 if (prices[j] < prices[i]) {
24:                     longest = Math.max(longest, maxLength[j]);
25:                 }
26:             }
27: 
28: 
29:             /*
30:             * Look to the left for the nubmer of ways to reach the longest
31:             * sequence.  If the length equals the current length, and
32:             * it's prices is less than the current price, then count it as
33:             * a way to reach the current sequence.
34:             */
35:             for (int k = 0; k < i; k++) {
36:                 if ((maxLength[k] == longest) && (prices[k] < prices[i])) {
37:                     waysToReachMaxLength[i] += waysToReachMaxLength[k];
38:                 }
39:             }
40: 
41:             // There's always at least 1 one to reach the max length.
42:             if (waysToReachMaxLength[i] == 0) waysToReachMaxLength[i] = 1;
43: 
44:             /*
45:             * We've found the longest by looking at the previous soutions.  Now
46:             * add on the current index.
47:             */
48:             maxLength[i] = 1 + longest;
49: 
50:             // Update the max length found if necessary.
51:             out[0] = Math.max(out[0], maxLength[i]);
52:         }
53: 
54:         /*
55:         * Add up all the ways to reach the maximum length.
56:         */
57:         for (int i = 0; i < prices.length; i++) {
58:             if (maxLength[i] == out[0]) {
59:                 out[1] += waysToReachMaxLength[i];
60:             }
61:         }
62: 
63:         return out;
64:     }
65: }

Notes:

This solution is based on the pseudo-code provided in the topcoder community forums. Found here

We're looking for the longest sequence of increasing numbers. The numbers need not be contiguous. One of the tests gives the prices [39, 88, 67, 5, 69, 87, 82, 64, 58, 61]. Here there are two increasing sequences of length four: 39, 67, 69, 87 and 39, 67, 69, 82. The expected return value is {4,2}.

To solve this, we'll work from left to right through the prices array. For each position, we'll calculate the longest sequence that ends at that position and store that in the maxLength[] array. We also store the number of sequences of that maximum length in the waysToReachMaxLength[] array.

To find the longest sequence that ends at the current position we'll look at positions to the left of the current position. This is a Dynamic Programming technique where we use values that have already been calculated to calculate the next value. The value will be 1 more than the longest sequence to the left, only counting prices that are less than the current price.

Once we know the length of the longest sequence that ends at the current element, we again look to the left, and sum the number of ways to reach any price that shares that maximum length. Again, only considering smaller prices. To illustrate how these two values are calculated, let's walk through using the sample input given above.

Array / Index	0	1	2	3	4	5	6	7	8	9
prices	39	88	67	5	69	87	82	64	58	61
maxLength	?	?	?	?	?	?	?	?	?	?
waysToReachMaxLength	?	?	?	?	?	?	?	?	?	?

The first price is 39. Since there are no previous prices, the longest sequence for index 0 is 1, and there is 1 way to accomplish that.

The price at the next position is 88. To get the longest, we look left and see that the longest sequence with a price less than 88 is 39. 39 has a sequence length of 1, so the length to 88 is 2. There is only one way to achieve the length of 2.

The same applies to the next position, 67. The longest previous sequence with a price less than 67 belongs to 39. Again the length is 2, and there is one way to achieve that length (39 -> 67). Our arrays now look like this:

Array / Index	0	1	2	3	4	5	6	7	8	9
prices	39	88	67	5	69	87	82	64	58	61
maxLength	1	2	2	?	?	?	?	?	?	?
waysToReachMaxLength	1	1	1	?	?	?	?	?	?	?

The next position 5 has no price smaller than it to the left. It's maximum length is therefore 1, and there is 1 way to do it.

Next is 69 at index 4. There are two prices smaller that it (39, and 67). Since 67 ends a sequence of length 2, 69 is added to form a sequence length of 3. Still there is only one way to reach a length of 3 (39 -> 67 -> 69).

The longest sequence to the left of 87 is that belonging to 69. So, 87 gets one more than 69's length. The same goes for the next position, 82. Note that 82, cannot use 87 length of 4, since 87's price is greater. Our arrays now look like:

Array / Index	0	1	2	3	4	5	6	7	8	9
prices	39	88	67	5	69	87	82	64	58	61
maxLength	1	2	2	1	3	4	4	?	?	?
waysToReachMaxLength	1	1	1	1	1	1	1	?	?	?

At index 7, we get a maximum sequence length that can be reached in different ways. Looking left, we see that 39 and 5 both end a sequence of length 1, which is the longest sequence coming into 64. Therefore, we can reach 64 in two ways 39 -> 64, and 5 -> 64.

Similarly, 58, has two ways to choose its maximum length sequence, 39 -> 58 and 5 -> 58.

Finally, 61, has two sequences of length 3: 39 -> 58 -> 61 and 5 -> 58 -> 61. At the end, our arrays look like this:

Array / Index	0	1	2	3	4	5	6	7	8	9
prices	39	88	67	5	69	87	82	64	58	61
maxLength	1	2	2	1	3	4	4	2	2	3
waysToReachMaxLength	1	1	1	1	1	1	1	2	2	2

Last, it's just a matter of summing all the ways to reach the elements that share the maximum length. 87 contributes 1, and 82 contributes another, for a final answer of {4,2}.

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