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

// Here we attempt to simulate asking people their birthdays until we get at least one of each
// of the possible 365 birthdays. Theoretically, the solution to this for n distinct items is
// n*H(n), where H(n) is the nth Harmonic number.

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

#define DAYSINYEAR 365
#define NUMTIMES 10000

int runSim();

int main() {

    srand(time(0));

    int i;

    double sum = 0;

    // Values to indicate that min and max haven't been set.
    int min = 0, max = 0;

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

        // Run simulation and update our running sum.
        int cur = runSim();
        sum = sum + cur;

        // Update for the first value and best seen.
        if (min == 0 || cur < min)
            min = cur;
        if (max == 0 || cur > max)
            max = cur;
    }

    // Print out 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 each number has been generated at least once.
// Returns the number of values generated in the simulation.
int runSim() {

    int freq[DAYSINYEAR];
    int i;

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

    int cnt = 0, numDistinct = 0;
    while (1) {

        // This is our current random birthday.
        int day = rand()%365;

        // Mark that we found a new one, if we did.
        if (freq[day] == 0)
            numDistinct++;

        // Update our frequency array and our overall day count.
        freq[day]++;
        cnt++;

        // We've generated all of them, get out!
        if (numDistinct == DAYSINYEAR) break;
    }
    return cnt;
}