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

#define SET unsigned long int
#define MAX_SET_SIZE 32

/*
   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 Bowling game where we can remove either
   one or two pins within one move
*/
unsigned int g(unsigned int n) {
   SET set = 0;
   if (n == 0) return 0;
   for (unsigned int a = 0; a < n; ++a) {
      for (unsigned int b = 0; a + b < n; ++b) {
	 if (a + b == n - 1 || a + b == n - 2) {
	    unsigned int val = nim_add(g(a), g(b));
	    set |= (1 << val);
	 }
      }
   }
   return mex(set);
}

/*
   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 pins) {
   unsigned int heap_size = 0;
   unsigned int result = 0;
   for (int i = 0; i < MAX_SET_SIZE; ++i) {
      if ((1 << i) & pins) {
	 ++heap_size;
      } else if (heap_size) {
	 result = nim_add(result, g(heap_size));
	 heap_size = 0;
      }
   }
   if (heap_size) {
      result = nim_add(result, g(heap_size));
   }
   return result;
}

/*
   compute the Nim value for a particular game state when the given
   move has been performed
*/
unsigned int evaluate(SET pins, unsigned int chosen_pin, bool take_next) {
   pins &= ~(1 << chosen_pin);
   if (take_next) {
      pins &= ~(1 << (chosen_pin + 1));
   }
   return nim_value(pins);
}


int main() {
   // select some initial number of pins per random
   srand(time(0) ^ getpid());
   unsigned int number_of_pins = 8 + rand() % 6;
   // setup pins
   SET pins = 0;
   for (int i = 0; i < number_of_pins; ++i) {
      pins |= (1 << i);
   }
   // print greeting
   puts("*** Dudeney's Game of Kayles ***");
   bool players_turn = true;

   while (pins) { // as long as there are pins still standing...

      // display pins
      for (int i = 0; i < number_of_pins; ++i) {
	 if (i > 0) putchar(' ');
	 if ((1 << i) & pins) {
	    // pin i is still standing
	    putchar('/'); putchar('\\');
	 } else {
	    // pin i is already gone
	    putchar(' '); putchar(' ');
	 }
      }
      putchar('\n');
      for (int i = 0; i < number_of_pins; ++i) {
	 if (i > 0) putchar(' ');
	 if ((1 << i) & pins) {
	    // pin i is still standing
	    printf("%02d", i + 1);
	 } else {
	    // pin i is already gone
	    putchar(' '); putchar(' ');
	 }
      }
      putchar('\n');
      //printf("Nim value = %d\n", nim_value(pins));


      // determine next move
      unsigned int chosen_pin;
      bool take_next;

      if (players_turn) {  /* Human */
	 for(;;) { // loop until we get a valid move
	    printf("Your move: ");
	    int move;
	    if (scanf("%d", &move) != 1) {
	       printf("Unable to read move. Exiting.\n"); return 0;
	    }
	    if (move == 0) {
	       printf("Invalid pin number.\n"); continue;
	    }
	    take_next = move < 0;
	    if (take_next) {
	       chosen_pin = -move - 1;
	    } else {
	       chosen_pin = move - 1;
	    }
	    if (chosen_pin >= number_of_pins) {
	       printf("Invalid pin number.\n"); continue;
	    }
	    if (take_next && chosen_pin == number_of_pins-1) {
	       printf("Invalid pair of pins.\n"); continue;
	    }
	    if (!((1 << chosen_pin) & pins)) {
	       printf("Pin %d is no longer standing.\n", chosen_pin + 1);
	       continue;
	    }
	    if (take_next && !((1 << (chosen_pin+1)) & pins)) {
	       printf("Pin %d is no longer standing.\n", chosen_pin + 2);
	       continue;
	    }
	    break; // looks good
	 }

      } else {  /* Bot */
	 bool found = false; unsigned int some_pin;
	 for (int i = 0; i < number_of_pins; ++i) {
	    if ((1 << i) & pins &&
		  i < number_of_pins-1 && (1 << (i+1)) & pins) {
	       chosen_pin = i; take_next = true;
	       if (evaluate(pins, chosen_pin, take_next) == 0) {
		  found = true; break;
	       }
	    }
	    if ((1 << i) & pins) {
	       chosen_pin = i; take_next = false;
	       if (evaluate(pins, chosen_pin, take_next) == 0) {
		  found = true; break;
	       }
	       some_pin = i;
	    }
	 }
	 if (!found) {
	    chosen_pin = some_pin; take_next = false;
	 }
	 printf("My move: %d\n", take_next? -(chosen_pin+1): chosen_pin+1);
      }


      // perform move
      pins &= ~(1 << chosen_pin);
      if (take_next) {
	 pins &= ~(1 << (chosen_pin + 1));
      }


      players_turn = !players_turn;
   }


   if (players_turn) {
      puts("*** You lose! ***");
   } else {
      puts("*** Congratulations, you've won! ***");
   }

   return 0;
}