opine.me

If you haven’t heard about the Cheryl Birthday Problem, it’s a cute little teaser and worth taking a look. Now I just saw this lovely post about how to Solve the Cheryl Birthday Problem with Prolog. I thought it might be neat to solve it in SQL!

The interesting thing about the problem is the peculiar way the problem is worded. I happen to like the wording quite a bit, and I think teasing out the meaning is most of the fun;

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?

Our first step is setting up the problem;

CREATE TABLE #Birthdays (Month int, Day int)
INSERT INTO #Birthdays VALUES (5, 15), (5, 16), (5, 19),
(6, 17), (6, 18), (7, 14), (7, 16), (8, 14), (8, 15), (8, 17)
-- (10 row(s) affected)

The trick is in reducing the dialog between Albert and Bernard into a process of elimination. Albert knows the month, and Bernard knows the day. Obviously Albert can’t possibly know the date, because every month has at least two potential dates when it could be Cheryl’s birthday. But there are two months with unique days, namely May 19 and June 18. If the answer was either of those, then Bernard would know off the bat. Therefore when Albert lets on that he knows that Bernard doesn’t know, that’s our first clue. Albert knows it’s a month where none of the possible days are unique. Or to flip the logic so we can do the test one step at a time, we will delete any Month which has a Day which is unique;

--I know Bernard doesn't know
--a.k.a Delete any months which have unique days
DELETE FROM #Birthdays
WHERE [Month] IN (SELECT MIN([Month]) FROM #Birthdays GROUP BY [Day] HAVING COUNT(1) = 1)
-- (5 row(s) affected)

The syntax of MIN([Month]) in the sub-query is something I’ve always seen as a failing of SQL. The COUNT(1)=1 means there can only ever possibly be a single record in each group. The query analyzer should know that, and let us directly access columns outside the aggregator without a warning in these cases. Or perhaps at least, provide an ONLY() hinting function to make the code easier to read! Anyway, back to the problem at hand…

The next clue is that Bernard tells us that now he knows the date. In other words, in the remaining set of dates, the day must be unique. Again, to flip the logic, we will delete any day which is not unique;

--Bernard didn't know originally but now he knows
--a.k.a Bernard's day must be unique in the resulting table
DELETE FROM #Birthdays
WHERE [Day] IN (SELECT [Day] FROM #Birthdays GROUP BY [Day] HAVING COUNT(1) > 1)
-- (2 row(s) affected)

Finally, now Albert also knows the right answer. This is the same deletion as above, except now we will delete any month which is not unique;

--Now Albert knows
--a.k.a Albert's month must be unique in the resulting table
DELETE FROM #Birthdays
WHERE [Month] IN (SELECT [Month] FROM #Birthdays GROUP BY [Month] HAVING COUNT(1) > 1)
-- (2 row(s) affected)

And now we simply print our result:

SELECT * FROM #Birthdays
Month       Day
----------- -----------
7           16
(1 row(s) affected)

I’m sure there are more direct ways to achieve the result in SQL, but this seems like the best match to how I actually worked through the solution step by step. Maybe we’ve found a more entertaining replacement for FizzBuzz! It would be interesting to code this instead as a set of nested SELECT statements, or perhaps using only a sequence of JOINS. Of course any Turing complete language can make easy work of Cheryl’s trickery, and as long as there’s cake for everyone at the end, I wouldn’t mind seeing more of Cheryl in future coding screens.

Hey guys,

I think your company is great, but haven’t had a chance to use you yet. How many people (myself included) are in the same boat?

I read about your latest music festival contest on HN. Maybe that’s ‘Mission Accomplished’ for you already. But I think you should consider running a different kind of contest. I think it comes down to: What market are you targeting with multicontinental music festivals? I can’t quite figure out if you only book multi-continent ’round-the-world’ flights, or if you’re up for more run of the mill business trips and family vacations?  Do you just do the flight, or can you do the hotel accommodations as well? What about something like flights to Europe plus hotel and train travel between countries?

How about running a contest a few more of us could relate to.  Show us how great you could be at planning a budget trip for a family of 4 with kids of different ages. That would solve an immediate problem for a lot of people, not just some sexy corner case. A quality budget experience when kids are involved means no hostels, no campgrounds (unless that’s the whole point), and age appropriate attractions. I’m sure your experts could justify the ‘finders fee’ with some of the great trips they could cook up!

I think part of the problem is I don’t understand what your target market actually is. It doesn’t click who exactly you are trying to serve. It’s the difference between me taking the time to learn about your ‘system’ and maybe even trying it out, and just ‘doing it the old way’.