Category Archives: Musings

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.

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

 

 

Thoughts on Facebook’s Ad Platform

Note to reader, please consider the following as a DRAFT only.  I’m still working on the software which will let you collaboratively edit it with me (if you so choose) without having to register.

If you listen to Facebook’s earnings call and you read the latest from the analysts then you already know that FB is looking for the technology which will give them the boost they need in mobile advertising.

Continue reading

Google Groups spam filters suck, and you can’t turn them off

Google Groups has been an amazing asset to me for the last several years. I use it, as I’m sure many do, as an archived listserv for various groups I participate in.  What’s great is you can setup the group as invite only, but allow anyone to post.  People outside the group send email in, but only members of the group can read it.

Incredibly common, incredibly useful, but recently on Google Groups, incredibly broken.

Continue reading

The Perfect Founders

For a while now, certain venture capitalists have had an unwritten rule: a good team consists of a developer, a designer, and a CEO. But I have news. It’s not a designer you need. It’s a system architect.

Continue reading

“We found a Higgs boson”

I watched the CERN webcast live at 2:00am PST, but I’m still not sure
what exactly to think about the discovery they announced,
and the particle they are calling Higgs’.

We can say we found a Higgs boson, but not the Higgs boson.
Rolf Heuer, Director General, CERN

Physicists have been testing (and confirming) parameters of the Standard Model
for more than three decades now.
So hearing that CERN has finally found “a Higgs boson” is a little bit like
NASA’s gravity probe experiment confirming Einstein’s general relativity;
entirely unsurprising.

Continue reading

First, look back

In a new year, the first step should always be to reflect on what has passed.

In business it can be called a ‘post mortem’. If you’ve heard the term, and if you’ve gone through them before, you know there’s a right way and a wrong way to get them done.

But the goal is basically the same for business or for personal reasons; learn from your mistakes.  At the least, we can all enter 2012 with that in mind.

If you want to leave a comment, consider telling us about a mistake you learned from.

 

Missing the Mark

SOPA related posts have dominated HN and Reddit for the last several weeks, as well it should. More recently, network administrators of the world have united against GoDaddy, who was for-SOPA, before they were not-quite-against-it.

December 29th is now ‘Leave GoDaddy Day’, but boycotters beware; transferring domains is an error prone and potentially risky process which can result in downtime. Several HOWTO articles have been written since the boycott started, followed by reports of failed transfers, finger pointing that GoDaddy was obstructing the process, and downtime for anyone using GoDaddy DNS before they tried to transfer.

Continue reading

Batttle Cry of a Startup

Sales happen at the moment when a buyer and seller agree on a price. When customers pay less than they would have, we call it consumer surplus. If you’re the type of person who speaks at shareholder meetings, consumer surplus is a bad thing.

Companies deal with consumer surplus by calibrating their product offerings to match different customer segments. Sometimes the variable pricing is actually a result of variable costs. More often than not, variable cost is just a concept that salesmen will use to rationalize their power grab for every last dollar of consumer surplus. In the auto industry they like to call this ‘optional equipment’. It’s almost universally true, as the price goes up, so too does the margin.

Continue reading