Find all expressions that evaluate to some value
Some friends came to visit last weekend, and we got to talk about the following problem, which seems to have made the news headlines (it was given at a math contest for ten year olds and apparently many math teachers couldn't figure out a solution):
We have numbers 1, 3, 4 and 6. Create an expression using any elementary operators (+, -, *, /), containing only these numbers, exactly once each, such that the result is 24.
(if you'd like to try finding a solution, stop reading now because there's a spoiler here)
I felt the problem itself is inappropriate for 10 y.o. kids and irrelevant for a maths contest; but it seemed like a good programming exercise, so I told'em “while you're banging your heads to guess a solution, I'll go and write a program to give me all solutions.”
I implemented it in Scheme, because it requires backtracking and using continuations for this is a joy. But in this blog post I'll work out the solution in JavaScript.
I whipped up quickly a program that tried all expressions of the form N op N op N op N, where the N-s make all permutations of the given numbers and op-s are any operators, but surprise — it found no solutions.
I asked my friend who sparkled the discussion if he knew of any solution, and he said: 6 / (1 - 3 / 4). Bummer, my program did not consider parentheses; I wrongfully assumed that if I try all possible operators with all possible number permutations, I wouldn't need to care about parens, but now that's obviously false. That expression cannot be constructed without parens with the same numbers.
My program just generated a flat list, alternating numbers and operator symbols. Mixing in parens seemed to add so much complexity that I gave up and we carried on with dinner, beer and unrelated conversation.
But after guests left, as I was glancing at my code still left open in the editor, the solution just clicked: “Reverse Polish Notation!”. Half an hour later I was enjoying that unique feeling you have when you solved what seemed to be a hard problem.
Reverse Polish Notation
RPN is an unambiguous notation for arithmetic expressions that doesn't need parentheses, assuming it is known in advance how many arguments will an operator take (2 arguments is the case in our problem). Here are a few examples, in standard infix notation and reverse polish notation:
1 + 2 1 2 + 1 + 2 * 3 1 2 3 * + (1 + 2) * 3 1 2 + 3 * <== here, parens! 6 / (1 - 3 / 4) 6 1 3 4 / - /
To solve our little problem, all we need is the ability to generate and test all possible expressions (order of evaluation — that is, parens — being taken into account). Nesting lists to represent order of evaluation would badly complicate the code, but RPN conveniently allows us to generate flat lists that still encode this information.
Computing an expression in RPN
If in my first version I was using eval to compute the expression, here I
had to implement a function that evaluates an expression given in reverse
polish notation. Fortunately, the algorithm is very simple:
start with an empty stack
while the expression is not empty:
take the first element out.
is it a number?
YES => push to stack.
NO => it's an operator;
pop two elements from the stack,
apply the operator on them,
push the result into the stack.
the result is the head of the stack.
To evaluate (6 1 3 4 / - /) we'll have these steps (below, the head of the stack is at the left side):
0. stack = () exp = (6 1 3 4 / - /) ; INIT
1. stack = (6) exp = (1 3 4 / - /) ; pushed 6
2. stack = (1 6) exp = (3 4 / - /) ; pushed 1
3. stack = (3 1 6) exp = (4 / - /) ; pushed 3
4. stack = (4 3 1 6) exp = (/ - /) ; pushed 4
5. stack = (0.75 1 6) exp = (- /) ; applied 3/4
6. stack = (0.25 6) exp = (/) ; applied 1-0.75
7. stack = (24) exp = () ; applied 6/0.25
;; exp is empty, 24 is the top of the stack (result)
(note that because a stack is last-in, first-out, we need to reverse the operands when applying the operator; if the stack is (2 1) and the operator is -, the result is -1).
The tail-recursive implementation in Scheme is quite elegant, but here I sticked to a more JS-esque (imperative) approach:
function compute(exp) {
var stack = [];
exp.forEach(function(v){
if (typeof v == "number") {
stack.push(v);
} else {
var b = stack.pop(), a = stack.pop();
switch(v) {
case "+": stack.push(a + b); break;
case "-": stack.push(a - b); break;
case "*": stack.push(a * b); break;
case "/": stack.push(a / b); break;
default: throw new Error("Unsupported operator " + v);
}
}
});
return stack[0];
}
// test
compute([ 6, 1, 3, 4, "/", "-", "/" ]); // ==> 24
The solve function
Now that we have a way to evaluate expressions in RPN, all we need to do is generate valid expressions with the
given numbers and print those which evaluate to the desired result. An expression, as you can see above, is just an
array containing numbers or the strings "+", "-", "*", and "/".
Let's imagine we have two magic functions, guess and fail. guess takes an array of values and a function, and will call that function with a value from the array. And fail() will jump back to the last guess and try the next value. Both of them abort the current computation (neither returns).
Given these two spells, here is the program that solves our problem:
var operators = [ "+", "-", "*", "/" ];
// the function `solve` takes an array of numbers and an expected
// result (also a number). It will find and print all expressions
// that contain the numbers exactly once and evaluate to that result.
function solve(numbers, result) {
// returns true if `sol` is a solution to our problem
function good_result(sol) {
return compute(sol) == result;
}
// returns a list of things (numbers/operators) that are
// valid to append to the current expression (`sol`).
function next_choices(sol) {
var available_numbers = numbers.filter(function(n){
return sol.indexOf(n) < 0;
});
if (accepts_operator(sol))
return operators.concat(available_numbers);
return available_numbers;
}
// the main loop
(function rec(sol){
var things_to_try = next_choices(sol);
if (things_to_try.length == 0) {
if (good_result(sol))
print(sol);
fail();
} else guess(things_to_try, function(value){
rec(sol.concat(value));
});
})([]);
}
There are two helper functions inside, good_result and next_choices, of which the former should be clear enough.
next_choices will return an array of things to try next. From the initial list of numbers, it filters out numbers which were already added to the expression (because the problem constraint is that no number can be used more than once). It also calls an additional function, accepts_operator, to figure out if it's okay to try adding operators.
For example if currently the expression is [ 1, 2 ], then an operator makes sense (the stack would contain
two values in the compute function). Same is the case for the expression [ 6, 1, 3, 4 ] — even
though the stack now contains 4 numbers. But in [ 1, 2, "+" ], or [ 5 ], we cannot add any
operators because the stack would have less than two elements.
The definition of accepts_operator is extremely simple:
function accepts_operator(exp) {
var n = 0;
exp.forEach(function(v){
if (typeof v == "number") n++;
else n--;
});
return n > 1;
}
It iterates the expression like compute, but it doesn't do any evaluation; it just counts how many
values would be left on the stack after evaluating exp. Each time we encounter a number we know it would
be pushed to the stack, hence n++. And each time we get an operator, two elements would be popped from
the stack and one result pushed back, therefore n--. If at least two elements remain finally in the
stack, the expression is incomplete and we can legally apply operators.
The main loop
It defines and immediately calls a function named rec. It takes a single argument (sol — the current expression, initially empty). It keeps adding elements to the current sol until there's nothing left to add. That happens when next_choices(sol) returns an empty list: means sol contains all the numbers and it's a complete expression (no operators are possible). At that point if the expression evaluates to the desired result we print it out. Then we call fail() in order to continue the search.
When next_choices(sol) returns a non-empty array we might have an incomplete expression (operators are possible) or didn't use all the numbers. Or both. In either case we know it can't possibly be a solution. So we use guess to add an element from things_to_try to the current solution and recurse.
The print function
Even though our solutions will be in reverse polish notation, we'd like to print them nicely, therefore we need a function to convert them into something more readable. That's again very simple:
function print(exp) {
function infix(exp) {
var out = [];
exp.forEach(function(v){
if (typeof v == "number") {
out.push(v);
} else {
var b = out.pop(), a = out.pop();
out.push([ a, v, b ]);
}
});
return out[0];
}
function stringify(exp) {
if (Array.isArray(exp))
return "(" + exp.map(stringify).join(" ") + ")";
return exp;
}
console.log(stringify(infix(exp)));
}
The two helpers defined inside do the following:
// infix does what its name says, that is,
// converts from RPN to algebraic (infix) notation.
// notice the similarity with `compute`.
infix([ 6, 1, 3, 4, "/", "-", "/" ]);
// ==> [ 6, '/', [ 1, '-', [ 3, '/', 4 ] ] ]
// stringify makes it easier to read:
stringify([ 6, '/', [ 1, '-', [ 3, '/', 4 ] ] ]);
// ==> "(6 / (1 - (3 / 4)))"
The output is fully parenthesized (I didn't bother to check for precedence to minimize the number of parens).
The backtracking mechanics: guess and fail
I wrote before about the amb operator and about doing tail recursion in JavaScript. guess and fail build up on those ideas.
guess must establish a failure point, and fail should return to that point and retry with another value. Internally they use exceptions, in order to avoid over-loading the stack.
First we define a Continuation object that holds a function (program) and arguments to feed it:
function Continuation(program, args) {
this.program = program;
this.args = args;
}
fail is a global variable, always holding a function, which is maintained by guess. Its initial definition throws a continuation which prints “we're done”:
var fail = function() {
throw new Continuation(function(){
console.log("Search tree exhausted"); // we're done.
});
};
And here's the guess function:
function guess(values, program) {
var oldfail = fail;
(fail = function() {
if (values.length > 0)
throw new Continuation(program, [ values.shift() ]);
(fail = oldfail)();
})();
}
It saves the current fail handler, and installs (and also calls immediately) a new one which takes a value from the array and calls the program with it (by throwing the Continuation). If the program will call fail, we get back here, fetch the next value, throw a new Continuation, and so on until there are no more values left to try. When that's the case we restore, and call immediately, the previous fail handler (which will itself throw a Continuation). Note that both fail and guess always throw — you can rely on the fact that they don't ever return. Also note that calling guess with an empty values array is equivalent to calling fail, though perhaps a bit slower.
Since all this is based on exceptions we need one final tool: the execute function will setup a loop that catches Continuation-s and executes them. Initially it takes a function (program) to execute and an array of arguments to pass to it.
function execute(program, args) {
while (true) try {
return program.apply(null, args);
} catch(ex) {
if (ex instanceof Continuation) {
program = ex.program;
args = ex.args;
}
else {
console.log(ex);
throw ex;
}
}
}
To run our program now:
// original problem:
// (that solution happens to be unique)
execute(solve, [
[ 1, 3, 4, 6 ],
24
]);
// add a 2 and demand the result to be 25:
// (1364 solutions)
execute(solve, [
[ 1, 2, 3, 4, 6 ],
25
]);
Finally, here's the whole program, runnable with NodeJS, if you care to play with it: 24.js.