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 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 = 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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: