Being a programmer means that every once in a while, instead of doing real work, you spend time writing a completely pointless program just for fun. Which is how I ended up writing a Prolog program to solve the Singapore Math Problem that has recently gone viral on the internet.
This is Amit Paranjape‘s fault. He asked me, “Isn’t solving this problem simply a question of creating sets of dates that satisfy the various conditions, and then intersecting them until you’re left with just one date? Wouldn’t it be easy to write a program to solve this program automatically?” And he went on to ask, “Isn’t there already some high level programming language where such set constraints can be described at a high level, and the program solves the problem for you?”
Turns out, there is. The Prolog programming language is a general purpose programming language that allows us to specify high level predicates that must be true of your data, and then it automatically figures out which pieces of data satisfy all your constraints. It’s a rather different kind of programming language.
So, I couldn’t resist. Like many other computer science graduates, I learnt a little about Prolog during my undergraduate studies, and then proceeded to never encounter it anywhere in my real life. But here was a problem that seemed like it would be fun to solve using Prolog. The fact that I actually don’t know Prolog isn’t something that I let bother me.
So, I spent a few hours downloading a Prolog compiler, learning the basics of the language, and solving the problem.
And, indeed, Prolog is a good language to solve the problem. The solution is below. If you don’t know anything about Prolog, you might still be able to make some sense of the program by doing the following: Any statement of the form “abc(x,y).” should be read as: the property abc is true for x and y. And any statement of the form “pqr(X) :- abc(X,Y), jkl(Y,Z).” should be read as: the property pqr is true for any X if abc is true for that X and some Y, and jkl is true for that Y and some Z. And the statements involving setof are simply trying to count the number of elements satisfying some property.
Here’s the solution:
% This is the original data that Cheryl gave birthday_candidate(may, 15). birthday_candidate(may, 16). birthday_candidate(may, 19). birthday_candidate(june, 17). birthday_candidate(june, 18). birthday_candidate(july, 14). birthday_candidate(july, 16). birthday_candidate(august, 14). birthday_candidate(august, 15). birthday_candidate(august, 17). % Now for some helper functions % Any list that has more than one % entry is ambiguous is_ambiguous(List) :- length(List, Len), Len>1. % Any list that has exactly one % entry is not ambiguous is_not_ambiguous(List) :- length(List, 1). % These will be true only for a % Month or Date in the original list candidate_month(Mon) :- birthday_candidate(Mon, _). candidate_date(Date) :- birthday_candidate(_, Date). % If you're given a month, and there % are multiple candidate dates % in that month, then you don't % have enough information to % deduce the birthday. % Same thing for dates. month_is_ambiguous(Mon) :- candidate_month(Mon), setof(D,birthday_candidate(Mon,D),L), is_ambiguous(L). date_is_ambiguous(Date) :- candidate_date(Date), setof(M,birthday_candidate(M, Date), L), is_ambiguous(L). % Albert's first deduction % The month that Albert has % been told is ambiguous, because he % couldn't figure out the birthday albert_month_is_ambiguous(Mon) :- candidate_month(Mon), month_is_ambiguous(Mon). % In addition, Albert knows that % Barnard doesn't know. % Meaning that each date that he can % deduce is ambiguous for Bernard albert_knows_bernard_doesnt_know(Mon) :- albert_month_is_ambiguous(Mon), forall(birthday_candidate(Mon,D), date_is_ambiguous(D)). % Bernard's first deduction % The date Bernard has been told is ambiguous, % did could not figure out the birthday. bernard_date_is_ambiguous(Date) :- candidate_date(Date), date_is_ambiguous(Date). % After hearing what Albert said, % Bernard's database is constrained by % the results of albert_knows_bernard_doesnt_know bernard_constrained(Mon,Date) :- bernard_date_is_ambiguous(Date), albert_knows_bernard_doesnt_know(Mon), birthday_candidate(Mon,Date). % But then, Bernard said that he % now knows the birthday; which means % that Month isn't ambiguous for him bernard_now_knows(Date) :- setof(M, bernard_constrained(M, Date), Mx), is_not_ambiguous(Mx). % Albert's second deduction % After hearing that Bernard now knows % the birthday, Albert's database is % constrained by the results of bernard_now_knows albert_constrained(Mon,Date) :- bernard_now_knows(Date), albert_knows_bernard_doesnt_know(Mon), birthday_candidate(Mon,Date). % And Albert said that he now knows. % Which means Month isn't ambiguous % for him albert_now_knows(Mon) :- setof(D, albert_constrained(Mon, D), Dx), is_not_ambiguous(Dx). % Final answer: take results of % albert_constrained and further constrain it % by the fact that albert_now_knows % and we get a single final answer. final_answer(Mon,Date) :- albert_constrained(Mon, Date), albert_now_knows(Mon).
Notes
- The answer is 16 July, in case you were wondering.
- Considering that this is probably the second Prolog program that I’ve ever written, I’m sure it is a terrible program. In fact there are lots of ways in which the program can be improved, but, I have real work to do. So this quick-n-dirty program will have to do.
- In fact, there exist theorem provers (like Coq) that are even more ideal for this job. But those are far too specialized, and I did not want to learn a theorem prover just to solve this problem.
- Which brings me to the question, why did I even bother doing this in Prolog? Considering that Prolog has not been, and will probably never be used in any serious programming work that I do, why bother? The more generalized version of this question is this: if there is a non-standard programming language (like Haskell, Lisp, Erlang, O’Caml) whose use in industry is uncommon, should you, as a serious programmer, with real work to be done and real deadlines, learn them in your free time? The motivated reader is encouraged to leave a comment below with the answer. Or, if you don’t know the answer and want my answer, please send me an email.
And, here’s a link to the original problem if you feel like solving it yourself. And here is another problem and yetanudder problem that require similar type of thinking to solve.