2

I am having a lot of trouble understanding the logic behind the infamous "Find total ways to achieve given sum with n throws of dice having k faces" question. After extensively searching for explanations, I have come up blank.

My confusion stems from the fact that it does not seem to follow the same logic as the "number of ways to make change with coins" problem, which is explained excellently in a number of videos, particularly this one.

My understanding of the coin change problem

This is, I believe, quite sound. Essentially, when we get past the first row, we look at the number of ways to make the target from both the first coin and the second coin, not just the second coin (in general, it is the current coin plus all previous coins). As explained at the linked video, we need to follow some rules to do this:

If <the value of the coin is greater than the target>
     Simply copy the value from the cell above.  
Else
     a) Determine the number of ways we can make the target when we EXCLUDE the current coin
     b) Determine the number of ways we can make the target when we INCLUDE the current coin
     c) Add the two together and store the result in the cell.

For step a, we can determine this by simply copying the value from the cell above: this is, after all, the number of ways we can make the same target without the current coin. So for 3, we copy the 0. This is correct; using a 2 coin, there are 0 ways of making the target of 3.

For step b, we need to subtract the current coin from the target, which will give us the remainder. Then, we need to determine how many ways there are of making this remainder from the current coin. So for change of value 3, we have (3-3) which is 0. For a target of zero, there is 1 way of making 0 with a 3-coin, as the table shows (highlighted). Thus we have 0 + 1 = 1.

CoinChangeTable

I can see how to populate the whole table therefore. The algorithm used is not important here.

My failure to understand the dice problem logic

The following algorithm is from the link above:

long findWays(int f, int d, int s) 
{ 
    // Create a table to store results of subproblems. One extra 
    // row and column are used for simpilicity (Number of dice 
    // is directly used as row index and sum is directly used 
    // as column index). The entries in 0th row and 0th column 
    // are never used. 
    long mem[d + 1][s + 1]; 
    memset(mem,0,sizeof mem); 
    // Table entries for no dices 
    // If you do not have any data, then the value must be 0, so the result is 1 
    mem[0][0] = 1; 
    // Iterate over dices 
    for (int i = 1; i <= d; i++) 
    { 
        // Iterate over sum 
        for (int j = i; j <= s; j++) 
        { 
            // The result is obtained in two ways, pin the current dice and spending 1 of the value, 
            // so we have mem[i-1][j-1] remaining combinations, to find the remaining combinations we 
            // would have to pin the values ??above 1 then we use mem[i][j-1] to sum all combinations 
            // that pin the remaining j-1's. But there is a way, when "j-f-1> = 0" we would be adding 
            // extra combinations, so we remove the combinations that only pin the extrapolated dice face and 
            // subtract the extrapolated combinations. 
            mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]; // CONFUSION POINT A
            if (j - f - 1 >= 0) 
                mem[i][j] -= mem[i - 1][j - f - 1];   // CONFUSION POINT B
        } 
    } 
    return mem[d][s]; 
} 

I have read this code over and over, perhaps too many times, but I just don't get it.

Inputs: number of dice (d) = 3, number of faces on each die (f) = 3, target value (s) = 3. I have added some debugging output and generated the following to show how the cells in my table are calculated:

[1,1] = [1,0] + [0,0]
[1,2] = [1,1] + [0,1]
[1,3] = [1,2] + [0,2]

!! [2,1] is never calculated, CONFUSION POINT C !!

[2,2] = [2,1] + [1,1]
[2,3] = [2,2] + [1,2]

So, having broken down the algorithm into plain English, what this shows is that

the number of ways of making 3 with 2 dice [2,3] is
    the number of ways of making 2 with 2 dice [2,2] +
    the number of ways of making 2 with 1 die  [1,2]

At this point, it does not appear to follow the logic of the coin change problem; that is, the psuedo code block I posted above. I even tried giving the die numeric values to try and apply this logic; i.e. die 1 is [ 1 ] and die 2 is [ 2,1 ] to follow a similar idea to "adding additional coins" but it just does not work. This is worrying for me because whereas I understand the (beautiful) concept behind dynamic programming, I cannot appear to apply the same logic to all similar problems of this nature.

My questions

Can someone please explain my three confusion points as indicated:

a) How this works and the logic behind it.

b) What on earth is this line doing?

