Category: Technology

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

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.

IBM’s Watson supercomputer tackles the problem of creativity in cooking

IBM’s supercomputer research team has been pushing the boundaries of what computers are capable of. Their Deep Blue first beat Kasparov at chess almost 20 years ago. Later, IBM’s Watson beat Ken Jennings at Jeopardy. And now the same Watson is tackling the most difficult problem yet – cooking and creativity.

IBM Research has begun work on an unnamed cyberchef, an AI system designed to create new dishes that can delight our palates at their theoretical peaks of enjoyment.

Why bother teaching a computer how to cook? Of course, the first reason is that it advances computer science. But there is another interesting angle. The supercomputer could cook up recipes that have never been seen by man, because there are some things that computer are just better than humans at:

For example:

In the case of the flavorbot, these “new things” IBM is after range from spotting underrated, highly flavorful ingredients (like black tea, bantu beer and cooked apples), strange-but-tasty flavor pairings (like white chocolate and caviar, jamaican rum and blue cheese, or even bell pepper and black tea), and even whole recipes, complete with basic preparation steps.

And how does Watson do this? Unsurprisingly, this is rather difficult. More interestingly, lots of science and maths comes into play here.

This is a high level description of what the AI needs to do:

To generate these food leads, if you will, AI cross references three databases of information:

  • A recipe index containing tens of thousands of existing dishes that allows the system to infer basics like “what makes a quiche a quiche”
  • Hedonic psychophysics, which is essentially a quantification of whether people like certain flavor compounds at the molecular level
  • Chemoinformatics, which sort of marries these two other databases, as it connects molecular flavor compounds to actual foods they’re in

And here is a journalist’s article about the results; he was sent a bottle of Watson’s Bengali Butternut Barbeque Sauce and this is what he found:

When I unwrapped the brightly colored box and found the bottle inside, I immediately flipped to the back label. Most BBQ sauces start with ingredients like vinegar, tomatoes, or even water, but IBM’s stands out from the get go. Ingredient one: White wine. Ingredient two: Butternut squash.

The list contains more Eastern influences, such as rice vinegar, dates, cilantro, tamarind (a sour fruit you may know best from Pad Thai), cardamom (a floral seed integral to South Asian cuisine) and turmeric (the yellow powder that stained the skull-laden sets of True Detective) alongside American BBQ sauce mainstays molasses, garlic, and mustard.

I pour a bit of the bottle onto a plate of roasted tofu and broccoli–even a pork lover has gotta watch his cholesterol–and tentatively took a bite. Watson’s golden sauce may have the pulpy consistency of baby food, but it packs a surprising amount of unique flavor.

Immediately, you can taste the sweet warmth of the wine and the squash. The tamarind blends seamlessly, backed by a duo of vinegars, to tickle your tongue with just the right amount of tartness. The other flavors combine to leave an indefinable, warm aftertaste that, as you have a few more bites, actually heats your mouth–thanks to Thai chiles

This resulted in a reddit discussion, and one of the people working on this project showed up to share details of how exactly it works:

In a nutshell, however, Watson consumes massive amounts of recipes from different sources and then parses out the ingredients and steps. It also takes in information about the basic flavor compounds in ingredients, the general nature of ingredients, and, perhaps most interesting, a database of the “pleasantness” of flavor compounds, and a few other things that really make up Watson’s “secret sauce”.

From there it’s a collaborative creative process between chef and watson. It typically starts with an ingredient. Let’s say “cardamom”. Watson then searches the database, which is a pretty straight forward process, for the types of cuisine that have that ingredient. For cardamom there are about 100 different cuisines from Indian to Swedish to Bhutani and Barbadian that have a recipe somewhere that uses cardamom. Next it searches through the recipe database to pick out recipes that have cardamom in it. Cardamom is most often found in soups and cake, but it also can be found in things like fudge, baklava, and kebabs.

In the next step Watson starts to create a template of what it thinks might go in Swedish/Barbadian fudge with cardamom. Here’s where you can go crazy with Watson. The most common elements are automatically selected, but there’s lots of other options. For example, most fudge has a sweetener, chocolate, dairy, oil, and some nuts. Because we wanted cardamom, Watson recommends some spices too. You can go crazy and add in things like meat, alcohol, cheese, and a variety of other things at this step. You can’t just add in anything you want because there are some things that Watson has a hunch will just turn out to be nasty.

In the final step Watson generates a number of recipes that meet the guidelines provided. It tries to ensure that the ingredients selected match up with the various cuisines and also with the dish selected. In addition, using some of the “secret sauce” it makes sure that the ingredients will taste good together too. At the end it presents a number of recipes rated on scales such as “surprise”, or how rare is recipe like this compared to the database, “pairing”, or how well do the flavors pair or contrast with each other, and “pleasantness” which is based on the science of hedonic psychophysics. From there the chef works with Watson to find the best recipe.

That final paragraph sounds so cool. You randomly suggest a bunch of ingredients to a supercomputer and it comes up with interesting recipes based around your rough guidelines, while all the time preventing you from totally screwing up and ensuring that the resultant dish will taste good. (But, this is also reminding me of Arthur in the Hitchhiker’s Guide to the Galaxy and his struggles to get Eddie, the shipboard computer, to make him some tea.

References: