Решение задачи о двух мудрецах

Давеча была опубликована логическая задача про Шерил, а в комментариях к ней хаброюзер сообщил о более интересной задаче про двух мудрецов.

Собствеено, задача:

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».

Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

Решение под катом.

Задачу я решил методом логики и подбора, видимо, иначе она не решается, во всяком случае я такого решения не встречал. Подбором просто найти первое решение, но остаётся загадкой единственно оно на заданном промежутке или нет. Мне пришла мысль написать решение с использованием ленивых коллекций и практики ради была выбрана scala. Итак начнём.

Будем двигаться по сообщениям мудрецов, смотреть, какую информацию они нам дают и писать соответствующие функции:

1. Али говорит, что он не знает загаданных чисел. Отсюда можно сделать вывод, что хотя бы одно из загаданных чисел не простое, иначе число раскладывалось бы на множители единственным способом. Соответственно создаём стрим простых чисел:

   lazy val primes: Stream[Int] = 2 #:: Stream.from(3).filter(i => isPrime(i))
   
     def isPrime(x: Int): Boolean = {
       primes.takeWhile(i => i*i <= x).forall { k => x % k > 0}
     }

   Всё просто — следующее число будет простым только если оно не делится без остатка ни на одно из всех уже известных простых чисел. Дальше можно создать список всевозможных чисел для Али убрав оттуда произведения простых чисел(6, 15,...), но мы пока этого делать не будем.

2. Дальше Вали сообщает, что он знал, что Али не знает загаданных чисел. Откуда он мог это знать? Видимо его число раскладывается на суммы пар таким образом, что среди них нет ни одной, в которой оба числа были бы простыми. Приведу пример: предположим, что шейх шепнул Вали число 7, его можно разложить на пары (5+2), (4+3). Мы ведь знаем что загаданные числа больше единицы, так что нет смысла раскладывать на 6+1. Смотрим на 5 и 2 — они оба простые, значит шейх не мог шепнуть Вали число 7. Теперь мы можем составить список всевозможных чисел, которые шейх мог шепнуть Вали:

   //раскладываем число на сумму двух других в соотв. с условиями задачи
     def expandBySum(x: Int): List[(Int, Int)] = {
       @tailrec def helper(accum: List[(Int, Int)], i: Int, j: Int): List[(Int, Int)] = {
         if (i < j) accum
         else helper((i, j) :: accum, i - 1, j + 1)
       }
       helper(List.empty, x - 2, 2)
     }
   
   lazy val ValiNumbers: Stream[Int] = Stream.from(4).filter(i => !expandBySum(i).exists(expanded => isPrime(expanded._1) && isPrime(expanded._2)))

   Генерируем поток чисел, которые не имеют ни одного разложения на сумму двух простых.

3. После того, как Али узнал, что числа, которые шейх мог сказать Вали ограничены, он восклицает, что знает ответ! Продолжаем распутывать клубок – судя по всему, число Али раскладывается на пару множителей так, что сумму только одной пары нельзя разложить на сумму двух простых чисел. То есть сумма только одной пары должна входить в список возможных чисел Вали!

   //раскладываем число на два множителя
     def expandByProduct(x: Int): List[(Int, Int)] = {
       var biggestPossibleDivision = x / 2
   
       @tailrec def helper(accum: List[(Int, Int)], i: Int): List[(Int, Int)] = {
         if (i == biggestPossibleDivision) return accum
   
         if (x % i == 0) {
           biggestPossibleDivision = if(x / i <= i) biggestPossibleDivision else x / i
           helper((x / i, i) :: accum, i + 1)
         }
         else helper(accum, i + 1)
       }
       helper(List.empty, 2)
     }
   
     def inValiNumbers(x: Int): Boolean = {
       ValiNumbers.takeWhile(valis => valis <= x).contains(x)
     }
   
   lazy val AliNumbers: Stream[Int] = Stream.from(4).filter(i => expandByProduct(i).count(expanded => inValiNumbers(expanded._1 + expanded._2)) == 1)

   Раскладываем число на список из двух множителей и проверяем, что сумма только одно пары входит в список чисел Вали. Так мы получаем все числа, которые шейх мог шепнуть Али.

4. Узнав, что Али вдруг понял, что-за числа загадал ему шейх, Вали тоже вычислил загаданные числа! Формулировка описания того, как он смог это сделать, получится весьма запутанной, так что подумайте сами :) А я лишь приведу пример кода, который фильтрует числа Вали так, чтобы для обоих мудрецов было решение:

   lazy val ValiNumbersWithSolution: Stream[Int] = ValiNumbers.filter(valis => expandBySum(valis).map(expanded => expanded._1 * expanded._2).count(inAliNumbers) == 1)

Ленивый список со всеми возможными парами чисел, которые мог загадать шейх:

lazy val solution: Stream[String] = ValiNumbersWithSolution.map(valis => {
    val solution = expandBySum(valis).filter(expanded => inAliNumbers(expanded._1 * expanded._2)).head
    "Alis number: " + solution._1 * solution._2 + "; Valis number: " + (solution._1 + solution._2) + "; solution: " + solution._1 + " & " + solution._2
})

Оказывается, в диапазона от 1 до 100 существует всего четыре пары чисел, которые бы мог загадать шейх. Иными словами, мудрецам неслабо фартануло :)

    println("Vali's possible numbers: " + (ValiNumbers.take(20).toList mkString ", "))
    println("Ali's possible numbers: " + (AliNumbers.take(30).toList mkString ", "))
    println("Vali's numbers that give solution to Ali: " + (ValiNumbersWithSolution.take(3).toList mkString ", "))
    println(solution.take(3).toList mkString "n")

"Vali's possible numbers: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87"
"Ali's possible numbers: 18, 24, 28, 50, 52, 54, 76, 92, 96, 98, 100, 112, 124, 140, 144, 148, 152, 160, 172, 176, 188, 192, 208, 212, 216, 220, 228, 232, 242, 244"
"Vali's numbers that give solution to Ali: 17, 65, 89"
"Alis number: 52; Valis number: 17; solution: 13 & 4"
"Alis number: 244; Valis number: 65; solution: 61 & 4"
"Alis number: 1168; Valis number: 89; solution: 73 & 16"

Ссылка на сорцы

Автор: pronvis

Источник