I've recently gotten into
TopCoder (don't ask me where I've been all this time). As a software engineer of about 7+ years, I was quite keen to find out where I stacked up in the programming stakes. I've programmed mostly in Java, so that was the language I chose to use in practice area of the Arena. I should also disclose that I got a tip to attempt some of the division 1 and 2 problems from a Google page about preparing for their interviews. This sparked my curiosity even further.
After starting the Arena (TopCode should have a UI contest to find a more user friendly place to show link to the jnlp. At the footer seems an odd place to have a link that is used frequently) I went into one of the practice rooms and picked a problem related to gambling. TopCoder does not allow unauthorized reproduction of their problems, so I won't violate their copyright. The problem can be found in practice room SRM 144 Div 1.
The crux of the problem is to find out how many combinations of a particular set of items that can be selected from another set of items. For example, if you have to pick 2 numbers from 1-10 inclusive, how many combinations can you include? What if the order is important (i.e. the second number you pick must be greater than the first)? What if the numbers must be unique (i.e. no repititions)? What if both the order and unique rules are necessary?
While I was intrigued with the logical challenge of solving this puzzle, I wondered whether this has a place as a problem for a software engineer. I suspect, depending on how the client has explained this problem (you would have to see the post for the problem from TopCoder) it either becomes a computer science or mathematical problem rather than one about building software. Many computer solutions are replacements for manual processes so sometimes it is necessary to ask the client, "What are you doing currently to solve this?" It could however be a new problem and it is unreasonable for the engineer to tell the client, "Sorry, I can't quite remember my high school math."
The solution to the problem required 4 routines:
- A method to calculate exponentials. In java - Math.pow is sufficient.
- A method to calculate permutations.
- A method to calculate factorials.
- A method to calculate binomial_coefficient.
Exponentials
Exponentials can be used to calculate the number of possibilities without any rules regarding order or uniqueness. For the example of 10,2 the number of possibilities is 100.
Permutations
From wikipedia, a permutation of a set of values is an arrangement of those values into a particular order. Going back to the original problem of picking 2 numbers between 1-10, regardless of order and ensuring the numbers are unique (i.e. 1,2 is valid but 2,2 is invalid), calculating the number of permutations of the 10 integers with 2 options for each.
- private long permutation(int n, int opts)
- {
- long result = 1;
-
- for (int idx = 0; idx < opts; idx++)
- result *= (n - idx);
-
- return result;
- }
Factorials are a little more interesting than permutations. The factorial of a positive integer n (n!) is the product of all positive integers less than or equal to n. The factorial of zero is defined as 1. This is useful for calculating binomial coefficients.
