cipher.c

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

typedef struct dict {
    char *bufz;
    unsigned bufz_size;
    unsigned count;
    unsigned words[];
} dict;

static const char *dict_target;
static int
dict_cmp(const void *a, const void *b)
{
    unsigned ai = *(unsigned *)a;
    unsigned bi = *(unsigned *)b;
    return strcmp(&dict_target[ai], &dict_target[bi]);
}

void
dict_sort(dict *d)
{
    dict_target = d->bufz;
    qsort(d->words, d->count, sizeof(d->words[0]), dict_cmp);
}

static bool
word_is_valid(const char *word)
{
    for (const char *p = word; *p; p++)
        if (!islower(*p) && !ispunct(*p))
            return false;
    return true;
}

dict *
dict_create(const char *file)
{
    unsigned max_words = 256;
    dict *d = malloc(sizeof(*d) + sizeof(unsigned) * max_words);
    d->count = 0;
    d->bufz_size = 4096;
    d->bufz = malloc(d->bufz_size);
    unsigned p = 0;
    FILE *in = fopen(file, "r");
    int last = ' ';
    int c;
    while ((c = fgetc(in)) != EOF) {
        if (!isspace(c)) {
            if (isspace(last))
                d->words[d->count++] = p;
            d->bufz[p++] = c;
        } else {
            if (!isspace(last)) {
                d->bufz[p++] = '\0';
                char *word = d->bufz + d->words[d->count - 1];
                if (!word_is_valid(word)) {
                    d->count--;
                    p = d->words[d->count];
                }
            }
        }
        last = c;
        if (p == d->bufz_size) {
            d->bufz_size *= 2;
            d->bufz = realloc(d->bufz, d->bufz_size);
        }
        if (d->count == max_words) {
            max_words *= 2;
            d = realloc(d, sizeof(*d) + sizeof(unsigned) * max_words);
        }
    }
    fclose(in);
    if (d->bufz[p] != '\0')
        d->bufz[p++] = '\0';
    dict_sort(d);
    d->bufz_size = p;
    d->bufz = realloc(d->bufz, d->bufz_size + 64);  // trim
    return realloc(d, sizeof(*d) + sizeof(unsigned) * d->count); // trim
}

void
dict_free(dict *d)
{
    free(d->bufz);
    free(d);
}

bool
dict_check(dict *d, const char *word)
{
    dict_target = d->bufz;
    strcpy(d->bufz + d->bufz_size, word);
    unsigned i = d->bufz_size;
    return bsearch(&i, d->words, d->count, sizeof(d->words[0]), dict_cmp)
        != NULL;
}

typedef struct cipher {
    char line[1024];
    char *words[256];
    int sub[26];
    int rev[26];
} cipher;

void
cipher_setsub(cipher *c, char from, char to)
{
    assert(isupper(from));
    assert(islower(to));
    c->sub[from - 'A'] = to   - 'a';
    c->rev[to   - 'a'] = from - 'A';
}

void
cipher_clearsub(cipher *c, char from)
{
    assert(isupper(from));
    char to = c->sub[from - 'A'] + 'a';
    assert(islower(to));
    c->sub[from - 'A'] = -1;
    c->rev[to - 'a'] = -1;
}

bool
cipher_has_sub(cipher *c, char x)
{
    if (islower(x))
        return c->rev[x - 'a'] != -1;
    else if (isupper(x))
        return c->sub[x - 'A'] != -1;
    assert("invalid character");
    return false;
}

void
cipher_load(cipher *c)
{
    for (int i = 0; i < 26; i++) {
        c->sub[i] = -1;
        c->rev[i] = -1;
    }
    fgets(c->line, sizeof(c->line), stdin);
    int wordcount = 0;
    for (char *p = c->line; *p; p++) {
        if (!isspace(*p)) {
            c->words[wordcount++] = p;
            while (*p && !isspace(*p))
                p++;
            p--;
        } else {
            *p = '\0';
        }
    }
    c->words[wordcount] = NULL;
    int pairs;
    scanf("%d", &pairs);
    for (int i = 0; i < pairs; i++) {
        char pair[3];
        scanf("%2s", pair);
        c->sub[pair[1] - 'A'] = pair[0] - 'a';
        c->rev[pair[0] - 'a'] = pair[1] - 'A';
    }
}

void
cipher_decode_word(const cipher *c, char *word)
{
    for (int i = 0; word[i]; i++)
        if (isupper(word[i]))
            word[i] = c->sub[word[i] - 'A'] + 'a';
}

void
cipher_decode_print_all(const cipher *c)
{
    for (char **p = (char **)c->words; *p; p++) {
        char word[strlen(*p) + 1];
        strcpy(word, *p);
        cipher_decode_word(c, word);
        printf("%s ", word);
    }
    printf("\n");
}

static void
cipher_solve(cipher *c, dict *dict, int word, int p)
{
    char *w = c->words[word];
    if (w == NULL) {
        /* Valid decoding! */
        cipher_decode_print_all(c);
        return;
    }
    /* Find next substitution. */
    for (; w[p]; p++)
        if (isupper(w[p]) && !cipher_has_sub(c, w[p]))
            break;
    if (w[p]) {
        /* Try all possible substitutions. */
        for (int i = 0; i < 26; i++) {
            char r = i + 'a';
            if (!cipher_has_sub(c, r)) {
                cipher_setsub(c, w[p], r);
                cipher_solve(c, dict, word, p + 1);
                cipher_clearsub(c, w[p]);
            }
        }
    } else {
        /* Check if this word decodes into a dictionary word. */
        char test[strlen(w) + 1];
        strcpy(test, w);
        cipher_decode_word(c, test);
        if (dict_check(dict, test))
            cipher_solve(c, dict, word + 1, 0);
    }
}

int
main(void)
{
    dict *dict = dict_create("/usr/share/dict/words");
    cipher cipher;
    cipher_load(&cipher);
    cipher_solve(&cipher, dict, 0, 0);
    dict_free(dict);
    return 0;
}