/**
 * 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;
}