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.