{"id":693,"date":"2015-04-15T19:06:08","date_gmt":"2015-04-15T13:36:08","guid":{"rendered":"http:\/\/smritiweb.com\/navin\/?p=693"},"modified":"2015-04-15T19:22:01","modified_gmt":"2015-04-15T13:52:01","slug":"which-programming-language-to-use-to-solve-the-singapore-math-problem","status":"publish","type":"post","link":"https:\/\/smritiweb.com\/navin\/technology\/which-programming-language-to-use-to-solve-the-singapore-math-problem","title":{"rendered":"Which Programming Language to use to solve the Singapore Math problem"},"content":{"rendered":"

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<\/a> that has recently gone viral on the internet.<\/p>\n

This is Amit Paranjape<\/a>‘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?”<\/p>\n

Turns out, there is. The Prolog programming language<\/a> 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.<\/p>\n

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.<\/p>\n

So, I spent a few hours downloading a Prolog compiler, learning the basics of the language, and solving the problem.<\/p>\n

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).<\/code>” should be read as: the property abc<\/code> is true for x<\/code> and y<\/code>.<\/em> And any statement of the form “pqr(X) :- abc(X,Y), jkl(Y,Z).<\/code>” should be read as: the property pqr<\/code> is true for any X<\/code> if abc<\/code> is true for that X<\/code> and some Y<\/code>, and jkl<\/code> is true for that Y<\/code> and some Z<\/code>.<\/em> And the statements involving setof<\/code> are simply trying to count the number of elements satisfying some property.<\/p>\n

Here’s the solution:<\/p>\n

\n
% This is the original data that Cheryl gave<\/span>\nbirthday_candidate<\/span>(may<\/span>, 15<\/span>).\nbirthday_candidate<\/span>(may<\/span>, 16<\/span>).\nbirthday_candidate<\/span>(may<\/span>, 19<\/span>).\nbirthday_candidate<\/span>(june<\/span>, 17<\/span>).\nbirthday_candidate<\/span>(june<\/span>, 18<\/span>).\nbirthday_candidate<\/span>(july<\/span>, 14<\/span>).\nbirthday_candidate<\/span>(july<\/span>, 16<\/span>).\nbirthday_candidate<\/span>(august<\/span>, 14<\/span>).\nbirthday_candidate<\/span>(august<\/span>, 15<\/span>).\nbirthday_candidate<\/span>(august<\/span>, 17<\/span>).\n\n% Now for some helper functions<\/span>\n% Any list that has more than one <\/span>\n% entry is ambiguous<\/span>\nis_ambiguous<\/span>(List<\/span>) :- \n    length<\/span>(List<\/span>, Len<\/span>), Len<\/span>>1<\/span>.\n% Any list that has exactly one <\/span>\n% entry is not ambiguous<\/span>\nis_not_ambiguous<\/span>(List<\/span>) :- \n    length<\/span>(List<\/span>, 1<\/span>).\n\n% These will be true only for a <\/span>\n% Month or Date in the original list<\/span>\ncandidate_month<\/span>(Mon<\/span>) :- \n    birthday_candidate<\/span>(Mon<\/span>, _<\/span>). \ncandidate_date<\/span>(Date<\/span>) :- \n    birthday_candidate<\/span>(_<\/span>, Date<\/span>).\n\n% If you're given a month, and there <\/span>\n% are multiple candidate dates <\/span>\n% in that month, then you don't <\/span>\n% have enough information to<\/span>\n% deduce the birthday.<\/span>\n% Same thing for dates.<\/span>\nmonth_is_ambiguous<\/span>(Mon<\/span>) :- \n    candidate_month<\/span>(Mon<\/span>), \n    setof<\/span>(D<\/span>,birthday_candidate<\/span>(Mon<\/span>,D<\/span>),L<\/span>), \n    is_ambiguous<\/span>(L<\/span>).\ndate_is_ambiguous<\/span>(Date<\/span>) :- \n    candidate_date<\/span>(Date<\/span>),\n    setof<\/span>(M<\/span>,birthday_candidate<\/span>(M<\/span>, Date<\/span>), L<\/span>),\n    is_ambiguous<\/span>(L<\/span>).\n\n\n% Albert's first deduction<\/span>\n% The month that Albert has <\/span>\n% been told is ambiguous, because he <\/span>\n% couldn't figure out the birthday<\/span>\nalbert_month_is_ambiguous<\/span>(Mon<\/span>) :- \n    candidate_month<\/span>(Mon<\/span>), \n    month_is_ambiguous<\/span>(Mon<\/span>).\n\n% In addition, Albert knows that <\/span>\n% Barnard doesn't know.<\/span>\n% Meaning that each date that he can <\/span>\n% deduce is ambiguous for Bernard<\/span>\nalbert_knows_bernard_doesnt_know<\/span>(Mon<\/span>) :- \n    albert_month_is_ambiguous<\/span>(Mon<\/span>), \n    forall<\/span>(birthday_candidate<\/span>(Mon<\/span>,D<\/span>),\n    date_is_ambiguous<\/span>(D<\/span>)).\n\n% Bernard's first deduction<\/span>\n\n% The date Bernard has been told is ambiguous,<\/span>\n% did could not figure out the birthday.<\/span>\nbernard_date_is_ambiguous<\/span>(Date<\/span>) :- \n    candidate_date<\/span>(Date<\/span>),\n    date_is_ambiguous<\/span>(Date<\/span>).\n\n% After hearing what Albert said, <\/span>\n% Bernard's database is constrained by <\/span>\n% the results of albert_knows_bernard_doesnt_know<\/span>\nbernard_constrained<\/span>(Mon<\/span>,Date<\/span>) :- \n    bernard_date_is_ambiguous<\/span>(Date<\/span>),\n    albert_knows_bernard_doesnt_know<\/span>(Mon<\/span>),\n    birthday_candidate<\/span>(Mon<\/span>,Date<\/span>).\n\n% But then, Bernard said that he <\/span>\n% now knows the birthday; which means <\/span>\n% that Month isn't ambiguous for him<\/span>\nbernard_now_knows<\/span>(Date<\/span>) :- \n    setof<\/span>(M<\/span>, bernard_constrained<\/span>(M<\/span>, Date<\/span>), Mx<\/span>),\n    is_not_ambiguous<\/span>(Mx<\/span>).\n\n% Albert's second deduction<\/span>\n\n% After hearing that Bernard now knows <\/span>\n% the birthday, Albert's database is <\/span>\n% constrained by the results of bernard_now_knows<\/span>\nalbert_constrained<\/span>(Mon<\/span>,Date<\/span>) :- \n    bernard_now_knows<\/span>(Date<\/span>),\n    albert_knows_bernard_doesnt_know<\/span>(Mon<\/span>),\n    birthday_candidate<\/span>(Mon<\/span>,Date<\/span>).\n\n% And Albert said that he now knows. <\/span>\n% Which means Month isn't ambiguous <\/span>\n% for him<\/span>\nalbert_now_knows<\/span>(Mon<\/span>) :- \n    setof<\/span>(D<\/span>, albert_constrained<\/span>(Mon<\/span>, D<\/span>), Dx<\/span>),\n    is_not_ambiguous<\/span>(Dx<\/span>).\n\n\n% Final answer: take results of <\/span>\n% albert_constrained and further constrain it <\/span>\n% by the fact that albert_now_knows<\/span>\n% and we get a single final answer.<\/span>\nfinal_answer<\/span>(Mon<\/span>,Date<\/span>) :- \n    albert_constrained<\/span>(Mon<\/span>, Date<\/span>),\n    albert_now_knows<\/span>(Mon<\/span>).\n<\/pre>\n<\/div>\n
<\/font><\/p>\n
Notes<\/h3>\n