Wednesday, March 18, 2015

ConvexPolygon

Problem:

TopCoder Problem Statement - ConvexPolygon
Single Round Match 166 Round 1 - Division II, Level Three

Overview:

Calculate the area of a convex polygon.

Java Source:
01: public class ConvexPolygon {
02: 
03:     public double findArea(int[] x, int[] y)  {
04: 
05:         double area = 0.0;
06: 
07:         /*
08:         * Sum the areas of the triangles {0,1,2}, {0,2,3}, ... {0,n-1,n}
09:         */
10:         for (int v = 2; v < x.length; v++)  {
11:             area += areaOfTriangle(x[0], y[0], x[v-1], y[v-1], x[v], y[v]);
12:         }
13: 
14:         return area;
15:     }
16: 
17:     /*
18:     * Given the coordinates of the three vertices, the area of a triangle is
19:     * given by:
20:     *
21:     * area = abs((X1(Y2-Y3) + X2(Y3 - Y1) + X3(Y1-Y2)) / 2)
22:     *
23:     */
24:     private double areaOfTriangle(int x1, int y1,
25:                                   int x2, int y2,
26:                                   int x3, int y3) {
27: 
28:         double term1 = x1 * (y2 - y3);
29:         double term2 = x2 * (y3 - y1);
30:         double term3 = x3 * (y1 - y2);
31: 
32:         double result = (term1 + term2 + term3) / 2.0;
33: 
34:         return Math.abs(result);
35: 
36:     }
37: 
38: }
Notes:

The simple formula for the area of a triangle (A = (b * h) / 2) won't help us much. Instead we use a formula like the one given here

The area of the polygon can be calculated by dividing it up into triangles. For a polygon with n points, the area is the sum of the triangles formed by the points {0,1,2} + {0,2,3} + ... {0,n-1,n}. This becomes obvious is you draw any convex polygon on a piece of paper.

An alternate approach is to carve off a triangle (and calculate its area), and then recursively call findArea() to get the area of the remaining polygon.

BinaryCardinality

Problem:

TopCoder Problem Statement - BinaryCardinality
Single Round Match 166 Round 1 - Division I, Level One
Single Round Match 166 Round 1 - Division II, Level Two

Overview:

Sort an arrray of integers based on their binary cardinality. Binary cardinality is the number of 1's in the binary representation of the number.

Java Source:
01: import java.util.Arrays;
02: import java.util.Comparator;
03: 
04: public class BinaryCardinality {
05: 
06:     private class BinaryCardinalityComparator implements Comparator  {
07: 
08:         /*
09:         * Compares the binary cardinality of the two numbers.  If that's
10:         * equal, then compare the value of the numbers themselves.
11:         */
12:         @Override
13:         public int compare(Integer o1, Integer o2) {
14: 
15:             int c1 = binaryCardinality(o1);
16:             int c2 = binaryCardinality(o2);
17: 
18:             if (c1 < c2) return -1;
19:             if (c2 < c1) return 1;
20: 
21:             return o1.compareTo(o2);
22:         }
23: 
24:         /*
25:         * Counts the number of 1's in the binary representation of the number.
26:         */
27:         public int binaryCardinality(Integer i)  {
28: 
29:             int c = 0;
30: 
31:             while (i > 0)  {
32:                 if ((i & 1) == 1) c++;
33:                 i = i >> 1;
34:             }
35: 
36:             return c;
37:         }
38:     }
39: 
40:     public int[] arrange(int[] numbers) {
41: 
42:         // Convert array of ints to an array of Integer
43:         Integer[] numbersAsIntegers = new Integer[numbers.length];
44: 
45:         for (int i = 0; i < numbers.length; i++)  {
46:             numbersAsIntegers[i] = numbers[i];
47:         }
48: 
49:         // Sort the numbers using our custom Comparator.
50:         Arrays.sort(numbersAsIntegers, new BinaryCardinalityComparator());
51: 
52:         // Convert array of Integer back to array of ints.
53:         int[] result2 = new int[numbers.length];
54: 
55:         for (int i = 0; i < numbers.length; i++)  {
56:             result2[i] = numbersAsIntegers[i];
57:         }
58: 
59:         return result2;
60:     }
61: 
62: }
63
Notes:

The class BinaryCardinalityComparator handles comparing two Integers based on their binary cardinality. This is done by calling binaryCardinality() on each number and checking the results. If the cardinality is the same, then we defer to Integer.compareTo() method to sort the numbers based on value. The binaryCardinality() method counts the number of 1's by examining the right-most bit, and then performing a bit-shift to the right. This loop continues until the value of the number eventually becomes 0.

By implementing our own Comparator, we can now use the built in Arrays.sort() method to sort the numbers. We simply pass an instance of our comparator as a second paramter.

The trouble with our BinaryCardinalityComparator class is that it requires objects (Integer) rather than ints. So, the arrange() method must first convert the given int[] into an Integer[]. It then performs the sort, and finally converts the Integer[] back into an int[].

Workshop

Problem:

TopCoder Problem Statement - Workshop
Single Round Match 166 Round 1 - Division II, Level One

Overview:

Determine the number of triangles that can be formed given a set of lengths.

Java Source:
01: public class Workshop {
02: 
03:     public int pictureFrames(int[] pieces) {
04: 
05:         int count = 0;
06: 
07:         /*
08:         * Loop through all possible combinations of side1, side2, and side3
09:         */
10:         for (int side1 = 0; side1 < pieces.length - 2; side1++) {
11:             int s1 = pieces[side1];
12: 
13:             for (int side2 = side1 + 1; side2 < pieces.length - 1; side2++) {
14:                 int s2 = pieces[side2];
15: 
16:                 for (int side3 = side2 + 1; side3 < pieces.length; side3++) {
17:                     int s3 = pieces[side3];
18: 
19:                     // Ensure the sum of any 2 sides is greater than the 3rd.
20:                     if (
21:                             ((s1 + s2) > s3) &&
22:                             ((s1 + s3) > s2) &&
23:                             ((s2 + s3) > s1)
24:                         ) count++;
25: 
26:                 }
27:             }
28:         }
29: 
30:         return count;
31:     }
32: }
Notes:

There are at most 50 possibilities for side 1, 49 for side 2, and 48 for side 3. This give 117,600 combinations, small enough for a brute force solution.

The nested for loops work through each possible combination. Inside the loops, we check so see if the sides form a legal triangle. This is true if and only if the length of any two sides is greater than the third.

If it's a valid triangle, increment count. Then return count at the end.