/**

 * lotto.c

 * computes the best n lottery-values from m loops out of [1..end]

 *

 *  ------------------------------------------------------------------------------

 * | ==18509== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 13 from 1)    |

 * | ==18509== malloc/free: in use at exit: 0 bytes in 0 blocks.                  |

 * | ==18509== malloc/free: 10,003 allocs, 10,003 frees, 280,600 bytes allocated. |

 *  ------------------------------------------------------------------------------

 */

#include <stdio.h>

#include <stdlib.h>

#include <getopt.h>

#include <time.h>

#ifndef DEBUG

#warning "NO DEBUG SUPPORT: COMPILE with -DDEBUG"

#endif

#define ONESECOND 500000

typedef long int LONG;

/*

 * compare function for qsort

 */

LONG compare (LONG * a, LONG * b)

{

    if (*a > *b)

        return 1;

    else

        return -1;

}

/*

 * lottery number generator for num values [ 1..end ]

 */

LONG *lottery (LONG end, LONG num)

{

    int i, j;

    LONG *z;

    int unique;

    if ((z = (LONG *) calloc (num + 1, sizeof (int))) == NULL)

        exit (0);

    for (i = 0; i < num; i++) {

        do {

            z[i] = 1 + (int)((float)end * rand () / (RAND_MAX + 1.0));

            unique = 1;

            for (j = 0; j < i; j++) {

                if (z[j] == z[i]) {

                    unique = 0;

                    break;

                }

            }

        } while (!unique);

    }

    qsort (z, num, sizeof (int), (void *)&compare);

    return z;

}

/*

 * evaluates an array of numbers with num elements

 */

LONG *evaluation (LONG * numbers, int num, int verbose)

{

    int i, j, k;

    int printed;

    LONG *values;

    LONG *z;

    int found;

    if (verbose) {

        printf ("\nProbabilistic evaluation\n------------------------\n");

        for (i = 0; i < num; i++)

            printf ("%4d: %8ld times\n", i + 1, numbers[i]);

        printf ("\n");

    }

    if ((values = calloc (num + 1, sizeof (int))) == NULL)

        exit (0);

    if ((z = calloc (num + 1, sizeof (int))) == NULL)

        exit (0);

    for (j = 0; j < num; j++) {

        values[j] = numbers[j];

    }

    qsort (numbers, num, sizeof (int), (void *)&compare);

    /*

     * numbers = sorted list

     * values  = unsorted list

     */

    printed = k = 0;

#ifdef DEBUG

    printf ("The following algorithm seems to be too slow\n");

#endif

    /*

     * REPLACE THIS

     */

    for (i = 0; i < num; i++)

        for (j = 0; j < num; j++) {

            if (numbers[i] == values[j]) {

                found = 0;

                for (k = 0; k < printed; k++)

                    if (z[k] == j) {

                        found = 1;

                        break;

                    }

                if (!found)

                    z[printed++] = j;

            }

        }

#ifdef DEBUG

    printf ("The algorithm ran %d times\n", i * j * k);

#endif

    /*

     * SLOW PIECE OF CODE

     */

    free (values);

    return z;

};

int main (int argc, char **argv)

{

    LONG *values;

    LONG *numbers;

    LONG max;

    int i, j;

    int found;

    int loop;

    int verbose, wide, end, num;

    verbose = wide = 0;

    end = 49;

    num = 6;

    max = ONESECOND;

    struct option options[] = {

        {"max", 1, 0, 'm'},

        {"end", 1, 0, 'e'},

        {"numbers", 1, 0, 'n'},

        {"verbose", 0, 0, 'v'},

        {"wide", 0, 0, 'w'},

        {"help", 0, 0, 'h'},

    };

    while ((i = getopt_long_only (argc, argv, "m:e:n:vwh", options, NULL)) != -1) {

        switch (i) {

        case 'm':

            max = atol (optarg);

            break;

        case 'e':

            end = atoi (optarg);

            break;

        case 'n':

            num = atoi (optarg);

            break;

        case 'v':

            verbose = 1;

            break;

        case 'w':

            verbose = 1;

            wide = 1;

            break;

        case 'h':

            printf ("Usage: %s [ -e end | -m max | -n num | -v | -w ]\n", argv[0]);

            printf ("       -e: Numbers from [1..end]\n");

            printf ("       -m: evaluates max loops\n");

            printf ("       -n: n-numbers from [1..end]\n");

            printf ("       -v: verbose output\n");

            printf ("       -w: verbose and wide output\n");

            return EXIT_SUCCESS;

        }

    }

    if (num >= end)

        num = end - 1;

    srand (time (NULL));

    if ((numbers = calloc (end + 1, sizeof (int))) == NULL)

        exit (0);

    for (loop = 0; loop < end; loop++)

        numbers[loop] = 0;

    for (loop = 0; loop < max; loop++) {

        values = lottery (end, num);

        for (i = 0; i < end; i++) {

            found = 0;

            for (j = 0; j < num; j++)

                if (values[j] == i + 1) {

                    if (verbose)

                        printf ("%3s", "XX");

                    numbers[i]++;

                    found = 1;

                    break;

                }

            if (verbose) {

                if (!found)

                    printf ("%3d", i + 1);

            }

            if (wide) {

                if ((i % 7) == 0)

                    printf ("\n");

            }

        }

        if (verbose)

            printf ("\n");

        free (values);

    }

    values = evaluation (numbers, end, verbose);

    for (i = 0; i < num; i++)

        numbers[i] = values[(end - 1) - i];

    qsort (numbers, num, sizeof (int), (void *)&compare);

    for (i = 0; i < num; i++)

        printf ("%ld ", numbers[i] + 1);

    printf ("\n");

    free (values);

    free (numbers);

    return EXIT_SUCCESS;

}