Enhyper: 2007-07-08

Saturday Afternoon Puzzle Club

A couple of weekends ago my daughter and I sat down with a brainpower DVD we picked up from the Times earlier this year. While we found that we could make good progress on most of the analytical puzzles as long as we spent enough time on each problem, we are unfortunately both quite lazy, and it didn't take long for us to start cheating.

For example:

When the letters of the following words are placed together how many eight letter words can you form?
VINE + FROG

The anagram puzzles are easiest to cheat on. All you need is a program that computes all the permutations of the letters and looks each resulting word up in an online dictionary to see if it's there. Now it's easy enough to find an online anagram search to do this, so you don't have to write one yourself.

But what happens if you have to compute the permutations of something other than letters in words, in particular, mathematical symbols?

Assume you are using a basic calculator. Press the numbers in order and replace each question mark, as you go, with a mathematical symbol. Using plus, minus, multiply and divide once only how many different arrangements are there for this equation to equal four?
7 ? 1 ? 7 ? 7 ? 4 = 4

In this case, you could evaluate the above expression with all permutations of the four symbols: * - / + and reject the ones that don't match. Now I realise that it would take longer for me to write a program to do this than it would for an eight-year-old to sit down and work out each of the possible values, but earlier this week I picked up the second and third fascicles of Volume 4 of Donald Knuth's Art of Computer Programming, and I felt like coding.

Algorithm L (lexicographic permutation generation) looks like this in Smalltalk:


LexicalPermutor >> permute: aSequenceableCollection
| n j l k |

"Precondition: the sequence is sorted lexicographically - necessary for step L3 to work"
sequence := OrderedCollection withAll: aSequenceableCollection asSortedCollection.
n := sequence size.

[
 "L1. visit the sequence"
 visitor visit: self.

 "L2. find j, the smallest subscript such that all permutations up to j have been visited"
 j := self smallestSubscriptVisited.

 "L3. increase a[j] (the current element in the sequence)"
 l := n.
 [(sequence at: j) >= (sequence at: l)] whileTrue: [ l := l - 1 ].
 sequence swap: j with: l.

 "L4. reverse a[j+1]...a[n]"
 k := j + 1.
 l := n.
  [ k < l ] whileTrue: [
   sequence swap: k with: l.
   k := k + 1.
   l := l - 1 ].

 ] repeat ]

where step L2 finds the smallest substring that hasn't yet been permuted (and also provides us with a stopping condition)

LexicalPermutor >> smallestSubscriptVisited
| j |

j := sequence size - 1.

[(sequence at: j) >= (sequence at: j+1)] whileTrue: [
 ((j := j - 1) = 0)
     ifTrue: [PermutationCompleteException raise]].

^j

The cool thing about this is that you can pass in any sequence of symbols you want - for example you could pass in the string 'vinefrog' and have a visitor class that looks up the value in a dictionary.

At the beginning of the book Knuth says that enumerating the permutations is just a fancy way of saying that we are counting them, which is actually not very interesting. Nor is it interesting to list them. What we want to do is visit them and do something intelligent. The visitor is doing the application-specific stuff, and the permutation algorithm essentially acts as a black box.

In this particular example, we want the visitor to evaluate an expression and only write an answer if the result is the same as some target value.

The permutation algorithm lives in a class called LexicalPermutor, and the visitor is called a FunctionListVisitor, which gets initialized with some parameters and a target value:

LexicalPermutor class >> example

| permutor visitor |

permutor := LexicalPermutor new.
visitor := FunctionListVisitor new
 numberList: #(7 1 7 7 4);
 target: 4.
permutor accept: visitor.
permutor permute: '+-*/'.

To answer the puzzle then, all we need is a visit: method that evaluates the expression, tests the result and prints a message if it finds something interesting:

visit: aTarget

[accumulatedValue := numberList first.
aTarget sequence keysAndValuesDo: [ :index :function |
 accumulatedValue := accumulatedValue perform: function asSymbol with: (numberList at: index + 1) ]]
     on: Number divisionByZeroSignal
     do: [ :ex | ^self ].

"Notify the world of successful evaluation"
(accumulatedValue = target)
 ifTrue: [
     total := total + 1.
     Transcript cr; show: total printString; tab.
     self print: aTarget sequence on: Transcript withResult: target ]

The first block of code just does what your calculator would do as you successively go through and perform: the function on the accumulated result (with a check for division by zero).

The second block just prints the result, which looks like this:

1    7 * 1 - 7 / 7 + 4 = 4
2    7 * 1 / 7 + 7 - 4 = 4
3    7 + 1 * 7 / 7 - 4 = 4
4    7 + 1 / 7 * 7 - 4 = 4
5    7 / 1 - 7 * 7 + 4 = 4

The answer is 5. But I knew that because an eight-year-old told me the answer before I could figure it out for myself.

The visitor to solve the following puzzle is very similar to the one above:

Assume you are using a basic calculator and press the numbers in the order shown, replacing each question mark with a mathematical sign. Plus, minus, multiply and divide can each be used once only. What is the highest number you can possibly score?
7 ? 6 ? 1 ? 8 ? 9 = ?

The next step is to look algorithms to generate combinations of t items taken n at a time. This will solve puzzles like this: