# =========================================================================================
# Problème de logique : qui a le zèbre ?
# Résolution du problème par force brute
# Version 2 : teste 200 millions de tableaux en 1 heure environ
# Pour cela on a préremplit 3 cases dans le tableau (1 case par ligne)
# nsi.gecif.net
# Janvier 2025
# =========================================================================================

"""
L'énoncé du problème est le suivant :

Cinq hommes de nationalités et de professions différentes habitent des maisons de couleurs différentes et situés côte
à côte dans le même alignement. Ils ont chacun un animal favori et une boisson préférée.

Les données du problème sont :

1 : l'anglais habite la maison rouge
2 : l'espagnol a un chien
3 : dans la maison verte on boit du café
4 : l'ukrainien boit du thé
5 :  la maison verte est immédiatement à droite de la maison blanche
6 : le sculpteur élève des escargots
7 : le diplomate habite la maison jaune
8 : dans la maison du milieu on boit du lait
9 : le norvégien habite la première maison à gauche
10: le médecin habite une maison voisine de celle où demeure le propriétaire du renard
11: la maison du diplomate est à côté de celle où il y a un cheval
12: le violoniste boit du jus d'orange
13: le japonais est acrobate
14: le norvégien habite à côté de la maison bleue

La problématique à résoudre est :

Qui boit de l'eau et qui possède le zèbre ?

"""

from itertools import *

# ##############################################################################################
#   Fonction solution()
# ##############################################################################################

def solution(tableau):
    # la fonction solution compare le tableau passé en paramètre à l'énnoncé du problème :
    # elle renvoie True si le tableau correspond en tout point à la problématique, False dans le cas contraire
    """
    En décortiquant l'énoncé on obtient 3 cases pleines définitivemant dans le tableau et 11 conditions simples :

        Les 3 certitures sont :
        9- le norvégien habite la première maison à gauche : maison 1 -> norvégien
        14- le norvégien habite à côté de la maison bleue : maison 2 -> bleue
        8- dans la maison du milieu on boit du lait : maison 3 -> lait

        Les 11 conditions à tester sont :
        1- l'anglais habite la maison rouge
        2- l'espagnol a un chien
        3- dans la maison verte on boit du café
        4- l'ukrainien boit du thé
        5- la maison verte est immédiatement à droite de la maison blanche
        6- le sculpteur élève des escargots
        7- le diplomate habite la maison jaune
        10- le médecin habite une maison voisine de celle où demeure le propriétaire du renard
        11- la maison du diplomate est à côté de celle où il y a un cheval
        12- le violoniste boit du jus d'orange
        13- le japonais est acrobate

    """
    # ###########################################################
    # 8 conditions avec une seule boucle (donc rapide à tester) :
    # ###########################################################

    # =========================================================================================
    # CONDITION 1 :
    # l'anglais habite la maison rouge
    for i in range(1,6):
        if  tableau[i]['nationalité']=='anglais' and tableau[i]['couleur']!='rouge':
            return False

    # =========================================================================================
    # CONDITION 2 :
    # l'espagnol a un chien
    for i in range(1,6):
        if  tableau[i]['nationalité']=='espagnol' and tableau[i]['animal']!='chien':
            return False

    # =========================================================================================
    # CONDITION 3 :
    # dans la maison verte on boit du café
    for i in range(1,6):
        if  tableau[i]['couleur']=='verte' and tableau[i]['boisson']!='café':
            return False

    # =========================================================================================
    # CONDITION 4 :
    # l'ukrainien boit du thé
    for i in range(1,6):
        if  tableau[i]['nationalité']=='ukrainien' and tableau[i]['boisson']!='thé':
            return False

    # =========================================================================================
    # CONDITION 6 :
    # le sculpteur élève des escargots
    for i in range(1,6):
        if  tableau[i]['profession']=='sculpteur' and tableau[i]['animal']!='escargots':
            return False

    # =========================================================================================
    # CONDITION 7 :
    # le diplomate habite la maison jaune
    for i in range(1,6):
        if  tableau[i]['profession']=='diplomate' and tableau[i]['couleur']!='jaune':
            return False

    # =========================================================================================
    # CONDITION 12 :
    # le violoniste boit du jus d'orange
    for i in range(1,6):
        if  tableau[i]['profession']=='violoniste' and tableau[i]['boisson']!='jus orange':
            return False

    # =========================================================================================
    # CONDITION 13 :
    # le japonais est acrobate
    for i in range(1,6):
        if  tableau[i]['nationalité']=='japonais' and tableau[i]['profession']!='acrobate':
            return False

    # ###########################################################
    # 3 conditions avec 2 boucles (donc plus lente à tester) :
    # ###########################################################

    # =========================================================================================
    # CONDITION 5 :
    # la maison verte est immédiatement à droite de la maison blanche
    # cherchons la position de la maison verte:
    for i in range(1,6):
        if  tableau[i]['couleur']=='verte':
            position_maisonverte=i
    # cherchons la positione de la maison blanche:
    for i in range(1,6):
        if  tableau[i]['couleur']=='blanche':
            position_maisonblanche=i
    if position_maisonverte-position_maisonblanche!=1 :
            return False

    # =========================================================================================
    # CONDITION 10 :
    # le médecin habite une maison voisine de celle où demeure le propriétaire du renard
    # cherchons la position de la maison du médecin :
    for i in range(1,6):
        if  tableau[i]['profession']=='médecin':
            position_medecin=i
    # cherchons la positione de la maison du renard :
    for i in range(1,6):
        if  tableau[i]['animal']=='renard':
            position_renard=i
    if abs(position_medecin-position_renard)!=1 :
            return False

    # =========================================================================================
    # CONDITION 11 :
    # la maison du diplomate est à côté de celle où il y a un cheval
    # cherchons la position de la maison du diplomate :
    for i in range(1,6):
        if  tableau[i]['profession']=='diplomate':
            position_diplomate=i
    # cherchons la positione de la maison du cheval :
    for i in range(1,6):
        if  tableau[i]['animal']=='cheval':
            position_cheval=i
    if abs(position_diplomate-position_cheval)!=1 :
            return False

    # On retourne True si on a "échapé" aux tests précédents, c'est-à-dire si les 11 conditions sont vérifiées :
    return True

