import java.util.concurrent.ThreadLocalRandom;

/**
 * Calculate the probability that at least two people from a random sample of 23 will have 
 * the same birthday. The probability is slightly higher than 50%, a perhaps surprising 
 * fact that is frequently referred to as the Birthday Paradox.
 *
 * @author Drue Coles
 */
public class BirthdayParadox {

    public static void main(String[] args) {

        int numPeople = 23;
        
        final int trials = 1_000_000;
        int matches = 0;
            
        // Monte Carlo simulation
        for (int i = 0; i < trials; i++) {
            if (sampleHasMatch(numPeople)) {
                matches++;
            }
        }

        System.out.printf("Sampling %d birthdays at random.%n", numPeople);
        double probability = (double) matches / trials * 100;
        System.out.printf("%.2f%% probability of a birthday match. %n", probability);
    }

    /**
     * Samples random birthdays and returns true if and only if there is at least one day
     * that is sampled twice.
     */
    private static boolean sampleHasMatch(int sampleSize) {
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        int[] days = new int[365];

        for (int i = 0; i < sampleSize; i++) {
            int j = rand.nextInt(days.length);
            days[j]++;
            if (days[j] == 2) {
                return true;
            }
        }
        return false;
    }
}