24
\$\begingroup\$

In Germany we have a lottery with the following rules:

You have to guess 6 numbers. The numbers shall be less than 50 and greater then 0. A number occurs only one time in a game. So you can not guess the same number multiple times in one game. If you have guessed 6 numbers right you won the game.

I wanted to know how many attempts it would take to have 6 right numbers and wrote this example. It works but unfortunately the example is very slow and needs a lot of time because it is very unlikely to have 6 numbers right. How could I improve the speed?

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

int play(int attempt[])
{
    // generate draw
    int draw[6];
    draw[0] = rand() % 49 + 1;
    for(int i = 1; i < 6; i++)
    {
        int random_number;
        generate:
        random_number = rand() % 49 + 1;
        for(int j = 0; j < i; j++)
        {
            if(random_number == draw[j])
            {
                goto generate;
            }
        }
        draw[i] = random_number;
    }

    // compare draw with attempt
    int compared = 0;
    for(int i = 0; i < 6; i++)
    {
        if(attempt[i] == draw[i])
        {
            compared++;
        }
    }

    if(compared == 6)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main()
{
    srand (time(NULL));

    int attempt[] = {1, 2, 3, 4, 5, 6};
    long long int counter = 1;
    while(!play(attempt))
    {
        counter++;
    } 
    printf("You only needed %lld attempts to get 6 right numbers!\n", counter);
}

By the way: after around 5 minutes the program was finished and I needed only 1,487,592,156 attempts!

\$\endgroup\$
  • 2
    \$\begingroup\$ Actually the rules of the German 6 aus 49 lottery are slightly different, due to the additional Superzahl, which results in a slightly different chance to win the "6 correct guesses" category (≈1/15.5M, not ≈1/14.0M). \$\endgroup\$ – mkrieger1 Aug 17 '17 at 11:09
  • \$\begingroup\$ @mkrieger1 As the OP does not generate the Superzahl, he actually tests for "6 correct guesses (without Superzahl) or 6 correct guesses with Superzahl", and then we are at about 1/14M again. I don't think he would mind "accidentally" being promoted to the higher class by the Superzahl ... \$\endgroup\$ – Hagen von Eitzen Aug 18 '17 at 12:47
29
\$\begingroup\$

Bug

Winning a 6/49 game is, of course, unlikely. The probability of any single ticket having all six numbers correct is

$$\dfrac{1}{\binom{49}{6}} = \dfrac{6!\,(49-6)!}{49!} = \dfrac{1}{13983816}$$

But your code required 1.5×109 draws to produce a win, which is 100 times more than the expected 1.4×107 draws. Why? Because your comparison loop…

// compare draw with attempt
int compared = 0;
for(int i = 0; i < 6; i++)
{
    if(attempt[i] == draw[i])
    {
        compared++;
    }
}

… requires the chosen numbers to be in the same order! Thus, a win is 720× less likely in your simulation than in a real-life 6/49 game.

Performance and style

Your // generate draw loop has a special case:

// generate draw
int draw[6];
draw[0] = rand() % 49 + 1;
for(int i = 1; i < 6; i++)
{
    …

You could easily eliminate the special case:

// generate draw
int draw[6];
for(int i = 0; i < 6; i++)
{
    …

You also have a goto to handle cases where you draw the same number twice. Well structured code should not have gotos. As an alternative to generating random numbers and checking for conflicts, consider doing a partial shuffle instead.

Suggested solution

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

const int *lotto_draw(int r)
{
    static int balls[] = {
         1,  2,  3,  4,  5,  6,  7,
         8,  9, 10, 11, 12, 13, 14,
        15, 16, 17, 18, 19, 20, 21,
        22, 23, 24, 25, 26, 27, 28,
        29, 30, 31, 32, 33, 34, 35,
        36, 37, 38, 39, 40, 41, 42,
        43, 44, 45, 46, 47, 48, 49
    };
    const static int n = sizeof(balls) / sizeof(balls[0]);

    // Partial Fisher-Yates shuffle on the last r elements
    for (int i = n - 1; i >= n - r; i--)
    {
        int j = rand() % (i + 1);
        int swap = balls[j];
        balls[j] = balls[i];
        balls[i] = swap;
    }
    return balls + n - r;
}

int play(int attempt[], int r)
{
    const int *draw = lotto_draw(r);

    // compare draw with attempt
    int correct = 0;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < r; j++)
        {
            if (attempt[i] == draw[j])
            {
                correct++;
            }
        }
    }

    return (correct == r);
}

int main()
{
    srand(time(NULL));

    int attempt[] = {1, 2, 3, 4, 5, 6};
    int r = sizeof(attempt) / sizeof(attempt[0]);
    long long int counter;
    for (counter = 1; !play(attempt, r); counter++);
    printf("You only needed %lld attempts to get %d right numbers!\n",
           counter, r);
}
\$\endgroup\$
  • \$\begingroup\$ That's how I understood the rules. I dont play lottery so I thought it would be that way. I will correct this. \$\endgroup\$ – Dexter Thorn Aug 16 '17 at 21:42
  • 1
    \$\begingroup\$ @DexterThorn Numbers drawn by the lottery are automatically ordered from small to large. In fact, a number of lottery forms just display every possible option in a grid and you just circle the ones you want. \$\endgroup\$ – Nzall Aug 17 '17 at 8:22
  • \$\begingroup\$ @Nzall If that's true, shouldn't that affect which numbers are valid? As in, if the first number is already a 3, the rest will not be lower than 3. \$\endgroup\$ – Mast Aug 17 '17 at 9:25
  • \$\begingroup\$ @Mast no, they first draw all balls, then sort them. If you get a 42 - 37 - 22 - 32 - 39 - 3, they're always seen as 3 - 22 - 32 - 37 - 39 - 42. The goal is just to guess all 6 numbers, but the order doesn't matter. in this case, if the 42 is drawn, that ball is taken out of the pool and the next ball is chosen from the remaining 48 balls. I suggest next time they broadcast a lottery drawing on your local TV station you watch and see what happens. \$\endgroup\$ – Nzall Aug 17 '17 at 11:53
12
\$\begingroup\$
  • No naked loops. Every time you feel compelled to put a comment like // generate draw, it means you need to factor the commented code into a generate_draw() function.

  • Return conditions, not flags.

    if(compared == 6)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    

    is a long way to say

    return compared == 6;
    

All that said, the outcome of the program is misleading. It is not that you need only that many attempts; it is that the program in this run took that many attempts.

The probability to hit the jackpot is \$\dfrac{1}{\binom{49}{6}}\$; a really tiny number, and an expected number of attempts is \$\binom{49}{6}\$. This is quite a big number; what's worse is that there is no guarantee that a particular run would ever result in a hit. In other words, there is a chance to wait indefinitely long (and there is a chance to win at the first try).

\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer! The output of the program is of course no absolute value, it just was interesting to see how much attempts it could need. My second try is now running for an half hour (and isn't finished). I first tried to generate an array in a seperate function and return it to the calling functions, but then i noticed that i need knowledge about pointers and that stuff to do that. For the sake of simplity i just generated the array in the same function. But I will try to seperate this code in another function as you said when I have learned something more about pointers. \$\endgroup\$ – Dexter Thorn Aug 16 '17 at 21:34
  • \$\begingroup\$ @Deduplicator I honestly don't see how the \$frac{1}{2}\$ factor may appear, but I could be as well wrong. \$\endgroup\$ – vnp Aug 16 '17 at 22:44
10
\$\begingroup\$

Even if rand() returns an evenly-distributed number, note that (rand() % 49) + 1 will not be evenly distributed. Your RNG will be ever-so-slightly biased towards smaller numbers (generally, those less than RAND_MAX % 49 + 1).

\$\endgroup\$
  • 2
    \$\begingroup\$ Since rand() sucks in most implementations, I would not try to eliminate that bias (e.g. via rejection), but switch to an alternative library which implements a quality prng and a high level API that supports generating numbers from the interval 0 to n-1. \$\endgroup\$ – CodesInChaos Aug 17 '17 at 9:20
  • 1
    \$\begingroup\$ I give an analysis of the bias introduced by this technique here: ericlippert.com/2013/12/16/… \$\endgroup\$ – Eric Lippert Aug 17 '17 at 14:34
4
\$\begingroup\$

As pointed out in 200_success's answer, the way you compare the guessed and drawn numbers is wrong. But instead of comparing each guessed number with each drawn number, you can speed up the comparison with a 49-element table. If the set of guessed numbers contains number i, the entry at index i is set to 1. Otherwise, it is set to 0. So you only need a single array lookup to determine whether a number is contained in the set of guessed numbers.

Here's an example based on the partial Fisher-Yates shuffle from 200_success's answer. Note that we can terminate early if any of the drawn numbers couldn't be matched.

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

int play(const char attempt_map[49])
{
    static int balls[] = {
         1,  2,  3,  4,  5,  6,  7,
         8,  9, 10, 11, 12, 13, 14,
        15, 16, 17, 18, 19, 20, 21,
        22, 23, 24, 25, 26, 27, 28,
        29, 30, 31, 32, 33, 34, 35,
        36, 37, 38, 39, 40, 41, 42,
        43, 44, 45, 46, 47, 48, 49
    };
    const static int n = sizeof(balls) / sizeof(balls[0]);

    // Partial Fisher-Yates shuffle on the last r elements
    for (int i = n - 1; i >= n - 6; i--)
    {
        int j = rand() % (i + 1);
        int swap = balls[j];
        if (attempt_map[swap-1] == 0)
        {
            return 0;
        }
        balls[j] = balls[i];
        balls[i] = swap;
    }
    return 1;
}

int main()
{
    srand (time(NULL));

    int attempt[] = {1, 2, 3, 4, 5, 6};
    char attempt_map[49] = {0};
    long long int counter = 1;

    // Precompute map.
    for (int i = 0; i < 6; i++)
    {
        attempt_map[attempt[i]-1] = 1;
    }
    while(!play(attempt_map))
    {
        counter++;
    }
    printf("You only needed %lld attempts to get 6 right numbers!\n", counter);
}

Instead of a 49-element char array, you could also use bitmap for an additional speedup.

\$\endgroup\$
  • \$\begingroup\$ Instead of writing out 49 numbers in the code, you might use a standard container and initialise it using std::iota. That makes it easier to change the number of balls for the draw. \$\endgroup\$ – Toby Speight Aug 17 '17 at 13:59
  • 2
    \$\begingroup\$ std::itoa smells like C++. My Code is written in clean C, so i can not use it here. \$\endgroup\$ – Dexter Thorn Aug 17 '17 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.