Which Programming Language to use to solve the Singapore Math problem

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) :- 
date_is_ambiguous(Date) :- 
    setof(M,birthday_candidate(M, Date), 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) :- 

% 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) :- 

% Bernard's first deduction

% The date Bernard has been told is ambiguous,
% did could not figure out the birthday.
bernard_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) :- 

% 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),

% 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) :- 

% 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),

% 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),


  • 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.

Interesting Data from Stack Overflow Developer Survey 2015

Stack Overflow has just released the results of their 2015 developer survey, in which 26000+ Stack Overflow users from 150+ countries responded to various questions regarding their programming habits.

Here are the items that I found most interesting/surprising:

  • Gender Gap: Only 5.6% of the respondents were female. This is even lower than I thought. Interestingly, 15.1% of the Indians were female, while only 4.8% of US respondents were female. So, does India have 3x the percentage of female developers?
  • 40+% of the respondents do not have a formal degree in computer science.
  • Programming Languages: If you disregard Javascript and SQL, then the top 5 languages are Java (37.4%), C# (31.6%), PHP (29.7%), Python (23.6%), and C++ (20.6%). Of these, all except Python have been declining if you look at the trends from 2013 to 2014 to 2015. Python increased slightly. Ruby comes in at a lowly #10 is declining.
  • Most Loved and Most Dreaded Languages: C++11 makes the list of “most loved” languages, coming in at an impressive #2 on the list. After listening to Stroustrup talk about the latest features in C++11 and C++14 a few months back, even I feel like checking it out. The “most dreaded” languages list is topped by “Salesforce” and contains other interesting entries like: WordPress, Perl, Matlab, and Coffeescript.
  • Editors: I am a part of the just 3.8% who use emacs. Vim has 15.2 percent. Of course, Notepad++ (34.7%), and Sublime Text (25.2%) top this category.
  • Version Control Systems: The “Which VCS to use?” question seems to be settled. 69.3% use git. The 36.9% use SVN are surely legacy, and will switch to git for their next project. And if you’re using any of the others, you are on the losing side. And if you are one of the 9.3% who don’t use VCS, please quit and change careers.
  • Tabs vs Spaces: Sadly, 45% of the developers are idiots who use tabs instead of spaces. However, there is hope because as developers gain experience, they start switching to spaces – people with 10000+ reputation points on Stack Overflow are 3 times more likely to prefer spaces.
  • Job Satisfaction: 76% of the respondents either love their job, or are at least satisfied by it. I wonder if this is indicative of the industry in general, or just the selection bias in the survey respondents.

Read the full report, it is interesting.

A delicious bookmarklet that works with noscript

This is technical, so unless you’re a do-it-yourself programming/javascript geek, you will not find it interesting.

I was trying to solve this problem:

  • I like to bookmark interesting links on my delicious.com account
  • I like to use NoScript with my firefox – this disables javascript/flash/ads/XSS and other things on a lot of sites, giving me a much more stable experience on various websites.

Unfortunately, both of these things don’t really go well together. NoScript blocks the delicious bookmarklet, and at this time there doesn’t seem to be a any easy way to get it to work as it is.

I tried adding https://delicious\.com/save to the Anti-XSS Protection Exceptions in NoScript preferences but that did not help.

Of course, I can always copy the URL of the site, go to delicious.com and then add the link manually, but that is too much effort. I do this often enough that I needed to automate the process.

After some trial-and-error I decided that the problem was the use of iframes in the delicious bookmarklet. So I wrote this much simplified delicious bookmarklet which works like a charm.

Here is the code for the bookmarklet:


Just add a bookmark to your Bookmarks Toolbar with “Add to Delicious” as the name and the above code as the location. Now on any website, click on “Add to Delicious” and you get redirected to a page that prompts you for the tags and will then add the delicious bookmark.

Note: if you want to automatically include the current selection as the note/description in the bookmark, use this code instead (I haven’t tested it, since I’m not interested in a note, but I think it should work):