lewis_carroll_distance

In 1879, Lewis Carroll proposed the following puzzle to the readers of Vanity Fair: transform one English word into another by going through a series of intermediate English words, where each word in the sequence differs from the next by only one substitution. To transform head to tail, one can use four intermediates, assuming we are using a standard English dictionary to determine words: head → heal → teal → tell → tall → tail. We refer to the smallest number of substitutions necessary to transform one word to another as the Lewis Carroll distance between the two words.