/*
   afb 10/2015, 11/2017
   Grundy's Game
   See Elwyin R. Berlekam, John H. Conway, Richard K. Guy:
   Winning Ways for Your Mathematical Plays. Volume 1,
   Second Edition, A K Peters, Natick 2001, ISBN 1-56881-130-6,
   pp. 96-97.
*/

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

/* === 007 game evaluation ============================================== */

#define SET unsigned int
#define MAX_SET_SIZE WORD_BIT

/*
   addition of Nim values
*/
unsigned int nim_add(unsigned int a, unsigned int b) {
   return a ^ b;
}

/*
   minimal exclusive, i.e. return the smallest number of 0, 1, 2, ...
   which is _not_ in the set; 0 is returned for empty sets
*/
unsigned int mex(SET set) {
   for (int i = 0; i < MAX_SET_SIZE; ++i) {
      if (!((1 << i) & set)) {
	 return i;
      }
   }
   return MAX_SET_SIZE;
}

/*
   return the mex of all nim values of all options for a heap of size n;
   this has been tailored to the 007 game where we can remove just three pins 
*/
unsigned int g(unsigned int n) {
   /* this array is used to cache previous results */
   static unsigned int result[MAX_SET_SIZE] = {0};
   static bool computed[MAX_SET_SIZE] = {false};

   SET set = 0;
   if (n < MAX_SET_SIZE && computed[n]) return result[n];

   if (n <= 2) return 0;
   if (n == 3) return 1;
   for (unsigned int a = 1; a < n; ++a) {
      for (unsigned int b = 1; a + b <= n; ++b) {
	 if (a + b == n && a != b) {
	    unsigned int val = nim_add(g(a), g(b));
	    set |= (1 << val);
	 }
      }
   }

   unsigned int gvalue = mex(set);
   if (n < MAX_SET_SIZE) {
      result[n] = gvalue; computed[n] = true;
   }
   return gvalue;
}

/*
   compute the Nim value for a particular game state;
   this is done by Nim adding all the g values of the individual heaps;
   if the Nim value is 0 the next player loses or can be forced to lose
*/
unsigned int nim_value(SET status, unsigned int len) {
   unsigned int heap_size = 0;
   unsigned int result = 0;
   for (int i = 0; i < len; ++i) {
      ++heap_size;
      if ((1 << i) & status) {
	 result = nim_add(result, g(heap_size));
	 heap_size = 0;
      }
   }
   return result;
}

/*
   compute the Nim value for a particular game state when the given
   move has been performed
*/
unsigned int evaluate(SET status, unsigned int len,
      unsigned int move) {
   status |= (1 << move);
   return nim_value(status, len);
}

bool valid_move(SET status, unsigned int len, unsigned int bp) {
   if (bp+1 >= len) return false;
   if ((1 << bp) & status) return false;
   unsigned int behind = 1;
   for (int i = bp + 1; i < len && !((1 << i) & status); ++i) {
      ++behind;
   }
   unsigned int before = 1;
   for (int i = bp - 1; i >= 0 && !((1 << i) & status); --i) {
      ++before;
   }
   return before > 0 && behind != before;
}

void print_status(SET status, unsigned int len) {
   for (int i = 0; i < len; ++i) {
      putchar('.');
      if ((1 << i) & status) {
	 putchar(' ');
      } else if (i + 1 < len) {
	 if (valid_move(status, len, i)) {
	    printf("%02d", i+1);
	 }
      }
   }
   putchar('\n');
}

#ifdef CHEAT
/* cheat and tell which moves are good ones */
void cheat(SET status, unsigned int len) {
   printf("Winning moves: "); bool found;
   for (int move = 0; move + 1 < len; ++move) {
      if (!valid_move(status, len, move)) continue;
      if (evaluate(status, len, move)) continue;
      printf(" %u", move+1); found = true;
   }
   if (!found) printf("none");
   printf("\n");
}
#endif

unsigned int read_move(SET status, unsigned int len) {
   for(;;) {
      printf("Your move: ");
      unsigned int move;
      if (scanf("%u", &move) != 1) {
	 printf("Bye!\n"); exit(1);
      }
      if (move == 0) {
	 printf("Move out of range!\n"); continue;
      }
      --move;
      if (!valid_move(status, len, move)) {
	 printf("Invalid move!\n");
      } else {
	 return move;
      }
   }
}

/* find a winning move for the situation, if possible,
   and chose a not too bad move if we are already on the losing side */
unsigned int find_move(SET status, unsigned int len) {
   unsigned int candidate = 0; bool candidate_found = false;
   for (int move = 0; move + 1 < len; ++move) {
      if (!valid_move(status, len, move)) continue;
      if (evaluate(status, len, move) == 0) {
	 /* winning move found */
	 return move;
      }
      if (!candidate_found) {
	 candidate = move;
	 candidate_found = true;
      }
   }
   /* no winning move found */
   assert(candidate_found);
   return candidate;
}

/* a game is finished when there no legal moves possible */
bool game_finished(SET status, unsigned int len) {
   for (int move = 0; move + 1 < len; ++move) {
      if (valid_move(status, len, move)) return false;
   }
   return true;
}

int main() {
#ifdef BEANS
   unsigned int len = BEANS;
#else
   /* initialize random generator */
   srand(time(0) ^ getpid());
   /* determine length of our field */
   unsigned int len = MAX_SET_SIZE - 2 - rand() % 10;
#endif

   /* explain the rules of the game */
   printf(
      "*** Grundy's Game ***\n"
      "One large heap of %u beans is given. In each move one of the heaps\n"
      "may be split into two smaller heaps, provided the resulting heaps\n"
      "are of different size. The player who is unable to split any remaining\n"
      "heap loses.\n"
      "\n"
      "Beans are represented by dots, possible splitting points with digits.\n"
      "If you are asked for a move, specify one of the breaking points.\n",
      len);
   /* who starts the game */
   bool humans_turn;
   for(;;) {
      printf("Do you want to start? Yes=1 No=2 ");
      int choice;
      if (scanf("%d", &choice) != 1) {
	 printf("Bye.\n"); exit(1);
      }
      if (choice == 1) {
	 humans_turn = true; break;
      } else if (choice == 2) {
	 humans_turn = false; break;
      }
   }
   /* initialize the game */
   SET status = 1<<(len-1);
   /* run the game */
   bool finished = false;
   do {
      print_status(status, len);
      unsigned int move;
      if (humans_turn) {
#ifdef CHEAT
	 cheat(status, len);
#endif
	 move = read_move(status, len);
      } else {
	 move = find_move(status, len);
	 printf("Computer splits a heap at position %u.\n", move + 1);
      }
      /* execute move */
      status |= 1<<move;
      if (game_finished(status, len)) {
	 finished = true;
      } else {
	 humans_turn = !humans_turn;
      }
   } while (!finished);

   /* print final status */
   print_status(status, len);
   if (humans_turn) {
      printf("Congratulations, you've won!\n");
   } else {
      printf("You lose!\n");
   }
}