Dice combination for a particular sum

[titan5]

I have been given a program to write in java but inspite of thinking hard I have not been albe to get the logic for doing it.
Here's the problem-
I am given n dice which are rolled simultaneously and one of the possible sum of the dice. The program should return the no. of combinations in which that sum is possible with n dice. I really have no idea of the logic behind it.

Eg-
Suppose u have 2 dice and sum =8.
The program should return the no of combinations by which the sum 8 could appear.
In this case (6+2), (5+3), (4+4). total=3 combinations. (counting 6+2 and 2+6 as 1). They could also be counted separately.

[NormR1]

One method is the brute force method. Write some loops that go thru all the possible combinations of rolls and selects those that sum to the desired value.

Think of the problem as numbers in sequence in base 6. Say there are 4 die. Then all the possible combos of numbers range from: 1111 to 6666. The numbers go: 1111, 1112, 1113, ..., 6665 and 6666.

[titan5]

I had thought about brute force but i dont know how it could be implemented. Wont it require n (n=no of dice) nested loops?

[JamesCherrill]

Yes (There are cleverer ways of structuring it, epecially when the number of dice is variable, but they still all come dowm to n nested loops).

[titan5]

Can u give the algo den? Isn't there any other way of doing it? n nested loops would also make it a very high order algo.

[JamesCherrill]

If you need an exact answer then I think you can't avoid Order 6^n.
Since this is your assignment it would be against the rules of this forum for me to just give you the algorithm.
But here's a thought...
Find all the ways of totalling t with n dice is the same as finding all the ways of totalling (t-1) ... (t-6) with n-1 dice. Recursion anyone?

[NormR1]

Depending on the constraints of the assignment, I wrote a 40 line pgm with one loop that does it based on the idea of using base 6 arithmetic.

I also assumed that 6+2 is different from 2+6. If they are the same its back to the drawing board.

[JamesCherrill]

Hi Norm. I guess your single loop is just the flattened version of the nested loops - ie 1 loop with 6^n iterations rather than n nested loops with 6 iterations? What's the value of n for max int?
I too was more interested by the 6+2 == 2+6 problem - looks like a challenge to find a way of encoding the solutions such that they can quickly be compared for equality disrgarding order. Best I can do so far is to encode each solution as a 6 element array = no of 1s, no of 2s ... no of 6s. Reasonably fast to encode and compare, but I can't help thinking there's some other much smarter lateral approach.

[NormR1]

a way of encoding the solutions such that they can quickly be compared for equality disrgarding order

Generate base 6 string of digits, sort the digits and store in a HashSet

[titan5]

I am not able to figure out what this base 6 arithmetic means..or is it simply nos from 1 to 6?

[NormR1]

base 6 is really 0-5.

You know and work with everyday base 10 which is 0-9

[titan5]

oops sorry...so i does using base 6 helps? is there any special function in java for doing this?
i mean why couldnt we do it in base 10?

[JamesCherrill]

Generate base 6 string of digits, sort the digits and store in a HashSet

Yes, that will work - but it's going to be v slow if n is large. I was wondering what the most efficient way ws?

[NormR1]

Absolutely correct. Here's time (in ms) for 10 dice:

count of 10 dice rolls suming to 44 is 1151370 duration was: 55578

[titan5]

Absolutely correct. Here's time (in ms) for 10 dice:

count of 10 dice rolls suming to 44 is 1151370 duration was: 55578

But how did u do it? I cant understand how u implemented base 6 arithmetic n used 1 loop..
n is it bruteforcing?

[NormR1]

Absolutely brute force. I generate all the combos from 1111... to 6666.... added them up and counted those with the correct total.

I rewrote the code NOT to use classes and now get a time less than 4 secs:
count of 10 dice rolls suming to 44 is 1151370 duration was: 3984

[JamesCherrill]

Sometimes the simple approach is best - the basic recursion scheme I outlined above runs the 10 dice/44 case in 300mSec on my 3 year old laptop.
Eliminating the duplicated cases is the killer (ie same digits but in a different order) those 1151370 combinations represent only 83 unique cases, but the best I can do is 5 seconds to eliminate the duplicates.

