index

Solution by the supercompiler JScp of the task of A.Einstein

russian.htm - russian text,

fish.zip - all programs,

fish.java - initial Java-program,

fish.js - outcome of supercompilation.

The given example is presented as a joint work with Andrey Klimov and Arkady Klimov.

The resume. The task offered by Albert Einstein is considered. He asserted that only 2 % of the world population are capable to solve this task. The Java-program is offered through supercompilation of which the task can be solved in 31 second time.

To the address http://www.refal.net/~korlukov/pearls/ryba/ the solution of the given task by the Refal-supercompiler Scp4 is placed.

Earlier on a site http://www.refal.net/~korlukov/pearls/ in the chapter "Recursive numbers" there was given an example demonstrating the program which was supercompiled several times faster than if executed.

A similar pattern is supervised below. The offered algorithm corresponds exhaustive search 5^25 cases. This number is equal to 298023223876953125, approximately 10^18, i.e. a billion billions. Therefore it is very inconvenient to measure the time of direct executing of the program (it will take many years).

The task.

There are 5 houses in 5 different colors. In each house lives a man with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar or drink the same beverage.

The question is: "Who owns the fish?"

Hints:

The Brit lives in the red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The green house is on the left of the white house.
The green house's owner drinks coffee.
The person who smokes Pall Mall rears birds.
The owner of the yellow house smokes Dunhill.
The man living in the center house drinks milk.
The Norwegian lives in the first house.
The man who smokes Blends lives next to the one who keeps cats.
The man who keeps the horse lives next to the man who smokes Dunhill.
The owner who smokes Bluemasters drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
The man who smokes Blends has a neighbor who drinks water.

Solution of the task.

The Java-program fish.java is offered. Its input data is the array

    String[][] houses = new String[nofHouses][nofProperties];

For example, answer to the task

    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"  }
    };

The program (method main) checks whether the input data meets the condition of the task. If "yes", the answer to a problem of the task is created. If "no", there is an abnormal stop "Exception in thread " main " a java. lang Exception ".

Method checkAndPrint(String[] [] houses) with an unknown array houses[][] is supercompiled.

The bat-file of the job on supercompilation was used

call jScp -m checkAndPrint -ul6 -i -ji -v0 Fish -d res %* > Fish.js

The outcome of supercompilation fish.js consists of two fragments. The first fragment is ended with line

throw new java.lang.Exception();

corresponding to a case when the array houses[][] is not the answer to a problem of the task.

The second fragment corresponds to a case, when the array houses[] [] is the answer to a problem of the task and looks as follows

    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;

The supercompiled program fish.java consists of 15 filters

condition1- condition15

Each filter corresponds to one of 15 hints applied to the task.

Only the condition of the task is actually programmed. No operations on organization of exhaustive search and cycles were conducted.

It would be curious to compare the following two times:

The time of supercompilation (the answer to the task is obtained)

The time of direct executing of the program. For this purpose it is necessary to add functions on organization of exhaustive search of all cases.

The solution of this task through the supercompiler looks "suspicious". There is an unknown array, in which 25 variables are indicated. And there is a Java-program which can not solve the given task. Actually, if to provide the program with all the 25 appropriate words, we shall receive "German". If to give something other, we shall receive an abnormal stop.

On the other hand, no "superfluous" operations are done. Indeed, only a recording of the condition of the task occurs. There are no cycles on organization of exhaustive search. In any program it is necessary to describe objects, with which the program works, - here it happens through the array houses [] [].There are 15 hints in the task: 15 filters to each hint.

The time of supercompilation depends on the order of the hint's processing. That variant indicated is the fastest - 31 seconds. If to use the hints from the first up to the fifteenth, then the time of supercompilation is about 27 minutes. It is completely understandable - different hints restrict exhaustive search of variants in different way. The outcome of supercompilation is the same.

There is no word "fish" in the text of the program except for the function in which the problem to the task is stated. Therefore, the question "who owns a fish?" looks strange. Nevertheless, the supercompiler gives the right answer.

It is possible to solve the task without hint 15. The outcome of supercompilation is as follows:

    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;

The supercompiler solved everything correctly. An exception was that the drink in the first house (houses1_0_4_25) was water. The word "water" is mentioned only in hint 15.

The references

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

There is a solution of this task on Lisp:

http://www.weitz.de/einstein.html