/* POTM ENTRY:     SnakePit
 * Name:           Tim Ruhl
 * Email:          tim@cs.vu.nl
 * Compilation:    Should work with cc and gcc.
 */

#define NDEBUG

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <signal.h>
#include <unistd.h>
#include <math.h>

				/* Constants */
#define NR_TIMEOUT 1
#define TIMEOUT    590

#define POP_SIZE   200
#define MUTATE     350

#define INIT_WORDS 5

				/* Types */

typedef struct board {
    char fields[25];
} board_t, *board_p;

typedef struct member {		/* Member of the genetic population */
    board_t b;
    int     score;
} member_t, *member_p;

				/* Constant variables */

static int moves[8] = {1, -1, 5, -5, 6, 4, -6, -4};
static int nb[25][8];
static int nrnb[25];
				/* Variables */

static char *progname;
static int timeout = TIMEOUT;
static int nr_timeout = NR_TIMEOUT;
static int running;
static int verbose;
static int give_score;
static int dump_eval;

/* Word list data structures */
static char words[1000][26];
static int  wordlen[1000];
static int  wordcnt[1000];
static int  next[1000][25][26];
static int  nr_words;
static int  freq[26];
static int  sum_freq;


/* Word finder */
static int word_used[1000];
static int used[49];
static int letters, count;
static int seqno;
static int print_words;

/* Genetic population */
static member_t pop[2][POP_SIZE];
static int curr;
static member_t best;

				/* Macros */
#define ABS(x) ((x) < 0 ? -(x) : (x))


				/* Functions  */

static void
usage(void)
{
    fprintf(stderr, "Usage: %s "
	    "[-r <seed>] "
	    "[-t <timeout>] "
	    "[-T <nr timeouts> ]"
	    "[-vdse] "
	    "<wordlist file>\n", progname);
    exit(1);
}

/* handler:
 *                 Handle SIGALRM. Set running to zero which causes the
 *                 computation to terminate.
 */
static void
handler(int s)
{
    running = 0;
}


/* init_neighbors:
 *                 Precompute the neighbor list for all fields.
 */
static void
init_neighbors(void)
{
    int row1, col1, row2, col2;
    int i, j, p;

    for(i = 0; i < 25; i++) {
	row1 = i / 5;
	col1 = i % 5;

	for(j = 0; j < 8; j++) {
	    p = i + moves[j];
	    if (p < 0 || p >= 25) continue;

	    row2 = p / 5;
	    col2 = p % 5;
	    
	    if (ABS(row1 - row2) <= 1 && ABS(col1 - col2) <= 1) {
		nb[i][nrnb[i]++] = p;
	    }
	}
    }
}
    
    

static void
read_words(char *file)
{
    FILE *fp;

    if ((fp = fopen(file, "r")) == NULL) {
	fprintf(stderr, "Cannot open word file %s\n", file);
	exit(1);
    }

    nr_words = 0;
    while(fscanf(fp, "%s", words[nr_words]) == 1) {
	nr_words++;
    }

    fclose(fp);
}

static void
compute_wordlen(void)
{
    int i;

    for(i = 0; i < nr_words; i++) {
	wordlen[i] = strlen(words[i]);
    }
}


/* compute_freq:
 *                 Get the number of occurences of each letter in the
 *                 wordlist. Used to select random letters.
 */
static void
compute_freq(void)
{
    int i, j;

    for(i = 0; i < nr_words; i++) {
	for(j = 0; j < wordlen[i]; j++) {
	    freq[words[i][j] - 'A']++;
	}
	sum_freq += wordlen[i];
    }
}

static void
sort_words(void)
{
    char buf[26];
    int i, j;
    int t;

    for(i = 0; i < nr_words; i++) {
	for(j = i + 1; j < nr_words; j++) {
	    if (strcmp(words[i], words[j]) > 0) {
		strcpy(buf, words[i]);
		strcpy(words[i], words[j]);
		strcpy(words[j], buf);

		t = wordlen[i];
		wordlen[i] = wordlen[j];
		wordlen[j] = t;
	    }
	}
    }
}

