A Word Ladder program is similar to a "6 degrees of separation"or Oracle of (Kevin) Bacon (Links to an externalsite.)Links to an external site. game, but using words ratherthan people or actors. Simply, from a given starting word, find theshortest "ladder" of single letter changes which leads to somefinal word, where each intermediate state is also a word.

For example:

clash, flash, flask, flack, flock, clock, crock, crook,croon, crown, clown.

As you might infer from the example above, there is no simplealgorithm that generates a word ladder. Rather, youhave to search for a ladder by generating all of the possibilities.Doing so will give you an opportunity to use Python data structureslike lists and dictionaries.

Your program should first read in the filefile.txtgiving it alarge collection of words to work with. All of the examplesin the tests that your program will be given will be of lengths 4,5 and 6, so you can discard all words that are not of one of thoselengths. However, you should write the program so that it isgeneral enough to make it easy for you to change it to handle otherword lengths.

You must then read in lines containing pairs of words from asecond file named words.txt and print out theladder for each pair or an indication that no ladder exists. You should check that the input words are of the same length andthat that length is in the range described above. You canassume that every line in the text file will contain two words; youonly need to check for potential length problems, as describedabove.