Saturday, 18 April 2015

Cheryl's birthday in Prolog

Cheryl's Birthday - The Math Question That Went Viral
"One word problem from a Singaporean school exam briefly became the talk of the Internet last weekend."
http://www.theatlantic.com/education/archive/2015/04/the-math-question-that-went-viral/390411/
https://groups.google.com/d/msg/comp.lang.prolog/G6yuaIsI-Cs/SVOlumZUiQoJ

I have put together two solutions in Prolog (in SWI-Prolog, last updated 2015-04-20T19:40:00+01:00), the source code can be downloaded here: http://julio.diegidio.name/Share/CherylsBirthdays.zip

The first solution (cheryls-birthday.aggr.pl) uses lists and aggregates:
?- problem(cbdate, BDate).
% 563 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
BDate = [7, 16].

?- time((between(1,1000,_),p_cbdate_input(CBDates),p_cbdate(CBDates, BDate),fail;true)).
% 563,001 inferences, 0.218 CPU in 0.220 seconds (99% CPU, 2577827 Lips)
true.
The second solution (cheryls-birthday.lists.pl) uses lists:
?- problem(cbdate, BDate).
% 5,163 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
BDate = [7, 16].

?- time((between(1,1000,_),p_cbdate_input(CBDates),p_cbdate(CBDates, BDate),fail;true)).
% 5,164,001 inferences, 1.513 CPU in 1.520 seconds (100% CPU, 3412614 Lips)
true.
The first solution, i.e. the implementation leveraging aggregates, turns out to be significantly faster...