26 April 2015

Cheryl's Birthday

blogdown: cheryl.md So for some reason, the entire internet (possibly an exaggeration) has latched onto this Cheryl's Birthday Problem. It's a logic puzzle where you can deduce the solution while knowing only a few facts about what other people in the puzzle know. I first stumbled across this Prolog solution which explains the problem quite nicely - and then found people had already started implementing their own solutions in e.g. Java, which made me decide to spend a lazy Monday afternoon hacking away on my own Perl 5 version.



I thought she calls herself Crystal now?

The problem is worded like this:-

Albert and Bernard have just met Cheryl. “When is your birthday?” Albert asked Cheryl. Cheryl thought for a moment and said, “I won’t tell you, but I’ll give you some clues”. She wrote down a list of ten dates:
  • May 15, May 16, May 19
  • June 17, June 18
  • July 14, July 16
  • August 14, August 15, August 17
“One of these is my birthday,” she said.
Cheryl whispered in Albert’s ear the month, and only the month, of her birthday. To Bernard, she whispered the day, and only the day. “Can you figure it out now?” she asked Albert.
  • Albert: “I don’t know when your birthday is, but I know Bernard doesn’t know, either.”
  • Bernard: “I didn’t know originally, but now I do.”
  • Albert: “Well, now I know, too!”
When is Cheryl’s birthday?

Working through this by hand, I initially got the wrong answer. The thing to remember about these puzzles is they're not just logic puzzles - they also exercise one's English skills, because you have to parse each statement of the puzzle and determine exactly what each is implying. In my humble opinion, that first statement by Albert could be better written as "I don't know when your birthday is, but I know Bernard cannot possibly know, either.". Because this tells us that part of Albert's knowledge implies that Bernard has an unsolvable problem - at least, in the first iteration of events.

Or was it Carol?

Let's get to the code. To set things up, we need to put in the selection of possible dates Cheryl first mentions. The easiest way to do this is to first make a list using Perl's "quote (words)" operator, qw//, and then split those up into little hashes of month and day.
my @DATES = qw/
      May_15 May_16 May_19
      June_17 June_18
      July_14 July_16
      August_14 August_15 August_17
   /;
@DATES = map { my ($m, $d) = split /_/; { month => $m, day => $d } } @DATES;
Unlike other solutions, I want to be a bit fancier about the output than just printing the solution. I want to see how each step of the process removes possible answers from the problem until only the solution is left. To do that, let's use a splash of Term::ANSIColor:-
sub coloured_date
{
   my ($date, @highlight) = @_;
   my $colour = 'red';
   $colour = 'green' if grep { $_->{month} eq $date->{month} && $_->{day} eq $date->{day} } @highlight;
   return colored("$date->{month} $date->{day}", $colour);
}
sub dates
{
   my (@highlight) = @_;
   return join(', ', map { coloured_date($_, @highlight) } @DATES);
}
We also need to declare a few 'predicates' to help us select answers more naturally. I prefer to choose excessively verbose names for these rather than things like 'Day()' and 'Month()' because readability is important when working through these complicated logic problems, not "amount of ink used". Also worth noting: These three subs all return the value of a call to Perl's grep. So they'll return a list of matching dates, if any - and when we need to test "does this predicate come up with a unique solution?", since it's Perl, all we need to do is test if it's == 1, because that will force scalar context and test the number of results instead of the results themselves. It's nice like that.
sub dates_sharing_this_day
{
   my ($candidate, @dates) = @_;
   return grep { $_->{day} eq $candidate->{day} } @dates;
}

sub dates_sharing_this_month
{
   my ($candidate, @dates) = @_;
   return grep { $_->{month} eq $candidate->{month} } @dates;
}

sub month_has_uniquely_determining_day
{
   my ($candidate, @dates) = @_;
   my @dates_with_unique_days = grep { dates_sharing_this_day($_, @dates) == 1 } @dates;
   return grep { $_->{month} eq $candidate->{month} } @dates_with_unique_days;
}
Okay, on to the actual working-through of the problem!
my @result = @DATES;
say "All dates Cheryl mentions:\n ", dates(@result);

say "\nAlbert doesn't immediately know; there are no unique months:\n ", dates(@result =
   grep { dates_sharing_this_month($_, @DATES) > 1 } @result);

say "Albert believes Bernard cannot possibly know:\n ", dates(@result =
   grep { dates_sharing_this_day($_, @DATES) > 1 } @result);

say "which implies that Albert has a month that wouldn't give Bernard a unique day:\n ", dates(@result =
   grep { ! month_has_uniquely_determining_day($_, @DATES) } @result);

say "\nBernard now says he knows the answer.\nSo given the remaining dates, he must have a day that uniquely determines the month:\n ", dates(@result =
   grep { dates_sharing_this_day($_, @result) == 1 } @result);

say "\nThis prompts Albert to say that he now also knows.\nSo given the remaining dates, he must have a month that uniquely determines the day:\n ", dates(@result =
   grep { dates_sharing_this_month($_, @result) == 1 } @result);
I'm not sure I can easily put the coloured output of the program here without taking a screenshot of text, which is kinda dumb... but hey, why don't you just run it yourself to find the answer? It only requires perl 5.10 for the 'say', really. You can see the full source on my bitbucket here: cheryl.pl

Edit: Aha! No, literally 'aha', a command-line tool I found to convert ANSI escapes to HTML.
All dates Cheryl mentions:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17

Albert doesn't immediately know; there are no unique months:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17
Albert believes Bernard cannot possibly know:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17
which implies that Albert has a month that wouldn't give Bernard a unique day:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17

Bernard now says he knows the answer.
So given the remaining dates, he must have a day that uniquely determines the month:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17

This prompts Albert to say that he now also knows.
So given the remaining dates, he must have a month that uniquely determines the day:
 May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17 



Also yes it's been a while since I posted anything, I had work, okay? More posts to come, probably maybe why not.

No comments:

Post a Comment