Engee documentation
Notebook

The algorithm for finding Cheryl's birthday

This example examines the implementation of the logical task "Cheryl's birthday" in the Julia programming language.

Introduction

Cheryl's birthday is a popular logic problem proposed in 2015. In it, two friends, Albert and Bernard, try to determine Cheryl's birthday based on a limited set of dates and logical statements. The solution to the problem is based on the analysis of the information possessed by the characters and the consistent elimination of impossible options.

Setting the task:

Albert and Bernard have just met Cheryl. They want to know when her birthday is. Cheryl offered them ten possible dates: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, and August 17.

May

15

16

19

June

17

18

July

14

16

August

14

15

17

Cheryl then told Albert the month of her birth, and Bernard the day. After that, a dialogue took place.

*Albert: I do not know when Cheryl's birthday is, but I know that Bernard does not know either.
*Bernard: I didn't know when Cheryl's birthday was at first, but I know now.
*Albert: Now I also know when Cheryl's birthday is.

When is Cheryl's birthday?

The main part

Source data and auxiliary functions

We set the possible dates of Cheryl's birthday in the format: [day, month].

In [ ]: 
const dates = [[15, "Мая"], [16, "Мая"], [19, "Мая"], [17, "Июня"], [18, "Июня"],
    [14, "Июля"], [16, "Июля"], [14, "Августа"], [15, "Августа"], [17, "Августа"]]
Out[0]:
10-element Vector{Vector{Any}}:
 [15, "Мая"]
 [16, "Мая"]
 [19, "Мая"]
 [17, "Июня"]
 [18, "Июня"]
 [14, "Июля"]
 [16, "Июля"]
 [14, "Августа"]
 [15, "Августа"]
 [17, "Августа"]

Defining a function that finds unique days.

A unique day is a day that occurs only once in the list.

In [ ]: 
uniqueday(parr) = filter(x -> count(y -> y[1] == x[1], parr) == 1, parr)
Out[0]:
uniqueday (generic function with 1 method)

The first step of logical analysis: removing months with unique days

In the first step, we exclude those months that have unique days.

This is because Albert says that he knows that Bernard cannot know the exact date.

Therefore, a birthday cannot be in a month containing a unique day.

In [ ]: 
const f1 = filter(m -> !(m[2] in [d[2] for d in uniqueday(dates)]), dates)
Out[0]:
5-element Vector{Vector{Any}}:
 [14, "Июля"]
 [16, "Июля"]
 [14, "Августа"]
 [15, "Августа"]
 [17, "Августа"]

Second step: Search for unique days in the remaining data

Now we are looking for unique days again, but in the remaining list of dates (f1).

This step corresponds to Bernard's assumption, which can now determine the date.

In [ ]: 
const f2 = uniqueday(f1)
Out[0]:
3-element Vector{Vector{Any}}:
 [16, "Июля"]
 [15, "Августа"]
 [17, "Августа"]

The third step: finding the final date

In the last step, we leave only those dates.,

which are in the month with the only possible date.

This corresponds to Albert's conclusion, which can now also determine the date.

In [ ]: 
const bday = filter(x -> count(m -> m[2] == x[2], f2) == 1, f2)[]
Out[0]:
2-element Vector{Any}:
 16
   "Июля"

We output the response.

In [ ]: 
println("День рождения Шерил $(bday[1]) $(bday[2]).")

День рождения Шерил 16 Июля.

Conclusion

In this example, we looked in detail at the implementation of the logical task "Cheryl's birthday" in the Julia language. By sequentially filtering the data and making logical assumptions, we were able to determine the exact date of the birthday. This example demonstrates the power and conciseness of the Julia language in solving logic programming and data analysis problems.

The example was developed using materials from Rosetta Code