letter exchange algorithm

[davidcollins001]

Hi,

I came across a neat problem that I have been trying to code to improve my programming problem solving skills. It is quite simple but I am struggling to get my head around it. Any help would be much appreciated.

The problem is the following: a starting word, such as head, is transformed into a second word, such as tail, by way of changing a single letter at a time. All intermediate words must be in the dictionary. The aim is to find the fewest number of intermediate word to perform the transform.

e.g. transform long --> line
long -> lone
lone -> line

So far i copy the start word into a secondary array to manipulate it and place this word at the start of a linked list. Using a function I start with the first letter and loop through all combinations from a-z checking that each is a dictionary word. If it is a word I recursively call the function checking it is not in the list, then add it to the head of the list. I keep recursively changing letters and testing until I find the transformed word.

This method is kind of working, but not really and I think that I am missing something vital. I could do with a few pointers to get me in the right direction. Here is the code I have so far (please ignore the memory leaking :P )

/*
 * find the shortest path to bread from short changing only one letter
 * at a time
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct words_t {
    char word[6];
    struct words_t *next;
};
 
int deep = 0;
 
int shuffle(struct words_t *head, char word[6], char target[6], int lp);
int dict(char word[6]);
int find(struct words_t *head, char word[6]);
int print(struct words_t *head);
 
char previous[BUFSIZ][5];
 
int
main(void) {
    char start[6] = "short", end[6] = "chart";
    struct words_t *words;
 
 
    /* make the first list element the starting point */
    words = malloc(sizeof(words));
    strncpy(words->word, start, 6);
    words->next = NULL;
 
    shuffle(words, start, end, 0);
 
    return 0;
}
 
 
int
shuffle(struct words_t *head, char word[6], char target[6], int lp) {
    int i, letter;
    char this_letter, current[6];
    struct words_t *new;
 
    if(find(head, word) == 1) {
        /* a match was found for this word already */
        return 0;
    }
 
    new = malloc(sizeof(new));
    strncpy(new->word, word, 6);
    strncpy(current, head->word, 6);
    new->next = head;
    head= new;
 
    printf("%d==> %s\n", lp, new->word);
 
    /* loop over all letters */
    for(i=0; i<5; i++) {
 
        /* remember the current letter */
        this_letter = current[i];
 
        /* increment letter */
        for(letter='a'; letter<='z'; ++letter) {
            if(letter == this_letter) ++letter;
            current[i] = letter;
 
            /* have we found a word in the dictionary? */
            if(dict(current)) {
                if(strncmp(current, target, 5) == 0) {
                    printf("\n\n\tFOUND IT!\n");
                    print(head);
                    exit(0);
                }
                shuffle(head, current, target, i);
            } 
        } 
 
        /* 
         * a word was not found with this letter, revert to
         * last word 
         */
        if(((letter-1) == 'z') && (! dict(current))) {
            current[i] = this_letter;                    
        }
    } 
}
 
 
int
find(struct words_t *head, char word[6]) {
    struct words_t *current = head;
 
    while(current->next != NULL) {
        if(strncmp(current->word, word, 5) == 0)
            /* this word has already been used return 1 */
            return 1;
        current = current->next;
    }
    return 0;
}
 
 
int
print(struct words_t *head) {
    struct words_t *current = head;
 
    while(current->next != NULL) {
        printf("<%s> ", current->word);
        current = current->next;
    }
    return 0;
}
 
 
int 
dict(char word[6]) {
    char grep[152];
 
    snprintf(grep, 152, "grep --silent '^%s$' /usr/share/dict/words", word);
 
    /* return 1 if a match is found */
    return !system(grep);
}
 

[Banfa]

You have an error at line 52

new = malloc(sizeof(n ew));

This allocates 4 bytes to assign to a pointer to a 10 (probably but could be 14) structure. Try this

new = malloc(sizeof *new);

You have the same error at line 27.