/* filter_duplicates:
 *                 Filter duplicate words. According to the FAQ, this is
 *                 not necessary, but I never removed it.
 */
static void
filter_duplicates(void)
{
    int i, j;

    j = 0;
    wordcnt[0] = 1;

    for(i = 1; i < nr_words; i++) {
	if (strcmp(words[i], words[j]) == 0) {
	    wordcnt[j]++;
	    continue;
	}
	
	j++;
	strcpy(words[j], words[i]);
	wordcnt[j] = 1;
	wordlen[j] = wordlen[i];
    }

    nr_words = j + 1;
}


/* compute_next:
 *                 For each word and each prefix length, compute the
 *                 index of the first word that has the same prefix plus
 *                 a letter.
 */
static void
compute_next(void)
{
    int i, j, k, l;
    int high;

    for(i = 0; i < nr_words; i++) {
	for(j = 0; j <= wordlen[i]; j++) {
	    for(k = i + 1; k < nr_words; k++) {
		if (strncmp(words[i], words[k], j) != 0) break;
	    }
	    high = k;
		
	    for(k = 0; k < 26; k++) {
		next[i][j][k] = -1;

		for(l = i; l < high; l++) {
		    if (words[l][j] == 'A' + k) {
			next[i][j][k] = l;
			break;
		    }
		}
	    }
	}
    }
}

/* random_letter:
 *                 Generate a random letter. The selection uses the
 *                 frequency counts of the letters to select letters that
 *                 are likely to occur.
 */
static char
random_letter(void)
{
    int s, t;
    int i;

    s = 1 + (rand() % sum_freq);

    t = 0;
    for(i = 0; i < 26; i++) {
	t += freq[i];
	if (t >= s) {
	    assert(freq[i]);
	    return 'A' + i;
	}
    }

    assert(0);
    return 'A';
}


/* impose_word:
 *                 Tries to place a word on the given board. It does not
 *                 deal with overwriting its own letters.
 */
static void
impose_word(board_p b, int p, int w, int offset)
{
    int s;

    if (offset == wordlen[w]) return;

    b->fields[p] = words[w][offset];

    s = rand() % nrnb[p];
    impose_word(b, nb[p][s], w, offset + 1);
}

/* random_word:
 *                 Select a random word and place in on the board.
 *               
 */
static void
random_word(board_p b)
{
    int w, p;

    w = rand() % nr_words;
    p = rand() % 25;

    impose_word(b, p, w, 0);
}

/* random_board:
 *                 Generate a random solution by placing random letters
 *                 on the board. After that, also some random words are
 *                 placed.
 */
static void
random_board(board_p b)
{
    int i;

    for(i = 0; i < 25; i++) {
	b->fields[i] = random_letter();
    }

    for(i = 0; i < INIT_WORDS; i++) {
	random_word(b);
    }
}

static void
print_board(board_p b)
{
    int i;

    for(i = 0; i < 25; i++) {
	putchar(b->fields[i]);
	if ((i + 1) % 5 == 0) putchar('\n');
    }
}

/* walk_path:
 *                 Try to find a path on the board that contains a word
 *                 from the wordlist. low specifies the first word in the
 *                 sorted wordlist that has a prefix of length len that
 *                 contains the letters on the current path. Avoid
 *                 duplicate words by assigning a sequence number to the
 *                 words_used table. If the table entry for a word is
 *                 equal to the current sequence number, the word has
 *                 already been used.
 */
static void
walk_path(board_p b, int p, int low, int len)
{
    int new;
    int i;

    /* Check whether there are any words with the current prefix. */
    low = next[low][len][b->fields[p] - 'A'];
    if (low == -1) return;

    if (wordlen[low] == len + 1 && word_used[low] != seqno) {
	word_used[low] = seqno;

	if (print_words) {
	    for(i = 0; i < wordcnt[low]; i++) {
		printf("%s\n", words[low]);
	    }
	}

	letters += (len + 1) * wordcnt[low];
	count += wordcnt[low];
    }
	

    for(i = 0; i < nrnb[p]; i++) {
	new = nb[p][i];
	if (used[new]) continue;

	used[new] = 1;

	walk_path(b, new, low, len + 1);

	used[new] = 0;
    }
}

