How to Solve the Puzzle With Code
From Ed Pegg Jr. of mathpuzzle.com: Rearrange the 11 letters of "interaction" to make
two closely related words. What words are they?
Well, that was quite a challenge! There are 399,168,000 possible solutions (11
factorial
times 10), so
you have to be quite careful to work efficiently. That is a lot of work even for a fast computer.
Fortunately I tuned my algorithm to completely avoid brute force; it runs way faster than a
naïve solution.
There are two issues you must take great care with when examining a solution set this huge: 1) try to avoid
unnecessary work, and 2) manage your memory carefully.
Don't Abuse Your Strings!
Memory management is important when dealing
with string data types, since they are
immutable
in .NET. That means that any time you modify a string,
perhaps by rearranging the letters, you are actually creating a new string and
abandoning the old. After we use up all our RAM creating new spellings of 'interaction',
we will sit there and wait while the
garbage collector
cleans house. Since the garbage collector runs on a low priority thread, we will
wait a long time. Unless, of course,
we are careful not to create 400 million new strings!
Note that there are two parts to solving this puzzle: 1) creating all the possible
permutations
of the word 'interactions', and 2) splitting each candidate into two subwords and checking whether
either of them are actual words. There isn't much I can do to improve the second
task, but the first task has lots of opportunity for improvement.
Sample Permutation
In order to understand the permutation algorithm, take a look at the permutations of the word 'cat':
Examine the list carefully: it will give you an idea how to solve the puzzle. Namely, rotate the all the
letters one position to the right, and move the last letter to the first
position. (I.e. transform cat into tca.) Then repeat the process for the the subword starting as position 2
(if you have cat, rotate subword at so you get cta).
Observe how we hold the first letter constant while rotating the letters to the
right of it, until we have exhausted their permutations.
When working with longer words, we follow the same pattern. This gives us a
systematic method we can extend to longer words. If you don't get it, practice
with pencil and paper. Use a 4-letter word if you need to.
Create Your Building Block Procedure
To implement the pattern: write a method that will rotate the
right-hand side of any word you give it. For each starting point in the word,
rotate your word, then call your method repeatedly for all the 'subwords' to the
right of your starting point. After you get that working, modify it so that it
will rotate starting at any position you like.
The Secret for Speed!
We want to run fast and efficient, so the secret is to stop if there aren't any valid
words that start with the starting letters of our current candidate. If our current
candidate is 'ninteractio', and we are rotating the last 6 letters, we can abort,
because there are no words that start with 'ninte'. So we can save 6 factorial steps by abandoning our
rotations now. (ninteractio has 11 letters; we have examined 5, there are
6! subwords remaining for our current candidate.)
The other main trick to get this algorithm to run efficiently is to manage your memory carefully by
using a char array, instead of a string, to rotate your letters.
I pasted a code snippet below to illustrate the top-level logic.
public void PermuteAndCheckSubWords(char[] aWord, int ndx) {
if (ndx < aWord.Length - 1) {
for (int i = ndx; i < aWord.Length; i++) {
RotateEnd(aWord, ndx);
if (i < aWord.Length - 1) {
EvaluatePotentialSubWords(aWord);
}
if (SomeWordsStartWithThis(aWord, ndx)) {
PermuteAndCheckSubWords(aWord, ndx + 1);
}
}
}
}
Note that
-
I have a method 'RotateEnd' that rotates letters in starting
with the specified index
-
My other method 'EvaluatePotentialSubWords' tries to split a candidate into sub-sections that might be
words. For example, when evaluating 'interaction, it checks whether 'i' is a word and whether, 'nteraction'
is a word, then whether 'in' is a word and whether 'teraction' is a word.
-
I have a method named 'SomeWordsStartWithThis' that determines whether there exist any words
which that start with the current beginning of the word candidate.
As discussed above, this is crucial if you want your solution to run fast!
-
The method is recursive,
i.e. it calls itself. Theoretically you can convert any recursive method into a non-recursive equivalent,
but after struggling with this for hours, I just left it alone and moved on!
Download
Download my solution code here. Note that you will
need a word list to run the code, and you will need to modify your code to reflect the path
where you saved your word list.
My references section has some nice word lists.