A popular word puzzle is to convert one word into another via a series of steps which replace only one letter and which always result in a valid word. For example, BAG can be converted to DOG via a path of five steps:
BAG -> BAT -> CAT -> COT -> COG -> DOG
Shorter paths also exist in this case; for example:
BAG -> BOG -> DOG
If one drew a graph whose vertices were labelled by words, with an edge between any pair of words that differ by one letter, then the shortest path from "BAG" to "DOG" would consist of two edges.
You are to write a program which receives as input a "dictionary" of words which all have the same length, representing all allowable words that can appear as steps along a path. It should output at least one "longest shortest path", that is, a path between two of the words which is:
no longer than any other path between those two words;
at least as long as the shortest possible path between any other pair of words in the list.
In the context of the graph described above, the length of such a path is the diameter of the graph.
In the degenerate case where none of the input words can be transformed into any of the others, output at least one path of length zero, that is, a single word.
The input ["bag", "bat", "cat", "cot", "dot", "dog"] should yield a path traversing all six words in that order (or reverse order), since the shortest path from "bag" to "dog" within this dictionary is the longest achievable, five steps.
The input ["bag", "bat", "bot" , "cat", "cot", "dot", "dog"] should yield the path "bag, bat, bot, dot, dog" and/or its reversal.
The input ["code","golf","male","buzz","mole","role","mold","cold","gold","mode"] should yield a path between "code and "golf".
The input ["one", "two", "six", "ten"] corresponds to a graph with no edges, so output one or more single-word (zero-length) paths.
If the input contains any two words of unequal length, the output is undefined.
- Standard code golf rules apply
- There will be multiple "shortest" paths. You must output at least one, but are free to output as many as you wish.
- You are free to decide how the input dictionary is passed into your program.
- Shortest code in bytes wins.