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 )
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 )
Code:
/*
* 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);
}
Comment