Решение суперкомпилятором Scp4 задачи А. Эйнштейна
ryba.zip - все программы,
rybabat.htm - задание на суперкомпиляцию,
rybamst.htm - MST-схема,
rybaref.htm - рефал-программа,
rybarref.htm - результат суперкомпиляции.
Резюме. Рассматривается задача, предложенная А.Эйнштейном. Он утверждал, что эту задачу способны решить лишь 2% людей. Предлагается программа, при суперкомпиляции которай за 1 час 30 минут получается решение задачи. Опыт показывает, что 2% людей решают эту задачу примерно за это же время.
Ранее на сайте http://www.refal.net/~korlukov/pearls/ в главе "Рекурсивные числа" приводилась программа, которая суперкомпилируется в несколько раз быстрее, чем исполняется.
Здесь наблюдается аналогичная картина. Предложенный алгоритм соответствует перебору 525 случаев. Это число равно 298023223876953125, примерно 1018 , т.е. миллиард миллиардов. Поэтому очень затруднительно измерить время непосредственного исполнения программы (исполнение займет многие годы).
Формулировка задачи.
ЧИСТАЯ ЛОГИКА
А. Эйнштейн придумал эту загадку в прошлом веке и полагал, что 98 процентов жителей Земли будут не в состоянии ее решить.
Принадлежите ли вы к 2 процентам самых умных людей планеты?
1. Есть 5 домов каждый разного цвета.
2. В каждом доме живет один человек, отличающийся от соседнего по национальности: немец, англичанин, швед, датчанин, норвежец.
3. Каждый пьет только один определенный напиток, курит определенную марку сигарет и держит определенное животное.
4. Никто из 5 человек не пьет одинаковые с другими напитки, не курит одинаковые сигареты и не держит одинаковое животное.
Вопрос: кому принадлежит рыба?
Подсказки:
1. Англичанин живет в красном доме.
2. Швед держит собаку.
3. Датчанин пьет чай.
4. Зеленый дом стоит слева от белого.
5. Жилец зеленого дома пьет кофе.
6. Человек, который курит Pall Mall, держит птицу.
7. Жилец из среднего дома пьет молоко.
8. Жилец из желтого дома курит Dunhill.
9. Норвежец живет в первом доме.
10. Курильщик Marlboro живет около того, кто держит кошку.
11. Человек, который держит лошадь, живет около того, кто курит Dunhill.
12. Курильщик сигарет Winfield пьет пиво.
13. Норвежец живет около голубого дома.
14. Немец курит Rothmans.
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду.
Решение задачи.
Предлагается программа rybaref.htm на языке программирования Рефал, исходными данными которой является конфигурация вида
(s.11 s.12 s.13 s.14 s.15) (s.21 s.22 s.23 s.24 s.25) (s.31 s.32 s.33 s.34 s.35) (s.41 s.42 s.43 s.44 s.45) (s.51 s.52 s.53 s.54 s.55)
Под эту конфигурацию подходит, например, ответ к задаче
(Norwegian Yellow Dunhill Cat Water ) (Dane Blue Marlboro Horse Tea ) (Englishman Red PallMall Bird Milk ) (German Green Rothmans Fish Coffee) (Swede White Winfield Dog Beer )
Программа проверяет, подходят ли исходные данные под условие задачи. Если "да", то строится ответ на вопрос задачи, если "нет", то происходит аварийная остановка "отождествление невозможно".
Результат суперкомпиляции rybarref.htm выглядит так
ryba1 {
Norwegian Yellow Dunhill Cat Water
Dane Blue Marlboro Horse Tea
Englishman Red PallMall Bird Milk
German Green Rothmans Fish Coffee
Swede White Winfield Dog Beer = German ;
}
Суперкомпилируемая программа состоит из 20 вложенных фильтров - 15 фильтров соответствуют 15 подсказкам в условии задачи, оставшиеся 5 фильтров проверяют наличие каждого объекта из условия по одному разу.
Реально запрограммировано только условие задачи, никакие действия по организации перебора и циклов не проводились.
Любопытно было бы сравнить следующие два времени:
Количество всех случаев равно 525 = 298023223876953125, примерно 1018 , т.е. третья часть от миллиарда миллиардов. Даже если компьютер будет перебирать миллиард случаев в секунду, то это займет 9 лет.