This project aims to generate "paths" of least cost between words. A path between two words of the same length, given as the start and end points, is a sequence of words of equal length where each word is obtained from its predecessor by replacing one or more characters. All words in the path must belong to a given dictionary.
The objective is to find a sequence of words that starts with a given word and ends with another given word. Each intermediate word in the sequence must be obtained by changing one or more letters, as long as the word is on the dictionary. Changing n letters has quadratic cost
For example, a path between the words "carro" and "pista" could be:
- carro
- corro
- corto
- porto
- porta
- posta
- pista
This has total cost
The program creates linked lists of words of same length based on the given dictionary and then uses Dijkstra's algorithm and an Heap to search for the path with least cost, if it exists.
To compile the program type make on your terminal in the project's file directory.
make
To execute the program:
./wordmorph [DICTIONARY] [WORDS]
wordmorph
: The executable name.DICTIONARY
: A.dic
file with a list of words, one per line.WORDS
: A.pal
file containing two words and max n letter changes at a time.
The output is a .path
file with starting word followed by the cost of the path or -1 if there is no available path.
Then one word per line until the last word of the path.
Adicional files with problems will be added so you can test it.