#include <cstdint>
#include <cstdlib>
#include <iostream>

/***************************************************
 * How long to get all four?
 *
 * The function std::rand() returns a pseudo-random
 * integer between 0 and RAND_MAX.
 *
 * On many systems,
 *
 *     RAND_MAX == 2^31 - 1.
 *
 * Thus, for this exercise,
 *
 *     std::rand() % 4
 *
 * produces one of
 *
 *     0, 1, 2, or 3.
 *
 *
 * THE EXPERIMENT
 *
 * Suppose we repeatedly roll a four-sided die whose
 * faces are numbered
 *
 *     0, 1, 2, and 3.
 *
 * We continue rolling until all four faces have
 * appeared at least once.
 *
 * For example, three possible trials are
 *
 *     2 3 1 3 1 2 0
 *
 *     0 2 1 3
 *
 *     2 1 3 1 2 3 1 1 2 1 0.
 *
 * These trials require 7, 4, and 11 rolls,
 * respectively.
 *
 * If these were our only three trials, the average
 * number of rolls would be
 *
 *     (7 + 4 + 11)/3
 *
 *         = 22/3
 *
 *         = 7.3333...
 *
 *
 * YOUR TASK
 *
 * Write a function that performs this experiment n
 * times and returns the average number of rolls
 * required to see all four faces.
 *
 * What do you expect this average to approach as n
 * becomes large?
 *
 *
 * WHY IS THIS A BITWISE EXERCISE?
 *
 * We need to remember whether each of the four faces
 * has appeared.
 *
 * Four bits are sufficient:
 *
 *     bit 0: have we rolled a 0?
 *     bit 1: have we rolled a 1?
 *     bit 2: have we rolled a 2?
 *     bit 3: have we rolled a 3?
 *
 * We can therefore use four bits as flags.
 *
 * Initially,
 *
 *     flags = 0000.
 *
 * If we roll a 2, we want
 *
 *     flags = 0100.
 *
 * If we then roll a 0,
 *
 *     flags = 0101.
 *
 * If we then roll a 3,
 *
 *     flags = 1101.
 *
 * We continue until
 *
 *     flags = 1111,
 *
 * indicating that all four faces have appeared.
 *
 *
 * SETTING THE APPROPRIATE BIT
 *
 * If the result of a roll is k, then
 *
 *     1 << k
 *
 * produces the appropriate mask:
 *
 *     k == 0:    0001
 *     k == 1:    0010
 *     k == 2:    0100
 *     k == 3:    1000.
 *
 * We can then set the corresponding flag using
 * bitwise OR:
 *
 *     flags |= 1 << k;
 *
 * Repeated rolls of the same face do not cause a
 * problem: setting a bit that is already 1 simply
 * leaves it equal to 1.
 ***************************************************/

// Function declarations
int main();
double trials( unsigned int n );

// Function definitions
int main() {
    std::cout << "RAND_MAX == "
              << RAND_MAX
              << std::endl;

    std::cout << trials(      10 ) << std::endl;
    std::cout << trials(     100 ) << std::endl;
    std::cout << trials(    1000 ) << std::endl;
    std::cout << trials(   10000 ) << std::endl;
    std::cout << trials(  100000 ) << std::endl;
    std::cout << trials( 1000000 ) << std::endl;

    return 0;
}

double trials( unsigned int n ) {
    return 0.0;
}
















































// Hint:
//
// Use the four low-order bits of an unsigned integer
// to record which faces have appeared:
//
//     0000    no faces have appeared
//
//     0001    face 0 has appeared
//     0010    face 1 has appeared
//     0100    face 2 has appeared
//     1000    face 3 has appeared
//
// Multiple bits may, of course, be set:
//
//     1101
//
// indicates that faces 0, 2, and 3 have appeared.
//
// Once
//
//     flags == 0b1111,
//
// all four faces have appeared.
















































// One solution:

/*
double trials( unsigned int n ) {
    std::uint64_t rolls{ 0 };

    for ( unsigned int k{ 0 }; k < n; ++k ) {
        unsigned int flags{ 0 };

        while ( flags != 0b1111 ) {
            unsigned int roll{
                static_cast<unsigned int>(
                    std::rand() % 4
                )
            };

            flags |= 1U << roll;
            ++rolls;
        }
    }

    return static_cast<double>( rolls )/n;
}
*/


/***************************************************
 * Afterthought
 *
 * This is an example of using the individual bits
 * of an integer as Boolean flags.
 *
 * Instead of storing four separate variables such
 * as
 *
 *     bool seen_0;
 *     bool seen_1;
 *     bool seen_2;
 *     bool seen_3;
 *
 * we store all four pieces of information in four
 * bits of one integer.
 *
 * This technique is commonly called a bit mask or
 * bit field.
 *
 *
 * What should the experimental result approach?
 *
 * There is also a theoretical answer.
 *
 * The expected number of rolls required to see all
 * four faces is
 *
 *     4(1/4 + 1/3 + 1/2 + 1)
 *
 *       = 25/3
 *
 *       = 8.3333...
 *
 * This is an example of the coupon collector
 * problem.
 ***************************************************/