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 l
t e a l
t e l l
t a l l

It 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?

About these ads

Pages: 1 2

6 Responses to “Dodgson’s Doublets”

  1. [...] 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 [...]

  2. [...] 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: [...]

  3. [...] we have another post from Programming Praxis’ Word Games. This time, it’s a puzzle inspired by Lewis Carroll [...]

  4. JP said

    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/TAIL gives us HEAD ↦ HEAL ↦ HEIL ↦ HAIL ↦ TAIL which is actually shorter than Dodgson’s given solution.

    The best solution I’ve found for BLACK/WHITE is BLACK ↦ CLACK ↦ CLICK ↦ CHICK ↦ CHINK ↦ CHINE ↦ WHINE ↦ WHITE.

    You can see my code here: Dodgson’s Doublet

  5. Lucas A. Brown said
    #! /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 =
        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 _
            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]
        for l in x: print l, lengths[l]

Leave a Reply


You are commenting using your account. Log Out / Change )

Twitter picture


Facebook photo


Google+ photo


Connecting to %s


Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: