Решение суперкомпилятором JScp задачи А. Эйнштейна
index.htm - английский текст,
fish.zip - все программы,
fish.java - исходная Ява-программа,
fish.js - результат суперкомпиляции.
Данный пример является результатом совместной работы с Андреем Климовым и Аркадием Климовым.
Резюме. Рассматривается задача, предложенная А.Эйнштейном. Он утверждал, что эту задачу способны решить лишь 2% людей. Предлагается Ява-программа, при суперкомпиляции которой за 31 секунду получается решение задачи.
По адресу http://www.refal.net/~korlukov/pearls/ryba/ размещено решение данной задачи суперкомпилятором рефала Scp4.
Ранее на сайте 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 живет по соседству с человеком, который пьет воду.
Решение задачи.
Предлагается программа fish.java на языке программирования Ява, исходными данными которой является массив
String[][] houses = new String[nofHouses][nofProperties];
Например, ответ к задаче
String[][] houses = {
{"Norwegian", "Yellow", "Dunhill", "Cat", "Water" },
{"Dane", "Blue", "Blend", "Horse", "Tea" },
{"Brit", "Red", "PallMall", "Bird", "Milk" },
{"German", "Green", "Prince", "Fish", "Coffee"},
{"Swede", "White", "BlueMaster", "Dog", "Beer" }
};
Программа (метод main) проверяет, подходят ли исходные данные под условие задачи. Если "да", то строится ответ на вопрос задачи, если "нет", то происходит аварийная остановка "Exception in thread "main" java.lang.Exception".
Суперкомпилируется метод checkAndPrint(String[][] houses) с неизвестным массивом houses[][]. Использовался bat-файл задания на суперкомпиляцию
call jScp -m checkAndPrint -ul6 -i -ji -v0 Fish -d res %* > Fish.js
Результат суперкомпиляции fish.js
состоит из двух фрагментов. Первый
фрагмент заканчивается строкой
throw new java.lang.Exception();
и соответствует случаю, когда массив houses[][] не является ответом на вопрос задачи.
Второй фрагмент соответствует случаю, когда массив houses[][] является ответом на вопрос задачи и выглядит так
java.lang.System.out.println("the owner of a fish = German") /*virtual*/;
java.lang.System.out.println("") /*virtual*/;
java.lang.System.out.println("house 1: Norwegian Yellow Dunhill Cat Water ") /*virtual*/;
java.lang.System.out.println("house 2: Dane Blue Blend Horse Tea ") /*virtual*/;
java.lang.System.out.println("house 3: Brit Red PallMall Bird Milk ") /*virtual*/;
java.lang.System.out.println("house 4: German Green Prince Fish Coffee ") /*virtual*/;
java.lang.System.out.println("house 5: Swede White BlueMaster Dog Beer ") /*virtual*/;
return;
Суперкомпилируемая программа fish.java состоит из 15 вложенных фильтров condition1- condition15, каждый фильтр соответствует одной из 15 подсказок в условии задачи.
Реально запрограммировано только условие задачи, никакие действия по организации перебора и циклов не проводились.
Любопытно было бы сравнить следующие два времени:
Количество всех случаев равно 525 = 298023223876953125, примерно 1018 , т.е. третья часть от миллиарда миллиардов. Даже если компьютер будет перебирать миллиард случаев в секунду, то это займет 9 лет.
Решение этой задачи при помощи
суперкомпилятора выглядит как-то "подозрительно".
Имеется неизвестный массив, в котором
указаны 25 переменных, и имеется Ява-программа,
которая не может решать данную задачу.
Действительно, если подать ей на вход все 25
правильных слова, то получим German, если дать
что-либо другое, то получим аварийную
остановку .
С другой стороны, никаких "лишних"
действий не делается. Реально происходит
запись условия задачи и больше ничего. Нет
никаких циклов по организации перебора. В
любой программе необходимо описать объекты,
с которыми работает программа, - здесь это
происходит при помощи массива houses[][]. В
задаче имеются 15 подсказок - здесь 15
фильтров, по одному на каждую подсказку.
Время суперкомпиляции зависит от
перестановки порядка обработки подсказок.
Тот вариант, который приведен, - наиболее
быстрый - 31 секунда. Если использовать
подсказки по-порядку от первой до
пятнадцатой, то время суперкомпиляции
увеличивается до 27 минут. Это совершенно
понятно - разные
подсказки по разному ограничивают перебор
вариантов. Результат суперкомпиляции при
этом не меняется.
Слово "рыба" в тексте программы
отсутствует, кроме функции, в которой
формулируется вопрос к задаче. Поэтому
вопрос "Кому принадлежит рыба?"
выглядит как-то странно. Тем не менее,
суперкомпилятор дает правильный ответ.
Можно выкинуть 15-ю подсказку - без нее задача тоже решается. Результат суперкомпиляции такой:
java.lang.System.out.println("the owner of a fish = German") /*virtual*/;
java.lang.System.out.println("") /*virtual*/;
java.lang.System.out.println("house 1: Norwegian Yellow Dunhill Cat " + houses1_0_4_25 + " ") /*virtual*/;
java.lang.System.out.println("house 2: Dane Blue Blend Horse Tea ") /*virtual*/;
java.lang.System.out.println("house 3: Brit Red PallMall Bird Milk ") /*virtual*/;
java.lang.System.out.println("house 4: German Green Prince Fish Coffee ") /*virtual*/;
java.lang.System.out.println("house 5: Swede White BlueMaster Dog Beer ") /*virtual*/;
return;
Суперкомпилятор все правильно определил, кроме того, что напиток в первом доме (houses1_0_4_25) - это вода. Определить воду он не мог в принципе, так как вода упоминается только в 15-ой подсказке.
Дополнительные ссылки
http://home.houston.rr.com/bybayouu/Puzzle/Puzzle_0.html
http://www.aitkin.k12.mn.us/hopperstad/HquizA.html
http://www.mirthe.org/farewell/brain_teaser.php
http://www.greylabyrinth.com/Puzzles/answer084.htm
http://www.begent.freeserve.co.uk/einstein.htm
http://www.pvv.ntnu.no/~nsaa/einstein_quiz.html
http://www.evillama.com/whatsgoingon/games/einstein.htm
http://www.mindspring.com/~mccarthys/puzzle1.htm
http://www.teop.org/content/1013711929
http://www.tektron.co.uk/riddle.html
http://www.desiboyzmasala.com/DesiBoyZ/Fun/Puzzles/p_stabatp.html
Здесь имеется решение этой задачи на Лиспе:
http://www.weitz.de/einstein.html