Learning Prolog: Semester 2 Lab 12

You may have noticed that I've skipped a week in this series. Don't panic - I've done it on purpose. The task for lab 11 felt very close to the assessed coursework (ACW) for the Artificial Intelligence module that I'm learning Prolog in. I've decided to play it safe and hold off on posting about it for now. I might post later - it all depends on what the ACW is.

Anyway, the main task for this lab was to finish the work we started last week, but there was an additional challenge, too. It was based on the following challenge:

SEND + MORE = MONEY

Each letter stands for a digit, and the idea is to write a Prolog program that work out what each of the letters stands for. This problem is actually quite simple, and the particular way that you'd go about solving this has a special name.

In the beginning, I only knew one way to writing programs: Functional programming. Next, University introduced me to the wonderful world of Object Oriented Programming. In my second year, my AI module has been bending my mind with Symbolic Programming. Now, I have learnt of a fourth programming paradigm - Constraint based programming.

The solution for the above was provided (and explained!) in the lecture slides for this week:

% From http://clip.dia.fi.upm.es/~vocal/public_info/seminar_notes/node13.html
smm :-
    % Let X be the set of variables which I am going to assign
    X = [S,E,N,D,M,O,R,Y],
    % ...and Digits is the unique set of digits to assign
    Digits = [0,1,2,3,4,5,6,7,8,9], /* assign recursively goes through the letter variables and assigns them a digit */        
    assign_digits(X, Digits),        
    M > 0,        S > 0,    
    % multiply to corresponding 10 to the n
    1000*S + 100*E + 10*N + D + 
    1000*M + 100*O + 10*R + E    =:=        
    10000*M + 1000*O + 100*N + 10*E + Y, 
    /*
    This is then the constraint in raw Prolog. =:= checks for equality in the expression.
    */
    write(X).

myselect(X, [X|R], R). % Assign to first and hand back the rest
myselect(X, [Y|Xs], [Y|Ys]):- myselect(X, Xs, Ys). /* ...otherwise on backtracking free up the old binding Y and go get another value of X from the other Xs */

assign_digits([], _List).
assign_digits([D|Ds], List):-
    myselect(D, List, NewList),
    assign_digits(Ds, NewList).

This code works by creating an array of unknowns, an array of digit values that the array of variables can take, and then assigning each of the variables a value one by one. The expression on lines 10-12 is then tested, and if it doesn't match (which it probably won't), Prolog backtracks and tries to reassign one of the variables it assigned before. It repeats this process until it finds the solution.

Brute force isn't very efficient or clever, but it does the job quickly enough:

smm.
[9, 5, 6, 7, 1, 0, 8, 2].

Very nice. But that wasn't actually the challenge to for the lab. The real challenge was to adapt the above code in order to solve a slightly different puzzle:

DONALD + GERALD = ROBERT

Thankfully, all this new problem takes is a slight adjustment to the smm/1 rule that the above solution came with:

dgr :-
    % Let X be the set of variables which I am going to assign
    X = [D, O, N, A, L, G, E, R, B, T],
    % ...and Digits is the unique set of digits to assign
    Digits = [0,1,2,3,4,5,6,7,8,9],
    % Assign recursively goes through the letter variables and assigns them a digit       
    assign_digits(X, Digits),        
    D > 0,        G > 0,    
    % Multiply to corresponding  10 to the n
    100000*D + 10000*O + 1000*N + 100*A + 10*L + D + 
           100000*G + 10000*E + 1000*R + 100*A + 10*L + D    =:=        
    100000*R + 10000*O + 1000*B + 100*E + 10*R + T,
    /*
    This is then the constraint in raw Prolog. =:= checks for equality in the expression.
    */  
    write(X).

All I did was alter the unknown variables to match the new problem. Here's my result:

smm.
[5, 2, 6, 4, 8, 1, 9, 7, 3, 0].

This may well be the last post (Edit:) in this series until the end of the ACW. See you later!