Solving a small primary school problem with Prolog

A couple of days ago my small son came home with math homework from school. The problem: add parenthesis to the following arithmetic expression so it makes sense.

14 * 3 - 8 / 2 = 17

When I saw that, I thought it was a nice little programming exercise. Also Prolog seems like an appropriate language to write the a solution for this problem.

To solve this problem we need at least to:

1. Choose a representation for the input formula and the results
2. A way to generate all possible combinations of arithmetic expressions
3. Something to evaluate the arithmetic expression so we can get the result
4. Let Prolog find the answer we need!

First, we need to generate all possible expressions from given the problem .

Input representation

We're going to represent the input formula as a list of the parts of the expression.

For example, given the following expression:

14 * 3 - 8 / 2 

The input representation for this formula is the following:

[ 14, '*', 3, '-', 8, '/', 2 ]

To represent the output formula I'm going to use a term with the form op(operator, left, right).

For example, to represent the following possible groupings:

(9*(6+(6/(6-9))))

It will be represented as:

 op(*, 9, op(+, 6, op(/, 6, op(-, 6, 9))))

Generating expression groupings

Given the representation of the problem we can write a predicate to generate all possible groupings of these operations.

After some unsuccessful attempts I came with the following predicate:

arith_op([X], X) :- number(X),!.
arith_op(Arr, op(Op, X, Y)) :-
    append(First, [Op | Second], Arr),
    arith_op(First, X),
    arith_op(Second, Y).

What I really like about Prolog is that with relative few words we can find a solution for problems like this.

Now I can take advantage from Prolog's backtracking mechanism and find all possible solutions for the following input.

?- arith_op([ 1, '*', 2, '+', 3, '/', 4]  ,X).
X = op(*, 1, op(+, 2, op(/, 3, 4))) ;
X = op(*, 1, op(/, op(+, 2, 3), 4)) ;
X = op(+, op(*, 1, 2), op(/, 3, 4)) ;
X = op(/, op(*, 1, op(+, 2, 3)), 4) ;
X = op(/, op(+, op(*, 1, 2), 3), 4) ;
false.

Evaluating the arithmetic expressions

Having a way to evaluate the expression is useful so we can verify the result of the operation. A simple way to implement it looks like this:

eval(op(Op,X,Y),Result) :-
     eval(X,R1),eval(Y,R2),
     ( (Op = '+',  Result is (R1 + R2))
     ; (Op = '-', Result is (R1 - R2))
     ; (Op = '*', Result is (R1 * R2))
     ; (Op = '/', Result is (R1 / R2))), !.
eval(X, X).

With this predicate we can get the result of an operation. For example:

?- eval(op('+', op('*', 34, 23), 34), R).
R = 816.

Solving the problem

With these two predicates we can solve the problem like this:

?- arith_op([ 14, '*', 3,'-', 8, '/', 2 ]  ,Operation), eval(Operation, 17).
Operation = op(/, op(-, op(*, 14, 3), 8), 2) ;
false.

Now it is useful to present the results using infix notation with parenthesis. To do this we can write the following predicate:

forprint(op(Op,X,Y)) :-
    writef("("),
    forprint(X),
    writef(Op),
        forprint(Y),
    writef(")"),!.
forprint(X) :-
    write(X),!.

Now we can write:

arith_op([ 14, '*', 3,'-', 8, '/', 2 ]  ,Operation), eval(Operation, 17), forprint(Operation).
(((14*3)-8)/2)
Operation = op(/, op(-, op(*, 14, 3), 8), 2) ;
false.

I can also use this predicate to generate samples of results for other groupings. For example:

?- arith_op([ 14, '*', 3,'-', 8, '/', 2 ]  ,Operation), eval(Operation, Result), Result > 0, forprint(Operation).
((14*3)-(8/2))
Operation = op(-, op(*, 14, 3), op(/, 8, 2)),
Result = 38 ;
(((14*3)-8)/2)
Operation = op(/, op(-, op(*, 14, 3), 8), 2),
Result = 17 ;
false.