You put the first word into the list twice, once at line 32 and once at line 53 on the first iteration. This also means that you have made find ignore the last word in the list when comparing to get round this starting corner case. However on every other iteration this is an error.

Pass an empty list to shuffle on the first iteration, fix find to search all entries.


Line 67

for(letter='a'; letter<='z'; ++letter) {

is platform defined behaviour, the C standard does not guarantee that 'a' + 1 == 'b' it is dependent on the execution character set that the platform uses.

Line 75 - 76

print(head);
exit(0);

Poor practice printing and exiting from the depths of a recursive function call, exit the recursive function to main and print in main. Also you do not release any of your allocated memory, also bad practice.

[davidcollins001]

Thank you for pointing out the errors, I would have expected to get more errors not allocating memory properly but it seemed to work and is fixed now. Also the head of the list is fixed. I knew about the (extensive) memory leak I will fix that when I understand the algorithm.

About the algorithm, this method I am using seems to work. However, it is slow and won't always find the quickest path unless I search every word in the dictionary, I am just wondering if there is a better approach to it. Does anyone have any ideas I can try? I am not looking for code, just a hand with how best to solve the problem at hand.

Thanks
David

[donbock]

How many times do you call dict in an average pass? It might be worth the overhead to organize the dictionary into a hash or tree so you can more quickly determine if a letter-pattern is a dictionary word.

[Banfa]

Also how big is the dictionary, can you cache some of it in memory?

[davidcollins001]

I thought about it a bit and changed my algorithm. Now I check every word that is one letter different from the current word instead of following every path to the end. Each letter change is a new level and I move down the level checking all new words against the target. When the target is found this is the shortest path.

I could put the dictionary into a hash and speed it up, but I am more interested in the algorithm.
Thanks :)

 
/*
 * find the shortest path to bread from short changing only one letter
 * at a time
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define WORDSIZ 5
 
struct words_t {
    int level;
    char word[WORDSIZ+1];
    struct words_t *next;
};
 
int shuffle(struct words_t **head, struct words_t *level, char target[WORDSIZ+1], int lp);
int dict(char word[WORDSIZ+1]);
int find(struct words_t *head, char word[WORDSIZ+1]);
int print(struct words_t *head);
 
 
int
main(void) {
    int counter;
    char start[WORDSIZ+1] = "short", end[WORDSIZ+1] = "bread";
    struct words_t *head;
 
    printf("START: %s\tTARGET:%s\n", start, end);
 
 
    head = malloc(sizeof(*head));
    head->level = 0;
    strncpy(head->word, start, WORDSIZ+1);
    head->next = NULL;
 
    counter = shuffle(&head, head, end, 0);
 
    printf("\n\n\tFOUND IT!\n");
    printf("count %d\n", counter);
    print(head);
 
    return 0;
}
 
 
int
shuffle(struct words_t **head, struct words_t *level, char target[WORDSIZ+1], int lp) {
    static int counter = 0;
    int i, j;
    char current[WORDSIZ+1];
    const char alpha[27] = "abcdefghijklmnopqrstuvwxyz";
    struct words_t *currlist = *head;
    struct words_t *nextlist = currlist;
    struct words_t *new;
 
    /* go to the next level of words */
    ++lp;
    printf("level: %d\n", lp);
 
    /* search through current level list of words */
    while((currlist != NULL) && (currlist->level == (lp-1))) {
 
        strncpy(current, currlist->word, WORDSIZ+1);
 
        /* increment letter */
        for(j=0; j<26; ++j) {
 
            /* loop over all letters */
            for(i=0; i<WORDSIZ; i++) {
 
                /* try next letter */
                if(alpha[j] == currlist->word[i]) ++i;
                current[i] = alpha[j];
 
                /* have we found a word in the dictionary? */
                if(dict(current)) {
 
                    if(find(*head, current) == 1) {
                        /* a match was found for this word already */
                        break;
                    }
 
                    new = malloc(sizeof(*new));
                    strncpy(new->word, current, WORDSIZ+1);
                    new->next = nextlist;
                    new->level = lp;
                    strncpy(new->word, current, WORDSIZ+1);
                    nextlist = new;
                    *head = nextlist;
 
 
                    /* end recursion here */
                    if(strncmp(current, target, WORDSIZ) == 0) {
                        /* the target word is found */
                        return 1;
                    }
                } 
 
                /* 
                 * a word was not found with this letter, revert to
                 * last word 
                 */
                current[i] = currlist->word[i];
            } 
        } 
        currlist = currlist->next;
    }
 
    /* current word matches the target */
    if((counter = shuffle(head, *head, target, lp))) {
        return ++counter;
    }
 
    /* only unused words reach here and are freed */
    //free(new);
    return 0;
}
 
 
int
find(struct words_t *head, char word[WORDSIZ+1]) {
    struct words_t *current = head;
 
    while(current != NULL) {
        if(strncmp(current->word, word, WORDSIZ) == 0)
            /* this word has already been used return 1 */
            return 1;
        current = current->next;
    }
    return 0;
}
 
 
int
print(struct words_t *head) {
    struct words_t *current = head;
 
    if(current == NULL) return 0;
 
    /* recursively print to get correct order */
    print(current->next);
    printf("<%d:%s> ", current->level, current->word);
 
    return 0;
}
 
 
int 
dict(char word[WORDSIZ+1]) {
    char grep[152];
 
    snprintf(grep, 151, "grep --silent '^%s$' /usr/share/dict/words", word);
 
    /* return 1 if a match is found */
    return !system(grep);
}
 

