When Is Cheryl's Birthday?

http://nbviewer.ipython.org/url/norvig.com/ipython/Cheryl.ipynb

by jonp • 11 years ago

240 128 11 years ago

nbviewer.ipython.org

ghurtado• 11 years ago

I thought this was a great puzzle when I first saw it. IMHO, it is more satisfying to "think through it" without paper and pencil, since it is relatively simple to resolve.

The Python solution proposed is really great, in that it captures both the expressive and functional spirit of the language.

ternaryoperator• 11 years ago

since it is relatively simple to solve

You are overestimating how simple it is.There are more than 1200 comments on the solution on the NYTimes[1] almost all of them arguing that other dates are correct.

[1] http://www.nytimes.com/2015/04/15/science/answer-to-the-sing...

Jach2• 11 years ago

It's relatively simple, if you're the kind of person who grasps that 1+1*0 is not 0 under most parsers and under the order of operations implied by e.g. the vector space axioms...

cam_l• 11 years ago

This comment is, in itself, a description of the issue it raises. Simple is an ambiguous term, and you are using it to describe a different aspect of the problem to the parent (you are both right).

tiler• 11 years ago

There are some great examples among the comments of people vehemently defending their provably false beliefs.

nazri1• 11 years ago

Bike shedding, layman version.

InclinedPlane• 11 years ago

It is a simple logic problem, simpler than the vast majority of logic puzzles. The fact that an enormous number of people in the developed world have poor logical reasoning skills is an entirely separate issue.

x0054• 11 years ago

I have to admit, it took me more than 5 minutes to figure this one out, so if this was a test problem, I probably failed. Maybe I am not as smart as I think, but it's probably not as simple as people, including other comments to this post, make it out to be. The trick to the problem is pretty obvious right away, but what tripped me is improper perspective. Reading the comments on NY Times, I think this is the same thing that trips up most people as well.

After eliminating May and June because they have unique days, which is obvious, I got stuck trying to figure out how Albert would be able to figure out the date after knowing that Bernard now knows the date. So I got stuck on July 16, Aug. 15 and Aug. 17 for a while, because I could not figure out how Albert would know the date if he was told August as the month. It took me a few minutes (ok, like 5 or so, more then I care to admit to my self I suppose :) ) to figure out that my job wasn't to figure out how Albert new, but rather to figure out what the answer was IF Albert now knew the answer.

From that it's pretty easy, but it's the perspective that trips most people up.

DannoHung• 11 years ago

This reminds me of the Blue/Brown eyed villager puzzle.

The trick is in figuring out what additional information is actually being added by whatever subsequent statements are being made.

It's weird. I usually have a lot of trouble with mathematical word puzzles. Particularly probability. But logic puzzles almost always seem to be pretty easy for me.

Now if you want a really fucking hard one, try your hand at this: http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

baddox12• 11 years ago

It's very simple in the context of logic puzzles. Similarly, the melody of "Ode to Joy" is very simple to play on the piano. That's not to say that there aren't at least 1,200 people unable to play it on the piano. But it is one of the simplest recognizable melodies to play on the piano, and is likely playable by the vast majority of people with a few months of piano lessons.

picardo• 11 years ago

I'd be interested in seeing a solution in Prolog.

sigterm• 11 years ago

it was posted here before:

https://news.ycombinator.com/item?id=9395604

shele• 11 years ago

Thanks

mattbeckman• 11 years ago

Friend of mine wrote a Scala solution: http://www.agileatwork.com/scala-solution-to-cheryls-birthda...

haddr• 11 years ago

still looking for solution using RDF/OWL logical reasoning...

the python solution is neat, but i have a feeling that there are tools that are more native to these kind of problems than general purpose programming language.

esfandia• 11 years ago

Epistemic logic would probably be the appropriate tool; at least that's what I thought when I first saw the problem. Epistemic logic is the logic of knowledge and belief: you use a modal operator to express the knowledge of an agent about a certain statement. The statement could be expressed in propositional or first-order logic depending on the expressiveness required (but of course there is a complexity trade-off).

