Combinations and Permutations for UVa 735

Darts

Combinations and permutations are worth learning about for programming puzzles, and for programming in general. UVa 735: Dart-a-Mania provides a basic introduction.

Dart-a-Mania

UVa 735 describes the rules of a dart game in which players throw three darts per turn. Each throw is scored based on where the dart lands on the board. The problem test cases represent score totals for three throws. Your job is to calculate how many combinations and how many permutations of three throw scores could add up to that total score, or if such a score is impossible to get with three throws.

Combinations and Permutations

As the problem statement explains, the combinations and permutations in this problem are both arrangements of three dart throws. For permutations, the order of the throws matters, while for combinations it doesn’t. The problem statement provides an example using arrangements that produce a score of two. For both the combination count and the permutation count, the problem considers sets of three throw scores, which sum to a target total score.

Combinations

Since the order doesn’t matter for combinations, what you’re counting is how many of each distinct throw score you have in your set. For example, these sets all have the same combination of throws:

2,0,0
0,2,0
0,0,2

Since each set contains one throw score of 2 and two throw scores of 0, all of those results count as just one combination. However, the set 0,2,2 would count as a different combination, since it contains two 2 throw scores and only one 0 throw score.

Permutations

For permutations, order does matter. Therefore, the three examples above count as three separate permutations. Based on this description, it should be clear that the permutation count must always be greater than or equal to the combination count.

That’s all you need to know about combinations and permutations for this problem. There are other uHunt problems that require a more in-depth knowledge of these topics, but this one only covers the basics.

Solving the Problem

Problem Statement

There’s a long problem statement that you can read to get the real-world situation that the problem is based on. But to solve the problem, you only need to know what I described above: you’re counting permutations and combinations of three throw scores that sum to a given total score.

One note about the sample data: the PDF version of the problem statement has the wrong number of asterisks in the sample output. There should be exactly 70, and it has 71. Keep this in mind if you’re using the PDF sample data to diff with your output.

Possible Throw Scores

A throw score is the score you get when you throw one dart. There are 62 possible throw scores:

  • A score of 0 if the dart misses the board
  • Integers from 1 to 20 (based on the board region that the dart hits)
  • Double or triple these integers (also based on board regions)
  • A score of 50 if the dart hits the exact center of the board

Adding those possible scores: $1 + 3 \times 20 + 1 = 62$

The first step in counting combinations and permutations is enumerating these possible throw scores, which we can do like this:

declare an int array of size 62
for each integer from 1 to 20
    store i in position i
    store i*2 in position i*2
    store i*3 in position i*3
store 50 in position 61

Java and many other languages automatically initialize int array elements to 0. You may or may not have to explicitly initialize position 0.

Possible Total Scores

A total score is the sum of three throw scores. Each test case represents one of these scores.

Since there is a small number of possible throw scores, and a small number of throws, we can enumerate all possible total scores before we even look at any test cases. The high-level idea is:

for each arrangement of three throw scores
    calculate the total score
    map the total score to the three throws (in order)
    map the total score to the three throws (unordered)

To handle the mapping in my Java implementation, I used both HashMap and HashSet. I have written before about the difference between TreeMap and TreeSet. HashMap and HashSet are based on the same interfaces (Map and Set, respectively), but they perform slightly faster in exchange for not keeping their keys sorted. Since we don’t have to extract keys in sorted order for this problem, we might as well use hash tables.

For uHunt problems, I find that I use Map-based collections more often than Set-based collections. I usually want to retrieve a value based on a key rather than just store a set of values. But in this problem, Set is appropriate, since it ensures that each list of throw scores is unique. This is convenient for counting combinations, since multiple arrangements of throws can result in the same combination, as we’ll see below.

Once we have a set of throw scores, we need to retrieve it based on a total score, since the test cases provide total scores. That’s where HashMap comes in. We can use that collection to map an integer (the total score) to a HashSet (the set of throw scores). Given a total score, we can then look up the appropriate set of throw scores, and print its size.

Mapping all Scores

Here’s the full pseudocode for finding and mapping all possible total scores, using the 62 possible throw scores:

create two HashMaps (comb and perm), each of which maps
    an integer (total score) to a HashSet
    (lists of throw scores)
for each of the 62 throw scores i
    for each of the 62 throw scores j
        for each of the 62 throw scores k
            totalScore = i + j + k
            add i, j, and k to a list of ints
            add the list to a HashSet
            insert or update the HashSet into perm,
                with totalScore as the key
            add i, j, and k to another list of ints
            sort this list
            add the list to a HashSet
            insert or update the HashSet into comb,
                with totalScore as the key

This triple-nested loop walks through each of the $62^3 = 238328$ permutations of three dart throws. It adds these directly to the permutation (perm) map, since we need to preserve the throw order for permutations.

For combinations, we don’t want to consider throw order. I handled that requirement by sorting the list of throw scores before adding it to the combination (comb) map. Consider the same example throw scores that I used above:

2,0,0
0,2,0
0,0,2

Sorting any of these lists produces the same list:

0,0,2

Because a Set only stores one copy of each element, we can add 0,0,2 to the Set as many times as we want without increasing the size of the set. That particular combination of throw scores — two 0s and one 2, in any order — will only count as one combination for the total score $0+0+2=2$.

Processing the Test Cases

The logic shown so far only needs to run once, regardless of the number of test cases that need to be processed. The comb and perm maps contain the answers we need for any possible test case. So processing the test cases is simple:

for each test case (total score)
look up the score in either one of the maps
if it does not exist, print the "cannot be made" message
otherwise
    retrieve the set for this score from the comb map
    print the combination message using the set size
    retrieve the set for this score from the perm map
    print the permutation message using the set size
print the row of asterisks

Both maps are indexed by the total scores produced by all of the 238,328 possible arrangement of three throw scores. Therefore, if we don’t find a score in one of the maps, it isn’t a score that can be made with three throws. If we do find it in either map, we can look up both the combination and permutation sets from their corresponding maps. The sets contain the lists of throw scores that sum to the appropriate total score. The answer we’re looking for in each case is the number of such lists in the set.

Summary

As combination/permutation problems go, this one is fairly straightforward. Due to the small problem space, we have enough time to generate all permutations: an $O(n^3)$ algorithm is fast enough when $n$ is fixed at 62. As we go through each permutation, we then only need to determine when multiple permutations refer to the same combination of throw scores. In my algorithm, I used sorting for this purpose. Once the algorithm is finished saving all of the permutations and combinations in sets, producing the answer for each test case is just a matter of querying set sizes.

(Image credit: Pete)