Einstein's Riddle

[Yoann Padioleau]

Petasis George <petasis at iit.demokritos.gr> writes:

> "Donal K. Fellows" wrote:
> > 
> > Thaddeus L Olczyk wrote:
> > > I also figure the fish thing was simply a typo, and that this guy (
> > > who hasn't resdponded ) was probably given this as a homework
> > > assignement, and is simply looking for a cheap way to get it done.
> > 
> > That'd be a very lame homework assignment.  Not unless you had to write
> > a program in $FAVOURITE_LANGUAGE to compute the answer automatically
> > (which is much more interesting, especially if you make the program
> > start from the natural language expression of the problem!  :^)
> > 
> Well, try this:-)
> Written by a friend of mine. Its amazing how small can programs be if you
> know STL. To bad I don't know stl :-)
> Of course it will need some time, as it randomly checks all combinations...
But your program dont really do the job cos it is too slow.
You first generate the permutations and then test, the pb is that
there is too many permutations : 
p[nation][english] can be either 0 1 2 3 4 or 5, same for the other variables
you have 5*(5!) possibililty = 24 883 200 000
if you are able to do 1 000 000 ValidConstraints per second (cos you have perhaps
a very very fast computer) you will need 24 883 seconds =~ 6hours to compute (in the worst case
i admit)

the prolog program i propose take 0.1 second to find the solution :)
who say that prolog is slower than c++ :))

> 
> George
> 
> //A simple randomiser to find the solution to the riddle, by J. Y. Goulermas
> 
> #include <vector>
> #include <ctime>
> #include <algorithm>
> #include <fstream>
> #include <iomanip>
> #include <iostream>
> 
> using namespace std;
> 
> enum element_type { nation,  colour,  pet,         drink,  cigs       };
> enum nation_type  { english, swedish, danish,      german, norwegian  };
> enum colour_type  { red,     blue,    yellow,      green,  white      };
> enum pet_type     { cat,     bird,    horse,       dog,    fish       };
> enum drink_type   { tea,     water,   milk,        beer,   coffee     };
> enum cigs_type    { palmal,  dunhill, bluemasters, prince, blends     };
> 
> char* codes[][5] = { { "english", "swedish", "danish",      "german", 
> "norwegian" },
>                      { "red",     "blue",    "yellow",      "green",  
> "white"     },
>                      { "cat",     "bird",    "horse",       "dog",    "fish" 
>       },
>                      { "tea",     "water",   "milk",        "beer",   
> "coffee"    },
>                      { "palmal",  "dunhill", "bluemasters", "prince", 
> "blends"    }
>                    };
> 
> inline bool ValidConstraints(const vector< vector<int> >& p)
> {
>   return   p[nation][norwegian] == 0                   //Rule 9
>          &&
>            p[colour][blue] == 1                        //Rule 14
>          &&
>            p[drink][milk] == 2                         //Rule 8
>          &&
>            p[nation][english] == p[colour][red]        //Rule 1
>          &&
>            p[nation][swedish] == p[pet][dog]           //Rule 2
>          &&
>            p[nation][danish] == p[drink][tea]          //Rule 3
>          &&
>            p[colour][yellow] == p[cigs][dunhill]       //Rule 7
>          &&
>            p[pet][bird] == p[cigs][palmal]             //Rule 6
>          &&
>            p[drink][beer] == p[cigs][bluemasters]      //Rule 12
>          &&
>            p[nation][german] == p[cigs][prince]        //Rule 13
>          &&
>             p[colour][green] == p[drink][coffee]       //Rule 5
>          &&
>            abs(p[cigs][blends] - p[pet][cat]) == 1     //Rule 10
>          &&
>            abs(p[cigs][blends] - p[drink][water]) == 1 //Rule 15
>          &&
>            abs(p[pet][horse] - p[cigs][dunhill]) == 1  //Rule 11
>          &&
>            p[colour][green] < p[colour][white];        //Rule 4
> }
> 
> void Output(const vector< vector<int> >& p,
>                   unsigned               c
>            )
> {
>   ofstream text("solution.txt");
> 
>   for (int i = nation; i <= cigs; ++i)
>   {
>     for (int j = 0; j < p[i].size(); ++j)
>       text <<setw(20)
>            <<codes[i][ find(p[i].begin(), p[i].end(), j) - p[i].begin() ]; 
> //get inverse permutation
>     text <<endl;
>   }
>   text <<"\n\nTotal attempts: " <<c;
> 
>   text.close();
> }
> 
> void main(void)
> {
>   //srand( (unsigned) time(NULL) ); //optional RNG seeding
> 
>   int                   ramp[] = { 0, 1, 2, 3, 4 };
>   vector< vector<int> > permutations;
>   unsigned              counter(0);
>   for (int i = nation; i <= cigs; i++ )
>     permutations.push_back( vector<int>(ramp, ramp + 5) );
> 
>   do
>   {
>     for (int i = nation; i <= cigs; i++)
>       random_shuffle( permutations[i].begin(), permutations[i].end() );
>     if ( ! (++counter % 100000) )
>       cout <<"\rRe-Randomisations: " <<counter;
>   }
>   while ( ! ValidConstraints(permutations) );
> 
>   Output(permutations, counter);
> }

-- 
Yoann  Padioleau,  INSA de Rennes, France,   http://www.irisa.fr/prive/padiolea
Opinions expressed here are only mine. Je n'écris qu'à titre personnel.
**____   Get Free. Be Smart.  Simply use Linux and Free Software.   ____**