Dodgson’s Doublets
March 20, 2009
Charles Dodgson was an English author, mathematician and logician of the nineteenth century; better known by his pseudonym Lewis Carroll, his most famous works are Alice’s Adventures in Wonderland and the sequel Through the Looking Glass. In 1879, Carroll published the Doublets word game in the Vanity Fair magazine:
The rules of the Puzzle are simple enough. Two words are proposed, of the same length; and the Puzzle consists in linking these together by interposing other words, each of which shall differ from the next word in one letter only. That is to say, one letter may be changed in one of the given words, then one letter in the word so obtained, and so on, till we arrive at the other given word. The letters must not be interchanged among themselves, but each must keep to its own place. As an example, the word ‘head’ may be changed into ‘tail’ by interposing the words ‘heal, teal, tell, tall’. I call the given words ‘a Doublet’, the interposed words ‘Links’, and the entire series ‘a Chain’, of which I here append an example:
H E A D
h e a l
t e a l
t e l l
t a l l
T A I LIt is, perhaps, needless to state that it is de rigueur that the links should be English words, such as might be used in good society.
Write a program that takes two words and finds a chain between them. What is the chain that connects black to white?
Programming Praxis 
[…] are a common data type, which we have used in several exercises (Mark V. Shaney, Word Frequencies, Dodgson’s Doublets, Anagrams). Hash tables are often used as the underlying implementation for dictionaries, and in a […]
[…] Dodgson’s Doublets Charles Dodgson was an English author, mathematician and logician of the nineteenth century; In 1879, Dodgson published the Doublets word game in the Vanity Fair magazine: […]
[…] we have another post from Programming Praxis’ Word Games. This time, it’s a puzzle inspired by Lewis Carroll […]
There weren’t as many solutions here as to most of the posts, so I decided to give it a try.
What I ended up with is actually three solutions (all in Racket): First a naive brute force, depth first solution and then a slightly better version that uses a simple heuristic to check the more likely branches first. Finally, I went for a depth first solution that took *much* longer to run, but is guaranteed to find a shortest solution. For example,
HEAD/TAILgives usHEAD ↦ HEAL ↦ HEIL ↦ HAIL ↦ TAILwhich is actually shorter than Dodgson’s given solution.The best solution I’ve found for
BLACK/WHITEisBLACK ↦ CLACK ↦ CLICK ↦ CHICK ↦ CHINK ↦ CHINE ↦ WHINE ↦ WHITE.You can see my code here: Dodgson’s Doublet
Basic A*: https://github.com/ftt/programming-praxis/blob/master/20090320-dodgsons-doublets/dodgsons-doublets.py
#! /usr/bin/env python # 1. head and tail must be of the same length. # 2. Both must be in words. # 3. words must be a list of words of the same length as head and tail. # 4. We will pretend that the contents of dontuse are not in words. def dodgson(head, tail, words, dontuse=[]): l = len(head) if sum(head[i] != tail[i] for i in xrange(l)) == 1: return [head, tail] heads = [] for w in words: if sum(head[i] != w[i] for i in xrange(l)) == 1 and w not in dontuse: heads.append(w) if heads == []: return None for h in heads: # This loop isn't necessary but on the average results in a huge speedup and significantly shorter ladders. if sum(h[i] != tail[i] for i in xrange(l)) == 1: return [head, h, tail] for h in heads: d = dodgson(h, tail, words, dontuse + [head]) if not d is None: return [head] + d return None if __name__ == "__main__": from sys import argv from random import shuffle if len(argv) == 4: g = open(argv[3], "r") else: g = open("/etc/dictionaries-common/words", "r") f = g.read() g.close() w, words = [], [] l = len(argv[1]) for w in f.split(): if all(l in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" for l in w) and len(w) == l: words.append(w.lower()) lengths = {} for _ in xrange(100000): if _ % 100 == 0: print _ shuffle(words) ladder = dodgson(argv[1].lower(), argv[2].lower(), words) l = len(ladder) if l in lengths: lengths[l] += 1 else: lengths[l] = 1 if l <= 6: print ladder x = [l for l in lengths] x.sort() for l in x: print l, lengths[l][…] studied word chains in a previous exercise; for instance, you can convert HEAD to TAIL by the word chain HEAD, HEAL, TEAL, TELL, TALL, TAIL in […]