indexeng

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

index.htm - Russian text,

fish.zip - all programs,

fish.java - initial Java-program,

fish.js - outcome of supercompilation.

The given example grows out of joint operation with Andrey Klimov and Arkady Klimov.

The resume. The task offered by Albert Einstein is considered. He asserted, that this task are capable to decide only 2 % of the people. The Java-program is offered, at which supercompilation the solution of the task is received for 31 second.

To the address http://www.refal.net/~korlukov/pearls/ryba/ The solution of the given task by the supercompiler рефала Scp4 is placed.

Earlier on a site http://www.refal.net/~korlukov/pearls/ in the chapter "Recursive numbers" the program was resulted by supercompilation in some times faster, than is executed.

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

Statement of 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 program fish.java on the programming language Java is offered, which 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 under a condition of the task approach. 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 ".

It is a supercompilation of method checkAndPrint(String [] [] houses) with a unknown by the array houses[][]. 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 by line

throw new java.lang.Exception();

corresponds 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 so

    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 nested filters condition1- condition15, each filter corresponds to one of 15 hints in a condition of the task.

The condition of the task is substantially programmed only any operations on organization of exhaustive search and cycles were not conducted.

It would be curious to compare the following two times:

The time of supercompilation, is received for this time the answer to the task,

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

The amount of all cases is equal 5^25 = 298023223876953125, approximately 10^18, i.e. third from billion billions. Even if the computer will sort out billion of cases per second, it will take 9 years

The solution of this task through the supercompiler looks as "suspiciously". There is a unknown array, in which 25 variables are indicated, and there is a Java-program, which can not decide the given task. Really, if to give her on an input all 25 words, we shall receive German if to give something other, we shall receive an abnormal stop.

On the other hand, any "superfluous" operations is not done. Substantially there is recording a condition of the task and more anything. 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 [] []. In the task there are 15 hints - here 15 filters, on one on each hint.

The time of supercompilation depends on swap about processing the hints. That variant, which is indicated, - fastest - 31 seconds. If to use the hints to the on - order from first up to fifteenth, the time of supercompilation is enlarged about 27 minutes. It is completely understandable - different The hints on any other business restrict exhaustive search of variants. The outcome of supercompilation thus does not vary.

The word "fish" in the text of the program misses, except for the function, in which the problem to the task is stated. Therefore problem "to whom belongs to a fish?" looks as strange. Nevertheless, the supercompiler gives the exact answer.

The task too is possible to throw out the hint 15- without it is decided. Outcome of supercompilation such:

    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 correctly has spotted all, besides that the drink in the first house (houses1_0_4_25) is a water. Spot water he could not basically, as the water is mentioned only in 15 hint.

The padding links

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

Here there is a solution of this task on Lisp:
http://www.weitz.de/einstein.html