c) Why is cell [2,1] never calculated? I am now pretty certain that this is simply because we cannot ever make 1 from 2 dice, but would like confirmation on this please in case I have missed something.

  • the difference is in the coin change problem you have the option of NOT using a coin. In the dice problem you must roll n dice. – Ewan Aug 21 at 10:34
  • OK, uhm, well firstly I guess thanks for commenting. But that doesn't really help me understand the logic, which is what I was asking... – Wad Aug 21 at 12:56
  • They're different problems. Stated properly, order doesn't matter in the correct change problem, but order does matter in the die problem. Another key difference: One way to yield a sum of 8 in the correct change problem is to give 8 pennies. This is not a solution to the die problem if one can only roll six dice. It shouldn't be surprising that the algorithms are different. What is common is that a naive solution to either repeatedly solves problems that have already been solved. – David Hammen Aug 22 at 11:12
  • Thank you; it is now clear that the algorithms are going to be different. With this realisation though, I still struggle to even formulate an "in plain English" solution in my head, as per my query on the answer given below (please see it if you have not already). Even after being given the algorithmic solution, (which I have no problem understanding what it does), the "in plain English" version of this (which is typically the first stage in solving an algorithm) just does not make sense. Perhaps you could clarify with an answer of your own? – Wad Aug 22 at 12:05
  • Isn't this an SO question? – Matt Messersmith Aug 23 at 19:35
4

Both algorithms are usually expressed using recursion, yet the actual implementation is then often done using iterative techniques. This sometimes leads to confusion, as the algorithm you present pre-fills a table with the desired values iteratively and then just returns the value in the one cell we are looking for.

Let's try to write up the recursive algorithm in detail: we want to find the number N(D,S) of ways to express a sum S using D dice with F faces each, all faces numbered from 1...F. Each die must be used, so we can immediately say that N(D,S) = 0 for all D > S, i.e. the left lower half of the N(D,S) table will be all zeroes. Also, N(D,S) = 1 for all D = S because there is only one way of rolling D with D dice (when all dice roll 1) so the diagonal will be 1.

All recursion begins with a base. There is one way of rolling any number between 1 and F with 1 die, and no way for all other numbers:

  1. N(1,S) = 1 for all S=1...F, N(1,S) = 0 for all other S

