Assignment 3
Word Game
Worth 10% Final Deadline : Wednesday 28th May at 11.59pm.
Checkpoint Deadline : Sunday 25th May at 11.59pm.
(Reasonable attempt at part A MUST be submitted).
Objectives : To learn more about graph algorithms and to appreciate the diversity of applications. To improve programming skills with common STL data structures. To recognize the importance of systematic development and testing.
Overview
In this assignment you are required to write a program which generates solutions to a common word game. The word game gives you a start word and a goal word and asks you to transform start to goal by changing only one letter at a time in the minimum number of steps. Each word in the path must be a valid word i.e. appear in given dictionary. For example you can change hate to love in the following steps.hate have hove love
Part A worth 5%.
Implement a program which reads in values for start and goal, performs a breadth first traversal of the implicit graph and displays a solution for the word game. We consider only 4-letter words.- Your program should read in dict.txt and store it in an appropriate data structure. This dictionary consists of about 2000 lower case 4-letter words, one per line.
- Your program should prompt, read in words, display result until end-of-file is entered. (control-d on unix or control-z on windows).
- Your program should prompt "Enter start : " and "Enter goal : " and read in the words. If start and goal words are in the dictionary, it should perform a breadth-first search to display the solution, if found or else "No solution ". If either word is not in dictionary then your program should display "Not in dictionary".
- The breadth-first search should use the pseudocode given with OPEN implemented as a FIFO queue and CLOSED implemented as a map.
- The map should keep track of the parent of each word in CLOSED so that on finding the goal you can print the solution from the start to the goal. Recall the example from lectures.
- You may submit as many files as you like as long as they compile and run with
g++ *.c* on titanic.
- This will be automatically marked so your program should match the sample run given (apart from white space).
Part B worth 5%
Implement a more efficient search for the shortest solution. You should consider using a priority queue with a weighting which "pulls" the search towards the goal. Note that your program may be timed out for this part if it is too slow.- You may submit as many files as you like as long as they compile and run with
g++ *.c* on titanic.
- This will be automatically marked so your program should match the sample run given (apart from white space).
Bonus worth 2%
Discuss your strategy for improving the efficiency of the search and justify the improvement (either a theoretical analysis or a practical demonstration of shorter timing or fewer iterations or similar).Pseudocode
You are provided with a general algorithm for searching an implicit finite graph G for vertex goal, commencing at vertex start.
// General algorithm to search an implicit finite graph G for vertex goal,
// commencing at vertex start.
// Both start and goal are vertices in G.
bool Search(start, goal)
{
bool success;
set_of_vertices OPEN, CLOSED;
vertex w, u;
OPEN = {start};
CLOSED = {};
success = false;
while (not OPEN = {} and not success)
{
choose a vertex, say w, in OPEN;
if (w = goal)
success = true;
else
{
remove w from OPEN;
generate the vertices adjacent to w;
for (each vertex u adjacent to w)
if (u is not in CLOSED)
put u into OPEN; put (u,w) into CLOSED;
}
}
return success;
}
Sample Input/Output
Diagrams
diagrams[an error occurred while processing this directive]