Did you use any String objects in the loop? That could account for the long times.
Do it with using any String objects. Keep the computations to ints

No. I just used long. with int I could use max 9 dice.

Why did you need longs? How large a number did you need to hold?
6 to the 10th is base10=60,466,176

Did your code work for the smaller numbers?

Edited by NormR1: n/a

Why did you need longs? How large a number did you need to hold?
6 to the 10th is base10=60,466,176

Did your code work for the smaller numbers?

i used long beacuse m working in base 10. i am storing each no in long. I didnt use arrays. Using int in base 10 only 9 dice are possible.

Did your code work for the smaller numbers?

Yeah its working. I checked till 4 dice. I didnt know what would be the output for higher nos so coudnt check it. Can you give me some test cases with ur program?
like no of combinations for 6 dice n a particular sum...2-3 such cases

There are some easy extreme cases to check - eg 6 dice total 6 or 36 (only one solution for each of those!). It's always a good idea to test the extreme cases.

Here are two values, first line mine, second line JamesCherrill

count of 6 dice rolls suming to 23 is 30 duration was: 16
Rolling 6 dice with target 23... 3906 solutions found in 0mSec 30 unique solutions:

count of 6 dice rolls suming to 25 is 25 duration was: 32
Rolling 6 dice with target 25... 2856 solutions found in 16mSec 25 unique solutions:

I tried the extreme cases.Works well till 8 dice.
For 8 dice-- 8 sec
9 dice- 84 sec!
Time must be depending to the system configuration also. I use a separate virtual machine which reduces the performance drastically

For 10 dice it took 745 sec!! pretty useless algo for large no of dice :)
Getting same output for 6 dice also for sum combiation 25 & 23. Thnx for the test cases. Helped me in verifying my program

There must be something very expensive in your code.
My first version took 55 seconds. I rewrote it and got it down to 4 seconds.
Strings are VERY expensive.

I'll surely post the code but after 3 days. I hope that wont be a problem. I wud luv to get suggestions from u to improve it.

No problem.
Now start looking at how to do it recursively.
Let James come in with his insights.

exremely sorry for delay in posting the code... here it is ..

``````public class dice
{

public static void main(String arg[])
{
int numOfCombinations=0;
int i=6;                         //No of dice
long sum=0, d;
long cheksum=10;                   //The sum which is to be checked
long S1=1;
long temp;
int k;
for(k=0; k<i-1; k++)              //Generating starting no 111...(no of 1's =n)
{
S1=S1*10;
S1=S1+1;
}
//System.out.println(S1);

long S2=6;                       //Generating last no. 666......
for(k=0; k<i-1; k++)
{
S2=S2*10;
S2=S2+6;

}
long m;

loop:		for(m=S1; m<=S2; m++)
{
sum=0;
temp=m;
while(temp>0)
{

d=temp%10;
if(d==0||d>6)
continue loop;
sum=sum+d;
temp=temp/10;
}

if((sum==cheksum) && (sum<=6*i))
{

numOfCombinations++;
}}
System.out.println("Comb	"+numOfCombinations);

}
}``````

Hi. Glad you came up with a solution to this problem. Well done!
Just for your amusement, and maybe for future reference, here's the simplest version of the recursive method:

``````int nSolutions = 0
public void roll(int nDice, int target) {
if (nDice == 1) {
if (target >= 1 || target <= 6) nSolutions++; // solution found
return;
}
for (int roll = 1; roll <= 6; roll++) {
roll(nDice - 1, target - roll);
}
}``````

Edited by JamesCherrill: n/a

ps I don't mean to be malicious, but how many ways can you roll three 12-sided dice for a total of 20?

ps I don't mean to be malicious, but how many ways can you roll three 12-sided dice for a total of 20?

:-0

57, of which 39 are unique (sorry)
;-)
J

u did it using recursion only.. rite?

