How to resolve hashing collisions in Java

Question

Write the following program using Java:

Suppose Player1 has 7 dice and Player2 has 5 dice (all 12 dice are standard 1 through 6 dice and fair). Both players roll their dice and compare their individual sum totals (i.e. Player1 rolls 1,3,5,2,6,1,1 = 19 and Player2 rolls 2,1,4,6,3 = 16). If Player1 rolls a total sum higher than Player2, Player1 wins the match, otherwise, Player2 wins. If all 2,176,782,336 combinations are rolled, how many matches will Player1 win? How many matches will Player2 win? How many matches will result in a tie? (note: only totals answering the three questions need to be printed)

The part where I'm stuck is how can I guarantee that I have no duplicate rolls?

Thanks.

import java.util.Random;

public class KDice {
public static void main(String[] args) {
    Random random = new Random();
    long playerOneWins = 0, playerTwoWins = 0, ties = 0;
    int playerOneSum, playerTwoSum;

    //for long number use L as suffix
    for (long i = 0; i < 2176782336L; i++) {
    //roll dice for player 1
        playerOneSum = rollDice(random, 7);
    //roll dice for player 2
        playerTwoSum = rollDice(random, 5);
        //find who won
        if (playerOneSum == playerTwoSum) {
            ties++;
        } else if (playerOneSum > playerTwoSum) {
            playerOneWins++;
        } else {
            playerTwoWins++;
        }
    }
    //after all the round done, display stats
    System.out.println("Player 1 win: " + playerOneWins);
    System.out.println("Player 2 win: " + playerTwoWins);
    System.out.println("Ties: " + ties);
}

public static int rollDice(Random random, int count) {
    int sum = 0;
    for (int i = 0; i < count; i++) {
        sum += generateRandomNumber(random);
    }

    return sum;
}

public static int generateRandomNumber(Random random) {
    return random.nextInt(6) + 1; //return number between 1 to 6
}

}

Answer 1

Here is a more compact and slightly more efficient way of achieving this. It works by:

• starting with an array of 12 dice, initialized to all 1's (except the last for the first "toss")
• then those dice are essentially incremented in a quasi base 7 to get the next toss. quasi because there are no 0's.
• the sums are modified by either adding 1 or subtracting 5 depending on the the transition between between adjacent dice which would alter the sum by either +1 or -5.

int[] dice = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 };
int sum5 = 4; // inital sum for sum of five dice before first toss
int sum7 = 7; // initial sum for sum of seven dice before first toss
int sum7wins = 0; 
int sum5wins = 0;
int ties = 0;
outer:
for(;;) {
    for (int i = dice.length - 1; i >= 0;) {
        int val = dice[i];
        if (val < 6) {
            dice[i] = val + 1;
            if (i < 7) {
                sum7++;
            } else {
                sum5++;
            }
            break;
        }
        if (i == 0) {
            // first die is a 6 so we're done.
            break outer;
        }
        dice[i] = 1;
        if(i < 7) {
            sum7-=5;
        } else {
            sum5-=5;
        }
        i--;
    }

    if (sum5 > sum7) {
        sum5wins++;
    } else if (sum7 > sum5) {
        sum7wins++;
    } else {
        ties++;
    }
}

System.out.println("sum7wins: " + sum7wins);
System.out.println("sum5wins: " + sum5wins);
System.out.println("ties: " + ties);

Prints

sum7wins: 1877205968
sum5wins: 225571216
ties: 74005152

Answer 2

To simulate each possible roll of 12 dice, I use 12 nested for-loops so that I can produce each possible roll.

I replaced your random rolls of the dice with this loop:

int[] dice = new int[12];

for (dice[0] = 1; dice[0] <= 6; dice[0]++) {
    System.out.println("dice[0] = " + dice[0]);

    for (dice[1] = 1; dice[1] <= 6; dice[1]++) {
        System.out.println("dice[1] = " + dice[1]);

        for (dice[2] = 1; dice[2] <= 6; dice[2]++) {
            System.out.println("dice[2] = " + dice[2]);

            for (dice[3] = 1; dice[3] <= 6; dice[3]++) {
                for (dice[4] = 1; dice[4] <= 6; dice[4]++) {
                    for (dice[5] = 1; dice[5] <= 6; dice[5]++) {
                        for (dice[6] = 1; dice[6] <= 6; dice[6]++) {
                            for (dice[7] = 1; dice[7] <= 6; dice[7]++) {
                                for (dice[8] = 1; dice[8] <= 6; dice[8]++) {
                                    for (dice[9] = 1; dice[9] <= 6; dice[9]++) {
                                        for (dice[10] = 1; dice[10] <= 6; dice[10]++) {
                                            for (dice[11] = 1; dice[11] <= 6; dice[11]++) {

                                                playerOneSum = dice[0] + dice[1] + dice[2] + dice[3] + dice[4] + dice[5] + dice[6];
                                                playerTwoSum = dice[7] + dice[8] + dice[9] + dice[10] + dice[11];


                                                //find who won
                                                if (playerOneSum == playerTwoSum) {
                                                    ties++;
                                                } else if (playerOneSum > playerTwoSum) {
                                                    playerOneWins++;
                                                } else {
                                                    playerTwoWins++;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

It took about three-four minutes to run through. I put in the println's to keep me from being too impatient. The results are:

Player 1 win: 1877280394
Player 2 win: 225654001
Ties: 73847941

Answer 3

2,176,782,336 is the number of possibilities of combination that can happens (= 6^12). As i see you are trying roll 2,176,782,336 times randomly - which i think cannot resolve your question.

Edit, using 12 nested for loop might resolve your question:

public static void main(String args[]) {
    int numP1Win = 0;
    int numP2Win = 0;
    int numdraw = 0;
    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                for (int l = 1; l <= 6; l++) {
                    for (int m = 1; m <= 6; m++) {
                        for (int n = 1; n <= 6; n++) {
                            for (int o = 1; o <= 6; o++) {
                                for (int p = 1; p <= 6; p++) {
                                    for (int q = 1; q <= 6; q++) {
                                        for (int r = 1; r <= 6; r++) {
                                            for (int s = 1; s <= 6; s++) {
                                                for (int t = 1; t <= 6; t++) {
                                                    if (i + j + k + l + m + n + o > p + q + r + s + t) {
                                                        numP1Win++;
                                                    }
                                                    else if (i + j + k + l + m + n + o < p + q + r + s + t) {
                                                        numP2Win++;
                                                    }
                                                    else {
                                                        numdraw++;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    System.out.println("Num P1 Win: " + numP1Win);
    System.out.println("Num P2 Win: " + numP2Win);
    System.out.println("Num Draw: " + numdraw);
}

Output:

Num P1 Win: 1877205968 Num P2 Win: 225571216 Num Draw: 74005152

Answer 4

It seems to me that you misunderstood the question.

The question asks you to go through all possible outcomes and classify each outcome to either "A wins", "B wins" or "a tie".

For that, you don't use random. The answer should not change if you run the program many times. To enumerate all possible combinations of rolled dice, you can use 12 nested for loops that each count from 1 to 6. This way, the body of innermost loop will be executed 6^12 times - exactly once per any possible outcome. What you need to do is to sum 7 of the loop variables and compare it to sum of 5 other loop variables. Based on that, you either increase the counter for "A wins", "B wins" or "ties".

Alternatively, you don't need to count ties, since you always know the total number of results.

Answer 5

If you are trying to go through every combination, you should not be rolling randomly. Just systematically go through every combination (e.g., with loops), and do your counting as you go along.