// Arup Guha
// 9/28/2021
// Code for Quiz 2 Version B COP 3502 (Fall 2021)

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

typedef struct node {
    int data;
    struct node* next;
} node;

// For Question #1
void testCountAs();
int countAs(char* word, int k);
int countAsAlt(char* word, int k);

// For Question #3
#define SIZE 4

void go(int* perm, int* used, int k, int n, int ok);
void print(int array[], int n);
void testNonDerange();

// For Questions 4, 5
void testLL();
node* insertFront(node* list, int x);
void freeList(node* list);
int getValue(node* listPtr);
void printNumber(node* listPtr);

// Comment in what you want to test.
int main(void) {
    //testCountAs();
    //testNonDerange();
    testLL();
    return 0;
}

// Wrapper test for countAs.
void testCountAs() {
    char word[20];
    strcpy(word, "abracadabra");
    printf("%d\n", countAs(word, 11));
    printf("%d\n", countAsAlt(word, 11));
}

// Returns the number of a's in word[0..k-1].
int countAs(char* word, int k) {

    // No letters, no a's.
    if (k == 0) return 0;

    // Add 1 if the last letter is a.
    int res = 0;
    if (word[k-1] == 'a') res++;

    // Add to the rest of the string.
    return res + countAs(word, k-1);
}

// Returns the number of a's in word[0..k-1].
int countAsAlt(char* word, int k) {

    // No letters, no a's.
    if (k == 0) return 0;

    // Add 1 if the last letter is a.
    int res = 0;
    if (word[0] == 'a') res++;

    // Add to the rest of the string.
    return res + countAs(word+1, k-1);
}

// Test Question 3.
void testNonDerange() {

    // Set up arrays and call recursive function.
    int perm[SIZE], used[SIZE];
    for (int i=0; i<SIZE; i++) used[i] = 0;
    go(perm, used, 0, SIZE, 0);
}

// Mystery function!
void go(int* perm, int* used, int k, int n, int ok) {

    // All filled in permutations are printed!
    if (k == n) {
        print(perm, n);
        return;
    }

    // canDo keeps track of if we are able to place a value in an index with its own value or not.
    int canDo = 0;
    for (int i=k; i<n; i++)
        if (!used[i])
            canDo = 1;

    // So, if we've never placed a value in its own index and can't do it in the future, STOP!
    if (!ok && !canDo) return;

    // Try each value in slot k.
    for (int i=0; i<n; i++) {

        // Avoids repeats.
        if (used[i]) continue;

        // Place i in slot k.
        used[i] = 1;
        perm[k] = i;

        // if k equals i, then ok must be 1, so we just OR this expression with ok so ok will equal
        // 1 if our permutation has already added a value in an index of the same value, or 0 otherwise.
        go(perm, used, k+1, n, ok || k == i);

        // Unmark i.
        used[i] = 0;
    }
}

// Prints array[0..n-1].
void print(int array[], int n) {
    for (int i=0; i<n; i++)
        printf("%d, ", array[i]);
    printf("\n");
}

// Hard-coded test for the linked list question.
void testLL() {
    node* num = NULL;
    num = insertFront(num, 5);
    num = insertFront(num, 8);
    num = insertFront(num, 2);
    num = insertFront(num, 3);
    printNumber(num);
    printf("\n");
    int value = getValue(num);
    printf("The value of the list is %d\n", value);
    freeList(num);
}

int getValue(node* listPtr) {

    // No value with no digits.
    if (listPtr == NULL) return 0;

    // Value of front is just whatever data is. The rest of the list left-shifted by 1 digit, so that is
    // the same as multiplying by 10!
    return listPtr->data + 10*getValue(listPtr->next);
}

// Prints the digits in the list pointed to by listPtr in reverse order.
void printNumber(node* listPtr) {

    // Nothing to print if pointer is NULL.
    if (listPtr != NULL) {

        // Print the rest of the list first.
        printNumber(listPtr->next);

        // Print the first digit in the list last.
        printf("%d", listPtr->data);
    }
}

// Inserts a new node storing x in the front of list and returns the new front of the list.
node* insertFront(node* list, int x) {
    node* tmp = malloc(sizeof(node));
    tmp->data = x;
    tmp->next = list;
    return tmp;
}

// Frees the memory associated with the list pointed to by list.
void freeList(node* list) {
    if (list != NULL) {
        freeList(list->next);
        free(list);
    }
}