[Plamen Panov]

I will describe the algorithm and the computer program in Standard C language to solve this word puzzle.

The goal is to order all the words in the dictionary in a tree like structure starting from the 'start' word .
This will be the trunk of the tree or level 0. Then the program iterates through the dictionary (a linked list of structures) and discovers all words with a single character difference. My procedure compares the words by comparing the characters instead of iterating the alphabet - less expensive. This will be our 1 level of the branches of the tree. Then for each word on level 1 and following levels the program iterates again through the dictionary, discovers words with single character difference and associates them (using C pointers) to the parent word. On the upper branches many words will point to a single parent word. Every time during the iteration the program checks if the targeted word was reached and if so, stops and prints the words in order. Once a word is associated on the tree it will be ignored in following iterations. The reason for ignoring the words already included on the tree is that if we don't it, then logically we are going in circles.

The dictionary is initialized from the beginning in the only linked list used in the program.

The word structure is like this:

struct words_t {
int level;
char word[WORDSIZE+1];
struct words_t *parent;
struct words_t *next;
};

pointer 'next' is for navigating the dictionary and pointer 'parent' is for constructing the tree like structure which will hold the result.

here it is:

NB the dictionary is truncated, but I have attached the full header file here too.







puzzle.h

#define WORDSIZE 4
 
struct words_t {
     int level;
     char word[WORDSIZE+1];
     struct words_t *parent;
     struct words_t *next;
 };
 
int find(struct words_t *currword, struct words_t *dicstart, struct words_t *target, int level); 
int print(struct words_t *path);
 
 
char *dictionary[] = {
"abet",
"able",
"ably",
"abut",
"aces",
"ache",
"acid",
"acme",
"acne",
"acre",
"acts",
"adds",
"adze",
"aeon",
"afar",
"aged",
..........
}
 

and

puzzle.c

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
 #include "puzzle.h" 
 
