0

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.

0

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

0

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.

0

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

0

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.

0

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:

0

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

0

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

0

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.

0

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.

0

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

0

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);
	
		
}
}
0

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

0

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

0

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

0

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
0

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

0

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("");
      }

   }
}
0

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

0

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

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.