Banagram/main.c

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

#define DICTFILE "/usr/share/dict/banawords"

/*
 * Copyright 2020 Alistair Michael
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to permit
 * persons to whom the Software is furnished to do so, subject to the
 * following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
 * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
 * USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#define LINELENGTH 200

// for string qsort
int compar(const void * l1, const void *l2) {
    return *(char *)l1 > *(char*)l2;
}

void make_lowercase(char *word) {
    int j = 0;
    while (word[j] != '\0') {
        if (isupper(word[j])) {
            word[j] = tolower(word[j]);
        }
        j++;
    }
}

int *count_char(char *word) {
    make_lowercase(word);
    int* counts = (int*)calloc(27, sizeof(int));

    int j = 0;
    while (word[j] != '\0') {
        if (word[j] > 'z' || word[j] < 'a') {
            free(counts);
            return 0;
        }
        counts[word[j] - 'a'] += 1;
        j++;
    }
    return counts;
}

FILE *open_dict_file(char *filename) {
    FILE *wfile = fopen(filename, "r");

    if (!wfile) {
        fprintf(stderr, "Unable to open dict\n");
        exit(1);
    }

    return wfile;
}

// @param allowed: additional characters allowed in anagram match, 
// set to NULL to allow matching any set of characters.
int get_minimum_match(char *word, int added, char *allowed) {
    FILE* wfile = open_dict_file(DICTFILE);

    char line[LINELENGTH];
    int err;
    int len = strlen(word);
    int *orig_word_letter_counts = count_char(word);
    if (!orig_word_letter_counts) {
        fclose(wfile);
        return 1;
    }

    // loop over every word in the word file and check if it is an allowed
    // anagram of word optionally containing some/all of the allowed letters
    do {
        int *max_letter_counts = NULL;
        int *anagram_letter_counts = NULL;

        err = fscanf(wfile, "%s\n", line);
        if (err == EOF) {
            break;
        }

        int line_len = strlen(line);
        if (line_len < len || line_len > (len + added)) {
            continue;
        }

        anagram_letter_counts = count_char(line);

        if (!anagram_letter_counts) {
            continue;
        }

        if (allowed) {
            max_letter_counts = count_char(allowed);
            if (!max_letter_counts) {
                return 1;
            }

            for (int i = 0; i < 26; i++) {
                max_letter_counts[i] += orig_word_letter_counts[i];
            }
        }

        bool match = true;

        for (int i = 0; (i < 26) && match; i++) {
            // if word contains a letter that the anagram does not
            if (orig_word_letter_counts[i] > anagram_letter_counts[i]) {
                match = false;
                break;
            }

            // if the anagram contains a letter that is not in the word, or 
            // pool of available letters
            if (allowed) {
                if (max_letter_counts[i] < anagram_letter_counts[i]) {
                    match = false;
                    break;
                }
            }
        }

        // print the anagram and the additional letters required
        if (match) {
            bool s = false;
            printf("%s", line);
            for (int i = 0; i < 26; i++) {
                int diff = anagram_letter_counts[i] - orig_word_letter_counts[i];
                if (diff > 0) {
                    if (!s) {
                        s = true;
                        printf(" +");
                    }
                    printf(" %d%c", diff, i + 'a');
                }
            }
            printf("       ");
            printf("\n");
        }

        free(anagram_letter_counts);
        if (max_letter_counts) {
            free(max_letter_counts);
        }
    } while (err != EOF);

    free(orig_word_letter_counts);
    fclose(wfile);
    return 0;
}


int get_exact_anag(char *word) {

    make_lowercase(word);
    FILE* wfile = open_dict_file(DICTFILE);

    char line[LINELENGTH];
    int err;
    int len = strlen(word);
    // sort line
    qsort(word, len, sizeof(char), compar);

    do {
        err = fscanf(wfile, "%s\n", line);
        if (err == EOF) {
            break;
        }
        if (strlen(line) != len) {
            continue;
        }
        make_lowercase(line);

        char nline[LINELENGTH];
        memcpy(nline, line, (sizeof(char) * LINELENGTH));

        // sort line
        qsort(line, len, sizeof(char), compar);

        if (!strcmp(line, word)) {
            printf("%s\n", nline);
        }

    } while (err != EOF);

    fclose(wfile);

    return 0;
}

int main (int argc, char **argv) {
    char *usage_string = "cmd min <num extra letters> <word> <(optional) pool "
        "of available letters>"
        "\ncmd exact <word>\n";
    
    char word[LINELENGTH];

    if (argc <= 2) {
        fprintf(stderr, "%s", usage_string);
        return 1;
    }

    if (argv[1][0] == 'e') {
        if (argc != 3) {
            fprintf(stderr, "Wrong args.\n");
            return 1;
        }
        strcpy(word, argv[2]);
        get_exact_anag(word);
    } else if (argv[1][0] == 'm') {
        if (argc < 4 || argc > 5) {
            fprintf(stderr, "Wrong args.\n");
            return 1;
        }
        int num = atoi(argv[2]);
        strcpy(word, argv[3]);
        if (num == 0) {
            get_exact_anag(word);
        } else {
            char *allowed = NULL;
            if (argc == 5) 
                allowed = argv[4];
            get_minimum_match(word, num, allowed);
        }
    } else {
        fprintf(stderr, "%s", usage_string);
    }
}