Carroll's doublets
In March 1879 Lewis Carroll published a new game in the magazine Vanity Fair, “doublets”. Given two words of the same length, turn the first into the second by changing one letter per move and keeping it in its place, and every intermediate word must be a real word. His own example: HEAD → HEAL → TEAL → TELL → TALL → TAIL. It works the same way in Russian: день → тень → течь → точь → ночь, “day” to “night”.
You are given a dictionary and two words from it. Find a chain with the fewest moves. One of the tests is all the five-letter words of “War and Peace” in the Russian original, and there it takes nine moves to get from «пушки» (“cannons”) to «ружья» (“guns”).
Input
The first line holds the number n, the size of the dictionary (1 ≤ n ≤ 10,000). The second holds the starting and final words separated by a space. Then n lines, the words of the dictionary, all different. The starting and final words are in the dictionary. All words have the same length L (1 ≤ L ≤ 10) and consist of lowercase letters: Latin in some tests, Cyrillic in others (the letter ё is replaced by е). The input is in UTF-8; in Go compare runes, not bytes.
Output
If one word cannot be turned into the other, print -1. Otherwise the first line is the smallest number of moves k, and the second a chain of k + 1 words separated by spaces, from the starting word to the final one. If there are several shortest chains, any will do.
Examples
Example 1
21 head tail tale belt read bead seal load lead road toll teal tail tell heal head heat bell meal toil tall beat held
5 head heal teal tell tall tail
Example 2
10 cold warm card cord wart warm bold core cold bolt word wore
-1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Words are the vertices of a graph, a move is an edge. Which traversal finds a path with the fewest edges?
2Hint 2
The graph can be built by comparing every pair of words. How many comparisons is that with ten thousand words? And how many neighbours can a word of length L really have?
3Hint 3
The words “head” and “heal” agree everywhere except the last letter. If it is covered with an asterisk, both turn into the same string “hea*”.
4The idea
You need an ordinary breadth-first search from the starting word: the first time the wave reaches the final word, that is the shortest chain, and the parents restore it backwards. All the difficulty is in the neighbours. For each word and each position make a key: the word with that letter replaced by *. All words with the same key differ pairwise in exactly one letter; these are the edges, and they are collected in one pass over the dictionary.
5Walkthrough
First sort the words into “buckets”: buckets["hea*"] = [head, heal, heat]. Then the breadth-first search: the neighbours of a word u are all words in its L buckets except itself. It is enough to open each bucket once: its words are neighbours of each other, and whoever opened the bucket first is closest to the start, so all its words get the right distance at once. The reference deletes a bucket after it is first opened.
There is a second way to find neighbours: try every replacement of every letter by every letter of the alphabet and check whether the resulting word is in the set. That is L · 33 checks per word instead of n comparisons, fast as well.
Why the answer is shortest is worked out in the article: the wave goes through the words layer by layer, and a word is first seen with the smallest possible number of moves.
5+Solution
6Complexity
There are at most nL buckets, each word lies in L buckets, and a key is built in O(L): O(nL²) time and memory in all. Comparing all pairs costs O(n²L): with n = 10,000 that is fifty million pairs of words, and in Python such a search takes minutes.
7Common mistakes
- All pairs of words. The answer is right, but a dictionary of ten thousand words will not fit in the time: this is
wrong.py. - Depth-first search. It finds a chain, but not the shortest: from «мать» (“mother”) to «отец» (“father”) in the dictionary of “War and Peace” it can easily wander off for hundreds of moves instead of nineteen.
- Bytes instead of letters. In UTF-8 a Cyrillic letter takes two bytes. If you compare bytes, words that differ in one Cyrillic letter often differ in two bytes in a row, and such a move will not count. In Go convert a word to
[]rune. - The start equals the end. The answer is 0 and a chain of one word.