[NormR1]

That's about the same results as I get for eliiminating dups:
count of 10 dice rolls suming to 44 is 83 duration was: 4890

Your recursion scheme time is 1/10 of mine.

[JamesCherrill]

titsn5: Sorry, norm and I seem to have hijacked your thread a bit. how are you getting on?

[titan5]

titsn5: Sorry, norm and I seem to have hijacked your thread a bit. how are you getting on?

Sorry I was busy in sumthing else. I am completely lost as to what the two of u have been doing.

From what I have understood till now is that Norm is generating nos from n 1's to n 6's. (for 5 dice from 11111 to 66666) and then for each no. he is summing the individual digits and checking with the required sum. But how do I initiate this loop for any n. For 5 dice how do I start it with 11111? How do I make it genereal?

[JamesCherrill]

Yes, norm and I have been playing with this offline, and I hope he will agree with this:
The base 6 numbers idea is interesting, and works, but the recursive solution is less code and executes faster. Eliminating duplicate solutions (is saying that a throw of 6-6-2 is the same as a throw of 6-2-6 or 2-6-6) is challenging, especially if you want it to run quickly.
I recommend you go with the recursive approach, and ignore the duplicates problem for now. I outlined this in my earlier post - have a look and come back with your questions.
The basic recursive algorithm comes down to 10 lines of simple code - so its really easy once you've grasped the recursive concept.

[titan5]

I am really weak with recursion and prefer doing programs using normal loops only.
I have succeeded in generating nos between n 1's and n 6's n calculating the sum of each individual no. I m not getting the correct output for some cases and i m trying to work on tht now. Will get back to you with my code if I am not able to resolve it

[JamesCherrill]

OK, but you are missing a very important learning opportunity. Recursion is an essential tool in the program designer's toolkit, and although it seems hard at first, it's easy when you get the hang of it. For this problem, with a variable number of dice, it's a very good approach.

[titan5]

ok i'll try that also. But first I'll finish my code using loops. Then perhaps you wont mind helping me with recursion.

[titan5]

I got my error. I am getting combinations which are not possible in dice throws. Now I understand why u were talking abt base 6 arithmetic.
Is there any method in java to change default base 10 to base 6 arithmetic?

[JamesCherrill]

I'll leave Norm to help you with the base 6 stuff. If/when you're ready for recursion, I'll be watching this thread.
J

[NormR1]

My approach was to define an array of "digit"s and to do arithmetic to them like you used to do when you added numbers on paper by hand. Start at the right most digit, add one, does the result exceed the base if so, set that digit to 0 and carry 1 to the next higher digit to the left. Continue until there was no carry.

[titan5]

I'll leave Norm to help you with the base 6 stuff. If/when you're ready for recursion, I'll be watching this thread.
J

OK i have completed my assingment and written a code using a for loop. Its taking a large time to calculate for large no of dice. For 10 dice I waited for 10 min to get the output and after that I terminated it. Anyways I have no restrictions on the order of the algo n so it will do.

How about to go wid recursion? I didnt understand much wat u wrote previously?

[NormR1]

If it ran that long without results, do you think it is in an endless loop?
Did you use any String objects in the loop? That could account for the long times.
Do it without using any String objects. Keep the computations to ints

To debug your code, use smaller numbers like 3 dice and total of 12.

[titan5]

My approach was to define an array of "digit"s and to do arithmetic to them like you used to do when you added numbers on paper by hand. Start at the right most digit, add one, does the result exceed the base if so, set that digit to 0 and carry 1 to the next higher digit to the left. Continue until there was no carry.

Ok I'll try this approach. Write now I have generated all nos from n 1's to n 6's. Then in each no I am checking if there is a 0 or a no >6. If so I just ignore that case and continue the loop for the other nos. Working fine for me but takes too much time. I couldnt get the output for 10 dice...