// Arup Guha
// 1/7/2013
// Simulation shown in COP 3930H: Math Modeling

// Here we attempt to simulate asking people their birthdays until we get one pair of people
// with the same birthday.

#include <stdio.h>
#include <time.h>

#define DAYSINYEAR 365
#define NUMTIMES 2000000

int runSim();

int main() {

    srand(time(0));

    int i;

    // Safe initial values.
    double sum = 0;
    int min = 365, max = 1;

    // Run each simulation.
    for (i=0; i<NUMTIMES; i++) {

        int cur = runSim();

        // Update each tally as needed.
        sum = sum + cur;
        if (cur < min)
            min = cur;
        if (cur > max)
            max = cur;
    }

    // Print the results.
    double avg = sum/NUMTIMES;
    printf("On average it took %lf people.\n", avg);
    printf("Min was %d\n", min);
    printf("Max was %d\n", max);
    return 0;
}

// Generates random numbers in [0, 364] until one number has been generated twice.
// Returns the number of values generated in the simulation.
int runSim() {

    int freq[DAYSINYEAR];
    int i;

    // Initialize the frequency array.
    for (i=0; i<DAYSINYEAR; i++)
        freq[i] = 0;

    int cnt = 0;
    while (1) {

        // Generate a random day and update our counters.
        int day = rand()%365;
        freq[day]++;
        cnt++;

        // We have a twin, get out!
        if (freq[day] > 1) break;
    }
    return cnt;
}