/* walk_board:
 *                 Count the number of words and letters on the given
 *                 board. The sequence number is used to detect
 *                 duplicates.
 */
static void
walk_board(board_p b)
{
    int i;

    letters = count = 0;
    seqno++;
    for(i = 0; i < 25; i++) {
	used[i] = 1;
	walk_path(b, i, 0, 0);
	used[i] = 0;
    }
}

static void
print_member(member_p m)
{
    if (verbose) printf("################\n");
    print_board(&m->b);
    if (verbose) printf("################\n");
    print_words = 1;
    walk_board(&m->b);
    print_words = 0;
    if (verbose || give_score) {
	printf("Score: %d letters with %d words\n", letters, count);
    }
    if (verbose) printf("\n");
}   


/* eval_pop:
 *                 Dump statistics for the current population.
 */
static void
eval_pop(int p)
{
    int sum, sumsq, avg, var, std;
    int count[20];
    int max;
    int i;

    sum = 0; sumsq = 0;

    max = 0;
    for(i = 0; i < POP_SIZE; i++) {
	sum += pop[p][i].score;
	sumsq += pop[p][i].score * pop[p][i].score;
	if (pop[p][i].score > max) max = pop[p][i].score;
    }

    for(i = 0; i < 20; i++) count[i] = 0;

    for(i = 0; i < POP_SIZE; i++) {
	count[(pop[p][i].score * 20 - 1) / max]++;
    }

    printf("Population score histogram (max %d; population size %d):\n", 
	   max, POP_SIZE);
    for(i = 0; i < 20; i++) {
	printf("%4d", count[i]);
    }
    printf("\n");

    avg = sum / POP_SIZE;
    var = sumsq / POP_SIZE - (avg * avg);
    std = sqrt(var) * 100 / avg;

    printf("Average: %d variance: %d normalized standard deviation: %d\n", 
	   avg, var, std);
}
    
/* init_pop:
 *                 Generate the initial population, consisting of
 *                 POP_SIZE members. 
 */
static void
init_pop(void)
{
    board_p b;
    int i;

    for(i = 0; i < POP_SIZE; i++) {
	b = &pop[0][i].b;

	random_board(b);
	walk_board(b);

	/* Add one bonus point to be able to randomly select members */
	pop[0][i].score = 1 + letters * 10 - count;
	if (pop[0][i].score > best.score) {
	    best = pop[0][i];
	}
    }
}

/* find_random:
 *                 Find a weighted random member of the population. Array
 *                 sum contains the sum of the score of the current
 *                 member and all members before it. Using this
 *                 accumulative array, a binary search is applied that
 *                 finds a member.
 */
static int
find_random(int sum[POP_SIZE + 1], int total)
{
    int low, high, middle;
    int s;

    s = 1 + (rand() % total);
    
    low = 0; 
    high = POP_SIZE + 1;
    middle = POP_SIZE / 2;

    while(sum[middle] < s || sum[middle - 1] > s) {
	if (sum[middle] < s) {
	    low = middle;
	} else {
	    high = middle;
	}

	middle = low + (high - low) / 2;
	
	assert(middle > 0 && middle <= POP_SIZE);
	assert(middle >= low);
	assert(middle <= high);
	assert(low <= high);
    }

    middle--;

    assert(middle >= 0 && middle < POP_SIZE);
    return middle;
}
	
    
/* new_member:
 *                 Generate a new member for the next population. First
 *                 two (different) members of the old population are
 *                 selected. The letters of the new member are selected
 *                 from one of the two old members, weighted by their
 *                 score. After that, the mutation factor decides whether
 *                 a new word should be added to the solution. I think
 *                 a mutation parameter of 35% is much too high to call
 *                 it a genetic algorithm, but this was the best value I
 *                 found for my testcase.
 */
static void
new_member(int p, member_p new, int sum[], int total)
{
    board_p b, b1, b2;
    member_p m1, m2;
    int score;
    int i;

    /* All scores are greater than 0 */
    assert(total > 0);

    m1 = &pop[p][find_random(sum, total)];
    do {
	m2 = &pop[p][find_random(sum, total)];
    }while(m1 == m2);
 
    b = &new->b;
    b1 = &m1->b;
    b2 = &m2->b;

    score = m1->score + m2->score;

    for(i = 0; i < 25; i++) {
	if ((rand() % score) < m1->score) {
	    b->fields[i] = b1->fields[i];
	} else {
	    b->fields[i] = b2->fields[i];
	}
    }

    if ((rand() % 1000) < MUTATE) {
	random_word(b);
    }

    walk_board(b);

    /* Add one bonus point to randomly select members */
    new->score = 1 + letters * 10 - count;

    if (new->score > best.score) {
	best = *new;
	if (verbose) print_member(&best);
    }
}

/* next_pop:
 *                 Based on the current population, compute the
 *                 next. First precompute the prefix sums of the
 *                 scores. Also put the best solution found so for in the
 *                 next population.
 */
static void
next_pop(void)
{
    int sum[POP_SIZE + 1];
    int total;
    int next;
    int i;

    total = 0;
    sum[0] = 0;
    for(i = 0; i < POP_SIZE; i++) {
	total += pop[curr][i].score;
	sum[i + 1] = sum[i] + pop[curr][i].score;
    }

    next = 1 - curr;

    pop[next][0] = best;
    for(i = 1; i < POP_SIZE; i++) {
	new_member(curr, &pop[next][i], sum, total);
    }

    curr = next;
}

int
main(int argc, char **argv)
{
    int dump_pop = 0;
    int i;

    progname = argv[0];

    argv++; argc--;

    while(argc && argv[0][0] == '-') {
	switch(argv[0][1]) {
	case 'r':
	    if (argc < 2) usage();
	    srand(atoi(argv[1]));
	    argv++; argc--;
	    break;
	case 't':
	    if (argc < 2) usage();
	    timeout = atoi(argv[1]);
	    argv++; argc--;
	    break;
	case 'T':
	    if (argc < 2) usage();
	    nr_timeout = atoi(argv[1]);
	    argv++; argc--;
	    break;
	case 'd':
	    dump_pop = 1 - dump_pop;
	    break;
	case 'v':
	    verbose = 1 - verbose;
	    break;
	case 's':
	    give_score = 1 - give_score;
	    break;
	case 'e':
	    dump_eval = 1 - dump_eval;
	    break;
	default:
	    usage();
	}

	argv++; argc--;
    }

    if (argc != 1) {
	usage();
    }

    init_neighbors();

    read_words(argv[0]);
    compute_wordlen();
    compute_freq();
    sort_words();
    filter_duplicates();
    compute_next();

    init_pop();
    if (verbose) print_member(&best);
    if (dump_eval) eval_pop(0);

    /* Generate statistics more than once. */
    while(nr_timeout--) {
	running = 1;
	signal(SIGALRM, handler);
	alarm(timeout);

	while(running) {
	    next_pop();
	}

	if (dump_eval) eval_pop(curr);
    }

    if (dump_eval) eval_pop(curr);

    print_member(&best);

    if (dump_pop) {
	printf("++++++++++++++++++++ Population dump +++++++++++++++++++\n");
	for(i = 0; i < POP_SIZE; i++) {
	    printf("Member %d\n", i);
	    print_member(&pop[curr][i]);
	}
    }

    return 0;
}


/*
Local Variables:
compile-command: "gcc -g -ansi -Wall -pedantic -o b1 b1.c -lm"
End:
*/