int main(int argc, char *argv[])
{
 
     if (( argc != 3 ) || ( strlen(argv[1]) !=4 ) || (strlen(argv[2]) != 4))
           {
                       puts("Usage: puzzle <(4char)From Word> <(4char)To Word>");
                                   return(-1);
           }
 
     char arg1[WORDSIZE+1];
     char arg2[WORDSIZE+1];
     int i;
 //To lower case 
     for (i=0;i<= WORDSIZE;i++){
    arg1[i]=tolower(argv[1][i]);
    arg2[i]=tolower(argv[2][i]);
     }
 
 
     printf("START: %s\tTARGET: %s\n",arg1, arg2);
 
     struct words_t *start = NULL;
     struct words_t *end = NULL;
     struct words_t *dict = NULL;
     struct words_t *new = NULL;
 
 
//Initialize dictionary
 
  i= 0;
  while (i < 1989){
     new = malloc(sizeof(*new));
     new->level = 1000000;
     strncpy(new->word, dictionary[i], WORDSIZE+1);
     new->parent = NULL; //pointer to the root of the treei (initialized as NULL)
     new->next = dict; //pointer to the next word in the dictionary
     dict = new;
     i++;
  }
//My start word goes here and next is the dictionary address: 
     start = malloc(sizeof(*start));
     start->level = 0;
     strncpy(start->word, arg1, WORDSIZE+1);
     start->parent = NULL; //this pointer will remain NULL as it is the root of the tree
     start->next = dict; //pointer to the first word from the dictionary
//The end (target word goes here)    
     end = malloc(sizeof(*end));
     end->level = 1000000;
     strncpy(end->word, arg2, WORDSIZE+1);
     end->parent = NULL;
     end->next = NULL;
 
 
 
     static int levelcounter = 0;
     struct words_t *cmpword = NULL;
 
     for (levelcounter=0;levelcounter<1000; levelcounter++){
    cmpword = start;
    while (cmpword != NULL){
  //printf("\nCHEKPOINT%d\n",cmpword->level);  
      if (cmpword->level == levelcounter){
            if(find(cmpword,start,end,levelcounter+1))
            {
              printf("\n\n\tShortest path found on step:%d\n",levelcounter+1);
              return 0;
            }
          }
    cmpword = cmpword->next;
       }
     }
     printf("\n\n\tPath was not found till step:%d\n",levelcounter);
   return 0;
 }
 
 
 
 int find(struct words_t *currword, struct words_t *dicstart, struct words_t *target, int level) {
 
     struct words_t *dicnext = dicstart->next;
 
    while(dicnext != NULL) {
       //Find a word that is a single character different from the start word and has not been used already
       //Words which have been attached to the tree have level != 1000000
     if ((dicnext->level == 1000000) &&                     
        (((currword->word[0] !=  dicnext->word[0]) && (currword->word[1] ==  dicnext->word[1]) && (currword->word[2] ==  dicnext->word[2]) && (currword->word[3] ==  dicnext->word[3])) ||
        ((currword->word[0] ==  dicnext->word[0]) && (currword->word[1] !=  dicnext->word[1]) && (currword->word[2] ==  dicnext->word[2]) && (currword->word[3] ==  dicnext->word[3])) ||
        ((currword->word[0] ==  dicnext->word[0]) && (currword->word[1] ==  dicnext->word[1]) && (currword->word[2] !=  dicnext->word[2]) && (currword->word[3] ==  dicnext->word[3])) ||
        ((currword->word[0] ==  dicnext->word[0]) && (currword->word[1] ==  dicnext->word[1]) && (currword->word[2] ==  dicnext->word[2]) && (currword->word[3] !=  dicnext->word[3]))))
        {
 
                 //printf("(level:%d %s)\n",level,dicnext->word);
          dicnext->parent = currword; //word with a single char difference is found and attached to the tree     
          dicnext->level = level; //tagging this word with the current level    
 
              //Check if this is our targeted last word
          if(strncmp(dicnext->word, target->word, WORDSIZE) == 0)
              {  
            //if it is the targeted word, print the chain and return 1
            print(dicnext);
            return 1;
              }
           }
 
        dicnext = dicnext->next;
 
     }
     return 0;
 }    
 
 
 
 
 
int  print(struct words_t *path) {
     struct words_t *current = path;
     //struct words_t *prev;
     if(current == NULL) return 0;
     /* recursively print to get correct order */
     print(current->parent);
     printf("<%d:%s>\n", current->level, current->word);
    return 0; 
}
 
 
 

Regards,
Plamen