Rand7

/**
* Write a method to generate a random number between 1 and 5 (with uniform
* probability distribution) using only standard Java randomness utilities.
*/

int rand5()
{
    srand(time(nullptr));
    return rand() % 5 + 1;
}

/**
* Write a method to generate a random number between 1 and 7 (with uniform
* probability distribution, given a method that generates a random number
* between 1 and 5 (i.e., implement rand7() using rand5()).
*/

/*
The Algorithm:

- This is more so a math problem than it is a programming one.
  The main idea is that 5 and 7 share a gcd of 35.
  My logic goes as follows:


Consider the matrix[5][5] = 
{
    1 2 3 4 5
    6 0 1 2 3
    4 5 6 0 1
    2 3 4 5 6
    0 1 2 3 4
}

Assume 0 = 7 (7 % 7 == 0).

First: the only way we can find rand7 is if we exceed 5 in someway, by only 
       generating integers 1 - 5.

In the matrix above, we can generate a [row][col]. However, not every
number has the same likelyhood of being selected. 1,2,3,4 all have a 
+1/25 more chance of being selected.

Consider the matrix[7][5] = 
{
    1 2 3 4 5
    6 0 1 2 3
    4 5 6 0 1
    2 3 4 5 6
    0 1 2 3 4
    5 6 0 1 2
    3 4 5 6 0
}

Here, we can reasonably select a random column. But for a random row,
we can have an option of 7 things. If we offset from the bottom,
or from the top, the numbers in the center become more likely
to be selected. This cannot work.

As precedented (5 x 7) is the first minimum matrix to produce
a mapping of all numbers 1-7 (consider 0 to be 7). In this case,
each number has the same uniform count of 5. We can generate the
same mapping 2x as large and obtain a count of 10, but since
products are associative, it doesn't matter how we shape this block
it will always require some mapping for rand7(). 

Instead one thing we can do is generate a different map. On that does
produce a random number 1-7 like so:

{
    1 2 3 4 5
    6 7 1 2 3 
    4 5 6 7 1
    2 3 4 5 6
    7 0 0 0 0
}

Here we have a dart map, but where the indices of the zeros denote an
a non-uniform number relative to the rest of the digits.

Here each digit 1-7 carries a unique count of 3. We can generate 
rand5() -> col and rand5() -> row. And continue doing so if we 
obtain a 0.

Ofcourse this means that the generation of a random number 1-7 
has a chance to run in a non-finite time, with a 4/25 chance
of repeating the loop. 

The chances of reseting the loop the first run is 4/25.
The chances of reseting the loop again is (4/25)^2

So the chances of success increases per iteration is 1 - (4/25)^i.
At roughly 6 iterations we have .99998 chance of success..but never quite = 1.
*/

int rand7_wrong()
{
    int block_number = rand5();
    int map_number = ((block_number - 1) * 7) + 1;

    int map_number_off_set = rand5();
    map_number += map_number_off_set;

    return (map_number / 5) + 1;
}

int rand7_correct()
{
    vector<vector<int>> dart_map = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int rand_i = 0;
    while (rand_i == 0) {
        rand_i = dart_map[rand5() - 1][rand5() - 1];
    }
    return rand_i;
}

void print_frequencies(unordered_map<int, int> &freqs)
{
    cout << endl << endl;
    for (auto i : freqs) {
        cout << i.first << ": " << i.second << endl;
    }
}

void print_matrix()
{
    unordered_map<int, int> num_freq;
    for (int i = 0; i < 7; i++) {
        num_freq.insert({ i, 0 });
    }

    int count = 1;
    while (1) {
        for (int i = 0; i < 5; i++) {
            cout << count++ % 7 << ' ';
            num_freq[(count - 1) % 7]++;
        }
        //print_frequencies(num_freq);
        pause();
    }

}

int main()
{
    while(1) {
        cout << rand7_correct() << " ";
        pause();
    }
}

/*

        while (true) {
            int num = 5 * (rand5() - 1) + (rand5() - 1);
            if (num < 7) {
                return (num + 1);
            }
        }
*/