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.

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

All Solutions and descriptions are now available on GitHub at https://github.com/pmonkelban/TopCodingSolutions