Einstein's Riddle

Petasis George petasis at iit.demokritos.gr
Wed Mar 14 07:40:00 CET 2001


"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...

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



More information about the Python-list mailing list