Yes. Recursion is the "only" proper way to do this! (See code in previous post- how neat is that? - it's complete, just call it & print the result)

Edited by JamesCherrill: n/a

To know how neat James's solution is, look at my brute force method:

``````import java.util.*;

public class DiceCombos {
final static String Zeros = "000000000000000000000000000000000000000000000000000000000000";  // for leading zeros
final static int MaxNbr = 5;  // max number for base 6

// Define the two controlling values:
final static  int nbrDice = 10;     // the number of dice
final static  int reqTotal = 36;    // the requested total

//----------------------------------------------------------------
// Class to save dice combos to eliminate counting duplicate rolls
static class SavedCombos {
int[] savedCombo;

SavedCombos(int[] combo) {
savedCombo = Arrays.copyOf(combo, combo.length); // copy to local
bubbleSort(savedCombo);  // sort
//        System.out.println("combo=" + Arrays.toString(combo));
}
@Override
public boolean equals(Object o) {      //<<<<<<<<<<<<<<<<<<< hashCode first then this one
SavedCombos sc = (SavedCombos)o;

for(int i=0; i < savedCombo.length; i++) {
if(sc.savedCombo[i] != savedCombo[i]) {
//            System.out.println("equals false for " + o + " vs " + this);
return false;
}
}
//        System.out.println("equals true for " + o + " vs " + this);
return true;   // all were equal
} // end equals()

@Override                             //<<<<<<<<<<<<<<<< THIS first
public int hashCode() {
//        System.out.println("hashCode");
//        try{throw new Exception("Who called");}catch(Exception x) {x.printStackTrace();};
/*
java.lang.Exception: Who called
at DiceCombos\$SavedCombos.hashCode(DiceCombos.java:32)
at java.util.HashMap.getEntry(HashMap.java:344)
at java.util.HashMap.containsKey(HashMap.java:335)
at java.util.HashSet.contains(HashSet.java:184)
at DiceCombos.main(DiceCombos.java:67)
*/
return sumDigits(savedCombo);   // redundant as we already know what the sum
} // end hashCode()

// For debug
public String toString() {
return Arrays.toString(savedCombo);
}
public String showDiceFaces() {
int[] faceVals = Arrays.copyOf(savedCombo, savedCombo.length); // copy to local
for(int i=0; i < faceVals.length; i++)
faceVals[i]++; // change to one based
return Arrays.toString(faceVals);
}

} // end class SaveCombos

//---------------------------------------------------------------
public static void main(String[] args) {
boolean showCombos = false;    // Only for small nbrDice!!!

// We'll use base 6 arithmetic to generate all the possible rolls from 1111 to 6666 (for 4 dice)
// NOTE: Our numbers are 0 based so the range will be 0000 to 5555
int startNbr = 0;
long endNbr = (long)Math.pow(6.0, 1.0 * nbrDice) - 1;
System.out.println("endNbr=" + Long.toString(endNbr, 6) + ", base10="  + endNbr);
//endNbr=5555555555, base10=60466175

//Generate all the numbers and count those with desired sum
int baseZeroReq = reqTotal - nbrDice;  // minus one for each die because of 0 basing
int count = 0;
int[] dice = new int[nbrDice]; // hold dies here

HashSet<SavedCombos> savedCombos = new HashSet<SavedCombos>();

long start = System.currentTimeMillis(); // save starting time

for(long i=0; i <= endNbr; i++) {
incrDice(dice);  // add one to digits in the array, propagating carry

if(sumDigits(dice) == baseZeroReq) {
SavedCombos sc = new SavedCombos(dice);
if(!savedCombos.contains(sc)) {
count++;          // count number of totals
//            System.out.println("Have saved " + savedCombos.size());
}

if(showCombos) {
String nxtNbr = "";
for(int j=0; j < dice.length; j++)
nxtNbr += ""+(dice[j]+1);  // build number going to 1 based
String showNbr = (Zeros + nxtNbr).substring(Zeros.length()-nbrDice+nxtNbr.length());
System.out.println("total=" + reqTotal + " for " + showNbr);  // remember zero based when viewing
}
} // end correct sum

// Problem here if sum is > desired total, need to skip to where sum could be desired again

} // end for(i)

System.out.println("count of " + nbrDice + " dice rolls suming to " + reqTotal + " is " + count
+ " duration was: " + (System.currentTimeMillis() - start) + " mSec");

// Show the saved combos
for(SavedCombos sc2 : savedCombos) {
System.out.println(sc2.showDiceFaces());
}
} // end main()

//increment elements in an array base 6
static void incrDice(int[] d) {
for(int i=d.length-1; i >= 0; i--) {
d[i]++;  // add one to this
// Test for overflow and if carry needed
if(d[i] > MaxNbr) {
d[i] = 0; // reset this and carry to next
} else {
break;  // exit if sum <= max
}
} // end for(i)
}

// Sum digits in array
static int sumDigits(int[] d) {
int sum = 0;
for(int i=0; i < d.length; i++) {
sum += d[i];
}
return sum;
} // end sumDigits()

//-------------------------------------------
static void bubbleSort(int[] list) {
boolean sorted = false;
//    int swapCnt = 0;

for (int top = list.length - 1; top > 0 && !sorted; top--) {
sorted = true;

for (int i = 0; i < top; i++) {
if (list[i] > list[i+1] ) {
sorted = false;
int temp = list[i];
list[i] = list[i+1];
list[i+1] = temp;
//          System.out.println("swapped " + list[i] + " - " + temp);
//          swapCnt++; // count number of swaps
}
} // end for(i)

} // end for(top)
//    System.out.println("swapCnt=" + swapCnt);
} // end bubbleSort()

}  // end class``````

Here's a complete runnable version with variable number of sides. Only change from previous simplest code is an extra test to prune impossible combinations - ie if target is < no of dice or > no of dice * no of sides - this saves checking a load of combinations that can never work anyway.

``````public class Dice {

public static void main(String[] args) {

int n = 3;   // number of dice
int s = 12;  // number of sides on each dice
int t = 20;  // target total

System.out.println("Rolling " + n + " " + s + "-sided dice with target " + t + "... ");

long start = new java.util.Date().getTime();
roll(n, s, t);
long end = new java.util.Date().getTime();

System.out.println(nSolutions + " solutions found in "
+ (end - start) + "mSec");
}

int nSolutions = 0; // includes duplicates

public static void roll(int nDice, int nSides; int target) {
if (nDice == 1) {
if (target >= 1 || target <= nSides) {
// this is the last die and target can be rolled in one
nSolutions++;
}
return;
}
int nDiceRemaining = nDice - 1;
for (int roll = 1; roll <= nSides; roll++) {
int targetRemaining = target - roll;
if (targetRemaining < nDiceRemaining
|| targetRemaining > nSides * nDiceRemaining) return; // no solution possible
roll(nDiceRemaining, nSides, targetRemaining);
}
}
}``````

(ps extracted from duplicate-finding version, please forgive any typos)
Have fun!

Edited by JamesCherrill: forgot to make method static in edited version

Hello again. I'm embarrased to admit that some nonsense crept into the code I last posted, and the numbers I gave for the 12-sided dice were dodgy.
Here, by way of apology, is the full version with extraction of duplicate results (ps Norm, the duplicate code is a vastly simpler, better version than the String based thing we discussed offline).

``````import java.util.ArrayList;
import java.util.Arrays;

public class Dice {

public static void main(String[] args) {

final int n; // number of dice
final int s; // no of sides per die
final int t; // target total

n = 3;  s = 12;  t = 20;
// n = 10;  s = 6;  t = 44;

System.out.println("Rolling " + n + " " + s + "-sided dice with target " + t
+ "... ");

long start = new java.util.Date().getTime();
Dice d = new Dice(n, s, t);
long end = new java.util.Date().getTime();

System.out.println(d.getNumberOfSolutions() + " solutions, (" +
d.getNumberOfUniqueSolutions() + " unique) found in " +
(end - start) + "mSec");
d.displayUniqueSolutions();
}

private int nSides; // no of sides/faces on each dice
private int[] rolls; // no of dice rolled for each side
// eg if you roll 5,4,5  then  rolls = {0,0,0,1,2,0}
private int nSolutions; // includes duplicates
private ArrayList<int[]> uniqueSolutions;
// contains copies of all the unique rolls[] that are a solution

public Dice(int nDice, int nSides, int target) {
this.nSides = nSides;
rolls = new int[nSides];
nSolutions = 0;
uniqueSolutions = new ArrayList<int[]>();
roll(nDice, target);
}

public void roll(int nDice, int target) {
if (nDice == 1) {
if (target >= 1 && target <= nSides) {
// this is the last die and target can be rolled in one
nSolutions++;
rolls[target - 1]++;
checkIfSolutionIsUnique(rolls);
rolls[target - 1]--;
}
return;
}
int nDiceRemaining = nDice - 1;
for (int roll = 1; roll <= nSides; roll++) {
int targetRemaining = target - roll;
if (targetRemaining >= nDiceRemaining
&& targetRemaining <= nSides * nDiceRemaining) {
rolls[roll - 1]++;
roll(nDiceRemaining, targetRemaining);
rolls[roll - 1]--;
}
}
}

void checkIfSolutionIsUnique(int[] solution) {
for (int[] s : uniqueSolutions) {
if (Arrays.equals(solution, s)) return; // already got this solution
}
}

public int getNumberOfSolutions() {
return nSolutions;
}

public int getNumberOfUniqueSolutions() {
return uniqueSolutions.size();
}

public void displayUniqueSolutions() {
System.out.println(uniqueSolutions.size() + " unigue solutions:");
for (int[] s : uniqueSolutions) {
// System.out.println(Arrays.toString(s));
for (int i = 1; i <= nSides; i++) {
int count = s[i-1];
if (count >= 1) System.out.print(count + "x" + i+ " ");
}
System.out.println("");
}

}
}``````

Your code is great!! Guess I should spend more time on recursion.. :)

Thank you for the compliment! And thanks for starting this thread; I've had a lot of fun playing with this problem.
Yes, recursion is one of those techniques that, when you have the right problem, is a fabulous solution.
If anyone is interested I've now made about an order of magnitude improvement in the performance of the de-duplication. I keep the known solutions in an array that's always sorted, so I can use a binary search to see if a new solution is already in the array (using the methods in the Arrays class, of course). The dreaded 10 dice totalling 44 case now runs in under 600mSec including de-duplication. I can post that code if anyone wants.

Edited by JamesCherrill: n/a