# Intégramme de Lewis Carroll, version simplifiée # Cécile Pierrot # La commande à lancer est : solution() ############################################################################# ############## QUESTION 1 ############################## #Declaration des criteres pris en compte dans l'enonce #list[str] nati=["anglais","espagnol","islandais","norvegien","slovene"] #list[str] prof=["ingenieur","sculpteur","diplomate","medecin","violoniste"] #list[str] anim=["chien","ane","renard","cheval","zebre"] #Declaration d'un objet approprie #type maison = tuple[str,str,str] ############################################################################# ############## QUESTION 3 ############################## def modifierliste(L,i,n): """list[int]*int*int->list[int] hypo : i apparait exactement une fois dans la liste L, qui est au moins de longueur 1 retourne la liste L ou l'on a remplace l'entier i (qui apparait) par l'entier n""" #LR:list[int] LR=[] #e : int for e in L: if e==i: LR.append(n) else: LR.append(e) return LR #jeu de tests assert modifierliste([1,2,3],3,5)==[1,2,5] def permutation_entiers(n): """int->list[list[int]] hypo : n >=1 retourne la liste des n! permutations possibles des entiers compris entre 0 et n-1. Une permutation est representee elle-meme par une liste d'entiers, celle des images.""" if n==1: return [[0]] else: #L : list[list[int]] L=[] # c'est la liste de retour que l'on complete pas à pas # i : int for i in range(0,n): #Lauxgrande : list[list[int]] LLauxgrande=permutation_entiers(n-1) #On travaille de manière récursive #j : int for j in range(0,len(LLauxgrande)): #Lauxpetite:list[int] Lauxpetite=modifierliste(LLauxgrande[j],i,n-1)#Lauxgrande[j] est une petite liste, ie une seule permutation de n-1 elts #On la modifie pour remplacer l'elt i par l'elt manquant, c'est à dire n L.append([i]+Lauxpetite) return L #jeu de tests assert permutation_entiers(1)==[[0]] assert permutation_entiers(3)==[[0, 2, 1], [0, 1, 2], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] def permutation(L): """list[alpha]->list[list[alpha]] hypothese : len(L)!=0 retourne la liste composee de toutes les listes possibles crees a partir des elements de L et dont les elements ontete permutes. La liste de retour a donc pour longueur len(L)!""" #LL:list[list[int]] LL=permutation_entiers(len(L)) #LLR : list[list[alpha]] LLR=[] # La liste resultat. On traduit simplement les entiers en chaines de caracteres #liste:list[int] for liste in LL: #listealpha:list[alpha] listealpha=[] #entier:int for entier in liste: listealpha.append(L[entier]) LLR.append(listealpha) return LLR #jeu de tests assert permutation(['lewis'])==[['lewis']] assert permutation(["charles","lutwidge","dodgson"])==[['charles', 'dodgson', 'lutwidge'], ['charles', 'lutwidge', 'dodgson'], ['lutwidge', 'charles', 'dodgson'], ['lutwidge', 'dodgson', 'charles'], ['dodgson', 'charles', 'lutwidge'], ['dodgson', 'lutwidge', 'charles']] ############################################################################# ############## QUESTION 4 ############################## #Attention, si on change le probleme, il faut changer cette fonction def verification(config): """list[maison]->bool Hypothese : config est une liste de maison utilisant une seule et unique fois chaque critère Retourne True si et seulement si config vérifie toutes les contraintes """ #conditions classiques : 1,2,3,4,9 On deconstruit chaque maison et on vérifie #qu'il n'y a pas d'incohérence. #place:int place=-1 #pour retenir certains elements necessaires aux conditions spatiales for (n,p,a) in config: place=place+1 if n=="anglais": if not (p=="sculpteur" or p=="medecin"): return False elif n=="espagnol": if not a=="chien": return False elif n=="islandais": #placeislandais:int placeislandais=place if not p=="ingenieur": return False elif n=="norvegien": #placenorvegien:int placenorvegien=place if p=="violoniste": return False else: #placeslovene:int placeslovene=place if p=="sculpteur": if not a=="ane": return False elif p=="medecin": #placemedecin:int placemedecin=place elif p=="diplomate": #placediplomate:int placediplomate=place if a=="renard": #placerenard :int placerenard=place elif a=="chien": #placechien:int placechien=place elif a=="cheval": #placecheval : int placecheval=place if not p=="violoniste": return False #conditions spatiales : 5,6,7 (n,p,a)=config[0] if n!="norvegien": #5 return False # Pour les 6, 7, 8, 10 et 11 on retient les parametres au moment du parcours des conditions non spatiales if placemedecin+1!=placerenard and placemedecin-1!=placerenard: #6 return False if placediplomate+1!=placecheval and placediplomate-1!=placecheval: #7 return False if placeislandais+1!=placeslovene and placeislandais-1!=placeslovene: #8 return False if placechien+1==placerenard or placechien-1==placerenard: #10 return False if placeislandais+1!=placemedecin and placeislandais-1!=placemedecin: #11 return False if placenorvegien+1!=placemedecin and placenorvegien-1!=placemedecin: #11bis return False ##Et si on est arrive jusque la... c'est que l'on a la bonne configuration ! return True ############################################################################# ############## QUESTION 5 ############################## def recherche(): """->list[maison] + str Retourne une configuration qui satisfait toutes les conditions, si elle existe, et un message d'erreur sinon. """ Lconfig=[] #n::list[str] for n in permutation(nati): #p:list[str] for p in permutation(prof): #a:list[str] for a in permutation(anim): #config=list[maison] config=[]#la liste resultat possible #i : int. i indique la maison que l'on considere for i in range(0,5): #les maisons vont de 0 à 4 config.append((n[i],p[i],a[i])) # on construit une configuration possible if verification(config): #on teste si toutes les conditions sont realisees return config return "Le problème est mal construit : il n'a pas de solution !" ############################################################################# ############## QUESTION 6 ############################## def solution(): """->str Retourne la nationalité du propriétaire du zèbre.""" #configuration : list[maison] configuration=recherche() for (n,p,a) in configuration: if a=="zebre": return n #################################### POUR LANCER L'EXECUTION ########### import time t0=time.clock() solution() print (time.clock() - t0, "seconds process time")