Re: The Math Question That Went Viral

[Julio Di Egidio]

[Follow-up set to sci.math, comp.lang.prolog.]

"The_Inquirer" <always@ask_.questions> wrote in message
news:mgp17g$lrt$1...@dont-email.me...
> On 17/4/2015 1:19 AM, Dr. Jai Maharaj wrote:
>> The Math Question That Went Viral
>
> can you look at this solution
>
> http://genuinesingaporemaths.blogspot.sg/2015/04/pri520150412bdp-guessing-cheryls.html
>
> and see whether it is correct or corrwrong?

Nice puzzle, I have resolved it in Prolog, same answer:

<http://seprogrammo.blogspot.co.uk/2015/04/cheryls-birthday.html>

Julio

[Dr. Jai Maharaj]

Compilation of this thread so far:

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: Dr. Jai Maharaj:
[ Subject: The Math Question That Went Viral
[ Newsgroups: soc.culture.indian,alt.fan.jai-maharaj,sci.math,alt.philosophy,
[ soc.culture.usa,soc.culture.singapore,alt.politics,talk.politics.misc,soc.culture.india
[ Date: Thu, 16 Apr 2015 17:19:19 UTC
[ Message-Id: <20150416Po6MaBe96v@HoBF>

The Math Question That Went Viral

April 14, 2015

[...]

Albert and Bernard just became friends with Cheryl, and
they want to know when her birthday is. Cheryl marks 10
possible dates: May 15, May 16, May 19, June 17, June 18,
July 14, July 16, August 14, August 15, or August 17.

Then Cheryl tells Albert the month of her birthday, but
not the day. She tells Bernard the day of her birthday,
but not the month. Then she asked if they can figure it
out.

Albert: I don't know when Cheryl's birthday is, but I
know Bernard doesn't know either.

Bernard: At first I didn't know when Cheryl's birthday
is, but now I know.

Albert: If you know, then I know too!

When is Cheryl's birthday?

[...]

http://www.theatlantic.com/education/archive/2015/04/the-math-question-that-went-viral/390411/

Jai Maharaj, Jyotishi
Om Shanti

http://groups.google.com/group/alt.fan.jai-maharaj

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: The_Inquirer <always@ask_.questions>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: soc.culture.indian,alt.fan.jai-maharaj,sci.math,alt.philosophy,soc.culture.usa
[ Date: Fri, 17 Apr 2015 03:07:19 +0800
[ Message-ID: <mgp17g$lrt$1...@dont-email.me>

On 17/4/2015 1:19 AM, Dr. Jai Maharaj wrote:
> The Math Question That Went Viral
>

can you look at this solution

http://genuinesingaporemaths.blogspot.sg/2015/04/pri520150412bdp-guessing-cheryls.html

and see whether it is correct or corrwrong?

= = = = = = = = = = = = = = = = = = = = = =

[ From: "Julio Di Egidio" <ju...@diegidio.name>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: sci.math,alt.philosophy,comp.lang.prolog
[ Date: Sat, 18 Apr 2015 11:22:37 +0100
[ Message-ID: <mgtbdp$15c$1...@dont-email.me>

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: Wally W. <ww8...@aim.com>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: soc.culture.indian,alt.fan.jai-maharaj,sci.math,alt.philosophy,soc.culture.usa
[ Date: Sat, 18 Apr 2015 09:34:37 -0400
[ Message-ID: <o5n4jatj8klqs485r...@4ax.com>

On Fri, 17 Apr 2015 03:07:19 +0800, The_Inquirer wrote:

>On 17/4/2015 1:19 AM, Dr. Jai Maharaj wrote:
>> The Math Question That Went Viral
>>
>
>can you look at this solution
>
>http://genuinesingaporemaths.blogspot.sg/2015/04/pri520150412bdp-guessing-cheryls.html
>
>and see whether it is correct or corrwrong?

Too convoluted.

I agree with the answer here:
http://en.wikipedia.org/wiki/Cheryl's_Birthday#Disputed_solution
"Alternative Answer (It should be the answer)"

Done in three steps.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: "Julio Di Egidio" <ju...@diegidio.name>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: sci.math,alt.philosophy
[ Date: Sat, 18 Apr 2015 15:04:29 +0100
[ Message-ID: <mgtodo$em6$1...@dont-email.me>

[Follow-up set to sci.math.]

"Wally W." <ww8...@aim.com> wrote in message
news:o5n4jatj8klqs485r...@4ax.com...

> On Fri, 17 Apr 2015 03:07:19 +0800, The_Inquirer wrote:
>>On 17/4/2015 1:19 AM, Dr. Jai Maharaj wrote:
>>> The Math Question That Went Viral
>>
>>can you look at this solution
>>
>>http://genuinesingaporemaths.blogspot.sg/2015/04/pri520150412bdp-guessing-cheryls.html
>>
>>and see whether it is correct or corrwrong?
>

> Too convoluted.
>
> I agree with the answer here:
> http://en.wikipedia.org/wiki/Cheryl's_Birthday#Disputed_solution
> "Alternative Answer (It should be the answer)"
>
> Done in three steps.

Wrong at step 1 already. Indeed, overall, that Wikipedia article is just
terrible: the problem is perfectly well defined, rather the article's
proposed analysis is not even wrong...

Julio

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: Wally W. <ww8...@aim.com>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: sci.math
[ Date: Sat, 18 Apr 2015 10:36:00 -0400
[ Message-ID: <fbq4jah8ffp5cc3ju...@4ax.com>

On Sat, 18 Apr 2015 15:04:29 +0100, Julio Di Egidio wrote:

>[Follow-up set to sci.math.]
>
>"Wally W." <ww8...@aim.com> wrote in message
>news:o5n4jatj8klqs485r...@4ax.com...

>> On Fri, 17 Apr 2015 03:07:19 +0800, The_Inquirer wrote:
>>>On 17/4/2015 1:19 AM, Dr. Jai Maharaj wrote:
>>>> The Math Question That Went Viral
>>>
>>>can you look at this solution
>>>
>>>http://genuinesingaporemaths.blogspot.sg/2015/04/pri520150412bdp-guessing-cheryls.html
>>>
>>>and see whether it is correct or corrwrong?
>>

>> Too convoluted.
>>
>> I agree with the answer here:
>> http://en.wikipedia.org/wiki/Cheryl's_Birthday#Disputed_solution
>> "Alternative Answer (It should be the answer)"
>>
>> Done in three steps.
>
>Wrong at step 1 already. Indeed, overall, that Wikipedia article is just
>terrible: the problem is perfectly well defined, rather the article's
>proposed analysis is not even wrong...
>
>Julio

No justification is given for the assertion that the most
straightforward path to the solution is "not even wrong."

The first step is the same as in the link provided by The_Inquirer.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[ From: John Gabriel <thenewc...@gmail.com>
[ Subject: Re: The Math Question That Went Viral
[ Newsgroups: sci.math
[ Date: Fri, 17 Apr 2015 00:05:56 -0700 (PDT)
[ Message-ID: <23f3caa0-6d98-4512...@googlegroups.com>

On Thursday, 16 April 2015 19:19:25 UTC+2, Dr. Jai Maharaj wrote:
> The Math Question That Went Viral
>

> April 14, 2015
>
> [...]
>
> Albert and Bernard just became friends with Cheryl, and
> they want to know when her birthday is. Cheryl marks 10
> possible dates: May 15, May 16, May 19, June 17, June 18,
> July 14, July 16, August 14, August 15, or August 17.
>
> Then Cheryl tells Albert the month of her birthday, but
> not the day. She tells Bernard the day of her birthday,
> but not the month. Then she asked if they can figure it
> out.
>
> Albert: I don't know when Cheryl's birthday is, but I
> know Bernard doesn't know either.
>
> Bernard: At first I didn't know when Cheryl's birthday
> is, but now I know.
>
> Albert: If you know, then I know too!
>
> When is Cheryl's birthday?
>
> [...]
>
> http://www.theatlantic.com/education/archive/2015/04/the-math-question-that-went-viral/390411/
>
> Jai Maharaj, Jyotishi
> Om Shanti
>
> http://groups.google.com/group/alt.fan.jai-maharaj

Mental masturbation. The question makes a lot of assumptions.

The dialog between Albert and Bernard doesn't give many clues.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

End of the compilation.

Jai Maharaj, Jyotishi
Om Shanti

http:s//groups.google.com/group/alt.fan.jai-maharaj

[j4n bur53]

Thank you for sharing.

Runs also in Jekejeke Prolog 1.0.5. Replace the imports by:

:- use_module(library(basic/lists)).
:- use_module(library(advanced/aggregate)).

The add to the Prolog text the following helpers:

% atomic_list_concat(+List, +Atom, -Atom)
atomic_list_concat([X,Y|Z], S, T) :-
atomic_list_concat([Y|Z], S, H),
atom_concat(S, H, J),
atom_concat(X, J, T).
atomic_list_concat([X], _, X).

% aggregate(+Aggregate, +Template, +Goal, -Value)
aggregate(count, T, G, R) :-
aggregate(nodup(T), G, L),
length(L, R).

% memberchk(+Elem, +List)
memberchk(X, L) :-
member(X, L), !.

The result is then (warm run):

?- problem(cbdate, BDate).
Uptime 6 Millis
GC Time 0 Millis
Thread Cpu Time 0 Millis
BDate = [7,16]




Julio Di Egidio schrieb:

[Julio Di Egidio]

[Follow-up set to comp.lang.prolog.]

"Julio Di Egidio" <ju...@diegidio.name> wrote in message
news:mgtbdp$15c$1...@dont-email.me...
<snip>

> Nice puzzle, I have resolved it in Prolog, same answer:
>
> <http://seprogrammo.blogspot.co.uk/2015/04/cheryls-birthday.html>

At that link, I have now put together two solutions (in SWI-Prolog).

The first solution (cheryls-birthday.aggr.pl) uses 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 second solution, not using aggregates, is maybe more readable, but the
first solution, based on aggregates, turns out to be significantly faster...

Julio

[j4n bur53]

Julio Di Egidio schrieb:

> ?- 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 fewer number of inferences the faster the solution.
Here is a solution with ca. 3200 inferences:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.35)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

?- time(birthday(X,Y)).
% 521 inferences, 0.000 CPU in 0.000 seconds
(?% CPU, Infinite Lips)
X = 'July',
Y = 16 ;
% 2,678 inferences, 0.000 CPU in 0.000 seconds
(?% CPU, Infinite Lips)
false.

?- time((between(1,1000,_),birthday(X,Y),fail;true)).
% 3,195,002 inferences, 0.359 CPU in 0.348 seconds
(103% CPU, 8904631 Lips)
true.

Code is here:
http://gist.github.com/jburse/5063984b219d912d5551

Maybe reintroducing the findall, as it was found
in John Feminella original solution, migt make
it faster again.

But could remove some unneeded range restrictions, which
were the day/1 and month/1 predicates in John Fletchers
solutions.

[j4n bur53]

j4n bur53 schrieb:

>
> The fewer number of inferences the faster the solution.
> Here is a solution with ca. 3200 inferences:

Bringing it down to even 2,181 inferences.

[j4n bur53]

j4n bur53 schrieb:

More goal reordering, 713 inferences.

[Julio Di Egidio]

"j4n bur53" <janb...@fastmail.fm> wrote in message
news:mh40po$2sp$1...@news.albasani.net...
<snip>

> The fewer number of inferences the faster the solution.

No, the number of inferences does not tell you how long calling any native
predicate has taken.

> Here is a solution with ca. 3200 inferences:

<snip>

> Code is here:
> http://gist.github.com/jburse/5063984b219d912d5551

Case in point, your latest code (**) now takes 713 inferences (as you say),
which is still more than the 563 inferences taken by my code based on
aggregates (***), yet it is already around twice as fast.

Anyway, your latest code I would think is the nearest to optimal and quite
Prolog-ish code (although at some point I'd like also to investigate what
CLP can do here). Yet your code, as John Feminella's original one (*), is
still not deterministic (which is properly a "bug" here, plus fixing it
would slightly increase the complexity of the program). Also, I'm thinking
there is still some room for improvement in your code, but at the same time
the structure of the problem statement shall not be lost...

So, I will see if I can take your code further: I will anyway rewrite it, at
least to fix the determinism and for uniformity with my previous solutions,
in order to properly benchmark. -- I might also use GitHubGist myself,
that is a good idea...

(*) <https://github.com/fj/cheryls-birthday-prolog/blob/master/cheryl.pl>
(**) <http://gist.github.com/jburse/5063984b219d912d5551>
(***) <http://julio.diegidio.name/Share/CherylsBirthdays.zip>

Julio

[j4n bur53]

Julio Di Egidio schrieb:

> Case in point, your latest code (**) now takes 713 inferences (as you
> say), which is still more than the 563 inferences taken by my code based
> on aggregates (***), yet it is already around twice as fast.

Oh, yeah, I didn't see the 563, was thing it was something 5630.
Oki, Doki. Cool.

> Anyway, your latest code I would think is the nearest to optimal and
> quite Prolog-ish code (although at some point I'd like also to
> investigate what CLP can do here).

Probably for CLP, I guess we would need to fully rethink the problem.
Something along a boolean variable for each possible birthdate,
or some such.

Bye

[j4n bur53]

j4n bur53 schrieb:

> % aggregate(+Aggregate, +Template, +Goal, -Value)
> aggregate(count, T, G, R) :-
> aggregate(nodup(T), G, L),
> length(L, R).

Julio Di Egidio wrote:
> No, the number of inferences does not tell you how long
> calling any native predicate has taken.

Yes

I am currently experimenting with bootstrapping
aggregate/4 as follows:

aggregate(A, T, G, R) :-
setof(T, G, L),
aggregate_all(A, member(T, L), R).

The predicate setof/3 can itself be bootstrapped from
bagof/3 as follows:

setof(T, G, L) :-
bagof(T, G, H),
sort(H, L).

The predicate which wouldn't get some inference counting
here is the predicate sort/2, since it is natively
implemented. For example in SWI-Prolog one sees:

?- time(sort([3,1,2],X)).
% 1 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = [1, 2, 3].

?- time(sort([3,1,2,5,7,4],X)).
% 1 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
X = [1, 2, 3, 4, 5, 7].

But SWI-Prolog uses a differnt aggregate/4 bootstrapping.
But something along these lines could be the reason.

Possibly you get also smaller inference counts between
warm and cold run in SWI-Prolog. I don't know exactly
why this is happening. But I see:

?- time(aggregate(count,X,member(X,[3,1,2]),R)).
% 99 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
R = 3.

?- time(aggregate(count,X,member(X,[3,1,2]),R)).
% 36 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
R = 3.

Maybe some effect of the just in time indexing, although
I believe this shouldn't happen. Or its meant to give
an account of the effort of just in time indexing.

Who knows?

Bye