Prolog

Posted by Daniel Lyons on August 11, 2008

There’s a wanker who keeps popping up on my blog and commanding me to do the I/O part of my Prolog programs. Coincidentally, Justin Dressel just popped up and asked me to solve a problem with him, he’s talking about doing it in Haskell while his girlfriend Darcey does it in Java (can you believe it?)

Have you played the game where you’re given 4 numbers, 

        and you have to form the number 10 out of them via any 

        combination of +, -, *, or /?

        

        e.g. 1, 2, 3, 4 → (4*2)+(3-1)

Boy, does that sound like a Prolog program or what?

First let’s handle one term.

% solve two terms for a third
        solve2(X, Y, Z, Op) :- Z is X + Y, Op = '+'.
        solve2(X, Y, Z, Op) :- Z is X - Y, Op = '-'.
        solve2(X, Y, Z, Op) :- Z is X * Y, Op = '*'.
        solve2(X, Y, Z, Op) :- Z is X / Y, Op = '/'.

If I use it, I get this kind of thing back:

?- solve2(4, 2, 6, Op).
        Op = + ;
        fail.
        
        ?- solve2(4, 2, 8, Op).
        Op = * ;
        fail.

Great. Now let’s get the whole enchilada:

% solve four terms for three operators, given a certain result
        solve4(A, B, C, D, Result, Op1, Op2, Op3) :-
        	solve2(A, B, X1, Op1),
        	solve2(X1, C, X2, Op2),
        	solve2(X2, D, Result, Op3).

All I’ve done here is created some variables X1 and X2 which are just placeholders for intermediate values. I don’t do anything with their value other than stitch together Prolog’s calculations with them. I keep all of the operators and pass them out. The result is passed in, that’s our constraint. For example, we can try this on our original problem statement:

?- solve4(1,2,3,4,10,Op1,Op2,Op3).
        Op1 = +,
        Op2 = +,
        Op3 = + ;
        Op1 = *,
        Op2 = *,
        Op3 = + ;
        fail.

So, Prolog is telling us we can get the result we want by doing ((1 + 2) + 3) + 4 or ((1 * 2) * 3) + 4.

Obviously, this isn’t all of the answers, nor is it particularly readable. I don’t want to have to worry about other operator groupings (which would be hard) when I can just reorder the input. And, to appease tndalpaul@yahoo.com, let’s do some I/O.

% solve([A, B, C, D], E), outputs the result
        solve(Four, Result) :-
        	permutation(Four, [A,B,C,D]),
        	solve4(A, B, C, D, Result, Op1, Op2, Op3),
        	
        	% I/O
        	write('(('), write(A), write(' '), write(Op1), write(' '), write(B), write(') '), 
        	write(Op2), write(' '), write(C), write(') '), write(Op3), write(' '), 
        	write(D), write(' = '), write(Result), nl,
        	 
        	% try the next one
        	fail.
        solve(Four, Result) :- true.

I’m using a peculiarly Prolog style of looping here, called failure-driven iteration. The top of solve/2 gets a list permutation and a solution, then it does an action that produces a side-effect: it prints out the state of the world. Then, I fail explicitly. Without a cut, Prolog backs up to the last choice-point and tries again. solve4/8 has several choice points, because there are many solutions, so it produces the next one if it can, or else it fails. If it produces another result, we go back through the I/O and then fail again. This will repeat until solve4/8 has no more solutions with this set of input. Then Prolog will back up to permutation and get another list permutation and resume the computation.

When all the permutations and all of the solutions have been enumerated and we fail that last time, Prolog backs up and searches for another solution to solve/2. There is one, which is just true, but because it is the second predicate, it only occurs after the first one. This terminates the loop.

The I/O which I’m complaining about is the giant pile of write() calls there. In Ruby, this would look like this:

puts "((#{A} #{Op1} #{B}) #{Op2} #{C}) #{Op3} #{D}"

Compare: one line with one template-looking string to three lines of horrid Prolog. Is there a better way? If so, please leave it in the comments.

So, finally, this is the output:

?- solve([1,2,3,4],10).
        ((1 + 2) + 3) + 4 = 10
        ((1 * 2) * 3) + 4 = 10
        ((2 + 1) + 3) + 4 = 10
        ((2 * 1) * 3) + 4 = 10
        ((2 / 1) * 3) + 4 = 10
        ((2 + 3) + 1) + 4 = 10
        ((2 * 3) * 1) + 4 = 10
        ((2 * 3) / 1) + 4 = 10
        ((2 + 3) + 4) + 1 = 10
        ((2 * 3) + 4) * 1 = 10
        ((2 * 3) + 4) / 1 = 10
        ((1 + 3) + 2) + 4 = 10
        ((1 * 3) * 2) + 4 = 10
        ((3 + 1) + 2) + 4 = 10
        ((3 * 1) * 2) + 4 = 10
        ((3 / 1) * 2) + 4 = 10
        ((3 + 2) + 1) + 4 = 10
        ((3 * 2) * 1) + 4 = 10
        ((3 * 2) / 1) + 4 = 10
        ((3 + 2) + 4) + 1 = 10
        ((3 * 2) + 4) * 1 = 10
        ((3 * 2) + 4) / 1 = 10
        ((1 + 3) + 4) + 2 = 10
        ((1 * 3) * 4) - 2 = 10
        ((3 + 1) + 4) + 2 = 10
        ((3 - 1) * 4) + 2 = 10
        ((3 * 1) * 4) - 2 = 10
        ((3 / 1) * 4) - 2 = 10
        ((3 + 4) + 1) + 2 = 10
        ((3 * 4) * 1) - 2 = 10
        ((3 * 4) / 1) - 2 = 10
        ((3 + 4) + 2) + 1 = 10
        ((3 * 4) - 2) * 1 = 10
        ((3 * 4) - 2) / 1 = 10
        ((1 + 2) + 4) + 3 = 10
        ((2 + 1) + 4) + 3 = 10
        ((2 + 4) + 1) + 3 = 10
        ((2 * 4) - 1) + 3 = 10
        ((2 + 4) + 3) + 1 = 10
        ((2 * 4) + 3) - 1 = 10
        ((1 + 4) + 2) + 3 = 10
        ((4 + 1) + 2) + 3 = 10
        ((4 + 2) + 1) + 3 = 10
        ((4 * 2) - 1) + 3 = 10
        ((4 + 2) + 3) + 1 = 10
        ((4 * 2) + 3) - 1 = 10
        ((1 + 4) + 3) + 2 = 10
        ((1 * 4) * 3) - 2 = 10
        ((4 + 1) + 3) + 2 = 10
        ((4 * 1) * 3) - 2 = 10
        ((4 / 1) * 3) - 2 = 10
        ((4 + 3) + 1) + 2 = 10
        ((4 * 3) * 1) - 2 = 10
        ((4 * 3) / 1) - 2 = 10
        ((4 + 3) + 2) + 1 = 10
        ((4 * 3) - 2) * 1 = 10
        ((4 * 3) - 2) / 1 = 10
        true.

Edit: Here are a few exercises for intrepid readers:

  1. Show that there are answers my program does not produce, and modify my program to produce them.
  2. Modify my program to not produce only unique answers.