-1

I'm trying to make a program that represents the birthday paradox. I understand the paradox and I'm pretty sure my code is wrong but I'm not sure where I went wrong. I've looked through related posts, but I haven't found anything that's helpful. I wrote the code when I was younger, so sorry if it's a bit messy. I know there are other ways to do it, and I understand why those work. I just want to know why my code doesn't work. Thanks!

EDIT: Sorry, it's late. Forgot to put what my actual problem was. I run it how it is and expect to get about 50.5%, which is the theoretical value. But, instead, I get about 21.1%.

public class Main {
    static int trialsSucceeded = 0; // Stores number of successful trials
    static final int TRIALS = 1000000; // 1,000,000 is a good number :) Biggest I've tried: 2,147,483,647, which is Integer.MAX_VALUE
    static int numberOfPeople = 23; // The 'n' value for the birthday paradox

public static void main(String[] args) {
    ArrayList<Integer> birthdays = new ArrayList<Integer>(); // Stores people's birthdays

    // Runs until desired trials are completed
    for (int trialNumber = 0; trialNumber < TRIALS; trialNumber++) {
        // Provides progress updates to user
        if (trialNumber % 1000 == 0)
            System.out.printf("%.1f%% complete\n", (double) trialNumber * 100 / TRIALS);

        // Populates the birthdays array
        for (int personNumber = 0; personNumber < numberOfPeople; personNumber++) {
            birthdays.add(getRandInt(1, 365));
        }

        // Used later to see if current trial should end
        int prevTrialsSucceeded = trialsSucceeded;

        // Checks each person's birthday against everyone else's
        for (int i = 0; i < birthdays.size(); i++) {
            for (int j = i + 1; j < birthdays.size(); j++) {
                // If birthdays match, marks trial as a success jumps to next trail
                if ((birthdays.get(i) == birthdays.get(j))) {
                    trialsSucceeded += 1;
                    break;
                }
            }
            // Jumps to next trial if this one has already succeeded
            if (prevTrialsSucceeded != trialsSucceeded) {
                break;
            }
        }
        // Clears list of birthdays to get ready for next trial
        birthdays.clear();
    }
    // Tells user ratio of successful trials to total trials
    System.out.println(((double) trialsSucceeded / TRIALS * 100) + "% of trials succeeded");
}

private static int getRandInt(int lowerBound, int upperBound) {
    // Returns random integer between lowerBound and upperBound
    Random random = new Random();
    return random.nextInt(upperBound - lowerBound + 1) + lowerBound;
}

}

Hades948
  • 21
  • 6
  • 2
    Your code [doesn't work](http://importblogkit.com/2015/07/does-not-work/)? – Robert Columbia Jan 11 '17 at 04:19
  • @Hades you did even provide a testcase and sample output. – Enzokie Jan 11 '17 at 04:20
  • @RobertColumbia My eyes don't work anymore. – shmosel Jan 11 '17 at 04:23
  • Beware! Beware! Beware the [question ban](http://meta.stackoverflow.com/questions/255583/what-can-i-do-when-getting-we-are-no-longer-accepting-questions-answers-from-th). You are well on the road to a question ban. You should read our information on what is [on topic](http://stackoverflow.com/help/on-topic) on this site. – Robert Columbia Jan 11 '17 at 04:24
  • You don't need `prevTrialsSucceeded`. It looks like you used that as a way to get out of a double loop. But there's a better way to do it: use a _labeled break_. Please see https://docs.oracle.com/javase/tutorial/java/nutsandbolts/branch.html. – ajb Jan 11 '17 at 04:39
  • Also, you shouldn't use `new Random()` every time you want a random number; instead, use it _once_ to create a random number generator, and then generate a stream of numbers from that. Using `new Random()` every time may lead to a poorer distribution. – ajb Jan 11 '17 at 05:05

2 Answers2

2

The underlying issue is this line:

if ((birthdays.get(i) == birthdays.get(j))) {

This is comparing Integer objects for identity equality. What you need to do here is compare for value equality:

if ((birthdays.get(i).equals(birthdays.get(j)))) {

This should give you the right result, slightly above 50%.

clstrfsck
  • 14,715
  • 4
  • 44
  • 59
  • Yes, I've tested this code with similar change and result is above 50%. I was about to post,but you were faster!! – Vijayakumar Udupa Jan 11 '17 at 04:36
  • Oh, okay. Thanks so much! This has been driving me insane for a while. Nice to know my logic was still fine and I'm not going crazy!! :D – Hades948 Jan 11 '17 at 04:39
1

As others have figured correctly your problem is rooted in comparing references... But even when fixing that problem the solution here is neither efficient nor easy to grasp.

There is a simpler way to check this: just use a Set to store the random number birthdays instead of a list. But before adding the next number you use Set.contains() to check if that number is already in the set. If so you found a match... and you can stop right there!

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • I know. Again, excuse my poor coding choices. But, when it breaks out of the inner loop, it should also break out of the outer loop. – Hades948 Jan 11 '17 at 04:28
  • Yes I missed the root cause... But I fixed that and improved the suggestion for a better solution. – GhostCat Jan 11 '17 at 04:52