Translating roughly from the problem statement (x being the variable holding Cheryl's birthday):

Not(Know_Albert(x)) and Know_Albert(Not(Know_Bernard(x) etc.

Semantically, the possible birthdays correspond to the possible worlds. A reasoner would be able to solve this by process of elimination, somewhat similarly to a constraint-solver.

Resources:

Wikipedia entry on Epistemic Logic: http://en.wikipedia.org/wiki/Epistemic_modal_logic

Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge: http://www.amazon.com/Reasoning-About-Knowledge-Ronald-Fagin...

I haven't read the entire book, but the first couple of chapters give you an idea and some great examples not too different from this puzzle.

andrewprock14• 11 years ago

Unfortunately, there are a number of rather curious, and culturally specific, assumptions one must make about the problem.

The real puzzles are:

1. "Why did Albert speak first?"

2. "Why did he speak in such cryptic language?"

anigbrowl3• 11 years ago

These are actually valid questions and you shouldn't be downvoted. The standard interpretation of the problem is highly questionable; Albert's initial remark is not actually dispositive to Bernhard, because if Bernhard had the 19 May date he would know the correct answer immediately without needing Albert to say anything.

The suggestion that Albert's first statement necessarily eliminates all dates in May is false, and the answer is indeterminable, as can be readily verified with a Venn diagram. It took me some time to spot the flaw in the problem construction; I initially found the official solution persuasive, but when you think more carefully about it you realize it's actually wholly illogical.

kleer001• 11 years ago

Along the lines of the "Bob uses cigarette butts to make new cigarettes. Bob needs 5 cigarette butts to make one new cig. If Bob starts with 25 butts how many cigs can he make?"

logicallee6• 11 years ago

can you make your whole comment more explicit, I don't follow your objection.

stephen_g7• 11 years ago

Your objection doesn't make sense. The fact that Albert can make the statement relies on the fact that he was given a month that rules out Bernard being given a unique date, such as the 19th, otherwise Albert would have to say, "I don't know when the birthday is but perhaps Bernard does" and the problem would be different.

Albert knows the month, and his statement, which translates directly to "given the month I know, it is not possible for Albert to independently determine the date" certainly does rule out the two months.

thuffy• 11 years ago

Solved this without even a pencil and paper, just in my head, in under 60 seconds while being distracted by another person in the room asking me what to have for breakfast. There is only one possible answer as the others pointed out; you are definitely wrong that the answer is indeterminable.

The whole ruckus surrounding this problem seems to be more a reflection of the sad state of the intelligence in our population, rather than anything to do with Asia.

Nursie8• 11 years ago

If we take silence as indicative of lack of knowledge, then nobody needs to speak.

  Bernard: Silence (he doesn't know the answer)
  Albert: Silence (he doesn't either)
  Bernard: I know it!

Interestingly it then becomes relevant who was silent first.

Basically it's nonsense.

stephen_g7• 11 years ago

Maybe I'm missing something, but we know exactly what Bernard would have said first from statement 2.

He says, "At first I didn't know", so all he could have said if he had spoken first would have been "I don't know when the birthday is". Then Albert would have said, "I don't know when the birthday is, and I knew that Bernard couldn't have".

So the problem is unchanged regardless of who speaks first.

It also doesn't seem that cryptic to me... It doesn't take that much reading between the lines to understand the statement "at first I didn't know, but I know now" to mean "the information that Albert just provided gives me enough information to determine the birthday"...

andrewprock14• 11 years ago

IIRC, if Bernard speaks first, then the correct answer is August 17.

john_butts• 11 years ago

1. HN comment about some aspect of fizzbuzz or whatever. Not how to solve fizzbuzz or whatever; rather, some insight into how people solve problems, which is the interesting part of the question. 2. Two dozen oblivious nerds tell u how to do it in 20 characters of perl

Gigablah• 11 years ago

Are you offended that people are sharing their knowledge?

zaroth• 11 years ago

My own contribution from last week:

https://news.ycombinator.com/item?id=9398638

http://opine.me/discovering-a-new-fizzbuzz/

gkoberger• 11 years ago

Maybe I'm missing something, but the "hard" part of this problem is figuring on the trick. Once you know that, it becomes relatively easy – and you can't use a program to figure out the trick.

jrpt• 11 years ago

The problem isn't difficult without programming. It's the programming that's elegant because it's an interesting way to solve the program, by expressing their statements as functions and using the know and tell functions. It's actually really great how the logic was translated in code, almost like a direct translation from English to Python. Now that I know how to write the program, if the puzzle were to get rapidly more complex, say with 20 different statements of moderate complexity, I feel confident I could solve it with a program whereas I might struggle with pencil and paper.

logicallee6• 11 years ago

I don't know, can code like this reason about knowledge-about-knowledge in general?

For example, can a version of the code be used to solve the 'hardest puzzle' -

https://xkcd.com/blue_eyes.html

(solution: https://xkcd.com/solution.html) ?

vacri2• 11 years ago

I find the problems with puzzles like these is not the rules, but the ridiculously contrived situations. Why do these entities that function like inert logic gates have to be human? It means that the question has to have silly rule placed on silly rule in order to keep the contrived situation afloat. It means I end up thinking of ways for the mute, inert people to free themselves from the island (who is feeding them? Are there trees to build a raft? etc), rather than 'play by the rules'.

malisper• 11 years ago

It can.

If you know someone else doesn't know, that just gives you more knowledge you yourself can use.

For the "hardest puzzle", on each day everyone learns that no one was able to figure out the solution the day before. Because of this, a person knows that for a possible number of blue-eyed people to be valid, a person who sees one less blue eyed person than that, must have been unable to figure it out on the previous day.

An Arc/Common Lisp solution I just wrote up: https://gist.github.com/malisper/80625bcda75c66780f81

brownbat• 11 years ago

Not to be confused with the "Hardest Logic Puzzle Ever," about identifying a truth telling god, a lying god, and a random oracle, none of whom even speak your language.

http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever

baddox12• 11 years ago

Which part is the trick? It all seems very straightforward to me.

codeulike4• 11 years ago

Its understanding what the question actually means when it says things like 'Bernard: At first I don't know when Cheryl's birthday is, but I know now.' ... this is actually a cryptic coding of the rules of the puzzle.

If you properly understand those rules and convert them to code (as in the OP) then searching the possible answers for a match is trivial.

DustinCalim• 11 years ago

The trick is to take it at face value and not question how they know, but what the answer has to be assuming they do know.

hyt7u• 11 years ago

It took me a bit to figure out that the third statement was meant to be Albert expressing his confidence that Bernard didn't know the answer and not Albert inducing from Bernard's silence that Bernard didn't know the answer. The latter implies something like the Python code below, which will end up giving August 17th as an answer instead:

  def statement3(date):
    possible_dates = tell(Month(date))
    return (not know(possible_dates)
      and not know(filter(lambda x : not know(x), 
        [tell(Day(d)) for d in possible_dates])))

userbinator2• 11 years ago

The "hard" part of any programming problem is to figure out what the program has to do. The machine can't tell you the correct answer without you giving it the correct instructions.

_asummers• 11 years ago

Where can I find more puzzles of this flavor? This generated some fun discussion on my Facebook wall.

bentcorner• 11 years ago

I don't know where to find a general place of more puzzles like this, but here's one I enjoyed:

http://www.xkcd.com/blue_eyes.html

n1ghtmare_• 11 years ago

A lot of similar puzzles:

http://puzzling.stackexchange.com/questions?sort=votes

frik2• 11 years ago

Could one use Julia instead of Python?

"iPython" already supports Haskell and Julia kernels too. A iPython Javascript kernel would also make sense given its popularity and its functional inspired syntax.

frik2• 11 years ago

A downvoter confused "iPython", its a "notebook" based (think Mathematica notebook) command shell for interactive computing in multiple programming languages. They already renamed it to "Jupyter" as "iPython" was very confusing name.

janhaak• 11 years ago

This is quite disturbing for me. My Aunt's name is Cheryl. Her husband, Bernard. Guess his brother's name!

rckclmbr• 11 years ago

Now write a program to calculate the probability of that happening :)

emerongi• 11 years ago

I bet her birthday is July 16.

sgentle• 11 years ago

At first I don't know his brother's name, but I know now.

vessenes• 11 years ago

This is just beautifully expressive python. I wouldn't think of using it this way: writing

  return (not know(possible_dates)
          and all(not know(tell(Day(d)))
                    for d in possible_dates))

feels almost zen to me; or at least like Mr. Norvig likes himself some lisp at times.

logicallee6• 11 years ago

Python: write pseudocode, and then make sure it's indented properly.

selectiveshift• 11 years ago

He does in fact like himself some lisp: http://norvig.com/paip.html

kyberias• 11 years ago

Couldn't resist. This is the solution ported to C#:

https://github.com/kyberias/cherylsharp

baronofcheese• 11 years ago

Funny you say it. I had a go at it as well. Seems like we ended up more or less the same :)

https://gist.github.com/Cheesebaron/f813576f62dce8391c3b

ibejoeb• 11 years ago

Here's my quick solution in modern SQL. This is more expensive than it needs to be, but doing it this way lets you see the truth table by commenting out the final predicate.

fiddle: http://sqlfiddle.com/#!15/0c419/160/0

gist: https://gist.github.com/ibejoeb/df57cb34bbe609293d6e

zhte4152• 11 years ago

The problem with this problem, the way it was originally put, was the utterly confusing English masked into a logic problem.

Write your specifications clearly, and then it does not become an internationally shared 'problem' to solve.

[I work with insanely documented specifications just like this, year after year. Not putting a problem clearly is not something to aspire to.]

baddox12• 11 years ago

Why do you think that confusion over the English description is more to blame than the difficulties many people face with logic puzzles?

zhte4152• 11 years ago

I do not make a comparison to 'difficulties many people face with logic problems' and did not make an assertion that many people face difficulties with logic puzzles.

Getting back to the article: the problem is worded so badly it should be sent back to the author to more coherently express what they think. Specifications, etc...

chongli3• 11 years ago

A lot of people reading it probably didn't even realize that it is a logic puzzle. To those, it may be some kind of obscure riddle with terrible grammar.

Heck, it's not even clear that Albert and Bernard are communicating with one another and not merely with the answerer. If you assume they do not communicate at all then the puzzle becomes impossible.

stephen_g7• 11 years ago

It's a puzzle - it's supposed to be tricky.

I don't really think it's especially obfuscated though. You just have to think about why people are saying what they say, which is a fairly useful thing to be able to do...

Fando• 11 years ago

Maybe someone already mentioned this, but this problem is a simplified formulation of a famous number thoery riddle called 'The Sum and Product Riddle' which is even more baffling. Here it is http://blog.computationalcomplexity.org/2007/01/sum-and-prod...

tomp• 11 years ago

For the more mathematically minded readers, here's a harder version of the problem:

http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...

xarien• 11 years ago

I'd have gone a different way since my setup and approach was a bit different (I took a more visual approach). While this solution is elegant, it's also incredibly hard to do in the real world as it requires far too much knowledge to properly assign the "correct" definitions. It's no different than having a perfect health heuristic land on your lap.

When I did this a while back, my approach was to construct a 5x4 matrix with blanks (5 unique dates x 4 unique months). This allowed the clues to cross off entire rows and or columns until only 1 pair stood standing. Personally, I find the construction of the solution much more interesting than the problem itself given how many people participated.

Nursie8• 11 years ago

If you're puzzling over this you've done it wrong.

There is no inference from silence. There is no humanity in such a question, there is simply the information you're given and the application of logic to narrow down the answers. The Singaporean kids that took the exam knew this and anyone that's ever taken a maths or logic exam should know this.

You don't guess what might have happened from human behaviour because you don't know, you don't look for a 'trick' to give away the answer, you simply use the data in the question to narrow down the possibilities until you can arrive at an answer.

The moment you think "but what if this action could have taken place because if he knew he would have said" you have failed.

And you probably suck at debugging.

When Is Cheryl's Birthday?

Related Stories