Now let's look at an arbitrary N(D,S) with D < S. The Dth die has one way each of showing any j with j = 1...F. So N(D,S) is the sum of all N(D-1,S') where S' is between S-F and S-1

  1. N(D,S) = SUM(N(D-1,S')) with S' = S-F ... S-1

so you basically add up F numbers in the horizontal strip to the top left of (D,S). So for any line D you can derive the numbers from the line above. Repeat that until you arrive at the first line and that already completes the recursion.

The algorithm you present computes this not recursively, but iteratively, and makes heavy use of precomputed data. You notice that at no point does it actually sum up the F values from the row above, there is no loop like

    // Iterate over the values in the row above
    for (int k = j-f-1; k <= j-1; k++) 

It can skip this because the value in the cell to the left already has something that is almost this. In particular

N(D,S-1) = SUM(N(D-1,S'')) with S'' = S-F-1 ... S-2

so

N(D,S) = N(D,S-1) + N(D-1,S-1) - N(D-1,S-F-1)

or in C:

mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]; // N(D,S-1) + N(D-1,S-1)
if (j - f - 1 >= 0)                            // prevent index underrun
    mem[i][j] -= mem[i - 1][j - f - 1];        // - N(D-1,S-F-1)

Additionally, if you set

N(0,0) = 1, N(0,S) = 0 for all S != 0

in other words:

mem[0][0] = 1;  // all other mem[i][j] are 0 by default, right?

you can move the base of the recursion one row up and avoid having to treat D=1 as a special case.

And that is what the code does. Let's look at an example. Here is the computed table for F=3, D=2, S=8:

-------------------
|1|0|0|0|0|0|0|0|0|
-------------------
|0|1|1|1|0|0|0|0|0|
-------------------
|0|0|1|2|3|2|1|0|0|
-------------------

Note that the value in each cell of the bottom row is the sum of the values in the horizontal three cell strip to the left in the previous row, but also equal to the value to the left plus the value to the top left minus the value 3 cells to the left of that.

Update: To understand why the recursion works, let's look at the example you mention. How many ways are there to roll 4 with 2 normal 6-faced dice? Well, in this simple case, we can write down all possible rolls in a table like this:

----------------------
|  | 1| 2| 3| 4| 5| 6|
----------------------
| 1| 2| 3| 4| 5| 6| 7|
----------------------
| 2| 3| 4| 5| 6| 7| 8|
----------------------
| 3| 4| 5| 6| 7| 8| 9|
----------------------
| 4| 5| 6| 7| 8| 9|10|
----------------------
| 5| 6| 7| 8| 9|10|11|
----------------------
| 6| 7| 8| 9|10|11|12|
----------------------

with the values on the dice in the top row and leftmost column, and the sum in the other cells. We can immediately see that we have exactly three combinations of rolls that add up to 4, namely (1,3), (2,2) and (3,1). Trivial, so far.

Now look at the second die: of the six sides, only 1, 2, 3 allow for a sum of 4. The number of ways we can throw a 1 with the second die is 1, because it has only one side with the number 1. So this does not add any multiplicitly to the solution: every solution that has a sum of 4 and 1 on die 2 also has 3 on die 1. We can map every combination that has a sum of 4 and 1 on the second die to a throw of the first die that rolls 3. So the number of ways you can have a sum of 4 and 1 on the second die is identical to the number of ways you can have 4-1=3 on the first die.

This is true for the general case, too. As long as each number j shows up on the Dth die only once, there is only one way to throw it, then there is a 1:1 mapping of each solution that has this number on the last die and the sum S to a solution for the smaller problem with D-1 dice and a sum of S-j. Hence, the number of such solutions must be identical. Add this for all possible values of j and you arrive at the recursion step.

Update 2

The dynamic programming technique, using the algorithm in the original question, to solve "How many ways are there to roll 4 with 2 normal 6-faced dice" generates the table shown in the image below, which has been annotated to aid in understanding. This shows how the previous row's values are used in calculating the current row's:

Walkthrough

With this simple walkthrough for 2 dice, the same logic of using the previous row's values can be hence applied to other problems with any number of dice/any target sum.

Update 3

The caveat to the above walkthrough is shown in the below image, which is where we are trying to generate 8 with 2 dice, each dice having three faces; the table for this is shown above, but repeated here for clarity.

Walkthrough2

In this case, summing values from the previous row in the manner described in update 2 is clearly not correct, because it would mean using values on the dice that are not present due to the limitation in the number of faces. This is where we need to be smart about what values we use, which is dealt with in the if case in the posted algorithm, labelled as CONFUSION POINT B.

  • Firstly, thanks. Now, you say So N(D,S) is the sum of all N(D-1,S') where S' is between S-F and S-1. This is where I struggle. Using your table and following this rule, cell [2,4] (no. ways of making 4 with 2 dice) is "num ways of making 3 with 1 die" + "num ways of making 2 with 1 die" + "num ways of making 1 with 2 die". (3=1+1+1) I am clearly missing something fundamental here, as I cannot even see how anyone could deduce that; that is, it doesn't even sound logical saying it in my head! Sorry. Can you possibly update your answer with details (in plain English if poss) please? – Wad Aug 21 at 20:04
  • You can similarly write a table with 2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 9 9 9 9 10 10 10 11 11 12 as the columns and 1 2 3 4 5 6 as the rows, and see the 3 dice case, etc. – Caleth Aug 23 at 12:54
  • @Caleth, I don't know what you mean; can you please elaborate as this sounds interesting...perhaps an answer would enable you to express what you mean without character limits? – Wad Aug 23 at 13:01
  • @Wad wallenborn has drawn a "sum of 2 six-sided dice" table here . Imagine a 36 sided die with faces numbered like that. If you roll such a die, you get the results with the same probability as a "sum of 2 six-sided dice" roll. You already have a method for summing two dice, of arbitrary sides, which is to tabulate the sides of the first against the sides of the second. Using that, we see a "sum of a six-sided die and a 36-sided die", which is the same as a "sum of 3 six-sided dice". This procedure can be repeated indefinitely. – Caleth Aug 23 at 13:13
  • Ugh I'm sorry I didn't see that wallenborn had updated the answer; I'll study that now... – Wad Aug 23 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.