diff --git a/lotto.c b/lotto.c new file mode 100644 --- /dev/null +++ b/lotto.c @@ -0,0 +1,252 @@ +/** + * $Id: main.c,v 1.1.1.1 2008-04-28 17:32:53 mbroeker Exp $ + * $Author: mbroeker $ + * + * 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 +#include +#include +#include + +#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; + + while ((i = getopt (argc, argv, "m:e:n:vwh")) >= 0) { + 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 0; + } + } + + 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 0; +}