Anonymous

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

static char *dict[] = { "aaaa", "aaab", "aaac", "aabb", "babb", "bbbb" };
static int *skip;
static int dictlen = 6;

/* 3 out of 4 characters should match */
static int match3(const char *word1, const char *word2)
{
    int match = 0, i;
    for (i = 0; i < 4; ++i)
        if (word1[i] == word2[i])
            ++match;
    return match == 3;
}

/* Because this algorythm is recursive, the printing is done inverted
 * to compensate for that, the word order is reverted, too */
int trymatch(char *destword, int whichwordnow)
{
    int i;

    /* Easiest case */
    if (match3(dict[whichwordnow], destword))
    {
        printf("%s -> %s", destword, dict[whichwordnow]);
        return whichwordnow;
    }

    /* Try to recursively call all words 1 away from current word */
    for (i = 0; i < dictlen; ++i)
        if (!skip[i] && match3(dict[i], dict[whichwordnow]))
        {
            int ret;
            skip[i] = 1;
            ret = trymatch(destword, i);
            if (ret >= 0)
            {
                printf(" -> %s", dict[whichwordnow]);
                return i;
            }
        }

    return -1;
}

int main() {
    char word[5] = "aaaa";
    char targetword[5] = "bbbb";
    int moi = -1, i;

    skip = malloc(sizeof(int) * dictlen);
    if (!skip) return 1;

    /* Fill dict, allocate skip */
    memset(skip, 0, sizeof(int) * dictlen);

    /* First the easiest case */
    if (!strcasecmp(word, targetword))
    {
        printf("Nothing to do.\n");
        return 0;
    }

    /* Convert targetword into a dictionary word */
    for (i = 0; i < dictlen; ++i)
        if (!strcasecmp(targetword, dict[i]))
        {
            moi = i;
            skip[i] = 1;
            break;
        }

    if (moi == -1)
    {
        printf("Error: '%s' not in dictionary!\n", targetword);
        return 1;
    }

    /* Do the magic, find the way to transform targetword into original word */
    int ret = trymatch(word, moi);
    if (ret == -1)
    {
        printf("Could not change '%s' to '%s'\n", word, targetword);
        return 1;
    }
    printf("\n");
    return 0;
}