### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

14 June 2015

Posted by on **From New Scientist #1435, 20th December 1984** [link]

A multiplet is a given set of words, and the game is to connect them with a network of as few link-words as possible. In the network, any two adjacent words are related in one of three ways:

(a) one letter is changed: e.g. MINUS → MINES

(b) one letter is added/removed: e.g. PLUS → PLUMS

(c) anagram: e.g. PLUMS → LUMPS or PLUMS → SLUMPThe picture shows a network for the multiplet “MINUS, ZERO, PLUS”, with 11 link-words.

For your Christmas prize, the multiplet is the first 10 natural numbers, “ONE, TWO, …, TEN”. Can you connect them with 15 or fewer link-words? If so, how?

All link-words must be of three or more letters. They must be in the

Concise Oxford Dictionary, or simple inflexions of words in it. Words there marked as abbreviations are not allowed; so “SEN” for instance is not permitted. Common words are preferable to obscure ones.

[enigma288a] [enigma288]

Advertisements

%d bloggers like this:

I thought this was a tough problem to solve programatically.

For a start I didn’t have a list of allowable words. I did find a file on my system under

/usr/share/dict/web2that is a list of words from Webster’s Second International [Dictionary], published in 1934. It includes SEN (which is apparently a monetary unit in some countries), and quite a lot of other obscure words that I didn’t really want in my solutions, so I used a list of stop words to weed out words I thought were too esoteric when they showed up.The problem with this list is that it doesn’t also include “simple inflexions of words” in the list (such as plurals, which are clearly useful for the example given with PLUS, MINUS and ZERO; for example, PLUMS does not appear in the list), but it didn’t look as though they would be particularly useful for the main problem, so I ignored this deficiency in my word list.

(If anyone knows of a more suitable wordlist available for download I like to hear from them).

The next problem was that the wordlist I did have has around 234,000 words in it. Constructing the complete graph that links all the words would take too long, so we need to work on a subset of the graph. And even when I have a suitable subgraph the problem of finding the smallest connected subgraph of a graph is an NP-hard problem (see Steiner Tree in Graphs).

To try and make some progress on the problem I adopted “greedy” strategies for both of these issues.

To construct a connected graph I use the following algorithm:

When the algorithm terminates the collection of graphs consists of a single graph that contains all the target vertices and is connected. Although the graph has been constructed with minimal “effort” there is no guarantee that the graph contains a minimally connected subgraph of the complete graph.

So we can now search the constructed graph to try and find a connected subgraph.

The strategy I used to try and connect the target vertices in an efficient way is as follows.

When the algorithm terminates all target vertices are in the trunk (and if the trunk was initially connected then it will still be connected).

This algorithm uses shortest paths to find a subgraph, but there is no guarantee that it will find the smallest possible subgraph.

But we are not asked to find the smallest possible subgraph, only if it is possible to achieve a subgraph containing the 10 target vertices and 15 or fewer intermediate vertices (i.e. 25 or fewer vertices in total).

So I implemented the algorithms in the Python program to appear below (I need to tidy it up a little before I post it). I tried each target vertex as the initial “trunk” and found that several of them did indeed produce a subgraph with 25 vertices.

Solution:Yes, the words: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN can be connected with 15 link words.Here is a diagram that shows some example solutions:

In the vertices with two options in them (e.g. “TOO/TOW”), either word can be used without changing the shape of the graph. There are also some cycles in the graph, which give rise to multiple spanning trees of the graph, any one of which is a viable solution.

I prefer not to use the archaic terms THINE and THEE in my solutions, although they are in the dictionary.

I found that choosing THREE or FIVE as the initial “trunk” gave a subgraph with 25 vertices (the others give a subgraph of size 26). Also, rather pleasingly, the solution given above can be found by selecting a “trunk” of TREE.

The published example solution is similar (using THINE, TOO, FOR and TREE), but replaces TOE with TON, which then links to TEN instead of TEE.

I found a list of

Scrabblewords online, the file is calledsowpods.txtand contains 267,627 candidate words (including SEN), and it includes word inflexions. Here’s my Python 3 code (of course you also need a wordlist for it to work). You can add words that you don’t like to the list of stopwords.You can provide a list of target words as the first command line argument, and an optional list of trunk words as the second command line argument (if no trunk words are given the first target word is used). (Note that the lists are space separated, so will probably need to be quoted to stop the shell from splitting them).

Depending on the wordlist and the trunk specified (if any), I get run times of about 8s to 15s for targets of ONE, …, TEN. (Most of the time goes in the construction of the subgraph, rather than searching it, so I should probably improve that part of the implementation).

I’d be interested to hear from anyone who has a program that generates a smallest possible subgraph in a reasonable time.

If SEN is not excluded from the list of candidate words we can get a solution graph with 24 vertices. (So 14 link words). Although the solution found also includes the words FON and FONE.

Running the program over a list of “normal” words provided by Hugh Casement with 61,752 candidate words in produces a connected graph with 419 vertices and several connected subgraphs with 25 vertices (15 link words) in 3.4s. (A lot smaller than the 267,627 candidate words and connected graph with 1176 vertices produced by the

ScrabbleWords).Most of the solutions are similar to the diagram given above, except that TING is not in the word list, so THINE is always included.

Interestingly one of the solutions uses: FIVE – FIE – FIX – SIX, rather than linking SIX via SEX into the TEN / SEVEN area, and FIVE via FINE into NINE.

Here are the branches of the tree from that solution: