#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

/* include game configuration */
#ifndef GAME_CONF
#define GAME_CONF "gold-cult.h"
#endif
#include GAME_CONF

/* in the following variables named selected, selected1, selected2
   refer to bitsets which represent selected words from words[] */

#ifndef LINE_LENGTH
#define LINE_LENGTH 70
#endif

/* print words that have not yet been selected */
void print_word_set(unsigned int indent, unsigned int group_size,
      unsigned int selected) {
   unsigned int printed = 0; unsigned int group_count = 0;
   for (unsigned int index = 0; index < nof_words; ++index) {
      if ((1<<index) & selected) {
	 int len = strlen(words[index]);
	 if ((group_size > 0 && group_count == group_size) ||
	       (printed > 0 && indent + printed + len + 1 > LINE_LENGTH)) {
	    printf("\n%*s", indent, "");
	    printed = 0; group_count = 0;
	 }
	 if (printed) {
	    printf(" "); ++len;
	 }
	 printf("%s", words[index]);
	 printed += len; ++group_count;
      }
   }
   printf("\n");
}

/* number of letters 'a' to 'z' */
enum { letters = 'z' - 'a' + 1 };

/* return true if the selected words win,
   i.e. if one of the letters occurs winning_count times */
char won(unsigned int selected) {
   unsigned int count[letters] = {0};
   for (unsigned int index = 0; index < nof_words; ++index) {
      if ((1<<index) & selected) {
	 for (char* cp = words[index]; *cp; ++cp) {
	    assert(islower(*cp));
	    unsigned int letter = *cp - 'a';
	    if (++count[letter] == winning_count) {
	       return letter + 'a';
	    }
	 }
      }
   }
   return 0;
}

/* if a player has won, print the words with
   the winning letters standing out */
void print_winning_letters(unsigned int selected) {
   char winning = won(selected);
   assert(winning);
   printf("Got %d occurrences of '%c':", winning_count, winning);
   for (unsigned int index = 0; index < nof_words; ++index) {
      if ((1<<index) & selected) {
	 if (!strchr(words[index], winning)) continue;
	 printf(" ");
	 for (char* cp = words[index]; *cp; ++cp) {
	    if (*cp == winning) {
	       printf("_%c_", *cp);
	    } else {
	       printf("%c", *cp);
	    }
	 }
      }
   }
   printf("\n");
}

/* return true if the union of selected1 and selected2
   covers the entire set of words */
bool all_selected(unsigned int selected1, unsigned int selected2) {
   unsigned int selected = selected1 | selected2;
   return selected == (1<<nof_words) - 1;
}

/* count letter occurrences for the selected set of words */
void count_letters(unsigned int selected, unsigned int count[letters]) {
   for (unsigned int index = 0; index < nof_words; ++index) {
      if ((1<<index) & selected) {
	 for (char* cp = words[index]; *cp; ++cp) {
	    unsigned int letter = *cp - 'a';
	    ++count[letter];
	 }
      }
   }
}

/* evaluate the letter counts for the player with the selected
   set of selected1 under consideration of his opponent's selection
   in selected2;
   the result is non-negative and
   larger results mean that a player is closer to winning */
int evaluate_counts(unsigned int selected1, unsigned int selected2) {
   static unsigned int overall_count[letters]; static bool initialized = false;
   if (!initialized) {
      count_letters((1<<nof_words)-1, overall_count);
      initialized = true;
   }

   unsigned int count1[letters] = {0};
   unsigned int count2[letters] = {0};
   count_letters(selected1, count1);
   count_letters(selected2, count2);
   int sum = 0;
   for (unsigned int letter = 0; letter < letters; ++letter) {
      if (overall_count[letter] - count2[letter] >= winning_count) {
	 unsigned int val = count1[letter];
	 sum += val * val;
      }
   }
   return sum;
}

/* evaluate situation for player 1 who has selected selected1 */
int eval(unsigned int selected1, unsigned int selected2) {
   if (won(selected1)) return INT_MAX;
   if (won(selected2)) return -INT_MAX;
   return evaluate_counts(selected1, selected2) - evaluate_counts(selected2, selected1);
}

#ifndef MAX_LEVEL
#define MAX_LEVEL 4   /* default recursion depth of chose_move */
#endif

/* chose a move for the next player:
    - selected1: selected words of the player
    - selected2: selected words of the opponent
    - move: pointer where the best move is stored
    - level: current recursion depth
   chose_move returns an integer value which is
    - > 0: if the situation is promising
    - = 0: if the situation appears to be balanced
    - < 0: if the opponent has an advantage */
int chose_move(unsigned int selected1,
      unsigned int selected2, unsigned int* move,
      unsigned int level) {
   unsigned int selected = selected1 | selected2;
   unsigned int best_move = 0; int best_result = 0;
   unsigned int best_move_count = 0;
   for (unsigned int index = 0; index < nof_words; ++index) {
      if (!((1<<index) & selected)) {
	 unsigned int next_selected = selected1 | (1 << index);
	 if (won(next_selected)) {
	    /* we win directly through this move */
	    *move = index; return INT_MAX;
	 }
	 int res;
	 if (all_selected(next_selected, selected2)) {
	    /* all words have been selected */
	    res = 0;
	 } else if (level == MAX_LEVEL) {
	    /* in case of deep recursions resort to eval */
	    res = -eval(selected2, next_selected);
	 } else {
	    /* select best move of the opponent */
	    unsigned int next_move;
	    res = -chose_move(selected2, next_selected, &next_move, level + 1);
	    if (res == INT_MAX) {
	       *move = index; return res;
	    }
	 }
	 if (best_move_count == 0 || res > best_result) {
	    best_move = index;
	    best_result = res;
	    best_move_count = 1;
	 } else if (res == best_result) {
	    /* if there are multiple equally good
	       moves, select one by random */
	    ++best_move_count;
	    if (rand() % best_move_count == 0) {
	       best_move = index;
	    }
	 }
      }
   }
   assert(best_move_count > 0);
   *move = best_move;
   return best_result;
}

/* read and check a move from a human player */
bool read_move(unsigned int selected1, unsigned int selected2,
      unsigned int* move) {
   for(;;) {
      printf("Which word? ");
      char word[word_len+1];
      if (scanf(word_format, word) != 1) {
	 printf("Bye!\n"); return false;
      }
      bool retry = false;
      for (unsigned int i = 0; !retry && i < nof_words; ++i) {
	 if (strcmp(word, words[i]) == 0) {
	    if ((1<<i) & (selected1 | selected2)) {
	       retry = true;
	    } else {
	       *move = i; return true;
	    }
	 }
      }
      if (retry) {
	 printf("%s has already been taken. Please chose another word.\n",
	    word);
      } else {
	 printf("This word is not on the table.\n");
      }
   }
}

#define INDENT 28 /* indentation width for word lists */

int main() {
   /* print rules of the game */
   printf("*** %s ***\n", name);
   printf("In this game players alternately select words from "
      "this set of words:\n");
   printf("   "); print_word_set(3, winning_count, (1<<nof_words)-1);
   printf("The player wins who is first able to collect "
      "%d occurrences of the same letter.\n", winning_count);

   /* who starts? */
   enum { human, computer } next_turn;
   printf("Do you want to start? Yes=1 No=0 ");
   int response;
   if (scanf("%d", &response) != 1) {
      printf("Bye!\n"); return 1;
   }
   if (response) {
      next_turn = human;
   } else {
      next_turn = computer;
   }

   /* prepare pseudo random generator
      which is only used to select randomly
      between equally good moves */
   srand(getpid() ^ time(0));

   /* prepare game */
   unsigned int selected_by_human = 0;
   unsigned int selected_by_computer = 0;
   unsigned int unselected = (1<<nof_words) - 1;

   for(;;) {
      /* print current state of the game */
      if (selected_by_computer) {
	 printf("%-*s", INDENT, "Words selected by computer:");
	 print_word_set(INDENT, 0, selected_by_computer);
      }
      if (selected_by_human) {
	 printf("%-*s", INDENT, "Words selected by you:");
	 print_word_set(INDENT, 0, selected_by_human);
      }
      printf("%-*s", INDENT, "Remaining words:");
      print_word_set(INDENT, 0, unselected);

      /* get next move */
      unsigned int move;
      if (next_turn == human) {
	 if (!read_move(selected_by_human, selected_by_computer, &move)) {
	    return 1;
	 }
	 selected_by_human |= (1<<move);
	 if (won(selected_by_human)) {
	    print_winning_letters(selected_by_human);
	    printf("Congratulations, you've won!\n");
	    break;
	 }
	 next_turn = computer;
      } else {
	 /* move by computer */
	 chose_move(selected_by_computer, selected_by_human, &move, 0);
	 printf("The computer selects %s\n", words[move]);
	 selected_by_computer |= (1<<move);
	 if (won(selected_by_computer)) {
	    print_winning_letters(selected_by_computer);
	    printf("Too bad, you lose!\n");
	    break;
	 }
	 next_turn = human;
      }

      unselected &= ~(1<<move);
      if (!unselected ||
	    /* stop playing when no player is able to win: */
	    (evaluate_counts(selected_by_human, selected_by_computer) == 0 &&
	    evaluate_counts(selected_by_computer, selected_by_human) == 0)) {
	 printf("Game ended with a draw!\n");
	 break;
      }
   }
   printf("Bye, thanks for playing!\n");
}