Coverage for src/ensae_teaching_cs/special/einstein_prolog.py : 82%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief This programs solves `Einstein's riddle <http://en.wikipedia.org/wiki/Zebra_Puzzle>`_ ou en
5Français `Intégramme <http://fr.wikipedia.org/wiki/Int%C3%A9gramme>`_. The algorithm is based
6on logic and its `clause <http://en.wikipedia.org/wiki/Clause_(logic)>`_.
7"""
8import copy
11#: definition of all possible values (French terms)
12#: colors
13ttcouleur = ["jaune", "bleu", "rouge", "blanc", "vert"]
14#: nationalities
15ttnationalite = ["danois", "norvegien", "anglais", "allemand", "suedois"]
16#: drinks
17ttboisson = ["eau", "the", "lait", "cafe", "biere"]
18#: smoke brand
19ttcigare = ["Dunhill", "Blend", "Pall Mall", "Prince", "Bluemaster"]
20#: animal
21ttanimal = ["chats", "cheval", "oiseaux", "poisson", "chiens"]
23#: all possibles values
24ensemble = [ttcouleur, ttnationalite, ttboisson, ttcigare, ttanimal]
27def permutation(nb):
28 """
29 Compute all permutations of set [[ 1, 2, ..., nb ]].
30 Example for 3:
32 ::
34 [[0, 1, 2], [0, 2, 1], [1, 0, 2],
35 [1, 2, 0], [2, 0, 1], [2, 1, 0]]
37 @param nb permutation over the set [[1..n]]
38 @return list of all possible permutations
40 @warning This method can be very long if nb is high (>10).
42 This function does something very similar to
43 `itertools.permutations <https://docs.python.org/3/library/itertools.html#itertools.permutations>`_.
44 """
45 per = []
46 p = [i for i in range(0, nb)]
47 while p[0] < nb:
48 next = False
49 for i in range(1, nb):
50 if p[i] in p[0:i]:
51 next = True
52 break
54 if not next:
55 per.append(copy.copy(p))
57 p[nb - 1] += 1
58 for j in range(nb - 1, 0, -1):
59 if p[j] >= nb:
60 p[j] = 0
61 p[j - 1] += 1
63 return per
66class Rule:
68 """
69 This class defines a constraint of the problem
70 or a clause (see `http://en.wikipedia.org/wiki/Clause_(logic)`)
72 There are 5 different types of clauses described by Einstein's enigma
73 each of them is described by a different class. There are defined by classes:
74 @ref cl RulePosition, @ref cl RuleEquivalence, @ref cl RuleVoisin,
75 @ref cl RuleAvant, @ref cl RuleEnsemble.
76 """
78 def __init__(self):
79 #: name of the rule
80 self.name = None
81 #: set of clauses
82 self.set = None
84 def genere(self):
85 """
86 Generates all possible clauses (list of lists)
87 (l [0][0] et l [0][1]) ou (l [1][0] et l [1][1]),
88 a clause is a triplet of
89 (person, (property, category) )
90 """
91 raise NotImplementedError()
93 def __str__(self):
94 """
95 display
96 """
97 if self.name is not None:
98 if not hasattr(self, "clauses"):
99 s = self.name + " \t: "
100 a = self.genere()
101 for al in a:
102 st = "\n ou " + str(al)
103 if len(st) > 260:
104 st = st[:260] + "..."
105 s += st
106 if len(s) > 1000:
107 break
108 return s
109 else:
110 s = self.name + " \t: " + str(self.set)
111 for al in self.clauses:
112 st = "\n ou " + str(al)
113 if len(st) > 260:
114 st = st[:260] + "..."
115 s += st
116 if len(s) > 1000:
117 break
118 return s
119 else:
120 return None
122 def combine(self, cl1, cl2):
123 """
124 combine two clauses, two cases :
125 1. nothing in common or everything in common --> concatenation of clauses
126 2. a position or a property in common --> null clause
128 @param cl1 clause 1
129 @param cl2 clause 2
130 @return the new clause
132 A clause is a @ref cl Rule.
133 """
134 # incompatibility
135 for p1 in cl1:
136 for p2 in cl2:
137 if p1[1][0] == p2[1][0]: # same property
138 if p1[0] != p2[0]: # but different positions
139 return None
140 if p1[0] == p2[0]: # same person
141 if p1[1][1] == p2[1][1] and p1[1][0] != p2[1][0]:
142 # same category but different properties
143 return None
144 # compatibility
145 r = copy.deepcopy(cl1)
146 for c in cl2:
147 if c not in r:
148 r.append(c)
149 return r
151 def combine_cross_sets(self, set1, set2):
152 """
153 combines two sets of clauses
154 @param set1 set of clauses 1
155 @param set2 set of clauses 2
156 @return combination
157 """
158 if len(set1) == 0:
159 return copy.deepcopy(set2)
160 if len(set2) == 0:
161 return copy.deepcopy(set1)
162 res = []
163 for cl1 in set1:
164 for cl2 in set2:
165 r = self.combine(cl1, cl2)
166 if r is not None:
167 res.append(r)
168 return res
171class RulePosition(Rule):
172 """
173 p1 at position
174 """
176 def __init__(self, p1, pos):
177 Rule.__init__(self)
178 self.set = [p1]
179 self.name = "position"
180 self.position = pos
182 def genere(self):
183 """
184 overrides method ``genere``
185 """
186 return [[(self.position, self.set[0])]]
189class RuleEquivalence(Rule):
190 """
191 p1 equivalent to p2
192 """
194 def __init__(self, p1, p2):
195 Rule.__init__(self)
196 self.set = [p1, p2]
197 self.name = "equivalence"
199 def genere(self):
200 """
201 overrides method ``genere``
202 """
203 lt = []
204 for i in range(0, 5):
205 lt.append([(i, self.set[0]), (i, self.set[1])])
206 return lt
209class RuleVoisin(Rule):
210 """
211 p1 and p2 are neighbors
212 """
214 def __init__(self, p1, p2):
215 Rule.__init__(self)
216 self.set = [p1, p2]
217 self.name = "voisin"
219 def genere(self):
220 """
221 overrides method ``genere``
222 """
223 lt = []
224 for i in range(0, 4):
225 lt.append([(i, self.set[0]), (i + 1, self.set[1])])
226 lt.append([(i + 1, self.set[0]), (i, self.set[1])])
227 return lt
230class RuleAvant(Rule):
231 """
232 p1 before p2
233 """
235 def __init__(self, p1, p2):
236 Rule.__init__(self)
237 self.set = [p1, p2]
238 self.name = "avant"
240 def genere(self):
241 """
242 overrides method ``genere``
243 """
244 lt = []
245 for j in range(1, 5):
246 for i in range(0, j):
247 lt.append([(i, self.set[0]), (j, self.set[1])])
248 return lt
251class RuleEnsemble(Rule):
253 """
254 permutation of the elements of a category
255 """
257 def __init__(self, sets, categorie):
258 Rule.__init__(self)
259 self.set = [(s, categorie) for s in sets]
260 self.name = "ensemble"
262 def genere(self):
263 """
264 overrides method ``genere``
265 """
266 lt = []
267 per = permutation(5)
268 for p in per:
269 tl = []
270 for i in range(0, len(p)):
271 tl.append((i, self.set[p[i]]))
272 lt.append(tl)
273 return lt
276class Enigma:
278 """
279 this class solves the enigma
280 """
282 def __init__(self, display=True):
283 """
284 we describe the enigma using the classes we defined above
285 @param display if True, use print to print some information
286 """
287 self.regle = []
289 self.regle.append(RulePosition(self.find("lait"), 2))
290 self.regle.append(RulePosition(self.find("norvegien"), 0))
292 self.regle.append(
293 RuleEquivalence(
294 self.find("Pall Mall"),
295 self.find("oiseaux")))
296 self.regle.append(
297 RuleEquivalence(
298 self.find("anglais"),
299 self.find("rouge")))
300 self.regle.append(
301 RuleEquivalence(
302 self.find("suedois"),
303 self.find("chiens")))
304 self.regle.append(
305 RuleEquivalence(
306 self.find("danois"),
307 self.find("the")))
308 self.regle.append(
309 RuleEquivalence(
310 self.find("vert"),
311 self.find("cafe")))
312 self.regle.append(
313 RuleEquivalence(
314 self.find("jaune"),
315 self.find("Dunhill")))
316 self.regle.append(
317 RuleEquivalence(
318 self.find("biere"),
319 self.find("Bluemaster")))
320 self.regle.append(
321 RuleEquivalence(
322 self.find("allemand"),
323 self.find("Prince")))
325 self.regle.append(
326 RuleVoisin(
327 self.find("Dunhill"),
328 self.find("cheval")))
329 self.regle.append(
330 RuleVoisin(
331 self.find("norvegien"),
332 self.find("bleu")))
333 self.regle.append(RuleVoisin(self.find("Blend"), self.find("eau")))
334 self.regle.append(RuleVoisin(self.find("Blend"), self.find("chats")))
336 self.regle.append(RuleAvant(self.find("vert"), self.find("blanc")))
338 self.regle.append(RuleEnsemble(ttcouleur, 0))
339 self.regle.append(RuleEnsemble(ttnationalite, 1))
340 self.regle.append(RuleEnsemble(ttboisson, 2))
341 self.regle.append(RuleEnsemble(ttcigare, 3))
342 self.regle.append(RuleEnsemble(ttanimal, 4))
344 for r in self.regle:
345 r.clauses = r.genere()
346 r.utilise = False
348 self.count = 0
350 def find(self, p):
351 """
352 finds a clause in the different sets of clause (houses, colors, ...)
354 @param p clause
355 @return tuple (clause, position)
356 """
357 for i in range(0, len(ensemble)):
358 if p in ensemble[i]:
359 return (p, i)
360 return None
362 def __str__(self):
363 """
364 usual
365 """
366 if "solution" not in self.__dict__ or self.solution is None or len(
367 self.solution) == 0:
368 if self.count > 0:
369 s = "solution impossible apres " + \
370 str(self.count) + " iterations \n"
371 else:
372 s = ""
373 for r in self.regle:
374 s += str(r) + "\n"
375 return s
376 else:
377 sr = ["solution, iteration " + str(self.count)]
378 matrix = [list(" " * 5) for _ in range(0, 5)]
379 for row in self.solution:
380 i = row[0]
381 j = row[1][1]
382 s = row[1][0]
383 matrix[i][j] = s + " " * (10 - len(s))
384 for row in matrix:
385 sr.append(", ".join(row))
386 classic = "\n".join(sr[1:])
387 html = classic.replace(",",
388 "</td><tr>").replace("\n",
389 "</td></tr>\n<tr><td>")
390 return sr[0] + "\n" + "\n".join([
391 classic,
392 "<table>",
393 "<tr><td>" + html + "</td></tr>",
394 "</table>"])
396 def solve(self, solution=None, logf=print): # solution = [ ]) :
397 """
398 Solves the enigma by eploring in deepness,
399 the method is recursive
401 @param solution [] empty at the beginning, recursively used then
402 @return solution
403 """
404 if solution is None:
405 solution = []
406 self.count += 1
407 if self.count % 10 == 0:
408 logf(
409 "*",
410 self.count,
411 " - properties in place : ",
412 len(solution) -
413 1)
415 if len(solution) == 25:
416 # we know the solution must contain 25 clauses,
417 # if are here than the problem is solved unless some
418 # incompatibility
419 for r in self.regle:
420 cl = r.combine_cross_sets([solution], r.clauses)
421 if cl is None or len(cl) == 0:
422 # the solution is incompatible with a solution
423 return None
424 self.solution = solution
425 return solution
427 # we are looking for the rule which generates the least possible clauses
428 # in order to reduce the number of possibilities as much as possible
429 # the research could be represented as a tree, we avoid creating two
430 # many paths
431 best = None
432 rule = None
434 for r in self.regle:
436 cl = r.combine_cross_sets([solution], r.clauses)
438 if cl is None:
439 # the solution is incompatible with a solution
440 return None
442 # we check rule r is bringing back some results
443 for c in cl:
444 if len(c) > len(solution):
445 break
446 else:
447 cl = None
449 if cl is not None and (best is None or len(best) > len(cl)):
450 best = cl
451 rule = r
453 if best is None:
454 # the solution is incompatible with a solution
455 return None
457 rule.utilise = True
459 # we test all clauses
460 for c in best:
461 r = self.solve(c, logf=logf)
462 if r is not None:
463 # we found
464 return r
466 rule.utilise = False # impossible
467 return None
470if __name__ == "__main__":
471 en = Enigma()
472 print(en)
473 print("-----------------------------\n")
474 en.solve()
475 print("-----------------------------\n")
476 print(en)