# ##############################################################################################
#   Programme principal
# ##############################################################################################

# la structure de données utilisée ici est une liste de dictionnaires :
# - les 5 maisons sont dans une liste à 6 éléments dont seuls les éléments 1 à 5 sont utilisés
# - la liste permet d'avoir la notion d'ordre
# - la liste contient 5 dictionnaires dont les 5 clés sont nationalité, profession, couleur, animal et boisson

# on crée la liste contenant 5 dictionnaires vides pour l'instant :
# liste_maisons[0] n'est pas utilisé et vaut None
# maison 1 : liste_maisons[1] (maison de gauche)
# maison 2 : liste_maisons[2]
# maison 3 : liste_maisons[3]
# maison 4 : liste_maisons[4]
# maison 5 : liste_maisons[5] (maison de droite)

"""Les 3 certitures sont :
        - le norvégien habite la première maison à gauche : maison 1 -> norvégien
        - le norvégien habite à côté de la maison bleue : maison 2 -> bleue
        - dans la maison du milieu on boit du lait : maison 3 -> lait
    L'idée est alors de remplir directement ces 3 cases dans tous les tableaux qu'on teste

de 24883200000 tableaux différents on passe à 199065600 tableaux différents à tester (soit 125 fois moins)
"""

liste_maisons=[None,\
{'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\
{'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\
{'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\
{'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\
{'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None}]

# liste des 4 nationalités (en plus de 'norvégien') :
liste_nationalite=['anglais','espagnol','ukrainien','japonais']
# liste des 5 professions :
liste_profession=['violoniste','sculpteur','médecin','diplomate','acrobate']
# liste des 4 couleurs (en plus de 'bleue') :
liste_couleur=['rouge','blanche','jaune','verte']
# liste des 5 animaux :
liste_animal=['escargots','chien','cheval','renard','zèbre']
# liste des 4 boissons (en plus de 'lait') :
liste_boisson=['jus orange','thé','eau','café']

tous_les_cas_nationalite=tuple(permutations(liste_nationalite))
tous_les_cas_profession=tuple(permutations(liste_profession))
tous_les_cas_couleur=tuple(permutations(liste_couleur))
tous_les_cas_animal=tuple(permutations(liste_animal))
tous_les_cas_boisson=tuple(permutations(liste_boisson))

solutions_testees=0
solutions_trouvees=0
progression=1

# Si le programme doit remplir un tableau vide :
# 120**5 = 24883200000 = 24 883 200 000 = 24 milliards d'itérations soit 24 milliards de tableaux à tester : il faut 120 heures (5 jours)

# Si on donne comme ici 3 cases remplies dans le tableau (une case par ligne) :
# 24**3*120**2 = 199065600 = 199 millions d'itérations soit 199 millions de tableaux à tester : il faut 1 heure
# 24883200000/199065600 = 125 : on divisant le nombre de tableaux à tester par 125 on a diviser le temps d'exécution par 125

# Si on donne 5 cases remplies dans le tableau (une case par ligne) :
# 24**5 = 7962624 = 7 millions d'itérations soit 7 millions de tableaux à tester : il faut 3 minutes
# 24883200000/7962624 = 3125 : on divisant le nombre de tableaux à tester par 3125 on a diviser le temps d'exécution par 3125

for t_nationalite_4 in tous_les_cas_nationalite: # boucle 24 fois
    # on ajoute à la main la 5ème nationalité ('norvégien') dans la maison 1 :
    t_nationalite=('norvégien',)+t_nationalite_4
    for t_couleur_4 in tous_les_cas_couleur: # boucle 24 fois
        # on ajoute à la main la 5ème couleur ('bleue') dans la maison 2 :
        t_couleur=tuple((t_couleur_4[0],)+('bleue',)+t_couleur_4[1:])
        print("Progression : %d / 576" % progression)
        progression+=1
        for t_boisson_4 in tous_les_cas_boisson: # boucle 24 fois
            # on ajoute à la main la 5ème boisson ('lait') dans la maison 3 :
            t_boisson=t_boisson_4[:2]+('lait',)+t_boisson_4[2:]
            for t_profession in tous_les_cas_profession: # boucle 120 fois
                for t_animal in tous_les_cas_animal: # boucle 120 fois
                    for i in range(1,5+1):
                        liste_maisons[i]['nationalité']=t_nationalite[i-1]
                        liste_maisons[i]['profession']=t_profession[i-1]
                        liste_maisons[i]['couleur']=t_couleur[i-1]
                        liste_maisons[i]['animal']=t_animal[i-1]
                        liste_maisons[i]['boisson']=t_boisson[i-1]

                    # on teste cette solution :
                    if solution(liste_maisons):
                        solutions_trouvees=solutions_trouvees+1
                        print('Solution n°%d trouvée :' % solutions_trouvees)
                        # affiche les solutions trouvées par le programme :
                        print(liste_maisons)

                    # on compte le nombre de solution testées :
                    solutions_testees=solutions_testees+1

print('\nLe programme a testé par force brute %d solutions différentes et en a trouvé %d correctes.' % (solutions_testees,solutions_trouvees))

# Le programme a testé par force brute 199065600 solutions différentes et en a trouvé 1 correctes.

# Le programme teste 24**3*120**2=199065600 solutions différentes (199 millions)

"""
Voici la solution attendue du problème (solution donnée par Prolog) :
maison(jaune,norvegien,renard,eau,diplomate)
maison(bleue,ukrainien,cheval,the,medecin)
maison(rouge,anglais,escargots,lait,sculpteur)
maison(blanche,espagnol,chien,jus,violoniste)
maison(verte,japonais,zebre,cafe,acrobate)

Et voici la solution unique trouvée par ce programme Python (en 30 minutes environ) :

Progression : 301 / 576
Solution n°1 trouvée :
[None,
{'couleur': 'jaune', 'nationalité': 'norvégien', 'boisson': 'eau', 'profession': 'diplomate', 'animal': 'renard'},
{'couleur': 'bleue', 'nationalité': 'ukrainien', 'boisson': 'thé', 'profession': 'médecin', 'animal': 'cheval'},
{'couleur': 'rouge', 'nationalité': 'anglais', 'boisson': 'lait', 'profession': 'sculpteur', 'animal': 'escargots'},
{'couleur': 'blanche', 'nationalité': 'espagnol', 'boisson': 'jus orange', 'profession': 'violoniste', 'animal': 'chien'},
{'couleur': 'verte', 'nationalité': 'japonais', 'boisson': 'café', 'profession': 'acrobate', 'animal': 'zèbre'}]
Progression : 302 / 576

Il faut environ 1 heure pour faire les 576 tests
"""