Tuesday, July 22, 2014

ManySquares

Problem:

TopCoder Problem Statement - ManySquares

Overview:

Determine how many squares can be made from a collection of sticks.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 627
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13277
08:  */
09:
10: import java.util.HashMap;
11: import java.util.Map;
12:
13: public class ManySquares {
14:
15:  public int howManySquares(int[] sticks) {
16:
17:         /*
18:          * Holds a mapping between the lenght of a stick,
19:          * and the number of sticks found of that length.
20:          */
21:         Map sticksOfLength = new HashMap<>();
22:
23:         for (int i : sticks)  {
24:
25:             /*
26:              * If a stick of this length has already been seen,
27:              * increment the count.  Otherwise initialize the count for this
28:              * size to 1.
29:              */
30:             if (sticksOfLength.containsKey(i))  {
31:                 sticksOfLength.put(i, sticksOfLength.get(i) +  1);
32:             } else  {
33:                 sticksOfLength.put(i,1);
34:             }
35:
36:         }
37:
38:         int count = 0;
39:
40:         /*
41:          * For each length of stick in the map, divide it's count by 4 to get
42:          * the number of squares that can be made of that length.  Increase
43:          * the total count by that amount.
44:          */
45:         for (int i : sticksOfLength.keySet())  {
46:             count += sticksOfLength.get(i) / 4;  // Rounds down, no fractions.
47:         }
48:
49:         return count;
50:  }
51: }
Notes:

When I began reading the problem description, I thought this was going to be a whole lot harder than it turned out to be. I envisioned having to combine sticks toghether to form each side. Maybe one 3 + 1 side, a size 4 stick on another side, and two 2 + 2 on the remaining sides. That would make an interesting problem, but it would be way beyond division 2 - 250 points.

Luckily, the problem states that the square can only be made up of 4 sticks.

I chose to use a HashMap to map a stick size, to the number of sticks found that are of that size. The Map's key is a size, and the value is the count. The for loop at line 23 iterates through the input array, and either sets or increments the count for each stick.

Then, it iterates through all the map's keys (the stick sizes), and divides the count by 4. This is integer division, so only the whole number of divisors is returned. (i.e. 3 / 4 = 0, 5 / 4 = 1). It increments the count by that amount, and finally returns the result.

No comments:

Post a Comment