День рождения Шерил
maximsidorovАлгоритм нахождения дня рождения Шерил
В этом примере рассматривается реализация логической задачи "День рождения Шерил" на языке программирования Julia.
Введение
День рождения Шерил (Cheryl's birthday) — это популярная логическая задача, предложенная в 2015 году. В ней два друга, Альберт и Бернард, пытаются определить день рождения Шерил, исходя из ограниченного набора дат и логических утверждений. Решение задачи строится на анализе информации, которой обладают персонажи, и последовательном исключении невозможных вариантов.
Постановка задачи:
Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат: 15 мая, 16 мая, 19 мая, 17 июня, 18 июня, 14 июля, 16 июля, 14 августа, 15 августа и 17 августа.
|
Май |
15 |
16 |
19 |
|||
|
Июнь |
17 |
18 |
||||
|
Июль |
14 |
16 |
||||
|
Август |
14 |
15 |
17 |
Затем Шерил сказала Альберту месяц своего рождения, а Бернарду — день. После этого состоялся диалог.
Альберт: Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает.
Бернард: Поначалу я не знал, когда у Шерил день рождения, но знаю теперь.
Альберт: Теперь я тоже знаю, когда у Шерил день рождения.
Когда у Шерил день рождения?
Основная часть
Исходные данные и вспомогательные функции
Задаем возможные даты дня рождения Шерил в формате: [день, месяц].
const dates = [[15, "Мая"], [16, "Мая"], [19, "Мая"], [17, "Июня"], [18, "Июня"],
[14, "Июля"], [16, "Июля"], [14, "Августа"], [15, "Августа"], [17, "Августа"]]
Определяем функцию, которая находит уникальные дни.
Уникальный день — это день, встречающийся только один раз в списке.
uniqueday(parr) = filter(x -> count(y -> y[1] == x[1], parr) == 1, parr)
Первый шаг логического анализа: удаление месяцев с уникальными днями
На первом шаге мы исключаем те месяцы, в которых есть уникальные дни.
Это объясняется тем, что Альберт говорит, что он знает, что Бернард не может знать точную дату.
Следовательно, день рождения не может быть в месяце, содержащем уникальный день.
const f1 = filter(m -> !(m[2] in [d[2] for d in uniqueday(dates)]), dates)
Второй шаг: поиск уникальных дней в оставшихся данных
Теперь мы снова ищем уникальные дни, но уже в оставшемся списке дат (f1).
Это шаг соответствует предположению Бернарда, который теперь может определить дату.
const f2 = uniqueday(f1)
Третий шаг: нахождение окончательной даты
На последнем шаге мы оставляем только те даты,
которые находятся в месяце с единственной возможной датой.
Это соответствует заключению Альберта, который теперь тоже может определить дату.
const bday = filter(x -> count(m -> m[2] == x[2], f2) == 1, f2)[]
Выводим ответ.
println("День рождения Шерил $(bday[1]) $(bday[2]).")
Заключение
В этом примере мы подробно рассмотрели реализацию логической задачи "День рождения Шерил" на языке Julia. С помощью последовательной фильтрации данных и логических предположений мы смогли определить точную дату дня рождения. Этот пример демонстрирует мощь и лаконичность языка Julia при решении задач логического программирования и анализа данных.
Пример разработан с использованием материалов Rosetta Code