{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 2A.algo - L'\u00e9nigme d'Einstein et sa r\u00e9solution\n", "\n", "R\u00e9solution de l'\u00e9nigme [L'\u00e9nigme d'Einstein](http://fr.wikipedia.org/wiki/%C3%89nigme_d'Einstein). Impl\u00e9mentatin d'une solution \u00e0 base de r\u00e8gles."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": ["from io import StringIO\n", "from pandas import read_csv"]}, {"cell_type": "markdown", "metadata": {}, "source": ["[L'\u00e9nigme d'Einstein](http://fr.wikipedia.org/wiki/%C3%89nigme_d'Einstein) est une \u00e9nigme comme celle que r\u00e9soud [Hermionne](http://www.encyclopedie-hp.org/hogwarts/chamber_of_stone.php) dans le premier tome de Harry Potter. Je la reproduis ici :\n", "\n", "Il y a cinq maisons de cinq couleurs diff\u00e9rentes. Dans chacune de ces maisons, vit une personne de nationalit\u00e9 diff\u00e9rente. Chacune de ces personnes boit une boisson diff\u00e9rente, fume un cigare diff\u00e9rent et a un animal domestique diff\u00e9rent.\n", "\n", "1. L'Anglais vit dans la maison rouge.\n", "2. Le Su\u00e9dois a des chiens.\n", "3. Le Danois boit du th\u00e9.\n", "4. La maison verte est \u00e0 gauche de la maison blanche.\n", "5. Le propri\u00e9taire de la maison verte boit du caf\u00e9.\n", "6. La personne qui fume des Pall Mall a des oiseaux.\n", "7. Le propri\u00e9taire de la maison jaune fume des Dunhill.\n", "8. La personne qui vit dans la maison du centre boit du lait.\n", "9. Le Norv\u00e9gien habite dans la premi\u00e8re maison.\n", "10. L'homme qui fume des Blend vit \u00e0 c\u00f4t\u00e9 de celui qui a des chats.\n", "11. L'homme qui a un cheval est le voisin de celui qui fume des Dunhill.\n", "12. Le propri\u00e9taire qui fume des Blue Master boit de la bi\u00e8re.\n", "13. L'Allemand fume des prince.\n", "14. Le Norv\u00e9gien vit juste \u00e0 c\u00f4t\u00e9 de la maison bleue.\n", "15. L'homme qui fume des Blend a un voisin qui boit de l'eau.\n", "\n", "Question : Qui a le poisson ?\n", "\n", "Apr\u00e8s quelques essais, une bonne feuille de papier, on arrive \u00e0 reconstituer la solution apr\u00e8s de nombreuses d\u00e9ductions logiques et quelques essais. On peut voir aussi ce jeu comme un puzzle : chaque configuration est un pi\u00e8ce du puzzle dont la forme des bords est d\u00e9finie par toutes ces r\u00e8gles. Il faut trouver le seul embo\u00eetement possible sachant que parfois, une pi\u00e8ce peut s'embo\u00eeter avec plusieurs mais qu'il n'existe qu'une fa\u00e7on de les embo\u00eeter toutes ensemble. Ecrire un programme qui r\u00e9soud ce probl\u00e8me revient \u00e0 s'int\u00e9resser \u00e0 deux probl\u00e8mes :\n", "\n", "1. Comment d\u00e9finir une pi\u00e8ce du puzzle ?\n", "2. Comment parcourir toutes les combinaisons possibles ?\n", "\n", "Chaque r\u00e8gle ou pi\u00e8ce de puzzle peut \u00eatre exprimer comme une [clause](http://fr.wikipedia.org/wiki/Clause_de_Horn). Pour notre probl\u00e8me, chaque pi\u00e8ce du puzzle est simplement d\u00e9crite par un attribut (rouge, norv\u00e9gien) et un num\u00e9ro de maisons (1 \u00e0 5). Les r\u00e8gles d\u00e9finissent la compatibilit\u00e9 de deux pi\u00e8ces. On peut regrouper ces r\u00e8gles en cinq cat\u00e9gories :\n", "\n", "1. Un attribut est \u00e0 la position p (r\u00e8gle 9).\n", "2. Deux attributs sont \u00e9quivalents (r\u00e8gle 1).\n", "3. Deux attributs sont voisins (r\u00e8gle 11).\n", "4. Deux attributs sont ordonn\u00e9s par rapport aux positions (r\u00e8gle 4).\n", "5. Deux attributs font partie du m\u00eame ensemble et sont exclusives : on ne peut pas \u00eatre l'un et l'autre \u00e0 la fois (rouge et jaune par exemple).\n", "\n", "Une fois que chaque r\u00e8gle a \u00e9t\u00e9 exprim\u00e9e dans une de ces cinq cat\u00e9gories, il faut d\u00e9finir l'association de deux r\u00e8gles (ou clause) pour former une clause plus complexe. Trois cas possibles :\n", "\n", "1. Deux clauses sont compatibles : on peut avoir l'une et l'autre.\n", "2. Deux clauses sont incompatibles : on ne peut avoir l'une et l'autre.\n", "\n", "Dans le premier cas, la clause r\u00e9sultante est simplement qu'on peut la clause A et la clause B : $A \\, et\\, B$. Dans le second cas, il existe deux possibilit\u00e9s, on peut avoir l'une et l'oppos\u00e9 de l'autre ou l'inverse : $(A \\, et\\, non \\, B) \\, ou\\, (non \\, A \\, et\\, B)$.\n", "\n", "Avec cette description, il est plus facile d'exprimer le probl\u00e8me avec des objets informatiques ce que fait le programme suivant. Il explicite ensuite toutes les configurations compatibles avec une r\u00e8gle donn\u00e9e (mais pas toutes ensembles).\n", "\n", "On commence par la fonction [permutation](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/ensae_teaching_cs/special/einstein_prolog.html?highlight=permutation#ensae_teaching_cs.special.einstein_prolog.permutation) qui \u00e9num\u00e8re les permutations d'un ensemble :"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["def permutation(nb):\n", " per = []\n", " p = [i for i in range(0, nb)]\n", " while p[0] < nb:\n", " cont = False\n", " for i in range(1, nb):\n", " if p[i] in p[0:i]:\n", " cont = True\n", " break\n", "\n", " if not cont:\n", " per.append(copy.copy(p))\n", "\n", " p[nb-1] += 1\n", " for j in range(nb-1, 0, -1):\n", " if p[j] >= nb:\n", " p[j] = 0\n", " p[j-1] += 1\n", "\n", " return per"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["position \t: \n", " ou [(2, ('lait', 2))]\n", "position \t: \n", " ou [(0, ('norvegien', 1))]\n", "equivalence \t: \n", " ou [(0, ('Pall Mall', 3)), (0, ('oiseaux', 4))]\n", " ou [(1, ('Pall Mall', 3)), (1, ('oiseaux', 4))]\n", " ou [(2, ('Pall Mall', 3)), (2, ('oiseaux', 4))]\n", " ou [(3, ('Pall Mall', 3)), (3, ('oiseaux', 4))]\n", " ou [(4, ('Pall Mall', 3)), (4, ('oiseaux', 4))]\n", "equivalence \t: \n", " ou [(0, ('anglais', 1)), (0, ('rouge', 0))]\n", " ou [(1, ('anglais', 1)), (1, ('rouge', 0))]\n", " ou [(2, ('anglais', 1)), (2, ('rouge', 0))]\n", " ou [(3, ('anglais', 1)), (3, ('rouge', 0))]\n", " ou [(4, ('anglais', 1)), (4, ('rouge', 0))]\n", "equivalence \t: \n", " ou [(0, ('suedois', 1)), (0, ('chiens', 4))]\n", " ou [(1, ('suedois', 1)), (1, ('chiens', 4))]\n", " ou [(2, ('suedois', 1)), (2, ('chiens', 4))]\n", " ou [(3, ('suedois', 1)), (3, ('chiens', 4))]\n", " ou [(4, ('suedois', 1)), (4, ('chiens', 4))]\n", "equivalence \t: \n", " ou [(0, ('danois', 1)), (0, ('the', 2))]\n", " ou [(1, ('danois', 1)), (1, ('the', 2))]\n", " ou [(2, ('danois', 1)), (2, ('the', 2))]\n", " ou [(3, ('danois', 1)), (3, ('the', 2))]\n", " ou [(4, ('danois', 1)), (4, ('the', 2))]\n", "equivalence \t: \n", " ou [(0, ('vert', 0)), (0, ('cafe', 2))]\n", " ou [(1, ('vert', 0)), (1, ('cafe', 2))]\n", " ou [(2, ('vert', 0)), (2, ('cafe', 2))]\n", " ou [(3, ('vert', 0)), (3, ('cafe', 2))]\n", " ou [(4, ('vert', 0)), (4, ('cafe', 2))]\n", "equivalence \t: \n", " ou [(0, ('jaune', 0)), (0, ('Dunhill', 3))]\n", " ou [(1, ('jaune', 0)), (1, ('Dunhill', 3))]\n", " ou [(2, ('jaune', 0)), (2, ('Dunhill', 3))]\n", " ou [(3, ('jaune', 0)), (3, ('Dunhill', 3))]\n", " ou [(4, ('jaune', 0)), (4, ('Dunhill', 3))]\n", "equivalence \t: \n", " ou [(0, ('biere', 2)), (0, ('Bluemaster', 3))]\n", " ou [(1, ('biere', 2)), (1, ('Bluemaster', 3))]\n", " ou [(2, ('biere', 2)), (2, ('Bluemaster', 3))]\n", " ou [(3, ('biere', 2)), (3, ('Bluemaster', 3))]\n", " ou [(4, ('biere', 2)), (4, ('Bluemaster', 3))]\n", "equivalence \t: \n", " ou [(0, ('allemand', 1)), (0, ('Prince', 3))]\n", " ou [(1, ('allemand', 1)), (1, ('Prince', 3))]\n", " ou [(2, ('allemand', 1)), (2, ('Prince', 3))]\n", " ou [(3, ('allemand', 1)), (3, ('Prince', 3))]\n", " ou [(4, ('allemand', 1)), (4, ('Prince', 3))]\n", "voisin \t: \n", " ou [(0, ('Dunhill', 3)), (1, ('cheval', 4))]\n", " ou [(1, ('Dunhill', 3)), (0, ('cheval', 4))]\n", " ou [(1, ('Dunhill', 3)), (2, ('cheval', 4))]\n", " ou [(2, ('Dunhill', 3)), (1, ('cheval', 4))]\n", " ou [(2, ('Dunhill', 3)), (3, ('cheval', 4))]\n", " ou [(3, ('Dunhill', 3)), (2, ('cheval', 4))]\n", " ou [(3, ('Dunhill', 3)), (4, ('cheval', 4))]\n", " ou [(4, ('Dunhill', 3)), (3, ('cheval', 4))]\n", "voisin \t: \n", " ou [(0, ('norvegien', 1)), (1, ('bleu', 0))]\n", " ou [(1, ('norvegien', 1)), (0, ('bleu', 0))]\n", " ou [(1, ('norvegien', 1)), (2, ('bleu', 0))]\n", " ou [(2, ('norvegien', 1)), (1, ('bleu', 0))]\n", " ou [(2, ('norvegien', 1)), (3, ('bleu', 0))]\n", " ou [(3, ('norvegien', 1)), (2, ('bleu', 0))]\n", " ou [(3, ('norvegien', 1)), (4, ('bleu', 0))]\n", " ou [(4, ('norvegien', 1)), (3, ('bleu', 0))]\n", "voisin \t: \n", " ou [(0, ('Blend', 3)), (1, ('eau', 2))]\n", " ou [(1, ('Blend', 3)), (0, ('eau', 2))]\n", " ou [(1, ('Blend', 3)), (2, ('eau', 2))]\n", " ou [(2, ('Blend', 3)), (1, ('eau', 2))]\n", " ou [(2, ('Blend', 3)), (3, ('eau', 2))]\n", " ou [(3, ('Blend', 3)), (2, ('eau', 2))]\n", " ou [(3, ('Blend', 3)), (4, ('eau', 2))]\n", " ou [(4, ('Blend', 3)), (3, ('eau', 2))]\n", "voisin \t: \n", " ou [(0, ('Blend', 3)), (1, ('chats', 4))]\n", " ou [(1, ('Blend', 3)), (0, ('chats', 4))]\n", " ou [(1, ('Blend', 3)), (2, ('chats', 4))]\n", " ou [(2, ('Blend', 3)), (1, ('chats', 4))]\n", " ou [(2, ('Blend', 3)), (3, ('chats', 4))]\n", " ou [(3, ('Blend', 3)), (2, ('chats', 4))]\n", " ou [(3, ('Blend', 3)), (4, ('chats', 4))]\n", " ou [(4, ('Blend', 3)), (3, ('chats', 4))]\n", "avant \t: \n", " ou [(0, ('vert', 0)), (1, ('blanc', 0))]\n", " ou [(0, ('vert', 0)), (2, ('blanc', 0))]\n", " ou [(1, ('vert', 0)), (2, ('blanc', 0))]\n", " ou [(0, ('vert', 0)), (3, ('blanc', 0))]\n", " ou [(1, ('vert', 0)), (3, ('blanc', 0))]\n", " ou [(2, ('vert', 0)), (3, ('blanc', 0))]\n", " ou [(0, ('vert', 0)), (4, ('blanc', 0))]\n", " ou [(1, ('vert', 0)), (4, ('blanc', 0))]\n", " ou [(2, ('vert', 0)), (4, ('blanc', 0))]\n", " ou [(3, ('vert', 0)), (4, ('blanc', 0))]\n", "ensemble \t: \n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('rouge', 0)), (3, ('blanc', 0)), (4, ('vert', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('rouge', 0)), (3, ('vert', 0)), (4, ('blanc', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('blanc', 0)), (3, ('rouge', 0)), (4, ('vert', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('blanc', 0)), (3, ('vert', 0)), (4, ('rouge', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('vert', 0)), (3, ('rouge', 0)), (4, ('blanc', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('bleu', 0)), (2, ('vert', 0)), (3, ('blanc', 0)), (4, ('rouge', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('rouge', 0)), (2, ('bleu', 0)), (3, ('blanc', 0)), (4, ('vert', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('rouge', 0)), (2, ('bleu', 0)), (3, ('vert', 0)), (4, ('blanc', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('rouge', 0)), (2, ('blanc', 0)), (3, ('bleu', 0)), (4, ('vert', 0))]\n", " ou [(0, ('jaune', 0)), (1, ('rouge', 0)), (2, ('blanc', 0)), (3, ('vert', 0)), (4, ('bleu', 0))]\n", "ensemble \t: \n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('anglais', 1)), (3, ('allemand', 1)), (4, ('suedois', 1))]\n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('anglais', 1)), (3, ('suedois', 1)), (4, ('allemand', 1))]\n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('allemand', 1)), (3, ('anglais', 1)), (4, ('suedois', 1))]\n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('allemand', 1)), (3, ('suedois', 1)), (4, ('anglais', 1))]\n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('suedois', 1)), (3, ('anglais', 1)), (4, ('allemand', 1))]\n", " ou [(0, ('danois', 1)), (1, ('norvegien', 1)), (2, ('suedois', 1)), (3, ('allemand', 1)), (4, ('anglais', 1))]\n", " ou [(0, ('danois', 1)), (1, ('anglais', 1)), (2, ('norvegien', 1)), (3, ('allemand', 1)), (4, ('suedois', 1))]\n", " ou [(0, ('danois', 1)), (1, ('anglais', 1)), (2, ('norvegien', 1)), (3, ('suedois', 1)), (4, ('allemand', 1))]\n", " ou [(0, ('danois', 1)), (1, ('anglais', 1)), (2, ('allemand', 1)), (3, ('norvegien', 1)), (4, ('suedois', 1))]\n", "ensemble \t: \n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('lait', 2)), (3, ('cafe', 2)), (4, ('biere', 2))]\n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('lait', 2)), (3, ('biere', 2)), (4, ('cafe', 2))]\n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('cafe', 2)), (3, ('lait', 2)), (4, ('biere', 2))]\n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('cafe', 2)), (3, ('biere', 2)), (4, ('lait', 2))]\n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('biere', 2)), (3, ('lait', 2)), (4, ('cafe', 2))]\n", " ou [(0, ('eau', 2)), (1, ('the', 2)), (2, ('biere', 2)), (3, ('cafe', 2)), (4, ('lait', 2))]\n", " ou [(0, ('eau', 2)), (1, ('lait', 2)), (2, ('the', 2)), (3, ('cafe', 2)), (4, ('biere', 2))]\n", " ou [(0, ('eau', 2)), (1, ('lait', 2)), (2, ('the', 2)), (3, ('biere', 2)), (4, ('cafe', 2))]\n", " ou [(0, ('eau', 2)), (1, ('lait', 2)), (2, ('cafe', 2)), (3, ('the', 2)), (4, ('biere', 2))]\n", " ou [(0, ('eau', 2)), (1, ('lait', 2)), (2, ('cafe', 2)), (3, ('biere', 2)), (4, ('the', 2))]\n", "ensemble \t: \n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Pall Mall', 3)), (3, ('Prince', 3)), (4, ('Bluemaster', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Pall Mall', 3)), (3, ('Bluemaster', 3)), (4, ('Prince', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Prince', 3)), (3, ('Pall Mall', 3)), (4, ('Bluemaster', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Prince', 3)), (3, ('Bluemaster', 3)), (4, ('Pall Mall', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Bluemaster', 3)), (3, ('Pall Mall', 3)), (4, ('Prince', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Blend', 3)), (2, ('Bluemaster', 3)), (3, ('Prince', 3)), (4, ('Pall Mall', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Pall Mall', 3)), (2, ('Blend', 3)), (3, ('Prince', 3)), (4, ('Bluemaster', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Pall Mall', 3)), (2, ('Blend', 3)), (3, ('Bluemaster', 3)), (4, ('Prince', 3))]\n", " ou [(0, ('Dunhill', 3)), (1, ('Pall Mall', 3)), (2, ('Prince', 3)), (3, ('Blend', 3)), (4, ('Bluemaster', 3))]\n", "ensemble \t: \n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('oiseaux', 4)), (3, ('poisson', 4)), (4, ('chiens', 4))]\n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('oiseaux', 4)), (3, ('chiens', 4)), (4, ('poisson', 4))]\n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('poisson', 4)), (3, ('oiseaux', 4)), (4, ('chiens', 4))]\n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('poisson', 4)), (3, ('chiens', 4)), (4, ('oiseaux', 4))]\n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('chiens', 4)), (3, ('oiseaux', 4)), (4, ('poisson', 4))]\n", " ou [(0, ('chats', 4)), (1, ('cheval', 4)), (2, ('chiens', 4)), (3, ('poisson', 4)), (4, ('oiseaux', 4))]\n", " ou [(0, ('chats', 4)), (1, ('oiseaux', 4)), (2, ('cheval', 4)), (3, ('poisson', 4)), (4, ('chiens', 4))]\n", " ou [(0, ('chats', 4)), (1, ('oiseaux', 4)), (2, ('cheval', 4)), (3, ('chiens', 4)), (4, ('poisson', 4))]\n", " ou [(0, ('chats', 4)), (1, ('oiseaux', 4)), (2, ('poisson', 4)), (3, ('cheval', 4)), (4, ('chiens', 4))]\n"]}], "source": ["import copy\n", "\n", "ttcouleur = [\"jaune\", \"bleu\", \"rouge\", \"blanc\", \"vert\"]\n", "ttnationalite = [\"danois\", \"norvegien\", \"anglais\", \"allemand\", \"suedois\"]\n", "ttboisson = [\"eau\", \"the\", \"lait\", \"cafe\", \"biere\"]\n", "ttcigare = [\"Dunhill\", \"Blend\", \"Pall Mall\", \"Prince\", \"Bluemaster\"]\n", "ttanimal = [\"chats\", \"cheval\", \"oiseaux\", \"poisson\", \"chiens\"]\n", "ensemble = [ttcouleur, ttnationalite, ttboisson, ttcigare, ttanimal]\n", "\n", "\n", "class Rule:\n", " \"\"\"\n", " This class defines a constraint of the problem\n", " or a clause (see `http://en.wikipedia.org/wiki/Clause_(logic)`)\n", "\n", " There are 5 different types of clauses described by Einstein's enigma\n", " each of them is described by a different class. There are defined by classes:\n", " @ref cl RulePosition, @ref cl RuleEquivalence, @ref cl RuleVoisin,\n", " @ref cl RuleAvant, @ref cl RuleEnsemble.\n", " \"\"\"\n", "\n", " def __init__(self):\n", " \"\"\"\n", " constructor\n", " \"\"\"\n", " #: name of the rule\n", " self.name = None\n", " #: set of clauses\n", " self.set = None\n", "\n", " def genere(self):\n", " \"\"\"\n", " Generates all possible clauses (list of lists)\n", " (`l[0][0]` et `l[0][1]`) ou (`l[1][0]` et `l[1][1]`),\n", " a clause is a triplet of\n", " `(person, (property, category))`.\n", " \"\"\"\n", " return None\n", "\n", " def __str__(self):\n", " \"\"\"\n", " display\n", " \"\"\"\n", " if self.name != None:\n", " if \"clauses\" not in self.__dict__:\n", " s = self.name + \" \\t: \"\n", " a = self.genere()\n", " for al in a:\n", " st = \"\\n ou \" + str(al)\n", " if len(st) > 260:\n", " st = st[:260] + \"...\"\n", " s += st\n", " if len(s) > 1000:\n", " break\n", " return s\n", " else:\n", " s = self.name + \" \\t: \" + str(self.set)\n", " for al in self.clauses:\n", " st = \"\\n ou \" + str(al)\n", " if len(st) > 260:\n", " st = st[:260] + \"...\"\n", " s += st\n", " if len(s) > 1000:\n", " break\n", " return s\n", " else:\n", " return \"None\"\n", "\n", " def combine(self, cl1, cl2):\n", " \"\"\"\n", " Combine two clauses, two cases:\n", " \n", " 1. nothing in common or everything in common --> concatenation of clauses\n", " 2. a position or a property in common --> null clause\n", "\n", " :param cl1: clause 1\n", " :param cl2: clause 2\n", " :return: the new clause\n", "\n", " A clause is a @ref cl Rule.\n", " \"\"\"\n", " # incompatibility\n", " for p1 in cl1:\n", " for p2 in cl2:\n", " if p1[1][0] == p2[1][0]: # same property\n", " if p1[0] != p2[0]: # but different positions\n", " return None\n", " if p1[0] == p2[0]: # same person\n", " if p1[1][1] == p2[1][1] and p1[1][0] != p2[1][0]:\n", " # same category but different properties\n", " return None\n", " # compatibility\n", " r = copy.deepcopy(cl1)\n", " for c in cl2:\n", " if c not in r:\n", " r.append(c)\n", " return r\n", "\n", " def combine_cross_sets(self, set1, set2):\n", " \"\"\"\n", " Combines two sets of clauses.\n", "\n", " :param set1: set of clauses 1\n", " :param set2: set of clauses 2\n", " :return: combination\n", " \"\"\"\n", " if len(set1) == 0:\n", " return copy.deepcopy(set2)\n", " if len(set2) == 0:\n", " return copy.deepcopy(set1)\n", " res = []\n", " for cl1 in set1:\n", " for cl2 in set2:\n", " r = self.combine(cl1, cl2)\n", " if r != None:\n", " res.append(r)\n", " return res\n", "\n", "\n", "class RulePosition (Rule):\n", " \"\"\"\n", " p1 at position\n", " \"\"\"\n", "\n", " def __init__(self, p1, pos):\n", " self.set = [p1]\n", " self.name = \"position\"\n", " self.position = pos\n", "\n", " def genere(self):\n", " \"\"\"\n", " overrides method ``genere``\n", " \"\"\"\n", " return [[(self.position, self.set[0])]]\n", "\n", "\n", "class RuleEquivalence (Rule):\n", " \"\"\"\n", " p1 equivalent to p2\n", " \"\"\"\n", "\n", " def __init__(self, p1, p2):\n", " self.set = [p1, p2]\n", " self.name = \"equivalence\"\n", "\n", " def genere(self):\n", " \"\"\"\n", " overrides method ``genere``\n", " \"\"\"\n", " l = []\n", " for i in range(0, 5):\n", " l.append([(i, self.set[0]), (i, self.set[1])])\n", " return l\n", "\n", "\n", "class RuleVoisin (Rule):\n", " \"\"\"\n", " p1 and p2 are neighbors\n", " \"\"\"\n", "\n", " def __init__(self, p1, p2):\n", " self.set = [p1, p2]\n", " self.name = \"voisin\"\n", "\n", " def genere(self):\n", " \"\"\"\n", " overrides method ``genere``\n", " \"\"\"\n", " l = []\n", " for i in range(0, 4):\n", " l.append([(i, self.set[0]), (i+1, self.set[1])])\n", " l.append([(i+1, self.set[0]), (i, self.set[1])])\n", " return l\n", "\n", "\n", "class RuleAvant (Rule):\n", " \"\"\"\n", " p1 before p2\n", " \"\"\"\n", "\n", " def __init__(self, p1, p2):\n", " self.set = [p1, p2]\n", " self.name = \"avant\"\n", "\n", " def genere(self):\n", " \"\"\"\n", " overrides method ``genere``\n", " \"\"\"\n", " l = []\n", " for j in range(1, 5):\n", " for i in range(0, j):\n", " l.append([(i, self.set[0]), (j, self.set[1])])\n", " return l\n", "\n", "\n", "class RuleEnsemble (Rule):\n", " \"\"\"\n", " permutation of the elements of a category\n", " \"\"\"\n", "\n", " def __init__(self, set, categorie):\n", " self.set = [(s, categorie) for s in set]\n", " self.name = \"ensemble\"\n", "\n", " def genere(self):\n", " \"\"\"\n", " overrides method ``genere``\n", " \"\"\"\n", " l = []\n", " per = permutation(5)\n", " for p in per:\n", " tl = []\n", " for i in range(0, len(p)):\n", " tl.append((i, self.set[p[i]]))\n", " l.append(tl)\n", " return l\n", "\n", "\n", "def find(p):\n", " for i in range(0, len(ensemble)):\n", " if p in ensemble[i]:\n", " return (p, i)\n", " return None\n", "\n", "\n", "regle = []\n", "\n", "regle.append(RulePosition(find(\"lait\"), 2))\n", "regle.append(RulePosition(find(\"norvegien\"), 0))\n", "\n", "regle.append(RuleEquivalence(find(\"Pall Mall\"), find(\"oiseaux\")))\n", "regle.append(RuleEquivalence(find(\"anglais\"), find(\"rouge\")))\n", "regle.append(RuleEquivalence(find(\"suedois\"), find(\"chiens\")))\n", "regle.append(RuleEquivalence(find(\"danois\"), find(\"the\")))\n", "regle.append(RuleEquivalence(find(\"vert\"), find(\"cafe\")))\n", "regle.append(RuleEquivalence(find(\"jaune\"), find(\"Dunhill\")))\n", "regle.append(RuleEquivalence(find(\"biere\"), find(\"Bluemaster\")))\n", "regle.append(RuleEquivalence(find(\"allemand\"), find(\"Prince\")))\n", "\n", "regle.append(RuleVoisin(find(\"Dunhill\"), find(\"cheval\")))\n", "regle.append(RuleVoisin(find(\"norvegien\"), find(\"bleu\")))\n", "regle.append(RuleVoisin(find(\"Blend\"), find(\"eau\")))\n", "regle.append(RuleVoisin(find(\"Blend\"), find(\"chats\")))\n", "\n", "regle.append(RuleAvant(find(\"vert\"), find(\"blanc\")))\n", "\n", "regle.append(RuleEnsemble(ttcouleur, 0))\n", "regle.append(RuleEnsemble(ttnationalite, 1))\n", "regle.append(RuleEnsemble(ttboisson, 2))\n", "regle.append(RuleEnsemble(ttcigare, 3))\n", "regle.append(RuleEnsemble(ttanimal, 4))\n", "\n", "\n", "for r in regle:\n", " print(r)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Parmi tous ces cas possibles, beaucoup sont incompatibles. L'objectif est d'\u00e9liminer tous ceux qui sont incompatibles pour ne garer que les 25 qui constituent la solution. L'algorithme est inspir\u00e9 de la [logique des pr\u00e9dicats](http://fr.wikipedia.org/wiki/Calcul_des_pr%C3%A9dicats). De mani\u00e8re r\u00e9cursive, la fonction ``solve`` combine les clauses jusqu'\u00e0 ce qu'il ne puisse plus continuer :\n", "\n", "1. Soit le m\u00eame attribut appara\u00eet \u00e0 deux positions diff\u00e9rentes : incompatibilit\u00e9.\n", "2. Soit deux attributs apparaissent \u00e0 la m\u00eame position : incompatibilit\u00e9.\n", "3. Soit il ne reste plus qu'une seule clause : c'est la solution."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["* 10 - properties in place : 14\n", "* 20 - properties in place : 12\n", "* 30 - properties in place : 21\n", "* 40 - properties in place : 19\n", "* 50 - properties in place : 22\n", "* 60 - properties in place : 21\n", "* 70 - properties in place : 22\n", "* 80 - properties in place : 12\n", "* 90 - properties in place : 14\n", "* 100 - properties in place : 24\n", "* 110 - properties in place : 22\n", "* 120 - properties in place : 16\n", "* 130 - properties in place : 12\n"]}, {"data": {"text/html": ["
\n", " | 0 | \n", "1 | \n", "2 | \n", "3 | \n", "4 | \n", "
---|---|---|---|---|---|
0 | \n", "jaune | \n", "norvegien | \n", "eau | \n", "Dunhill | \n", "chats | \n", "
1 | \n", "bleu | \n", "danois | \n", "the | \n", "Blend | \n", "cheval | \n", "
2 | \n", "rouge | \n", "anglais | \n", "lait | \n", "Pall Mall | \n", "oiseaux | \n", "
3 | \n", "vert | \n", "allemand | \n", "cafe | \n", "Prince | \n", "poisson | \n", "
4 | \n", "blanc | \n", "suedois | \n", "biere | \n", "Bluemaster | \n", "chiens | \n", "