Search code examples
prologcryptarithmetic-puzzle

Prolog Cryptarithmetic program

I'm taking a programming course and the professor just lightly skimmed over Prolog due to lack of time. Anyways, he suggested we research it on our own. I came across a Cryptarithmetic program that is supposed to calculate? AM+PM = DAY. I do not know what is supposed to be added as input in the SWI interpreter and what should be received as the correct output...If this makes any sense?

I tried...

solve([AM],[PM],[DAY]).

That does nothing. Any help on what the correct input would be for AM+PM = DAY or something similar would be great! Here is the program I was playing with...

solve([A,M,P,D,Y]):-
   select(A,[0,1,2,3,4,5,6,7,8,9],WA), % W means Without
   not(A=0),
   select(M,WA,WMA),
   select(P,WMA,WMAP),
   not(P=0),
   select(D,WMAP,WMAPD),
   not(D=0),
   select(Y,WMAPD,WMAPDY),
   DAY is 100*D+10*A+Y,
   AM  is 10*A+M,
   PM  is 10*P+M,
   DAY is AM+PM.

Please keep in mind that we only had two classes on Prolog so I know next to nothing!

Scott

Solution

  • Okay, this program will give a variable assignment for the formula

    DAY = AM + PM

    Where each of the characters is a digit from 0 to 9 no, digit may be used twice and A,P and D mustn't be 0 (no leading zeroes allowed).

    For beginners trying to understand prolog programs it might be more feasible to ask the question: "How is it (the program) true", instead of "what input generates which output". Prolog gladly supplies you with the variable settings it needed to make, to give you a true. (It also tracks on the way where it could have gone another way, so can ask again).

    The program uses pattern matching, but basically wants a list of five elements which represent the variables A, M,P,D and Y (in that order).

    select's arguments are:

    1. something (you can put in a list)
    2. a list that contains the first argument
    3. the list without the first argument.

    not tries to solve what it is given and fails if it succeeds.

    , is a short cirquiting and, like && in many C-like languages.

    The last four lines are simple arithmetics, while the lines above just ensure that you aren't selecting doubles and leading 0s.

    so after you have loaded your program, you can query for answers:

    ?- solve([A, M,P,D,Y]).
A = 2,
M = 5,
P = 9,
D = 1,
Y = 0

    If you want another solution, you can hit space or ;. If you want to know, if there is a solution with A = 5, you can query like this: 

    ?- A = 5, solve([A, M,P,D,Y]).
A = 5,
M = 6,
P = 9,
D = 1,
Y = 2

    If you want to "reassemble" it, this line might help:

    ?- solve([A, M,P,D,Y]), format('~w~w~w= ~w~w + ~w~w~n', [D,A,Y,A,M,P,M]).

    format is something like printf in many other languages.