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

#define SZ 10000

int isPalindromeHelper(char word[], int size) {
    if (size <= 1)
        return 1;

    if (!isalnum(word[0]))
        return isPalindromeHelper(word+1, size-1);
    if (!isalnum(word[size-1]))
        return isPalindromeHelper(word, size-1);
    
    return tolower(word[0]) == tolower(word[size-1])
        && isPalindromeHelper(word+1, size-2);
}

int isPalindrome(char word[]) {
    return isPalindromeHelper(word, strlen(word));
}


int baseHelper(char num[], int radix, int acc) {
    int digit;
    
    if (num[0]) {
        digit = (num[0] > '9') ?
            toupper(num[0])-'A' + 10 : num[0]-'0';
        return baseHelper(num+1, radix, acc*radix + digit);
    }
    else
        return acc;
}

int base(char num[], int radix) {
    return baseHelper(num, radix, 0);
}


void merge(int x[], int xnum, int y[], int ynum, int z[]) {
    if (xnum != 0  ||  ynum != 0) {
        if (ynum == 0  ||  (xnum != 0  &&  x[0] <= y[0])) {
            z[0] = x[0];
            merge(x+1, xnum-1, y, ynum, z+1);
        }
        else {
            z[0] = y[0];
            merge(x, xnum, y+1, ynum-1, z+1);
        }
    }
}


int subsetsHelper(char word[], int sz, char arr[], char elem[], int esz) {
    char temp;
    int chunk;
    
    if (esz == sz) {
        temp = elem[esz];
        elem[esz] = '\0';

        strcpy(arr, elem);
        
        elem[esz] = temp;
        arr[esz] = ',';

        return esz+1;
    }
    else if (!word[0])
        return 0;
    else {
        elem[esz] = word[0];
        chunk = subsetsHelper(word+1, sz, arr, elem, esz+1);
        return chunk + subsetsHelper(word+1, sz, arr+chunk, elem, esz);
    }
}

void subsets(char word[], int sz, char arr[]) {
    char elem[11];
    arr[subsetsHelper(word, sz, arr, elem, 0)-1] = '\0';
}


int main(int argc, char **argv) {
    char c;
    char in[SZ];
    char out[SZ];
    int  x;
    
    do {
        printf("(p)alindrome, (b)ase, (m)erge, (s)ubsets, (q)uit: ");

        while ((c = getchar()) == '\n');
        getchar();

        switch (c) {
        case 'p':
            printf("Your sentence: ");
            fgets(in, SZ, stdin);

            x = strlen(in);
            if (in[x-1] == '\n')
                in[--x] = '\0';

            if (isPalindrome(in))
                printf("Palindrome: \"%s\"\n", in);
            else
                printf("Not a palindrome \"%s\"\n", in);
            break;
            
        case 'b':
            printf("Your number: ");
            fgets(in, SZ, stdin);

            x = strlen(in);
            if (in[x-1] == '\n')
                in[--x] = '\0';

            printf("Radix: ");
            scanf("%d", &x);

            printf("%s_%d = %d\n", in, x, base(in, x));
            
            break;
            
        case 'm':
            printf("N/A\n");
            break;
            
        case 's':
            printf("Your word: ");
            fgets(in, SZ, stdin);

            x = strlen(in);
            if (x > 10)
                in[x = 10] = '\0';
            if (in[x-1] == '\n')
                in[--x] = '\0';

            printf("Subset size: ");
            scanf("%d", &x);
            subsets(in, x, out);
            printf("\"%s\", size=%d: %s\n", in, x, out);
            
            break;
        }
    } while (c != 'q');

    return 0;
}