Discovering a New FizzBuzz – The Cheryl Birthday Problem

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.

The Value of a Low Valuation

Business Insider analyzed a leaked email between Evan Spiegel (CEO of Snapchat) and Mitch Lasky, a Board member of Snapchat (Partner at Benchmark Capital). The email was leaked as part of the Sony hack, because the CEO of Sony, Michael Lynton, is also on the Board of Snapchat. Snapchat lost a lot of sensitive emails in the Sony breach because of that connection.

One interesting topic for that Board discussion was Snapchat’s Section 409A valuation. The IRS requires paying taxes as restricted stock vests (or up front if you so-elect) based on the fair market value of the stock. Or, if options, based on the intrinsic + time-value of the options. So maintaining a low common stock valuation becomes a crucial exercise if you want to actually be able to issue any meaningful number of shares to your employees.

Continue reading

The Self-Hosting Moonshot

Self-hosting an app may provide some unique advantages, like scalability and privacy, but it comes at a cost. There’s a huge usability gap in the setup cost. Users expect the web to ‘just work’ and don’t want the cognitive load of ‘configuring’ or managing something. So the self-hosted app has to “feel” like a local app, and nothing more. From the user perspective, the back-end is “weightless”.

Continue reading


The Future of Bitcoin Escrow

Bitcoin has a built-in functionality, called CHECKMULTISIG, where you can require two or more private keys in order to spend a transaction. There are an incredible number of ways you could theoretically use CHECKMULTISIG, but the most obvious use case is a secure escrow functionality. A quick glance at the history of Bitcoin powered services over the last 3 years shows how much the community could benefit from better ways to escrow payments.

Continue reading

How Lavabit Will Win on Appeal

There’s something missing from the arguments being set forth in the Lavabit appeal, and I think it opens a gaping hole in the government’s case. This case actually isn’t about encryption keys at all, and I think refocusing the argument will give the appeals court the “out” they’re looking for to decide in Lavabit’s favor without actually deciding the issue of whether the government can compel production of SSL keys.

Continue reading

US Response Missing in Egyptian Government’s Mass Killings of Protesters

I just read this NY Times article on the mass killings in Egypt, and I highly recommend you take the time to read it:

This is incredibly disturbing on so many levels. I haven’t been keeping up to speed on current events in Egypt as much as now I think I should, so this was eye opening and I think a must-read. There is too much in the article to try quoting specific parts or recapping it; I think you just need to read the source, especially if you’re not up to speed.

There are so many thoughts and questions that this brings to mind… and I hope we can at least drive some critical discussion following these events.

CERT Advisory on DNS Amplification Offers Little Hope

CERT released an advisory today on DNS Amplification Attacks.  These attacks are nothing new; in fact dealing with this kind of load is business as usual for the Tier1/2 providers. But I was surprised with how little apparently CERT has to offer in the way of advice to thwart the attacks.

Open Letter to Flightfox

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’.



SRP vulnerability when using a 256-bit modulus

Note to reader: This SRP vulnerability applies only if a 256-bit modulus is being used. For example, in Blizzard’s 2 protocol, the modulus is 1024-bit [1].

In my prior blog post, I explained how an attacker can use a dictionary attack to try to guess users’ passwords based on the recent Blizzard data breach, where they were using SRP to store the passwords. Some readers have pointed out, it is significantly slower to dictionary attack SRP than raw SHA1, so SRP at least protects users who have chosen strong / random passwords. However, depending on the bit-length of the modulus, there may be an improved technique which could allow significantly faster attacks.

Continue reading

SRP Won’t Protect Blizzard’s Stolen Passwords

Blizzard announced today they they have suffered a major data breach, and sensitive user data was stolen from their servers.  According to their statement the specific data stolen includes email address, the answer to the personal security question, and information relating to two-factor authentication. They also lost their SRP server-side verifier database, which is the database they use to verify user passwords.

And despite what Blizzard is claiming, I believe the majority of their users’ plain text passwords have been exposed as well.

Continue reading