## 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!

## Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro network networking nibriboard node.js operating systems own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems projects prolog protocol protocols pseudo 3d python reddit redis reference releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg talks technical terminal textures thoughts three thing game three.js tool tutorial twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 xmpp xslt

Art by Mythdael