6 out of 49 Lottery

Question

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!

Answer 1

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×10⁹ draws to produce a win, which is 100 times more than the expected 1.4×10⁷ 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);
}

Answer 2

• 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).

Answer 3

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).

Answer 4

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.