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

int main() {

    srand(getpid() ^ time(0)); // set seed
    int h[3]; // heaps
    // initialize heaps
    for (int i=0; i<3; ++i) {
        h[i] = rand() % (10 - 5 + 1) + 5;
    }

    printf("*** Three Heaps ***\n");
    printf("Initial state: %d %d %d\n", h[0], h[1], h[2]);
    printf("Rules: In each turn each player may take one, two, or three\n");
    printf("       sticks from one of the heaps. The player who removes\n");
    printf("       the last sticks wins.\n");
    printf("Do you want to begin? 1 = yes, 0 = no: ");
    int players_turn;
    if (scanf("%d", &players_turn) != 1 ||
      (players_turn != 0 && players_turn != 1)) {
        exit(255);
    }
    while (h[0] > 0 || h[1] > 0 || h[2] > 0) {
        /* print current state */
        printf("Heaps: %d %d %d\n", h[0], h[1], h[2]);

        /* next move: */
        int heap; // select heap
        int quantity; // number of sticks that are to be removed from the heap

        /* get next move */
        if (players_turn) {
            /* read move from our human player */
            do {
                printf("Which heap (1-3)? ");
                if (scanf("%d", &heap) != 1) exit(255);
            } while (heap < 1 || heap > 3);
            do {
                printf("How many? ");
                if (scanf("%d", &quantity) != 1) exit(255);
            } while (quantity < 1 || quantity > 3);

	    if (quantity > h[heap-1]) {
                printf("Not that many sticks left on heap %d\n", heap);
                continue;
            }
            players_turn = 0; // computer is next
        }
        else { // computer's turn
            /* determine move */
            if ( (h[0]^h[1]^h[2])%4 == 0) {
                /* take only one stick from first non-empty heap*/
                quantity = 1;
                for (int i = 0; i < 3; ++i) {
                    if (h[i] != 0) {
                        heap = i+1; 
                        break;
                    }
                }
            }
            else {
                /* find a winning move:
                  We go through all possible moves and take the first
                  one that delivers a nim value of 0. */
                bool found = false;
                for (int i = 0; i < 3; ++i) {
                    int max_quantity = 3;
                    if (h[i] < 3) max_quantity = h[i];
                    for (quantity = 1; quantity <= max_quantity; ++quantity) {
                        // determine new nim value:
                        int new_nimval = 0;
                        // compute binary digital sum of modified heap sizes
                        for (int j = 0; j < 3; ++j) {
                            if (j == i) {
                                new_nimval ^= (h[j] - quantity) % 4;
                            } else {
                                new_nimval ^= h[j] % 4;
                            }
                        }
                        if (new_nimval == 0) { // winning move
                            found = true;
                            break;
                        }
                    }
                    if (found) {
                        heap = i+1;
                        break;
                    }
                }
                assert(found);
            }
            players_turn = 1; // computer finishes, human player is next
        }
        /* execute move */
        printf("Taking %d sticks from heap %d\n", quantity, heap);
        h[heap-1] -= quantity;
    }
    if (players_turn) {
        printf("You lose!\n");
    } else {
        printf("Congratulations, you've won!\n");
    }
}