// Arup Guha
// 12/5/2023
// Solution to Q12 of COP 3502 Section 1 Part B Exam

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print(int* piles, int n);
int xor(int* piles, int n);
int* getwinmove(int* piles, int n);

int main() {

    srand(time(0));

    // Do a random test.
    int piles[6];
    for (int i=0; i<6; i++) piles[i] = rand()%1024;
    print(piles,6);

    // Run it.
    int* res = getwinmove(piles, 6);

    // Test if it's really impossible to win.
    if (res == NULL) {
        int myxor = xor(piles, 6);
        if (myxor == 0) printf("This worked, XOR is 0 and we got NULL\n");
        else printf("error in code\n");
    }

    // Make the move and test the new XOR.
    else {
        piles[res[0]] -= res[1];
        int newxor = xor(piles, 6);
        if (newxor == 0)
            printf("It worked, got XOR 0 by taking %d from pile %d\n", res[1], res[0]);
        else
            printf("oops should have gotten xor 0 but didn't\n");
    }

    // See new piles.
    print(piles,6);

    return 0;
}

// For debugging.
void print(int* piles, int n) {
    for (int i=0; i<n; i++) printf("%d ", piles[i]);
    printf("\n");

}

// Returns the XOR of piles[0..n-1].
int xor(int* piles, int n) {
    int res = 0;
    for (int i=0; i<n; i++)
        res ^= piles[i];
    return res;
}

// Returns res[0] = winning pile, res[1] = # of stones to take if you can win NIM with the
// current state of piles (of size n).
int* getwinmove(int* piles, int n) {

    int xor = 0;

    // Just need the XOR of everything.
    for (int i=0; i<n; i++)
        xor ^= piles[i];

    // We can't win.
    if (xor == 0) return NULL;

    int* res = calloc(2, sizeof(int));

    // Try each pile.
    for (int i=0; i<n; i++) {

        // How many we need to leave in this pile after the move.
        int leave = piles[i]^xor;

        // A possible move!
        if (leave < piles[i]) {
            res[0] = i;
            res[1] = piles[i]-leave;
            // If we break we get the first possible move. This does the last.
        }
    }

    // Ta da!
    return res;
}