When Is Cheryl's Birthday?

[gkoberger]

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]

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.

[logicallee]

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) ?

[userbinator]

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.

[baddox]

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

[ghurtado]

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]

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

[vessenes]

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.

[logicallee]

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

[selectiveshift]

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

[ibejoeb]

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

[zhte415]

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

[baddox]

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

[stephen_g]

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

[tomp]

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

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

[xarien]

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.

[picardo]

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

[sigterm]

it was posted here before:

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

[zaroth]

My own contribution from last week:

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

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

[john_butts]

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]

Are you offended that people are sharing their knowledge?

[Fando]

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

[janhaak]

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

[sgentle]

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

[rckclmbr]

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

[emerongi]

I bet her birthday is July 16.

[_asummers]

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

[bentcorner]

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_]

A lot of similar puzzles:

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

[mattbeckman]

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

[Nursie]

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.

[kyberias]

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

https://github.com/kyberias/cherylsharp

[baronofcheese]

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

[haddr]

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]

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.

[frik]

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.

[frik]

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.

[andrewprock]

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?"

[stephen_g]

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

[anigbrowl]

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.