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.
titan5 0 Junior Poster in Training
NormR1 563 Posting Sage Team Colleague
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?
titan5 0 Junior Poster in Training
Why did you need longs? How large a number did you need to hold?
6 to the 10th is base10=60,466,176Did 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.
NormR1 563 Posting Sage Team Colleague
Did your code work for the smaller numbers?
titan5 0 Junior Poster in Training
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
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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.
NormR1 563 Posting Sage Team Colleague
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:
titan5 0 Junior Poster in Training
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
titan5 0 Junior Poster in Training
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
NormR1 563 Posting Sage Team Colleague
If you care for comments on your code please post it.
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.
titan5 0 Junior Poster in Training
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.
NormR1 563 Posting Sage Team Colleague
No problem.
Now start looking at how to do it recursively.
Let James come in with his insights.
titan5 0 Junior Poster in Training
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);
}
} JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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);
}
} JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
ps I don't mean to be malicious, but how many ways can you roll three 12-sided dice for a total of 20?
MoZo1 -3 Junior Poster
http://en.wikipedia.org/wiki/Brute-force_search
http://en.wikipedia.org/wiki/Backtracking
http://en.wikipedia.org/wiki/Dynamic_programming
So to start with bruteforce, you have to test each combination of the dices if it sums to the number you need. Just watch out for combinations and variations, to answer the correct question you've been asked to...
titan5 0 Junior Poster in Training
http://en.wikipedia.org/wiki/Brute-force_search
http://en.wikipedia.org/wiki/Backtracking
http://en.wikipedia.org/wiki/Dynamic_programming
So to start with bruteforce, you have to test each combination of the dices if it sums to the number you need. Just watch out for combinations and variations, to answer the correct question you've been asked to...
Sorry I didnt get wat u mean..????
titan5 0 Junior Poster in Training
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
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
57, of which 39 are unique (sorry)
;-)
J
titan5 0 Junior Poster in Training
u did it using recursion only.. rite?
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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)
NormR1 563 Posting Sage Team Colleague
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
savedCombos.add(sc);
// 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 JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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!
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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
}
uniqueSolutions.add(Arrays.copyOf(solution, nSides));
}
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("");
}
}
} titan5 0 Junior Poster in Training
Your code is great!! Guess I should spend more time on recursion.. :)
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.